Постановка задачи: на интервале \([a, b]\) задана функция \(f(x)\), удовлетворяющая некоторым условиям. Известно, что на этом интервале только один корень. Требуется его найти.
Просто будем перебирать значения переменной \(x\) с некоторым шагом (в данном случае шаг равен \(0{,}1\)). Запоминаем такое значение переменной \(x\), при котором значение \(y\) минимально (по модулю).
Найдём значение \(f(x)\) в середине интервала. Далее нужно определить, в какой половине находится корень — в левой или правой. Воспользуемся простым трюком: умножим \(f(a)\) на \(f(x)\). Если результат умножения отрицательный, то эти значения имеют разный знак.
Положительное × положительное = положительное.
Положительное × отрицательное = отрицательное.
Отрицательное × положительное = отрицательное.
Отрицательное × отрицательное = положительное.
А значит, где-то между ними находится корень (график пересекает ось \(OX\)). Иначе корень находится в правой части интервала. Выбираем левую или правую половину интервала и проделываем всё то же самое для этого подынтервала. И так до тех пор, пока мы не найдём самое маленькое значение \(|y|\).
Этот метод повторяет метод дихотомии, но интервал делится не пополам, а на значение \(\Phi \approx 1{,}618\). Так достигается более высокая скорость сходимости метода.
Проведём хорду (отрезок) от точки (\(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)}$$
В отличие от других методов, здесь нет интервала, зато задаётся начальное приближение (в примере ниже это \(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})}}$$
Метод Ньютона очень быстро сходится, но не лишён недостатков: если неверно задать начальное приближение, он может и не сойтись.
Интересный факт. Метод Ньютона использовался в необычном методе быстрого вычисления обратного корня с волшебной константой 0x5F3759DF. Метод не использует вычисление квадратного корня и операцию деления и сочетает магию чисел с плавающей запятой для поиска первого приближения и первую итерацию метода Ньютона.