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

В этом методе матрица С выбирается единичной: СºЕ. Тогда

В координатной форме:

Для сходимости метода простой итерации достаточно, чтобы

|| B ||<1. (4.13)

Доказательство можно найти, например, в книге Ю.П. Боглаева [9].

Условие сходимости в разных нормах будет выглядеть следующим образом:

в евклидовой норме ;

в норме Чебышева .

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

Отсюда вывод: преобразование исходной системы А х = b к итерационному виду x ^{( k +1)}=B x ^{( k )}+ d нужно осуществить таким образом, чтобы коэффициенты при неизвестных в правых частях стали существенно меньше единицы.

Отметим, что существует необходимое и достаточное условие сходимости метода простой итерации, формулируемое следующей теоремой.

Если А х = b имеет единственное решение, то последовательные приближения x ^{(k+ 1 )} =B x ^(k)+ d сходятся к решению исходной системы при любом начальном приближении х ⁽⁰⁾ тогда и только тогда, когда все собственные значения матрицы В по модулю меньше единицы.

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

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

Например, получение системы с диагональным доминированием, то есть такой системы, у которой абсолютные величины диагональных коэффициентов больше суммы абсолютных величин недиагональных элементов этой строки (см. п. 4.4). Если теперь разделить все уравнения на соответствующие диагональные элементы и выразить из каждого уравнения неизвестное с коэффициентом, равным единице, то будет получена система с коэффициентами | b_ij |<1. Затем необходимо проверить условие сходимости. Если оно не выполняется ни в одной норме, то нужно вернуться к исходной системе и попытаться выполнить преобразование так, чтобы добиться лучшего результата[1].

Пример 3. Решить систему уравнений.

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

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

Запишем исходное уравнение метода простой итерации и его итерационную схему:

,

или, вычитая,

. (4.14)

Нормируя получившееся выражение, имеем

. (4.15)

Преобразуем разность (4.14), прибавив к левой и правой части x ^{( k –1)}:

,

или, нормируя и преобразовывая

,

.

Используя (4.15) и то, что (1–||B||)>0, окончательно получаем оценку

.

Таким образом, для остановки итерационного процесса при заданной погрешности e можно использовать оценку

,

или . (4.16)

Если || B ||»0,5, то тогда можно использовать оценку .

Существует и априорная оценка точности метода, с помощью которой можно определить необходимое число итераций для достижения заданной погрешности e [5].

.

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