Одномерные нелинейные уравнения

Рассмотрим задачу нахождения корня уравнения

\[f(x) = a\]

для более-менее произвольной функции \(f:\mathbb{R}\to\mathbb{R}\) (если функция определена не на всей числовой прямой, доопределим её чем угодно).

Бинарный поиск

Предположим, что на отрезке \(S=[L,R]\) функция \(f\) обладает свойством промежуточных значений: для любых \(x,y\in S\) и любого \(M\) между \(f(x)\) и \(f(y)\) существует точка \(m\), расположенная между \(x\) и \(y\), для которой \(f(m)=M\).

Тогда если \(f(L)\) и \(f(R)\) находятся по разные стороны от \(a\), можно организовать бинарный поиск: переходить от отрезка \([x,y]\) к отрезку \([(x+y)/2,y]\) или \([x,(x+y)/2]\) в зависимости от значения \(f((x+y)/2)\) так, чтобы \(a\) по-прежнему находилось между значениями функции на краях отрезка.

Бинарный поиск работает всегда, причём весьма стабильно: с каждым шагом абсолютная погрешность уменьшается в два раза (абсолютной погрешностью мы в данном случае называем длину отрезка, на котором мы можем гарантировать наличие корня).

Метод хорды (секущей)

Для функций, близких к линейно-неоднородным (линейно-неоднородные — функции вида \(f(x)=kx+b\)), есть существенно более быстрая разновидность бинарного поиска: идея в том, чтобы смотреть не на середину отрезка, а на пересечение «хорды», соединяющей крайние точки графика на текущем отрезке, с прямой, вертикальная координата которой равна \(a\).

Если мы сейчас находимся на отрезке \([x,y]\), то прямая, проходящая через точки \((x,f(x)))) и \((y,f(y))\) является графиком отображения

\[ t\mapsto \frac{t-y}{x-y} f(x) + \frac{t-x}{y-x} f(y) \]

Нетрудно решить уравнение

\[ \frac{t-y}{x-y} f(x) + \frac{t-x}{y-x} f(y) = a \]

Оно равносильно

\[ (t-y) f(x) - (t-x) f(y) = a(x-y) \]

Это, в свою очередь, равносильно

\[ t (f(x) - f(y)) = a(x-y) + y,f(x) - x,f(y) \]

То есть искомое значение новой «середины» отрезка равно

\[ t = \frac{x-y}{f(x)-f(y)} a + \frac{y,f(x) - x,f(y)}{f(x)-f(y)} \]

Отметим, что метод секущих способен проявлять очень плохую сходимость для функций с большим разбросом значений производной.

Метод Ньютона (касательной)

Одним из самых популярных методов решения уравнений является метод Ньютона. В отличие от вышеприведённых методов, он имеет дело не с последовательностью отрезков, а с последовательностью точек — приближений к искомому корню.

Описание

Каждая следующая точка получается как пересечение касательной, построенной к функции в текущей точке, и прямой с вертикальной координатой \(a\). Чтобы не усложнять анализ лишними выражениями, будем считать без ограничения общности \(a=0\) (то есть, формально говоря, будем вместо \(f\) рассматривать отображение \((x\mapsto f(x)-a)\)).

Производную далее будем обозначать буквой \(d\). Касательная, построенная к \(f\) в точке \(x\), является графиком отображения

\[ t \mapsto df(x)\cdot (t - x) + f(x) \]

Пересечение с нулевым значением получить нетрудно:

\[ t = x - \frac{f(x)}{df(x)} \]

Оценка

Оценим сходимость метода Ньютона. Нам понадобятся дополнительные предположения: пусть мы изначально находимся левее корня, при этом на промежутке от нас до корня функция убывает (то есть её первая производная отрицательна) и выпукла вниз (то есть её вторая производная неотрицательна).

