3.3. Метод простой итерации решения систем линейных уравнений

Систему уравнений ,(1) всегда можно преобразовать в виду (2), т.е.

Правые части системы (2) определяют отображение с помощью функцийF: (3). При этом. Задав каким - либо образом начальную точкуможно построить итерационную последовательность

Вопрос сходимости итерационной последовательности системы (2) решается несколько более сложно, чем скалярного уравнения x=f(x). Для этого приходится применять метод сжимающих отображений. Рассмотрим множество Х. Для любых двух точек x,y X введем расстояние (метрику) , таким образом, чтобы выполнились условия:

1)

2)

3) =

4)

Множество Х с введенной на нем метрикой  называется метрическим пространством (Х, ). В метрическом пространстве можно определить понятие предела последовательности и фундаментальной последовательности.

Последовательность {} множества Х называется сходящейся к х элементу, если т.е..

Последовательность {} множества Х называется фундаментальной, если

В любом метрическом пространстве сходящаяся последовательность является фундаментальной. Обратное верно не всегда. Если в пространстве Х любая фундаментальная последовательность сходится, пространство Х называется полным метрическим пространством.

При решении методом простой итерации нужно: «погрузить» систему в подходящее полное метрическое пространство (т.е. подходящим образом ввести метрику в ).

Пусть отображение множества (Х,р) в себя. Пусть. ОтображениеF множества Х в себя называется - сжимающим, если . Точка хХ называетсянеподвижной относительно отображения F, если F(x)=x.

Применительно к системе (2) – неподвижная точка – это решение системы (при условии, что F – сжимающее отображение).

Существование неподвижной точки устанавливает теорема Банаха:

Если F - сжимающее отображение полного метрического пространства Х в себя, то существует единственная неподвижная точка хХ, такая, что х=F(x), причем итерационная последовательность сходится кx при любом начальном значении .

Оценка расстояния между приближением и неподвижной точкой оценивается по формулам

где – коэффициент из условия сжимаемости.

Таким образом если отображение F(х) является сжимающим отображением полного метрического пространства в себя, то решение системы (2) может быть найдено с любой степенью точности при любом выборе начального приближения .

Существует много способов введения метрики в пространстве , при этом пространство будет полным метрическим пространством. Можно рассматривать одну из следующих метрик:

1)

2)

3)

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

1. в пространстве

сумма абсолютных величин коэффициентов по строкам

2. в пространстве

сумма абсолютных величин коэффициентов по столбцам

3. в пространстве

был меньше 1.

Получим, например первое условие:

,

Таким образом, решение системы линейных уравнений вида (1) ,, Состоит из следующих этапов:

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

Пример:

x+2y+1=0 x+y+2=0

2y=-x-1 0,5x+0,5y+1=0

y=-0,5x-0,5 -0,5x-0,5y-1=0

x=0,5x-0,5y-1

2) Вычислить коэффициент  и выбрать подходящую метрику.

3) Задать начальное приближение и построить итерационную последовательность, на каждом шаге оценивая расстояние между приближением и точным решением в выбранной метрике: .

4) Когда требуемая точность будет достигнута, определить невязку для найденного приближения.