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

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

Идея метода

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

$x=\varphi (x)$,

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

$\varphi (x)=x-{\lambda }(x)f(x)\!,$

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

Описание

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

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

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

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

$\displaystyle y=f(x_{i})+{\frac {1}{{\lambda }_{0}}}(x-x_{i}).$

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

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

$\displaystyle f(x_{i})+{\dfrac {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={\dfrac {1}{{\lambda }_{0}}}$ того же знака, что производная $f'(x_{0})$. (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция $f(x)$ или возрастает; во-вторых, что прямые, проводимые при разных $x_{i}$, имеют один и тот же угловой коэффициент $k$ и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью $OX$.

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

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

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

$\displaystyle \vert {\varphi }'(x)\vert =\vert 1-{\lambda }_{0}f'(x)\vert \leqslant {\gamma }<1.$

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

$\displaystyle -{\gamma }+1\leqslant {\lambda }_{0}f'(x)\leqslant {\gamma }+1,$

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

$\displaystyle {\lambda }_{0}f'(x)>0,$

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

$\displaystyle \vert k\vert ={\dfrac {1}{\vert {\lambda }_{0}\vert }}>{\dfrac {M_{1}}{2}},$

где $M_{1}=\max \limits _{x}\vert f'(x)\vert$. Таким образом, угловой коэффициент $k$ не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка $x_{1}$ может выскочить из рассматриваемой окрестности корня $x^{*}$, и сходимости к корню может не быть.

См. также

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