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

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

Идея метода

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

<math>x=\varphi(x)</math>,

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

<math>\displaystyle 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>, и сходимости к корню может не быть.

См. также

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

К:Википедия:Статьи без источников (тип: не указан)

Отрывок, характеризующий Метод простой итерации

Какой восторг разлился по перстам!
Пел он страстным голосом, блестя на испуганную и счастливую Наташу своими агатовыми, черными глазами.
– Прекрасно! отлично! – кричала Наташа. – Еще другой куплет, – говорила она, не замечая Николая.
«У них всё то же» – подумал Николай, заглядывая в гостиную, где он увидал Веру и мать с старушкой.
– А! вот и Николенька! – Наташа подбежала к нему.
– Папенька дома? – спросил он.
– Как я рада, что ты приехал! – не отвечая, сказала Наташа, – нам так весело. Василий Дмитрич остался для меня еще день, ты знаешь?
– Нет, еще не приезжал папа, – сказала Соня.
– Коко, ты приехал, поди ко мне, дружок! – сказал голос графини из гостиной. Николай подошел к матери, поцеловал ее руку и, молча подсев к ее столу, стал смотреть на ее руки, раскладывавшие карты. Из залы всё слышались смех и веселые голоса, уговаривавшие Наташу.
– Ну, хорошо, хорошо, – закричал Денисов, – теперь нечего отговариваться, за вами barcarolla, умоляю вас.
Графиня оглянулась на молчаливого сына.
– Что с тобой? – спросила мать у Николая.
– Ах, ничего, – сказал он, как будто ему уже надоел этот всё один и тот же вопрос.
– Папенька скоро приедет?
– Я думаю.
«У них всё то же. Они ничего не знают! Куда мне деваться?», подумал Николай и пошел опять в залу, где стояли клавикорды.
Соня сидела за клавикордами и играла прелюдию той баркароллы, которую особенно любил Денисов. Наташа собиралась петь. Денисов восторженными глазами смотрел на нее.
Николай стал ходить взад и вперед по комнате.
«И вот охота заставлять ее петь? – что она может петь? И ничего тут нет веселого», думал Николай.
Соня взяла первый аккорд прелюдии.
«Боже мой, я погибший, я бесчестный человек. Пулю в лоб, одно, что остается, а не петь, подумал он. Уйти? но куда же? всё равно, пускай поют!»
Николай мрачно, продолжая ходить по комнате, взглядывал на Денисова и девочек, избегая их взглядов.
«Николенька, что с вами?» – спросил взгляд Сони, устремленный на него. Она тотчас увидала, что что нибудь случилось с ним.
Николай отвернулся от нее. Наташа с своею чуткостью тоже мгновенно заметила состояние своего брата. Она заметила его, но ей самой так было весело в ту минуту, так далека она была от горя, грусти, упреков, что она (как это часто бывает с молодыми людьми) нарочно обманула себя. Нет, мне слишком весело теперь, чтобы портить свое веселье сочувствием чужому горю, почувствовала она, и сказала себе:
«Нет, я верно ошибаюсь, он должен быть весел так же, как и я». Ну, Соня, – сказала она и вышла на самую середину залы, где по ее мнению лучше всего был резонанс. Приподняв голову, опустив безжизненно повисшие руки, как это делают танцовщицы, Наташа, энергическим движением переступая с каблучка на цыпочку, прошлась по середине комнаты и остановилась.
«Вот она я!» как будто говорила она, отвечая на восторженный взгляд Денисова, следившего за ней.
«И чему она радуется! – подумал Николай, глядя на сестру. И как ей не скучно и не совестно!» Наташа взяла первую ноту, горло ее расширилось, грудь выпрямилась, глаза приняли серьезное выражение. Она не думала ни о ком, ни о чем в эту минуту, и из в улыбку сложенного рта полились звуки, те звуки, которые может производить в те же промежутки времени и в те же интервалы всякий, но которые тысячу раз оставляют вас холодным, в тысячу первый раз заставляют вас содрогаться и плакать.
Наташа в эту зиму в первый раз начала серьезно петь и в особенности оттого, что Денисов восторгался ее пением. Она пела теперь не по детски, уж не было в ее пеньи этой комической, ребяческой старательности, которая была в ней прежде; но она пела еще не хорошо, как говорили все знатоки судьи, которые ее слушали. «Не обработан, но прекрасный голос, надо обработать», говорили все. Но говорили это обыкновенно уже гораздо после того, как замолкал ее голос. В то же время, когда звучал этот необработанный голос с неправильными придыханиями и с усилиями переходов, даже знатоки судьи ничего не говорили, и только наслаждались этим необработанным голосом и только желали еще раз услыхать его. В голосе ее была та девственная нетронутость, то незнание своих сил и та необработанная еще бархатность, которые так соединялись с недостатками искусства пенья, что, казалось, нельзя было ничего изменить в этом голосе, не испортив его.
«Что ж это такое? – подумал Николай, услыхав ее голос и широко раскрывая глаза. – Что с ней сделалось? Как она поет нынче?» – подумал он. И вдруг весь мир для него сосредоточился в ожидании следующей ноты, следующей фразы, и всё в мире сделалось разделенным на три темпа: «Oh mio crudele affetto… [О моя жестокая любовь…] Раз, два, три… раз, два… три… раз… Oh mio crudele affetto… Раз, два, три… раз. Эх, жизнь наша дурацкая! – думал Николай. Всё это, и несчастье, и деньги, и Долохов, и злоба, и честь – всё это вздор… а вот оно настоящее… Hy, Наташа, ну, голубчик! ну матушка!… как она этот si возьмет? взяла! слава Богу!» – и он, сам не замечая того, что он поет, чтобы усилить этот si, взял втору в терцию высокой ноты. «Боже мой! как хорошо! Неужели это я взял? как счастливо!» подумал он.