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

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

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

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

1)

2)

3) =

4)

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

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

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

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

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

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

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

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

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

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

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

Таким образом если отображение 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) Вычислить коэффициент a и выбрать подходящую метрику.

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

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

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

1. Запишите алгоритм метода Гаусса с выбором главных элементов в столбцах для решения линейной системы.

2. Как конкретизируется принцип сжимающих отображений для приближенного решения линейных систем?

3. Запишите алгоритм метода простой итерации для решения линейной системы.

4. Запишите и обоснуйте условия при которых отображение F является сжимающим.

5. Как приводится линейная система к виду, удобному для применения метода простой итерации?

Литература

1. Вержбицкий В.М. Основы численных методов. М.: Высшая школа, 2002.

2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. -М., Наука, 1987.

3. Вабищевич П.Н.. Численное моделирование. М.: 1993.

4. Заварыкин В. М., Житомирский Г. В., Лапчик М. П. Численные методы. - М., Просвещение, 1990.