Лекция № 5 Итерационные методы решения систем линейных алгебраических уравнений

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

Пусть дана система СЛАУ

Ах = b (1)

с неособенной матрицей А.

здесь - квадратная матрица размера n´n,

, - векторы n-го порядка.

Чтобы применить к (1) метод итерации, необходимо привести (1) к виду:

х = aх + b (2)

здесь - квадратная матрица размера n´n,

, - векторы n-го порядка.

СПОСОБ ПРИВЕДЕНИЯ СЛАУ ВИДА (1) к ВИДУ (2):

Предполагая, что диагональные элементы

,

разрешаем (1) относительно х.

Разделим i-ое уравнение системы Ах = b на диагональные элементы

В получившемся уравнении оставим в левой части уравнения х_i, все остальное перенесем в правую часть уравнения:

обозначим ,

Получаем систему уравнений, эквивалентную исходной системе, которая в матричной форме запишется в виде

х = aх + b,

причем: если в исходной матрице имелось диагональное преобладание, т.е.

то будем иметь < 1.

или

< 1.

Если в матрице А нет диагонального преобладания, его можно добиться каким-либо способом.

Систему (2) будем решать методом последовательных приближений.

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

Строим последовательно столбцы:

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

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

Вообще говоря , k=0,1,2, (3)

Последовательность приближений x⁽⁰⁾, x⁽¹⁾,…, x^(k)
(k = 0,1,2,...) к решению х^* системы (1) можно строить по рекуррентным формулам

.. (4),

при этом начальное приближение х⁽⁰⁾ можно брать, вообще говоря, любое.

Итерационный процесс (4), начинающийся с некоторого вектора , будем называть методом простых итераций. (МПИ).

Запишем (4) в развернутом виде:

(5)

Если последовательность x^(k) сходится, т. е. существует , то х^* есть решение исходной системы (1).

В этом легко убедиться, если в (4) перейти к пределу при к®¥.

т. е. х^* = aх^* + b

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

Теорема (достаточное условие сходимости МПИ):

Пусть . Тогда при любом начальном векторе метод простых итераций сходится к единственному решению задачи (1) и при всех справедливы оценки погрешности:

1. (6)

2. (7)

Доказательство:…………………………………………………………………

Для того, чтобы метод простой итерации (4) сходился при любом х^{(0 )}, необходимо и достаточно, чтобы |l(a)|<1, где l(a) - все собственные значения матрицы a.

При этом, если выполнено достаточное условие сходимости (||a||<1), то необходимое и достаточное условие автоматически выполняется, ибо | l(a)|<||a||.

Чаще всего останавливаются на проверке двух условий:

1)

2)

Если одно из них выполняется, то метод итераций сходится при любом начальном приближении х⁽⁰⁾.

Если требуется вычислить приближенное значение решения системы (1) с некоторой заданной степенью точности e т.е.

или

,

то из (6) можно получить условие окончания итерационного процесса

£ e

Тогда

или