Выпуклость обеспечивает нам то, что все последующие приближения будут левее корня. Абсолютной погрешностью теперь будем называть разность между корнем и таким приближением. Сам корень обозначим буквой \(r\), а \(n\)-е приближение к нему обозначим \(r_n\). Начинаем с \(r_0\) и действуем согласно соотношению

\[ r_{n+1} = r_n - \frac{f(r_n)}{df(r_n)} \]

Абсолютную погрешность \(n\)-го приближения обозначим \(a_n\). Нетрудно заметить (вычтя \(r\) из обеих частей соотношения), что

\[ a_{n+1} = a_n - \frac{f(r_n)}{|df(r_n)|} \]

Заметим теперь, что согласно теореме Лагранжа есть точка \(m_n\) на промежутке между \(r_n\) и \(r\), для которой

\[ f(r_n) = f(r_n) - f(r) = df(m_n)(r_n - r) = |df(m_n)| a_n \]

Отсюда получаем

\[ a_{n+1} = a_n \left( 1 - \frac{|df(m_n)|}{|df(r_n)|} \right) \]

или, что то же самое (поскольку обе производные отрицательны)

\[ a_{n+1} = a_n \left( 1 - \frac{df(m_n)}{df(r_n)} \right) \]

Линейная сходимость

Учитывая неравенства \(|df(r)|\leqslant |df(m_n)|\) и \(|df(r_0)|\geqslant |df(r_n)|\), делаем вывод, что

\[ a_{n+1} = a_n \left( 1 - \frac{|df(m_n)|}{|df(r_n)|} \right) \leqslant a_n \left( 1 - \frac{|df(r)|}{|df(r_0)|} \right) \]

Это означает, что \( a_{n} \leqslant \alpha^n a_{0} \) для некоторой положительной константы \(\alpha\lt1\).

Если ввести относительную погрешность \( \delta_n = a_n / a_0 \), то видно, что \( \delta_{n+1} \leqslant \alpha \delta_n \).

Такая сходимость называется линейной (термин выбран не слишком удачно, но что поделать…): верхняя оценка на относительную погрешность на каждом шаге меняется линейно (по сравнению с оценкой на предыдущем шаге).

В более приземлённых терминах: на каждом шаге количество известных нам цифр корня увеличивается на одну и ту же величину.

Квадратичная сходимость

Теперь докажем, что метод Ньютона сходится быстрее, чем линейно.

Ещё раз применим теорему Лагранжа, только на этот раз — для производной:

\[ df(m_n) = d^2f(s_n) (m_n - r_n) + df(r_n) \]

Отметим, что точка \(s_n\) находится между \(r_n\) и \(m_n\).

С учётом этого равенства соотношение для абсолютных погрешностей принимает вид

\[ a_{n+1} = a_n \left( 1 - \frac{df(m_n)}{df(r_n)} \right) = a_n \frac{|d^2f(s_n) (r_n-m_n)|}{|df(r_n)|} \]

Чтобы дать окончательную оценку погрешности, потребуем, чтобы вторая производная на интересующем нас отрезке не превосходила \(M\). Учитывая, что первая производная по абсолютной величине убывает, получаем оценку

\[ a_{n+1} \leqslant a_n^2 \frac{M}{|df(r)|} \]

Чтобы эта оценка стала понятнее, «обезразмерим» её, поделив на \(a_0\) и введя обозначение для «относительной» погрешности \(\delta_n = a_n/a_0\). Получим

\[ \delta_{n+1} \leqslant \delta_n^2 \frac{Ma_0}{|df(r)|} \]

Заметим, что если мы начали с такого момента, что

\[ \frac{Ma_0}{|df(r)|} \lt 1 \]

то \(\delta_{n+1} \lt \delta_{n}^2\). Это означает, грубо говоря, что с каждым следующим приближением количество известных нам цифр удваивается.

Также заметим, что если мы начали не с такого момента, то до такого момента рано или поздно дойдём: это сразу следует из доказанной выше линейной сходимости метода Ньютона.