Dyzzet|
C++ Data Science Алгоритмы Темы · Блог · YouTube
Нули функции
Численные методы

Постановка задачи: на интервале \([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 xMin;
}

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

Найдём значение \(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) / 2;
y = f(x);
if (f(a) * y < 0)
{
b = x;
}
else
{
a = x;
}
} while (abs(y) > epsilon);
return x;
}

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

Этот метод повторяет метод дихотомии, но интервал делится не пополам, а на значение \(\Phi \approx 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.

$$\frac{y - y_{1}}{y_{2} - y_{1}} = \frac{x - x_{1}}{x_{2} - x_{1}}$$

$$\frac{y - f(a)}{f(b) - f(a)} = \frac{x - a}{b - a}$$

$$\frac{0 - f(a)}{f(b) - f(a)} = \frac{x - a}{b - a}$$

$$x = a - \frac{f(a)(b-a)}{f(b)-f(a)}$$

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

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\). Составим уравнение прямой по двум точкам: (\(x_{1}\), \(y_{1}\)) и (\(x_{2}\), \(y_{2}\)). Ордината точки пересечения равна 0. Выразим \(x\) и сделаем простую замену.

$$\frac{y - y_{1}}{y_{2} - y_{1}} = \frac{x - x_{1}}{x_{2} - x_{1}}$$

$$x = x_{1} + \frac{(y - y_{1})(x_{2} - x_{1})}{y_{2} - y_{1}}$$

$$x = x_{1} + \frac{(0 - y_{1})(x_{2} - x_{1})}{y_{2} - y_{1}}$$

$$x = x_{1} - \frac{y_{1}\color{CornflowerBlue}{(x_{2} - x_{1})}}{\color{CornflowerBlue}{y_{2} - y_{1}}}$$

$$f'(x_{1}) = \lim \frac{\Delta y}{\Delta x} = \frac{\color{CornflowerBlue}{y_{2} - y_{1}}}{\color{CornflowerBlue}{x_{2} - x_{1}}}$$

$$x = x_{1} - \frac{f(x_{1})}{\color{CornflowerBlue}{f'(x_{1})}}$$

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

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
Зарегистрируйтесь и войдите, чтобы оставлять комментарии и голосовать.

Также может быть интересным
© MMXI—MMXXIII. RSS. Поддержать сайт
Светлая тема / тёмная тема