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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Идея метода[править | править код]

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

,

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

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

Описание[править | править код]

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

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

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

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

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

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

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

Условие сходимости[править | править код]

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

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

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

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

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

Примечания[править | править код]

  1. Математический энциклопедический словарь. — М.: «Сов. энциклопедия », 1988. — С. 847.

См. также[править | править код]