Системы линейных уравнений - метод простых итераций, метод Зейделя

Глава IV. Численные методы алгебры

§1. Системы линейных уравнений: метод простых итераций, метод Зейделя

Задача: Дано: , i=1,...,m.

Найти: , удовлетворяющее системе.

Пусть система Крамеровская, т.е. m = n.

Запишем систему в матричной форме:

             (1),

где  – столбец неизвестных,  – столбец свободных коэффициентов.

Метод простых итераций:

Рекомендуемые материалы

1. Преобразуем уравнение (1) в уравнение вида   (2)  (B=E-A);

2. Составим рекуррентную формулу:  (3);

3. Выберем любое начальное приближение .

По формуле (3) найдем , , …, ;

4. Если метод сходится, то последнее найденное приближение  приблизительно равно решению системы (2).

Определения нормы вектора:

Опр. 1. .

Опр. 2. .

Опр. 3. .

Определения нормы матрицы, согласованной с нормой вектора:

Опр. .

Следовательно:

Опр. 1. .

Опр. 2. .

Опр. 3. , где  – собственное значение матрицы ,  – сопряженная к A матрица (.

Замечание: Если  уменьшается при , то метод простых итераций сходится.

Теорема. (Достаточное условие сходимости метода простых итераций)

Если ||B|| < 1, то система (2) имеет единственное решение, и итерационный процесс по формуле (3) сходится со скоростью убывающей геометрическое прогрессии.

Док-во:

1. Если  – решение системы (2), то

.

Тогда однородная система  имеет решение, удовлетворяющее

, т.е. решение существует (нулевой вектор) и единственное.

Следовательно система (2) имеет единственное решение (по теореме об общем решении СЛУ, равной сумме общего решения однородной системы и частного решения неоднородной).

2. Пусть  – точное решение системы (2).

Тогда  – погрешность на шаге k, и

;  при .

Если обозначить , то норма погрешности меньше членов убывающей геометрической прогрессии с шагом q.

Теорема 2. (без док-ва) (Необходимое и достаточное условие сходимости метода простых итераций)

Пусть система (2) имеет единственное решение. Итерационный процесс по формуле (3) сходится к решению системы (2) при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы B по модулю меньше 1.

Своеобразная модификация метода простых итераций – метод Зейделя.

Метод Зейделя:

Пусть в системе  (1) в матрице A все диагональные элементы отличны от нуля.

1. Определим матрицы ; .

Получим систему  (4).

2. Построим рекуррентную формулу  (5).

3. Выберем любое начальное приближение .

Информация в лекции "13 - Гемодинамика" поможет Вам.

Система (5) имеет вид

Из первого уравнения системы (5) найдем , из второго уравнения системы (5) найдем , и т.д. Таким образом, найдем . Аналогично, найдем  , …, .

4. Если норма разности  уменьшается, то метод сходится, и последнее найденное приближение  приблизительно равно решению системы (4).

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

Теорема 3. (без док-ва)

Если A – вещественная, симметричная, положительно определенная (т.е. все главные миноры положительны) матрица, то метод Зейделя сходится.