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

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

Идея методаПравить

Идея метода простой итерации состоит в том, чтобы уравнение   привести к эквивалентному уравнению

 ,

так, чтобы отображение   было сжимающим. Если это удаётся, то последовательность итераций   сходится. Такое преобразование можно делать разными способами. В частности, сохраняет корни уравнение вида

 

если   на исследуемом отрезке. Оптимальным выбором является  , что приводит к методу Ньютона, который является быстрым, но требует вычисления производной. Если в качестве   выбрать константу того же знака, что и производная в окрестности корня, то мы получаем простейший метод итерации.

ОписаниеПравить

В качестве функции   берут некоторую постоянную  , знак которой совпадает со знаком производной   в некоторой окрестности корня (и, в частности, на отрезке, соединяющем   и  ). Постоянная   обычно не зависит и от номера шага. Иногда берут   и называют этот метод методом одной касательной. Формула итераций оказывается предельно простой:

 

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

Эта формула, а также требование совпадения знаков   и   легко выводятся из геометрических соображений. Рассмотрим прямую, проходящую через точку   на графике   с угловым коэффициентом  . Тогда уравнением этой прямой будет

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

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

 

откуда  . Следовательно, эта прямая пересекает ось   как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки  , через соответствующие точки графика   проводятся прямые с угловым коэффициентом   того же знака, что производная  . (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция   или возрастает; во-вторых, что прямые, проводимые при разных  , имеют один и тот же угловой коэффициент   и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью  .

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

Условие сходимостиПравить

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

 

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

 

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

 

так как   (тем самым проясняется смысл выбора знака числа  ), а во-вторых, когда   при всех   на всём рассматриваемом отрезке, окружающем корень. Это второе неравенство заведомо выполнено, если

 

где  . Таким образом, угловой коэффициент   не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка   может выскочить из рассматриваемой окрестности корня  , и сходимости к корню может не быть.

ПримечанияПравить

См. такжеПравить