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

(8.30)

Определение 4. Линейным одношаговым итерационным методом называют метод вида

(8.31)

где k –номер итерации.

, – нестационарный метод,

– стационарный метод.

Требование к итерационным методам: после подстановки в них точного решения системы (8.30) должно получиться тождество

 

= .

Линейный одношаговый итерационный метод для решения системы (8.31):

(8.32)

Вопрос сходимости:

Теорема 1.

Для сходимости нестационарного одношагового итерационного метода (8.32) достаточно, чтобы нормы всех матриц B_i были меньше единицы: <1 i B , i = 0,1,...,m.

Выразим матрицу из второго соотношения в (8.32)

Вычитаем из этого равенства точное решение :

.

Так как k = 0,1,...,m,

.

Отсюда . Теорема доказана.

Одношаговый стационарный метод :

(8.33)



Теорема 2.

Для сходимости стационарного метода (8.33) необходимо и достаточно, чтобы все собственные числа матрицы B по модулю были меньше единицы.

Доказательство.

При k = 0,1,..., m: .

Для сходимости метода (8.33) необходимо и достаточно, чтобы сходился матричный ряд E + B + ...+ B^k + ....

Для сходимости этого матричного ряда, необходимо и достаточно, чтобы все собственные числа матрицы B по модулю были меньше единицы.

Теорема доказана.

Следствие 1. Для сходимости стационарного метода (8.33) достаточно, чтобы какая-либо из норм матрицы B была меньше единицы.

Сходящийся итерационный метод (8.33):

Матрица B зафиксирована, .

Организация расчетов: - начальное приближение – ?,

- точность расчетов – малое e > 0 – ?,

- критерий окончания расчетов– ?

1) Начальное приближение выбирается произвольно.

2) Критерий окончания итерационного процесса:

Для стационарных итерационных методов:

в пределе  .

,

.

– критерий окончания расчетов

Для нестационарных итерационных методов:

.

 ,

– критерий окончания расчетов (8.34)

Пусть . Для уменьшения начальной погрешности в 1/e необходимо итераций.

– характеристика скорости сходимости итерационного метода.

Целая часть – минимальное число итераций при точности e.

ln(1/q) – скорость сходимости итерационного метода.

Скорость сходимости целиком определяется свойствами матрицы B – матрицы перехода от итерации к итерации и не зависит ни от начального приближения , ни от задаваемой точности e .

Построение итерационного метода:

 Операция не простая и требует специальных знаний

. (8.35)

Способ приведения системы:

 . Выбор C конкретизирует итерационный метод.

Способ (метод Якоби):

,

. (8.36)

(8.37)

Теорема 2. Если A – матрица с диагональным преобладанием, то метод Якоби сходится.

Способ (метод Гаусса-Зейделя):

(8.38)

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

,

где`

.

Для метода Гаусса-Зейделя справедливы утверждения:

Теорема 3. Пусть . Тогда метод Гаусса-Зейделя сходится при любом начальном приближении и справедлива оценка для любого .

Теорема 4. Пусть , где B – матрица (8.37). Тогда для метода Гаусса-Зейделя справедлива оценка для любого .

Пример:

– метод Гаусса-Зейделя не сходится

.

Собственные числа матрицы : (-2.2853;-0.6845;0.0).

Если A – симметричная и положительно определенная матрица с диагональным преобладанием, то методы Якоби и Гаусса-Зейделя сходятся, причем второй не медленнее, чем первый.

Каноническая форма одношагового итерационного метода:

Определение 5. Канонической формой одношагового итерационного метода решения системы (8.30) ( ) называется его запись в виде

(8.39)

Здесь – матрица, задающая тот или иной итерационный метод,

– итерационный параметр.