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

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

Идея метода

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

${\displaystyle x=\varphi (x)}$,

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

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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

См. также

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

Эта страница в последний раз была отредактирована 24 марта 2021 в 12:02.