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

Перепишем систему в виде:

x₁ = a₁₁×x₁+a₁₂×x₂+...+a_1n×x_n + β₁

x₂ = a₂₁×x₁+a₂₂×x₂+...+a_2n×x_n + β₂                                                                            (1)

.....................................................

x_n = a_n1×x₁+a_n2×x₂+...+a_nn×x_n + β₁

или сокращенно:                                              (2)

Правая часть системы определяет отображение F:

, преобразующее точку x (x₁, x₂,..., x_n) n – мерного пространства в точку y (y₁, y₂,..., y_n) того же пространства. Используя систему (1) и выбрав начальную точку x (x₁, x₂,..., x_n) можно построить итерационную последовательность точек n – мерного пространства:

x⁽⁰⁾, x⁽¹⁾, x⁽²⁾,..., x⁽ⁿ⁾,...

Пример. Пусть дана система:

Примем за x(0) =(0, 0, 0). Получим x(1) = (-1, -2, -3). Далее x(2) = (1, -2, -2) и т.д. При определенных условиях последовательность сходится, и ее предел является решением системы.

Напомним следующие понятия математического анализа.

Функцию r (x, y) называют метрикой, если выполняются следующие условия:

1. r (x, y) ³ 0

2. r (x, y) =0 тогда и только тогда, когда x = y.

3. r (x, y) = r (y, x)

4. r (x, y) £ r (x, z) + r (z, y).

Множество с введенной на нем метрикой называется метрическим множеством Е.

Пусть F – отображение, действующее в метрическом пространстве Е с метрикой r, и для любых x, yÎЕ Fx, Fy – образы этих точек. Отображение F пространства Е в себя называется сжимающим, если существует a, такое, что 0 < a < 1 и для любых x, y ÎЕ выполняется неравенство: r (Fx, Fy) £ a×r (x, y).

Точка x называется неподвижной точкой отображения F, если Fx = x.

Неподвижная точка x применительно к системе (1) является решением системы.

Теорема. (Принцип сжимающих отображений). Если F – сжимающее отображение, определенное в метрическом пространстве, то существует единственная неподвижная точка x, такая, что Fx = x. При этом итерационная последовательность, построенная для отображения F с любым начальным элементом x(0), сходится к x.

Оценка расстояния между неподвижной точкой x и приближением x(k) дается формулой (без доказательства):

 , где a - множитель из условия сходимости.

Вывод: для решения системы (1) методом итераций достаточно установить, что отображение F, заданное соотношением (2), является сжимающим.

Тогда решение системы может быть получено с любой точностью при любом x⁽⁰⁾.