velikol.ru
1

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

Рассмотрим задачу решения одного уравнения с одним неизвестным:




f(x) = 0,

(1)

где функция f (x) определена и непрерывна в некотором конечном или бесконечном интервале a < x < b.

Приведем уравнение (1) к эквивалентному уравнению:




x = g(x).

(2)

      Для нахождения корня уравнения (2) выберем какое-либо начальное приближение x(0) (расположенное, по возможности, близко к корню x*). Далее будем вычислять последующие приближения x(1), x(2), ..., x(k), ... по формуле




x(k+1) = g(x(k)), k = 0, 1, 2, ...

(3)

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


Сформулируем достаточное условие сходимости итерационного процесса.

Теорема. Пусть функция g(x) определена и дифференцируема на отрезке [a; b] и для неё выполняются условия:

1) g(x) [a; b] для всех x [a; b];

2) существует неотрицательное число q, такое, что |g'(x)|  q < 1 для всех x [ab].

Тогда уравнение (2) имеет единственный на [a; b] корень x*, к которому сходится последовательность {x(k)}, определяемая формулой (3), с любого x(0)[a; b]. При этом для любого k = 1, 2, 3, ...справедливы оценки погрешности

,
.

Доказательство.

Для доказательства сходимости метода итерации будем использовать теорему Банаха. Рассмотрим отображение g(x) на пространстве X = [ab] с метрикой (xy) = x – y. Известно, что отрезок является полным метрическим пространством.

Покажем, что отображение g(x) является сжимающим.

Условие 1) теоремы означает, что g(x) отображает отрезок [ab] в себя.

Возьмем две произвольных точки x и y из отрезка [ab]. Рассмотрим (g(x), g(y)) = g(x) – g(y).

В силу теоремы Лагранжа g(x) – g(y) = g'()(x – y), где  – некоторая точка из [ab]. В силу условия 2) теоремы |g'()|  q < 1, поэтому

(g(x), g(y)) = g(x) – g(y)= g'()(x – y) qx – y= q(xy).

Так как q < 1, то отображение g(x) – сжимающее. Поэтому можем закончить доказательство ссылкой на теорему Банаха.

Теорема доказана.


Дадим геометрическую интерпретацию решения уравнения (2) методом простой итерации.



Рис. 1. Геометрическая интерпретация решения уравнения (2) методом простой итерации

Отметим, что графическое решение уравнения (2) означает отыскание абсциссы точки пересечения графика функции y = g(x) с прямой y = x. Выберем начальное приближение x(0). Для построения следующего приближения x(k+1) находим точку на графике y = g(x) с абсциссой x(k) и проводим прямую, параллельную оси абсцисс, до пересечения с прямой y = x. Так как абсцисса точки, лежащей на графике функции y = x, равна ординате, то абсцисса полученной точки равна g(x(k)) = x(k+1).

Для представленного на рис. 1 случая взаимного расположения линий y = g(x) и y = x неограниченное повторение вычислений по формуле (3) позволяет сколь угодно близко подойти к точному значению корня x*.


Допустим, что при отыскании k – гo приближения была допущена ошибка и вместо x(k) получили . Поскольку последовательность {x(k)} сходится с любого начального приближения, то итерационный процесс можно продолжать, он все равно приблизит нас к точному решению x*. Это свойство метода простой итерации позволяет называть метод самоисправляющимся.


Рассмотрим теперь систему вида




.

(4)

Здесь F1, F2, …, Fn – действительные функции n переменных векторов с областями определения DF1,DF2, ..., DFn из полного метрического пространства Rn. Полагаем, что множество – область определения системы – не является пустым.

Введем в рассмотрение векторы

x = (x1, x2, …, xn)t и

F(x) = (F1(x1, x2, …, xn), F2(x1, x2, …, xn), …, Fn( x1, x2, …, xn))t,

тогда систему (4) можно записать более кратко:




x = F (x).

Пусть k – номер члена в последовательность nмерных векторов, тогда в обозначении k – го вектора индекс k будем писать вверху: x(k) = (x1(k), x2(k), …, xn(k)). Для нахождения вектор–корня x* = (x1*, x2*, …, xn*) построим последовательность векторов x(k) следующим образом:




x(k+1) = F ( x(k)), (k = 0, 1, 2, …)

(5)

В пространстве X = Rn введем норму. Норма вектора ||x|| определяется правилом . Связанная с векторной матричная норма для матрицы A = {aij} вычисляется следующим образом: . Обозначим матрицу, составленную из частных производных, через .


Теорема (Достаточное условие сходимости).

     Пусть вектор-функция F=(F1, F2, …, Fn) определена и непрерывна в известной области D действительного n – мерного пространства Rn, причем

      1) функция F отображает D в себя;

      2) функция F дифференцируема на D, и существует число q, 0 q < 1 такое, что

||F' (x)|| q, при всех xD.

Тогда в D существует единственный корень x* уравнения x = F(x), который можно найти как предел последовательности (x(k)) точек из D, определяемой рекуррентной формулой x(k+1) = F(x(k)), (k = 0, 1, 2, …) с любым начальным приближением x(0)D. При этом погрешности приближений (x(k)) оцениваются по формулам:




,

(2.6)







.

(2.7)

Доказательство также сводится к применению теоремы Банаха (см. электронный учебник – п.2.2 в теме «Решение систем нелинейных уравнений методом простой итерации»).


Теорема Банаха.
      Пусть отображение F является сжимающим на полном метрическом пространстве X с коэффициентом сжатия 0 q < 1. Тогда:
      1) на X существует одно и только одно решение уравнения x = F(x) (единственная неподвижная точка отображения F);
      2) решение x* уравнения x = F(x) равно пределу итерационной последовательности {x(k)} точек из X, определяемой рекуррентной формулой x(k+1) = F(x(k+1)), (k = 0, 1, 2, …), где x(0) – произвольный элемент из X;
      3) при каждом k = 1, 2, … справедливы оценки

и .