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

Пусть задана нелинейная непрерывная функция действительного переменного f(x) на отрезке [a,b]?R. Требуется решить уравнение

f(x)=0 (1)

Метод простой итерации состоит в том, что уравнение (1) заменяем на основе равносильных преобразований уравнением вида

x=j(x) (2)

а затем строим последовательность приближений к корню уравнения x^*по правилу

(3)

Здесь k-номер итерации. Приближенное значение корня с нулевым индексом, т.е. называют начальным приближением. Это значение выбирается из каких-либо условий конкретной задачи или берется произвольно. Подставляем это значение в правую часть соотношения (3) и получаем , затем вычисленное таким образом каждое очередное приближение подставляем в правую часть и получаем

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

Корень уравнения (1) или (2) x=x* вычисляют приближенно с относительной погрешностью e?0 так, чтобы для всех k?k₀(e) стало верным неравенство

(4)

Число k₀(e) - это минимальное количество итераций, при котором выполняется условие сходимости. Последовательность будет сходящейся, если при неограниченном росте числа итераций существует ее предел и этим пределом является корень уравнения x*, т.е. если при k®? $ lim{x_k}=x*. Следовательно всегда можно прекратить процесс поиска корня методом простой итерации, если число итерации будет равно k₀(e).

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

(5)

где число М не зависит от номера итерации k, а 0<q<1, то говорят, что метод сходится линейно со скоростью геометрической прогрессии со знаменателем q.

Проблемы сходимости и единственности численного решения для метода простой итерации решаются и исследуются с помощью понятия о сжимающем отображении и теоремы о достаточном условии сходимости метода. Если x=x* является корнем функции f(x), то и итерируемая функция j(x) должна обладать следующим свойством x*=j(x*), а значение x* называется неподвижной точкой функции j(x).

Дадим геометрическую интерпретацию метода простой итерации. Будем предполагать, что функции j(x) и j?(x) являются непрерывными. На плоскости X0Y построим графики функции Y=x и Y=j(x). Каждый вещественный корень x* уравнения (2) является абсциссой точки пересечения кривойY=j(x) с прямой Y=x. Начиная с некоторой точки A₀(x₀, j(x₀)), строим ломаные линии A₀B₁A₁B₂A₂…(лестница), звенья которой попеременно параллельны оси 0X и оси 0Y, причем вершины A₀,A₁,A₂… лежат на кривой Y=j(x) . Общие абсциссы точек A₁ и B_1, A₂ и B₂ … представляют собой последовательные приближения корня x*, которые сходятся к нему монотонно и односторонне.

На рисунке представлен случай, когда 0<j?(x)<1, т.е. угол касательной к графику функцииY=j(x) меньше 45⁰, т.е.a< 45⁰. Функция Y=j(x) является возрастающей и вогнутой. Если -1<j?(x)<0, то ломаная A₀B₁A₁B₂A₂… будет иметь вид спирали. В этом случае сходимость является двусторонней, т.е. искомый корень всегда принадлежит отрезку . Функция Y=j(x) является убывающей и вогнутой.

Если |j?(x)|>1, т.е. угол наклона касательной к кривой j(x) превышает 45⁰, то в этом случае итерации сходиться не будут

Если же |j?(x)|<1 в некоторой окрестности корня, а вдали от него это неравенство не выполняется, то итерационный процесс будет сходящимся только в том случае, если начальное приближение выбрано достаточно близко к корню.

При произвольном выборе начального приближения сходимости может не быть.

Прежде, чем исследовать условия сходимости метода простой итерации, напомним понятие Липшиц-функции.

Говорят, что непрерывная на отрезке [a,b] функция f(x) удовлетворяет на этом отрезке условию Липшица, если существует такая константа q, что для любых двух значениях аргумента из этого отрезка имеет место неравенство

(6)

Величину q в этом случае называют постоянной Липшица.

Доказывается, что если функция f(x) на отрезке [a,b] имеет ограниченную производную, то она удовлетворяет условию Липшица с постоянной q=m,

Теорема о сходимости итерационной последовательности метода простой итерации имеет несколько эквивалентных формулировок. Одна из них такова.

Пусть функция j(x) из уравнения (2) на некотором отрезке где x*- корень этого уравнения, удовлетворяет условию Липшица с постоянной 0<q<1. Т.е. выполняется условие |j(x₁)-j(x₂)| ?q |x₁-x₂|. Тогда при любом выборе начального приближения из окрестности корня, т.е. существует бесконечная итерационная последовательность{x_k}, линейно сходящаяся к корню x*, который является единственным решением уравнения (2) на отрезке . Для погрешности будет справедлива оценка

