Метод простой итерации

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

Идея метода

Идея метода простой итерации состоит в том, чтобы уравнение $f(x)=0$ привести к эквивалентному уравнению

$x=\phi (x)$,

так, чтобы отображение $\phi (x)$ было сжимающим. Если это удаётся, то последовательность итераций $x_{i+1}=\phi (x_i)$ сходится. Такое преобразование можно делать разными способами. В частности, сохраняет корни уравнение вида

$\phi (x)=x-\lambda (x)f(x),$

если $\lambda (x)\ne 0$ на исследуемом отрезке. Оптимальным выбором является $\lambda (x)=\frac{1}{f^{\prime }(x)}$, что приводит к методу Ньютона, который является быстрым, но требует вычисления производной. Если в качестве $\lambda (x)$ выбрать константу того же знака, что и производная в окрестности корня, то мы получаем простейший метод итерации.

Описание

В качестве функции $\lambda (x)$ берут некоторую постоянную ${\lambda }_0$, знак которой совпадает со знаком производной $f^{\prime }(x)$ в некоторой окрестности корня (и, в частности, на отрезке, соединяющем $x_0$ и $x^{*}$). Постоянная ${\lambda }_0$ обычно не зависит и от номера шага. Иногда берут ${\lambda }_0=\frac{1}{f^{\prime }(x_0)}$ и называют этот метод методом одной касательной. Формула итераций оказывается предельно простой:

$x_{i+1}=x_i-{\lambda }_{0}f(x_i),$

и на каждой итерации нужно один раз вычислить значение функции $f(x)$.

Эта формула, а также требование совпадения знаков $f^{\prime }$ и ${\lambda }_0$ легко выводятся из геометрических соображений. Рассмотрим прямую, проходящую через точку $(x_i;f(x_i))$ на графике $y=f(x)$ с угловым коэффициентом $\tan \mathrm{\backslash nolimits}\alpha ={\frac{1}{\lambda }}_0$. Тогда уравнением этой прямой будет

$y=f(x_i)+\frac{1}{{\lambda }_0}(x-x_i).$

Файл:Xy.png

Иллюстрация последовательных приближений метода простой итерации.

Найдём точку пересечения этой прямой с осью $OX$ из уравнения

$f(x_i)+\frac{1}{{\lambda }_0}(x-x_i)=0,$

откуда $x=x_i-{\lambda }_{0}f(x_i)=x_{i+1}$. Следовательно, эта прямая пересекает ось $OX$ как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки $x_0$, через соответствующие точки графика $y=f(x)$ проводятся прямые с угловым коэффициентом $k=\frac{1}{{\lambda }_0}$ того же знака, что производная $f^{\prime }(x_0)$. (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция $f(x)$ или возрастает; во-вторых, что прямые, проводимые при разных $x_i$, имеют один и тот же угловой коэффициент $k$ и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью $OX$.

На чертеже справа изображены итерации при $f^{\prime }(x)>0$ в случае $k=\frac{1}{{\lambda }_0}<f^{\prime }(x_0)$ и в случае $k=\frac{1}{{\lambda }_0}>f^{\prime }(x_0)$. Мы видим, что в первом случае меняющаяся точка $x_i$ уже на первом шаге «перепрыгивает» по другую сторону от корня $x^{*}$, и итерации начинают приближаться к корню с другой стороны. Во втором случае последовательные точки $x_i$ приближаются к корню, оставаясь всё время с одной стороны от него.

Условие сходимости

Достаточное условие сходимости таково:

$|{\phi }^{\prime }(x)|=|1-{\lambda }_0{f}^{\prime }(x)|⩽\gamma <1.$

Это неравенство может быть переписано в виде

$-\gamma +1⩽{\lambda }_0{f}^{\prime }(x)⩽\gamma +1,$

откуда получаем, что сходимость гарантируется, когда, во-первых,

${\lambda }_0{f}^{\prime }(x)>0,$

так как $-\gamma +1>0$ (тем самым проясняется смысл выбора знака числа ${\lambda }_0$), а во-вторых, когда ${\lambda }_0{f}^{\prime }(x)<2$ при всех $x$ на всём рассматриваемом отрезке, окружающем корень. Это второе неравенство заведомо выполнено, если

$|k|=\frac{1}{|{\lambda }_0|}>\frac{M_1}{2},$

где $M_1=\max {\mathrm{\backslash limits}}_x|f^{\prime }(x)|$. Таким образом, угловой коэффициент $k$ не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка $x_1$ может выскочить из рассматриваемой окрестности корня $x^{*}$, и сходимости к корню может не быть.

См. также

• Метод Ньютона (метод касательных)
• Метод Мюллера
• Обратная параболическая интерполяция
• Метод хорд