Метод Ньютона для корней

Как с помощью касательных молниеносно находить корни уравнений.

Метод Ньютона ищет корень уравнения $f(x)=0$ итерациями: $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$.

Большинство уравнений нельзя решить «в лоб» формулой. Как найти корень $x^2=2$ или $\cos x = x$? Здесь блистает метод Ньютона — элегантный численный приём, использующий производную. Он невероятно быстр: число верных знаков примерно удваивается на каждом шаге.

Идея: скользим по касательной

Возьмём начальное приближение $x_n$. Проведём касательную к графику в этой точке и посмотрим, где она пересекает горизонтальную ось — это и будет следующее, лучшее приближение $x_{n+1}$. Касательная — линейное приближение функции, а линейное уравнение решается мгновенно. Геометрия даёт формулу:

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

Мы делим значение функции на её наклон и вычитаем — словно «скатываемся» по касательной к оси. Повторяем, пока приближение не стабилизируется.

Симуляция сходимости

Найдём $\sqrt{2}$ как корень уравнения $f(x)=x^2-2=0$. Здесь $f'(x)=2x$. Стартуем с $x_0=2$ и смотрим, как стремительно приближение сходится.

import math

def f(x): return x*x - 2
def df(x): return 2*x

x = 2.0
for step in range(1, 6):
    x = x - f(x) / df(x)
    err = abs(x - math.sqrt(2))
    print(f"шаг {step}: x={x:.12f}  ошибка={err:.2e}")

print("sqrt(2) =", math.sqrt(2))

Вывод:

шаг 1: x=1.500000000000  ошибка=8.58e-02
шаг 2: x=1.416666666667  ошибка=2.45e-03
шаг 3: x=1.414215686275  ошибка=2.12e-06
шаг 4: x=1.414213562375  ошибка=1.59e-12
шаг 5: x=1.414213562373  ошибка=0.00e+00
sqrt(2) = 1.4142135623730951

Посмотрите на ошибку: $0{,}08 \to 0{,}002 \to 0{,}000002 \to 10^{-12}$. Число верных знаков примерно удваивается на каждом шаге — это квадратичная сходимость. За пять итераций мы получили $\sqrt{2}$ с машинной точностью.

Как работает под капотом

Формула напрямую следует из уравнения касательной. Касательная в точке $x_n$: $y = f(x_n) + f'(x_n)(x - x_n)$. Приравниваем $y=0$ и решаем относительно $x$ — получаем именно $x_n - f(x_n)/f'(x_n)$. Поскольку касательная — отличное приближение вблизи точки, её корень оказывается гораздо ближе к настоящему, чем исходная точка. Повторяя, мы стремительно «зумируем» в корень.

Частые ошибки

Метод Ньютона мощный, но капризный. Первая опасность — производная близка к нулю: тогда мы делим на крошечное число, и шаг улетает в бесконечность. Вторая — плохое начальное приближение: метод может разойтись или зациклиться между двумя точками. Третья — кратные корни замедляют сходимость с квадратичной до линейной. Поэтому на практике добавляют защиту: ограничение числа шагов и проверку, что значение функции убывает.

Итог

• Метод Ньютона: $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$.
• Геометрически — скольжение по касательной к оси.
• Сходимость квадратичная: число верных знаков удваивается.
• Опасности: $f'\approx 0$, плохой старт, кратные корни.