Нули функции

Численные методы

Постановка задачи: на интервале [a, b] задана функция f(x), удовлетворяющая некоторым условиям. Известно, что на этом интервале только один корень. Требуется его найти.

Метод грубой силы (перебора)

Просто будем перебирать значения переменной x с некоторым шагом (в данном случае шаг равен 0,1). Запоминаем такое значение переменной x, при котором значение y минимально (по модулю).

Шаг → Перезапуск

function bruteForce(f(x), a, b, step = 0.2)
{
xMin = a;
yMinAbs = abs(f(a));
for (x = a + step; x < b; x += step)
{
y = abs(f(x));
if (y < yMinAbs)
{
xMin = x;
yMinAbs = y;
}
}
return minX;
}

Метод дихотомии (деления пополам)

Найдём значение f(x) в середине интервала. Далее нужно определить, в какой половине находится корень — в левой или правой. Воспользуемся простым трюком: умножим f(a) на f(x). Если результат умножения отрицательный, то эти значения имеют разный знак.

Положительное × положительное = положительное.

Положительное × отрицательное = отрицательное.

Отрицательное × положительное = отрицательное.

Отрицательное × отрицательное = положительное.

А значит, где-то между ними находится корень (график пересекает ось OX). Иначе корень находится в правой части интервала. Выбираем левую или правую половину интервала и проделываем всё то же самое для этого подынтервала. И так до тех пор, пока мы не найдём самое маленькое значение y (по модулю).

Шаг → Перезапуск

function dichotomy(f(x), a, b, epsilon = 0.1)
{
x = 0;
y = 0;
do
{
x = a + (b - a) / 2;
y = f(x);
if (f(a) * y < 0)
{
b = x;
}
else
{
a = x;
}
} while (abs(y) > epsilon);
return x;
}

Метод золотого сечения

Этот метод повторяет метод дихотомии, но интервал делится не пополам, а на значение Φ ≈ 1,618. Так достигается более высокая скорость сходимости метода.

Шаг → Перезапуск

function goldenSection(f(x), a, b, epsilon = 0.1)
{
x = 0;
y = 0;
do
{
x = a + (b - a) / 1.618;
y = f(x);
if (f(a) * y < 0)
{
b = x;
}
else
{
a = x;
}
} while (abs(y) > epsilon);
return x;
}

Метод хорд

Проведём хорду (отрезок) от точки (a; f(a)) к точке (b; f(b)). Найдём абсцисса точки пересечения хорды с осью OX. Как и в двух предыдущих методах, выберем левый либо правый подынтервал. И точно так же будем продолжать, пока не найдём минимальное y(x) (по модулю).

Покажем, как вычисляется абсцисса точки пересечения хорды с осью OX. Составим уравнение прямой по двум точкам: (a, f(a)) и (b, f(b)). Ордината точки пересечения равна 0.

Шаг → Перезапуск

function chords(f(x), a, b, epsilon = 0.1)
{
x = 0;
y = 0;
do
{
x = -(f(a) * (b - a)) / (f(b) - f(a)) + a;
y = f(x);
if (f(a) * y < 0)
{
b = x;
}
else
{
a = x;
}
} while (abs(y) > epsilon);
return x;
}

Метод Ньютона (касательных)

В отличие от других методов, здесь нет интервала, зато задаётся начальное приближение (в примере ниже это x = 3). Также нужно вычислять производную функции. Проведём касательную к графику функции в этой точке и найдём точку пересечения касательной с осью OX. Это новое приближение. Продолжаем так же до тех пор, пока не найдём минимальное y(x) (по модулю).

Покажем, как вычисляется абсцисса точки пересечения касательной с осью OX. Составим уравнение прямой по двум точкам: (x1, y1) и (x2, y2). Ордината точки пересечения равна 0. Выразим x и сделаем простую замену.

Шаг → Перезапуск

function newton(f(x), f'(x), x, epsilon = 0.1)
{
do
{
x -= f(x) / f'(x);
} while (abs(f(x)) > epsilon);
return x;
}

Метод Ньютона очень быстро сходится, но не лишён недостатков: если неверно задать начальное приближение, он может и не сойтись.

Интересный факт. Метод Ньютона использовался в необычном методе быстрого вычисления обратного корня с волшебной константой 0x5F3759DF. Метод не использует вычисление квадратного корня и операцию деления и сочетает магию чисел с плавающей запятой для поиска первого приближения и первую итерацию метода Ньютона.

18 марта 2018 · нули функций · программирование · численные методы