Численное решение нелинейных уравнений: бисекция и метод Ньютона

Уравнение $x=\cos x$ выглядит безобидно. Попробуйте его решить — и упрётесь: формулы нет ни у Кардано, ни у кого-либо ещё. При этом инженеру нужен ответ, и не в общем виде, а числом с пятью знаками. Здесь начинается численный анализ: вместо формулы — алгоритм, который за несколько шагов сам приближается к корню. Разберём два главных: медленный, но непотопляемый метод бисекции — он же метод половинного деления — и стремительный метод Ньютона. Как устроены обе быстрые машины, чтобы верные знаки удваивались за шаг: метод касательных Ньютона и метод секущих — коротко в словаре.

Этап локализации: где живёт корень#

Задача ставится так: найти корень уравнения $f(x)=0$ с точностью $\epsilon$. Прежде чем запускать любой метод, корень локализуют — отрезают отрезок, внутри которого он сидит. Опора — теорема Больцано–Коши: если функция $f$ непрерывна на $[a,b]$ и на концах принимает значения разных знаков, $f(a)\cdot f(b)<0$, то внутри отрезка есть хотя бы один корень.

1. 1
   Переписываем в стандартной форме: $f(x)=\cos x-x=0$
2. 2
   Таблица значений: $f(0)=1>0$, $f(1)=-0.46<0$ — знаки разные
3. 3
   $f$ непрерывна всюду, значит, корень лежит на $[0;1]$
4. 4
   Эскиз показывает: $\cos x$ убывает от 1 до 0.54, прямая $y=x$ растёт — пересечение одно. Отрезок чист

Кратные корни — отдельная ловушка: у $f(x)=(x-2{)}^2$ корень двойной, знак функции не меняется, и условие $f(a)\cdot f(b)<0$ не сработает. Бисекция и секущие к такому корню пробираются плохо, Ньютону помогает лишь удачный старт. Проверяйте график до запуска алгоритма.

Метод бисекции: один бит за итерацию#

Идея до комичного проста: корень сидит в $[a,b]$, значит, делим отрезок пополам и оставляем ту половину, где знаки на концах разные. Повторяем. Каждая итерация режет неопределённость вдвое — длина отрезка после $n$ шагов равна $\frac{b-a}{2^n}$.

1. Вычисляем середину $c=\frac{a+b}{2}$ и значение $f(c)$
2. Если $f(a)\cdot f(c)<0$ — корень в левой половине, кладём $b=c$; иначе $a=c$
3. Повторяем, пока длина отрезка не станет меньше $\epsilon$; ответ — любой конец или середина последнего отрезка

Прогоним на том же $f(x)=x^2-2$ на $[1;2]$ — ищем $\sqrt{2}\approx 1.4142136$:

Для $[1;2]$ и $\epsilon =10^{-6}$: ${\log }_{2}10^6\approx 19.9$, значит, 20 итераций. Для $\epsilon =10^{-12}$ — сорок. Говорят, что бисекция добывает один бит за итерацию: каждая итерация добавляет к точности ровно один двоичный разряд. Никакая сложность функции $f$ на это число не влияет — только длина отрезка.

У бисекции есть потолок, о котором редко говорят: точность самой функции. Если $f(x)$ вычисляется с ошибкой $delt{a}_f$ (а в double это неизбежно), то вблизи корня знак $f$ уже не отличить, и деление пополам слепнет. Глубже уровня $delt{a}_f/|f^{\prime }(r)|$ опуститься нельзя — что бы ни обещала формула log_2rac{b-a}{arepsilon}. Та же граница стоит перед любым методом: счётная точность функции — фундамент всего здания, и утопить в ней корень проще, чем кажется.

Метод Ньютона: касательная как ускоритель#

Ньютон работает иначе. Стоя в точке $x_n$, проведём касательную к графику $f$ и посмотрим, где она пересекает ось $x$. Эта точка пересечения — следующее приближение $x_{n+1}$. Уравнение касательной в точке $x_n$: $y=f(x_n)+f^{\prime }(x_n)(x-x_n)$; приравняв нулю, получаем формулу метода:

Считаем честно для $x^2-2$ со стартом $x_0=1.5$: ошибка старта $8.6\cdot 10^{-2}$. Дальше ошибка падает так, как не падает ни у одной бисекции:

Это и есть квадратичная сходимость: вблизи корня $|x_{n+1}-r|\approx C|x_n-r{|}^2$. Ошибка в тысячную даёт ошибку в миллионную, затем — сразу на уровне $10^{-12}$. Отсюда практическое правило: методу Ньютона хватает 4–6 итераций, чтобы выжать всё, что умеет хранить double. Но плата за скорость — требования: производная должна существовать и не обращаться в ноль рядом с корнем, а стартовая точка обязана быть достаточно близкой к нему.

