§ 1. Итерационные методы решения линейных систем

1. Метод простой итерации (метод Якоби).

Рассмотрим квадратную систему линейных уравнений с вещественными коэффициентами (3.10) (см. п. 1 § 2 гл. 3), которую запишем в матричном виде

понимая под А основную матрицу системы

а под векторы-столбцы вида первый из которых подлежит определению, а второй задан.

Предполагая однозначную разрешимость системы (6.1), заменим матричное уравнение (6.1) эквивалентным ему матричным уравнением в котором через обозначено вещественное число, обычно называемое стационарным параметром.

С помощью этого последнего уравнения составим итерационную последовательность векторов определив ее рекуррентным соотношением

при произвольном выборе «нулевого» приближения

Метод простой итерации заключается в замене точного решения X системы итерацией с достаточно большим номером Оценим погрешность метода простой итерации.

Из соотношений (6.3) и (6.1) сразу же вытекает следующее матричное уравнение для погрешности

где Е — единичная матрица порядка

Введем в рассмотрение норму вектора в пространстве и операторную норму квадратной матрицы порядка Как обычно, назовем нормой вектора X число равное корню квадратному из суммы квадратов координат этого вектора. Назовем операторной нормой произвольной матрицы А число равное либо точной верхней грани отношения на множестве всех ненулевых векторов X, либо (что то же самое) точной верхней грани норм на множестве всех векторов X, имеющих норму, равную единице.

Итак, по определению

Напомним, что для любой симметричной матрицы А опера торная норма этой матрицы равна наибольшему по модулю собственному значению этой матрицы (см. п. 4 § 5 гл. 5), т. е.

Из (6.5) вытекает следующее неравенство, справедливое для любой матрицы Л и любого вектора X:

Из матричного уравнения для погрешности (6.4) и из неравенства (6.7) мы получим, что для любого номера k

Докажем теперь следующую простую, но важную теорему.

Теорема 6.1. Для того чтобы итерационная последовательность (6.3) при любом выборе нулевого приближения и при данном значении параметра сходилась к точному решению X системы (6.1), достаточно, чтобы было выполнено условие

При этом последовательность (6.3) сходится со скоростью геометрической прогрессии со знаменателем

В случае, если матрица А является симметричной, условие (6.9) является и необходимым условием сходимости итерационной последовательности (6.3) при любом выборе нулевого приближения

Доказательство. Для установления достаточности условия (6.9) заметим, что из неравенства (6.8) вытекает следующее соотношение:

Из (6.10) очевидно, что условие (6.9) обеспечивает сходимость последовательности погрешностей к нулю со скоростью геометрической прогрессии со знаменателем

В случае, если матрица А является симметричной, будет симметричной и матрица , а поэтому в силу (6.6) условие (6.9) можно переписать в эквивалентном виде

(здесь через обозначены собственные значения матрицы А).

Убедимся в том, что условие (6.11) является необходимым условием сходимости к нулю последовательности при любом выборе нулевого приближения Предположим, что условие (6.11) не выполнено. Тогда существует собственное значение удовлетворяющее неравенству Обозначим через отвечающий этому собственному значению собственный вектор матрицы А и выберем нулевое приближение так, чтобы совпало с Тогда, последовательно записывая соотношение (6.4) для номеров мы получим, что

Из последнего соотношения в силу неравенства вытекает, что не стремится к нулю при Теорема 6.1 доказана.

Сразу же заметим, что для практических целей недостаточно установить только факт сходимости последовательности итераций. Центральной задачей численных методов является оценка скорости сходимости. Очень важно знать, как наилучшим способом распорядиться стационарным параметром т.для того, чтобы получить наиболее быструю сходимость. Остановимся на этом вопросе подробнее.

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

Из (6.9) и (6.10) вытекает, что , стало быть, (6.12) выполняется при , т. е. при

Отсюда видно, что для уменьшения числа итераций достаточных для достижения требуемой -точности, следует выбрать параметр так, чтобы получить минимум функции

Считая матрицу А симметричной и положительно определенной, мы приходим к следующей задаче оптимизации: найти минимум функции

Решение этой и несколько более общей задачи, предложенное А. А. Самарским, излагается в следующем пункте. Там будет доказано, что указанный минимум функции достигается для значения где — соответственно минимальное и максимальное собственные значения матрицы А, причем минимальное значение функции равно