k=0,1,2,… (7)

(Доказательство теоремы - см.Самарский ЧМ с.196)

Сформулированная теорема имеет простой смысл. Будем говорить, что функция j осуществляет отображение точки x на точку y=j(x). Тогда условие Липшица с постоянной q<1 означает, что отображение j является сжимающим: расстояние между точками больше, чем расстояние между их изображениями . Корень x* является неподвижной точкой отображения j, он преобразуется сам в себя x*=j(x*). Поэтому каждый шаг в итерационном процессе (3), сжимая расстояния, должен приближать члены последовательности к неподвижной точке x*.

Для практического применения теорема неудобна, поэтому обычно используют следствие из этой теоремы, которое звучит следующим образом. Если функция j(x) непрерывно дифференцируема на отрезке , то условие Липшица можно записать как

(8).

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

Число итераций, при котором выполняется условие сходимости (4) получаем из условия (7). На основании этих соотношений можно записать и .Минимальное число итераций, при котором выполняется условие сходимости равно

(9).

Здесь [а] означают ближайшее к а сверху целое число.

Рассмотрим пример

Решить уравнение с точностью e=0.01.

Отделим корни, найдем, что существует 3 корня на отрезках [-3;-2], [-1,0] и [0;1]. Будем последовательно искать приближение на каждом отрезке.

1. На отрезке [-3;-2] выполняется условие , следовательно, можем разделить обе части уравнения f(x)=0 на . Получаем

Преобразуем это уравнение , которое имеет вид x=j(x) (2).

Можем записать, что . Проверим условие сходимости должно выполняться неравенство на этом отрезке. Производная функции имеет вид . И ее максимальное значение на отрезке [-3;-2] : max =1/4, Следовательно . Для проверки условия сходимости можно построить график функции на отрезке [-3;-2]. Далее следует убедиться, что на указанном отрезке максимальные по модулю значения на графике не превышают 1.

В качестве первого приближения возьмем , тогда

2. Рассмотрим отрезок [-1;0] . На этом отрезке не выполняется условие , следовательно, мы не можем разделить обе части уравнения f(x)=0 на . Приведем уравнение к виду

, т.е. ,

и условие сходимости выполняется

В качестве начального приближения возьмем и начнем процесс итерирования для поиска приближения с заданной точностью.

3. На отрезке [0;1] поступаем аналогично предыдущему случаю, только возьмем функцию с положительным знаком. Имеем , для которой выполнение условия сходимости определим из графика

Возьмем начнем процесс итерирования для поиска приближения с заданной точностью.

Так как для реализации решения уравнения f(x)=0 (1) методом простых итераций необходимо преобразовать его к виду x=j(x) (2) и выбор функции j(x) имеет большое значение для сходимости, то укажем достаточно общий прием такого преобразования.

Умножим уравнение вида (1) f(x)=0 на функцию s(x)?0, т.е. эта функция не имеет корней на отрезке [a,b], и значит функция s(x) не меняет знак на этом отрезке (в частности s(x) может быть const). Сложим полученное уравнение с тождеством x?x, получим x=x+s(x)?f(x) . Обозначим правую часть j(x)=x+s(x)?f(x). Имеем x=j(x). Подбором функции s(x)?0 добиваемся, чтобы в окрестности корня для функции j(x)=x+s(x)?f(x) выполнялось условие сжатия, т.е. . При этом необходимо получить как можно меньшие значения параметра q.

В некоторых случаях после преобразования получаем, что в окрестности корня. Чтобы использовать метод простой итерации в этом случае следует представить уравнение в виде x=S(x), где - функция, обратная для j(x). В этом случае будет выполняться условие сходимости для функции S(x).

Практическая схема решения нелинейного уравнения методом простой итерации состоит в следующем.

- Отделить корни уравнения (1) f(x)=0, т.е. выделить интервалы, на которых f(x) имеет один корень.

- Выбрать один из найденных интервалов и преобразовать уравнение (1) к виду (2) x=j(x).

- Для выбранной формы записи уравнения проверить выполнение теоремы о сходимости метода простой итерации. Если условие не выполняется, выбрать другой вид уравнения (2).

- Задать начальное приближение и начать итерационный процесс.

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