Ловушки Ньютона: нулевая производная, зацикливание, побег#

Скорость Ньютона оплачивается хрупкостью. Первая ловушка — нулевая производная: если $f^{\prime }(x_n)=0$, касательная горизонтальна, ось не пересекает, формула делит на ноль. Даже близкая к нулю производная швыряет следующую точку далеко: знаменатель мал — дробь огромна.

Отдельная история — кратные корни. У $f(x)=(x-1{)}^2$ корень двойной: касательная у корня горизонтальна почти так же, как у параболы в вершине, и квадратичная сходимость вырождается в линейную — ошибки делятся лишь вдвое за шаг. Лечение известно: если кратность $m$ известна, работает модификация x_{n+1} = x_n - m,rac{f(x_n)}{f'(x_n)}. Для $m=2$ она возвращает методу квадратичный темп. Не знаете кратность — смотрите на медленную сходимость как на симптом.

Вторая ловушка — зацикливание. Возьмите $f(x)=x^3-2x+2$ и старт $x_0=0$: $f(0)=2$, $f^{\prime }(0)=-2$, значит, $x_1=0-\frac{2}{-2}=1$. А из $x_1=1$: $f(1)=1$, $f^{\prime }(1)=1$, и $x_2=0$. Итерации ходят по кругу ноль → один → ноль, ни на шаг не приближаясь к корню $-1.7693$. Третья ловушка — уход в бесконечность: стартовая точка на пологом участке кривой даёт почти горизонтальную касательную, и следующее приближение вылетает за пределы разрядной сетки. Классический пример — попытка найти корень $f(x)=\arctan x$ со стартом больше $\approx 1.39$: итерации убегают на $+\infty$.

Метод секущих: Ньютон без производной#

Производная не всегда доступна: $f$ может задаваться программой на тысячу строк. Секущие заменяют касательную хордой по двум последним точкам — производная аппроксимируется разностным отношением:

Прогон для $x^2-2$ со стартами $x_0=1$, $x_1=2$: $x_2=1.3333$, $x_3=1.4$, $x_4=1.414634$, $x_5=1.4142114$, $x_6=1.4142135621$, и на седьмой итерации — машинная точность. Ошибки $8.1\cdot 10^{-2}\to 1.4\cdot 10^{-2}\to 4.2\cdot 10^{-4}\to 2.1\cdot 10^{-6}\to 3.2\cdot 10^{-10}$ делятся примерно на золотое сечение в каждой степени: порядок сходимости метода секущих равен $\phi =\frac{1+\sqrt{5}}{2}\approx 1.618$. Это медленнее квадратуры Ньютона, но каждая итерация требует лишь одного нового вызова $f$ против двух у Ньютона (значение функции и производной).

Второй старт берут рядом с первым — разнесённые точки делают секущую грубой. И следите за знаменателем: если $f(x_n)=f(x_{n-1})$ (функция вышла на плато), метод взрывается делением на ноль. Хитрость бывалых: хранить не два, а три приближения — если знаменатель слишком мал, отбрасывается самая старая точка и итерация пересчитывается. Дешёвая страховка вместо лишней производной.

Сравнение методов и критерий останова#

Когда останавливаться? Наивный ответ «когда $|f(x_n)|$ мало» обманчив: если производная у корня мала, функция почти плоская, и $|f|=10^{-8}$ может соответствовать ошибке по $x$ в целый процент. Добросовестный критерий смотрит на сам аргумент: $|x_{n+1}-x_n|\le {\epsilon }_{abs}+{\epsilon }_{rel}|x_n|$, где ${\epsilon }_{rel}$ берут на пару порядков больше машинного эпсилон, например $10^{-12}$. Останов по разности соседних приближений — прямой мостик к теме источников погрешностей: относительная мера там объявлена главным арбитром, и здесь она работает так же. Тот же критерий останова обслуживает и метод простой итерации — каркас любых итерационных пересчётов.

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

План на практику: возьмите классику учебников $x^3-2x-5=0$, локализуйте корень между 2 и 3, прогоните бисекцию и Ньютон вручную по три итерации — и сверьте с $2.0945515$. Дальше по курсу те же идеи переходят на системы: численное решение ОДУ использует неявные схемы, где на каждом шаге решается нелинейное уравнение всё тем же Ньютоном. Определение производной, на котором держится вся механика метода, разобрано в уроке производная: определение и касательная, непрерывность, требуемая теоремой Больцано–Коши, — в материале про непрерывность и точки разрыва, а правила вычисления $f^{\prime }$ собраны в шпаргалке производных. Слово касательная из словаря пригодится при разговоре о геометрии метода.