Русская Википедия:Метод простой итерации
Метод простой итерации — один из простейших численных методов решения уравнений. Метод основан на принципе сжимающего отображения, который применительно к численным методам в общем виде также может называться методом простой итерации или методом последовательных приближений[1]. В частности, для систем линейных алгебраических уравнений существует аналогичный метод итерации.
Идея метода
Идея метода простой итерации состоит в том, чтобы уравнение <math> f(x)=0</math> привести к эквивалентному уравнению
- <math>x=\varphi(x)</math>,
так, чтобы отображение <math>\varphi(x)</math> было сжимающим. Если это удаётся, то последовательность итераций <math>x_{i+1}=\varphi(x_i)</math> сходится. Такое преобразование можно делать разными способами. В частности, сохраняет корни уравнение вида
- <math>\varphi(x)=x-{\lambda}(x)f(x)\!,</math>
если <math>{\lambda}(x) \neq 0</math> на исследуемом отрезке. Оптимальным выбором является <math>\lambda(x) = \frac{1}{f'(x)}</math>, что приводит к методу Ньютона, который является быстрым, но требует вычисления производной. Если в качестве <math>\lambda(x)</math> выбрать константу того же знака, что и производная в окрестности корня, то мы получаем простейший метод итерации.
Описание
В качестве функции <math> {\lambda}(x)</math> берут некоторую постоянную <math> {\lambda}_0</math>, знак которой совпадает со знаком производной <math> f'(x)</math> в некоторой окрестности корня (и, в частности, на отрезке, соединяющем <math> x_0</math> и <math> x^*</math>). Постоянная <math> {\lambda}_0</math> обычно не зависит и от номера шага. Иногда берут <math> {\lambda}_0=\frac{1}{f'(x_0)}</math> и называют этот метод методом одной касательной. Формула итераций оказывается предельно простой:
- <math>\displaystyle x_{i+1}=x_i-{\lambda}_0f(x_i)\!,</math>
и на каждой итерации нужно один раз вычислить значение функции <math> f(x)</math>.
Эта формула, а также требование совпадения знаков <math> f'</math> и <math> {\lambda}_0</math> легко выводятся из геометрических соображений. Рассмотрим прямую, проходящую через точку <math> (x_i;f(x_i))</math> на графике <math> y=f(x)</math> с угловым коэффициентом <math>\tan\nolimits\alpha=\frac{1}\lambda_0</math>. Тогда уравнением этой прямой будет
- <math>\displaystyle y=f(x_i)+\frac{1}{{\lambda}_0}(x-x_i).</math>
Найдём точку пересечения этой прямой с осью <math> OX</math> из уравнения
- <math>\displaystyle f(x_i)+\dfrac{1}{{\lambda}_0}(x-x_i)=0,</math>
откуда <math> x=x_i-{\lambda}_0f(x_i)=x_{i+1}</math>. Следовательно, эта прямая пересекает ось <math> OX</math> как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки <math> x_0</math>, через соответствующие точки графика <math> y=f(x)</math> проводятся прямые с угловым коэффициентом <math> k=\dfrac{1}{{\lambda}_0}</math> того же знака, что производная <math> f'(x_0)</math>. (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция <math> f(x)</math> или возрастает; во-вторых, что прямые, проводимые при разных <math> x_i</math>, имеют один и тот же угловой коэффициент <math> k</math> и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью <math> OX</math>.
На чертеже справа изображены итерации при <math> f'(x)>0</math> в случае <math> k=\dfrac{1}{{\lambda}_0}<f'(x_0)</math> и в случае <math> k=\dfrac{1}{{\lambda}_0}>f'(x_0)</math>. Мы видим, что в первом случае меняющаяся точка <math> x_i</math> уже на первом шаге «перепрыгивает» по другую сторону от корня <math> x^*</math>, и итерации начинают приближаться к корню с другой стороны. Во втором случае последовательные точки <math> x_i</math> приближаются к корню, оставаясь всё время с одной стороны от него.
Условие сходимости
Достаточное условие сходимости таково:
- <math>\displaystyle \vert{\varphi}'(x)\vert=\vert 1-{\lambda}_0f'(x)\vert\leqslant {\gamma}<1.</math>
Это неравенство может быть переписано в виде
- <math>\displaystyle -{\gamma}+1\leqslant {\lambda}_0f'(x)\leqslant {\gamma}+1,</math>
откуда получаем, что сходимость гарантируется, когда, во-первых,
- <math>\displaystyle {\lambda}_0f'(x)>0,</math>
так как <math> -{\gamma}+1>0</math> (тем самым проясняется смысл выбора знака числа <math> {\lambda}_0</math>), а во-вторых, когда <math> {\lambda}_0f'(x)<2</math> при всех <math> x</math> на всём рассматриваемом отрезке, окружающем корень. Это второе неравенство заведомо выполнено, если
- <math>\displaystyle \vert k\vert=\dfrac{1}{\vert{\lambda}_0\vert}>\dfrac{M_1}{2},</math>
где <math> M_1=\max\limits_{x}\vert f'(x)\vert</math>. Таким образом, угловой коэффициент <math> k</math> не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка <math> x_1</math> может выскочить из рассматриваемой окрестности корня <math> x^*</math>, и сходимости к корню может не быть.
Примечания
См. также
- Метод Ньютона (метод касательных)
- Метод Мюллера
- Обратная параболическая интерполяция
- Метод хорд
