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

 

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

(9)

Если все диагональные элементы , то систему (1) можно представить в приведенном виде

(10)

где

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

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

(11)

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

- первое приближение

-второе приближение (12)

.........

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

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

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

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

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

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

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

(k-норма)

Пример: для матрицы

 

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

, (13)

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

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

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

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

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

(11)

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

- первое приближение

-второе приближение (12)

.........

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

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

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

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

 

 

 

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

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

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

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

(k-норма)

Пример: для матрицы

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

, (13)

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

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

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

k-норма или сферическая норма.

Из неравенства (13) можно получить оценку числа итераций k, необходимых для обеспечения заданной точности e.

Отклонение приближения от решения x по норме не будет превышать e, если

(14)

 

Для вывода (14) достаточно рассмотреть равенства:

; ; ;

;

; и т.д.

Далее .

И учитывая, что , т.к. норма .

В неравенствах (13) и (14) используются согласованные нормы для матриц и векторов, т.е. m и l-нормы.

Неравенство (14) дает завышенную оценку числа итераций k. Из (14) можно получить удобное условие, позволяющее принять приближение в качестве решения с точностью e.

(15)

Пример: Найти решение системы уравнений

методом итераций с точностью 10^-2.

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

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

(16)

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

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

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

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

.

; т.к. то ; .

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

.

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

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

 

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

 

;

 

 

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

 

;

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

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

 

 

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

Лабораторная работа 2