3.1. Принцип сжимающих отображений

Большинство итерационных методов (и не только для систем линейных уравнений) может быть получено применением принципа неподвижной точки (сжимающих отображений). Приведем его формулировку.

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

Предложение (принцип сжимающих отображений). Пусть -замкнутое ограниченное множество в и отображение - сжимающее на множестве . Тогда уравнение

имеет в единственное решение . При этом при любом выборе вектора последовательность

сходится при к .

3.2. Метод простых итераций (последовательных приближений)

Заменим систему (1) эквивалентной системой, имеющий вид (24):

Построим по начальному приближению итерационный процесс, задаваемый формулой (сравните с формулой (25))

Алгоритм (27) называется методом простой итерации или стационарным методом.

Укажем наиболее распространенные способы перехода от системы (1) к эквивалентной системе вида (26):

1.

2.

где - некоторая невырожденная матрица.

3.

где - числовой параметр, - невырожденная матрица.

Для третьего способа перехода от исходной системы (1) к эквивалентной системе (26) алгоритм (27) принято записывать в виде

Формула (28) называется общим неявным методом простой итерации. Значение параметра выбирается для каждой конкретной системы так, чтобы скорость сходимости последовательности приближений была максимальной.

Теорема 1. Если то система (26) имеет единственное решение и метод простой итерации (27) сходится

при любом выборе начального приближения со скоростью не медленнее, чем геометрическая прогрессия со знаменателем . При этом:

Внимание! Для сходимости метода простой итерации достаточно выполнения условия в любой норме.

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

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

Обозначим через реально вычисленное значение -ого приближения, а через - вектор погрешности округления на -ом шаге. Вместо формулы (27) получим:

.

Вектор суммарной ошибки на -ом шаге имеет вид:

.

В условиях теоремы 1 имеем:

.

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

Замечание 10. Теорема 2 хотя и дает необходимые и достаточные условия сходимости метода простых итераций, но часто ее практическое значение не велико.

Рассмотрим систему (1) с матрицей из примера 1. Воспользовавшись первым способом перехода к системе (26), допускающей применение метода простых итераций, получим эквивалентную систему в которой матрица имеет вид

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

Выясним, что будет происходить, если для решения системы использовать метод простых итераций.

Будем считать, что по формуле (27) вычисляются не векторы , а приращения :

В реальных вычислениях получим

где - матрица ошибок на - ом шаге.

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

При имеем

Отсюда следует, что если , но не настолько велико, чтобы наступило переполнение, когда , то сходимости итераций все равно не будет.

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

Для ускорения сходимости итерационный процесс (27) должен быть построен так, чтобы норма матрицы была возможно меньше. Если возвратиться к способам перехода от системы (1) к эквивалентной системе (26), это означает, что нужно выбирать матрицу или, соответственно, параметр и матрицу так, чтобы нормы или были возможно меньше.

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

Замечание 11. В приложениях довольно часто встречаются системы с положительно определенными симметричными матрицами. Мы не приводим здесь подробности применения итерационных методов для решения таких систем. Их изложение можно найти, например, в [3]. Отметим только, что для любой положительно определенной симметричной матрицы можно так подобрать матрицу , чтобы итерационный процесс (27) сходился. Действительно, так как собственные числа матрицы принадлежат некоторому интервалу , то можно положить

Нетрудно видеть, что спектральный радиус матрицы меньше единицы .

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