Метод простой итерации. Пусть E = (E,r) - полное метрическое пространство и j(x) – отображение, определенное на E

Пусть E = (E, r) - полное метрическое пространство и j(x) – отображение, определенное на E. Если это отображение удовлетворяет двум условиям:

1) j(x)Î E при " x Î E, (j – отображение E в себя);

2) $ 0 £ q < 1 такое, что r (j(x), j(z)) £ q× r (x, z) при " x, z Î E, (j – сжимающее отображение),

то существует единственное xÎ E такое, что справедливо равенство

x = j (x). (1)

Точка x называется неподвижной точкой отображения j. Для приближенного вычисления неподвижной точки применяется

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

состоящий в построении последовательности { x ^{( n )}} по итерационной формуле

x ^{(n +1)} = j (x ⁽ⁿ⁾ ), n = 0, 1, 2, …, (2)

начиная из любого начального приближения x ⁽⁰⁾ Î E.

Условия 1) и 2) являются также и достаточными условиями сходимости метода простой итерации к неподвижной точке x.

Приведенные общие результаты применим к двум частным случаям.

Приложение I. Рассмотрим метрическое пространство E = ([ a; b ], | × |) и функцию j(x), определенную на [ a; b ]. Неподвижную точку x функции j в силу равенства (1) называют корнем уравнения

x = j (x). (3)

Метод простой итерации (2) для приближенного вычисления корней уравнения (3) запишем в виде:

x_{n +1} = j (x_n ), n = 0, 1, 2, …. (4)

Условия 1) и 2) существования и единственности корня уравнения (3) и сходимости к нему метода простой итерации (4) удобно записать в виде:

a) j (x) Î [ a; b ] " x Î [ a; b ];

b) $ 0 £ q < 1, что | j' (x)| £ q " x Î [ a; b ].

" Правило останова": вычисления прекращаются, когда впервые удовлетворяется неравенство

.

Искомый приближенный корень = x_n.

Приложение II. Рассмотрим метрическое пространство E = (E ₃ , r), где E ₃ – трехмерное векторное пространство, а расстояние между векторами x = (x ₁ , x ₂ , x ₃), z = (z ₁ , z ₂ , z ₃) определим по формуле

.

Рассмотрим отображение j, любому вектору x = (x ₁ , x ₂ , x ₃) ставящее в соответствие вектор y = (y ₁ , y ₂ , y ₃) по правилу

y_i=a _{i 1} x ₁ +a _{i 2} x ₂ + a _{i 3} x ₃ + b _i,, i = 1, 2, 3.

Неподвижную точку x = (x ₁ , x ₂ , x ₃) отображения j в этом случае называют решением системы линейных уравнений нормального вида:

(5)

Метод простой итерации для приближенного вычисления решения системы (5) принимает вид:

n= 0, 1, 2, …, (6)

и называется итерационным методом Якоби.

Условия 1) и 2) выполняются, если

. (7)

" Правило останова": вычисления прекращаются, когда впервые удовлетворяется неравенство

Искомое приближенное решение

= x ⁽ⁿ⁾ = .

Иногда можно ускорить сходимость, если вместо (6) проводить вычисления по итерационным формулам

n= 0, 1, 2, ….

Этот метод называется итерационным методом Зейделя.

Контрольные вопросы

1. Каковы достаточные условия сходимости метода простой итерации?

2. Какое условие является критерием достижения заданной точности при решении уравнения методом простой итерации?

3. Как обобщается метод простой итерации на решение уравнений в метрическом пространстве? Как формулируется принцип сжимающих отображений?

4. Как строится итерационная последовательность для нахождения решения системы линейных уравнений в методах Якоби и Зейделя?

5. Как формулируются достаточные условия сходимости итерационного процесса в случае систем линейных уравнений?

Задание №1. Вычислить один корень заданного уравнения с точностью , используя метод простой итерации.

Варианты задания 1 приводятся в таблице 1.

Задание №2. Методами Якоби и Зейделя решить с точностью заданную систему трех линейных уравнений с тремя неизвестными:

a₁₁ x₁+ a₁₂ x₂+ a₁₃ x₃=b₁ ,

a₂₁ x₁+ a₂₂ x₂+ a₂₃ x₃=b₂ ,

a₃₁ x₁+ a₃₂ x₂+ a₃₃ x₃=b₃ .

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

Варианты задания 2 приводятся в таблице 2.

Таблица 2

Продолжение таблицы 2

Указания к выполнению заданий

Задание №1. Уравнение, заданное в общем виде f (x) = 0, необходимо записать в виде x = j (x) с соблюдением следующих условий:

1) на промежутке изоляции [ a; b ] выбранного корня эти уравнения равносильны;

2) на промежутке [ a; b ] выполняются условия a) и b) сходимости метода простой итерации.

Иногда это сведение удается выполнить искусственно. Но есть общий прием: если f (a)< 0, f (b)> 0 и 0< m ₁ £ f ' (x) £ M ₁, то j (x) = x - , причем ; если f (a)> 0, f (b)< 0 и производная f ' (x) отрицательна, то, заменив уравнение f (x) = 0 на - f (x) = 0, придем к рассмотренному случаю.

Результаты вычислений итераций (4) записать в таблице

Контроль за " остановом" осуществляется по последнему столбцу таблицы.

Задание №2. Заданную систему привести к нормальному виду так, чтобы выполнялось условие (7) сходимости метода простой итерации. Если диагональные коэффициенты по модулю больше, чем сумма модулей двух других коэффициентов соответствующей строки, то такое сведение осуществляется непосредственно. Если диагональные коэффициенты не удовлетворяют этому условию, то заданную систему следует предварительно преобразовать с помощью элементарных преобразований.