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

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

Идея метода

Идея метода простой итерации состоит в том, чтобы уравнение [math]\displaystyle{ f(x)=0 }[/math] привести к эквивалентному уравнению

[math]\displaystyle{ x=\varphi(x) }[/math],

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

[math]\displaystyle{ \varphi(x)=x-{\lambda}(x)f(x)\!, }[/math]

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

Описание

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

[math]\displaystyle{ \displaystyle x_{i+1}=x_i-{\lambda}_0f(x_i)\!, }[/math]

и на каждой итерации нужно один раз вычислить значение функции [math]\displaystyle{ f(x) }[/math].

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

[math]\displaystyle{ \displaystyle y=f(x_i)+\frac{1}{{\lambda}_0}(x-x_i). }[/math]

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

Найдём точку пересечения этой прямой с осью [math]\displaystyle{ OX }[/math] из уравнения

[math]\displaystyle{ \displaystyle f(x_i)+\dfrac{1}{{\lambda}_0}(x-x_i)=0, }[/math]

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

На чертеже справа изображены итерации при [math]\displaystyle{ f'(x)\gt 0 }[/math] в случае [math]\displaystyle{ k=\dfrac{1}{{\lambda}_0}\lt f'(x_0) }[/math] и в случае [math]\displaystyle{ k=\dfrac{1}{{\lambda}_0}\gt f'(x_0) }[/math]. Мы видим, что в первом случае меняющаяся точка [math]\displaystyle{ x_i }[/math] уже на первом шаге «перепрыгивает» по другую сторону от корня [math]\displaystyle{ x^* }[/math], и итерации начинают приближаться к корню с другой стороны. Во втором случае последовательные точки [math]\displaystyle{ x_i }[/math] приближаются к корню, оставаясь всё время с одной стороны от него.

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

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

[math]\displaystyle{ \displaystyle \vert{\varphi}'(x)\vert=\vert 1-{\lambda}_0f'(x)\vert\leqslant {\gamma}\lt 1. }[/math]

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

[math]\displaystyle{ \displaystyle -{\gamma}+1\leqslant {\lambda}_0f'(x)\leqslant {\gamma}+1, }[/math]

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

[math]\displaystyle{ \displaystyle {\lambda}_0f'(x)\gt 0, }[/math]

так как [math]\displaystyle{ -{\gamma}+1\gt 0 }[/math] (тем самым проясняется смысл выбора знака числа [math]\displaystyle{ {\lambda}_0 }[/math]), а во-вторых, когда [math]\displaystyle{ {\lambda}_0f'(x)\lt 2 }[/math] при всех [math]\displaystyle{ x }[/math] на всём рассматриваемом отрезке, окружающем корень. Это второе неравенство заведомо выполнено, если

[math]\displaystyle{ \displaystyle \vert k\vert=\dfrac{1}{\vert{\lambda}_0\vert}\gt \dfrac{M_1}{2}, }[/math]

где [math]\displaystyle{ M_1=\max\limits_{x}\vert f'(x)\vert }[/math]. Таким образом, угловой коэффициент [math]\displaystyle{ k }[/math] не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка [math]\displaystyle{ x_1 }[/math] может выскочить из рассматриваемой окрестности корня [math]\displaystyle{ x^* }[/math], и сходимости к корню может не быть.

См. также

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