Нули функции. Численные методы

Нули функции

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

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

Зарегистрируйтесь и войдите, чтобы оставлять комментарии и голосовать.

Также может быть интересным

Светлая тема / тёмная тема