Метод итераций (Гаусса-Зейделя).

Рассмотрим метод на примере системы (2.2), преобразовав ее к виду:

(2. 5)

Если задать начальные приближения , то получим из первого уравнения первое приближение . Подставим его и во второе уравнение получим . Подстав в третье уравнение и получим , т.е.:

Аналогичным образом можно продолжить итерации и поэтому можно записать алгоритм в общем виде:

(2.6)

Процесс итераций следует продолжать до удовлетворения неравенств max . Строго говоря, это не метод простых итераций, поскольку вновь полученные значения используются далее на той же итерации. Метод итераций предпочтительнее, если число итераций менее n. Число операций для метода итераций пропорционально n², а для метода Гаусса оно пропорционально n³.

Метод итераций позволяет наглядно показать графически роль ведущих элементов расположенных на главной диагонали.

рис. 2.2

Рассмотрим систему Запишем ее в форме (2.6):

Выбираем точку на прямой (a) y=0 и x=1. Определяем значение y на прямой (b) y = 3/2. Вновь переходим на прямую (a) и определяем x = 1/4, переходим на прямую (b) и определяем y=9/8. На рис. 2.2 видим, что процесс итераций сходится к решению системы x =2/5, y = 6/5. Переставим уравнения, т.е. запишем .

Для начального значения y = 0 имеем на прямой (c) x = -2.

Переходим на прямую (d) и определяем y = 6. И далее необходимо перейти на прямую (c) и т.д. Очевидно, что процесс итераций расходится. Сравните диагональные элементы для систем (a), (b) и (c), (d).

Имеются жесткие необходимые условия, которые обеспечивают сходимость метода:

В каждой строке диагональный элемент превосходит сумму всех остальных. Такие матрицы называются строго диагонально доминирующими.

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

2.3. Метод LU преобразования.

Разложим матрицу A на произведение нижней треугольной матрицы L c единицами на главной диагонали и верхней треугольной U с неравными нулю диагональными элементами. Тогда система уравнений запишется: LUx = b.

Верхняя треугольная матрица получается методом исключения Гаусса. А нижняя треугольная содержит в качестве элементов множители, использованные для исключения Гаусса. Треугольные системы легко решать.

Например,

Поскольку предполагается, что A не вырождена, то диагональные элементы для всех k.

Кроме того, требуется вводить в разложение матрицу перестановок P: PA = LU. Это эквивалентно перестановке строк при выборе главного элемента. Например, .

Для примера, рассмотренного в методе Гаусса, приведем представление матрицы в виде:

А=РLU, т.е. разложим матрицу А в произведение PLU, где Р – матрица перестановок, а L и U – треугольные матрицы (нижняя и верхняя).

Р – единичная матрица, но с учётом перестановок строк при выборе главного диагонального элемента.

U – верхняя треугольные матрица для обратного хода метода Гаусса.

L – нижняя треугольная матрица, в диагонали которой расположены 1, а множители m_i используются в качестве элементов.

, , ,

Представление А=PLU называется LU – разложением или треугольным разложением матрицы А.

Треугольное разложение можно сформировать не зная матрицы b, а это весьма удобно для решения задач, в которых при одной и той же матрице А необходимо решить систему Ax=b для различных матриц b.

После разложения решение исходной системы можно найти, решая более простые системы:

Pz=b, , (), (2.7)

Ly=z, , (), (2.8)

Ux=y, , (). (2.9)

Подставляя последовательно y из уравнения (2.9) в уравнение (2.8), а затем z из уравнения (2.8) в уравнение (2.7), получим исходную систему PLUx=b.

Имея в распоряжении матрицы P, L и U, необходимо получить решения, записанные в формулах (2.7), (2.8) и (2.9).