Решение систем линейных алгебраических уравнений методом итераций

Рассмотрим систему линейных алгебраических уравнений (2.9)

. (2.9)

Если все диагональные элементы (i=1,2,…,n), то систему (2.1) можно представить в приведенном виде (2.10):

, (2.10)

где (i=1,2,…,n)

.

Введем обозначения

.

Тогда систему (2.2) можно представить так:

. (2.11)

В качестве начального приближения возьмем вектор b и подставим его в уравнение (2.11). Получим . Продолжая процесс, получим последовательности приближений:

– первое приближение;

– второе приближение; (2.12)

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

– (k+1)-е приближение.

Если существует предел x последовательности векторов то, переходя к пределу в равенстве при , убеждаемся, что x является решением уравнения (2.11):

.

Достаточное условие сходимости итерационного процесса представлено ниже.

Теорема. Если какая-нибудь норма матрицы А меньше единицы: , то уравнение (2.11) имеет единственное решение x, к которому стремится последовательность итераций (2.12) при любом выборе начального приближения.

Под нормойматрицы понимают следующие выражения:

– (m-норма) сумма модулей элементов строки;

– (l-норма) сумма модулей элементов столбца;

– (k-норма).

Например, для матрицы .

В расчетах полагают . Погрешности приближенного решения уравнения (2.11) на k-м шаге оценивают неравенством

, (2.13)

где – норма вектора X.

– m-норма или кубическая норма;

– l-норма или октаэдрическая норма.

Введем обозначения

.

Тогда система (2.2) запишется в виде

. (2.14)

В качестве начального приближения возьмем вектор b и подставим его в уравнение (2.14). Получим . Продолжая процесс, получим последовательности приближений:

– (k+1)-е приближение. (2.15)

Если существует предел x последовательности векторов то, переходя к пределу в равенстве при , убеждаемся, что x является решением уравнения (2.14):

Достаточное условие сходимости итерационного процесса:

Теорема. Если какая-нибудь норма матрицы А меньше единицы: ( ), то уравнение (2.14) имеет единственное решение x, к которому стремится последовательность итераций (2.15) при любом выборе начального приближения.

Блок-схема решения системы линейных алгебраических уравнений методом Гаусса с выбором главного элемента (по столбцу) приведена на рис. 2.1а, 2.1б.

Рис.2.1 а

Решение:Приведем систему к виду (2.10)

.

Запишем последовательность итераций

. (2.19)

Для приведенной матрицы достаточное условие ходимости выполняется по m-норме:

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

Число итераций для достижения заданной точности определяем из неравенства (2.13) , которое запишем так:

, действительно:

.

; , так как

то ; .

Вычислим теперь три последовательных приближения по формулам (2.19) и оценим погрешность каждого результата, используя неравенство (2.18) в виде:

. .

Первое приближение:

.

.

Следовательно, дает значение корня ξ с погрешностью, не превышающей величины .

Далее последовательно находим:

;

.

Третья итерация:

;

.

Заданная точность достигается за пять шагов. Точное решение .

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

Рис. 2.2 а

		Рис 2.2 б

Блок-схема алгоритма решения системы линейных уравнений алгебраических уравнений приведена на рис. 2.2 а, рис. 2.2 б.