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

1. Приведение системы к виду, удобному для итераций.

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

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

Здесь В — квадратная матрица с элементами — вектор-столбец с элементами

В развернутой форме записи система (6.2) имеет следующий вид:

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

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

из второго уравнения — неизвестное

и т. д. В результате получим систему

в которой на главной диагонали матрицы В находятся нулевые элементы. Остальные элементы выражаются по формулам

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

Часто систему (6.1) преобразуют к виду где специально выбираемый числовой параметр (см. п. 5).

2. Описание метода.

Выберем начальное приближение Подставляя его в правую часть системы (6.2) и вычисляя полученное выражение, находим первое приближение

Подставляя приближение в правую часть системы (6.2), получим

Продолжая этот процесс далее, получим последовательность приближений, вычисляемых по формуле

В развернутой форме записи формула (6.6) выглядит так:

В случае, когда для итераций используется система (6.4) с коэффициентами, вычисленными по формулам (6.5), метод простой итерации принято называть методом Якоби.

3. Сходимость метода простой итерации.

Теорема 6.1. Пусть выполнено условие

Тогда: 1°) решение х системы (6.2) существует и единственно, 2°) при произвольном начальном приближении метод простой итерации сходится и справедлива оценка погрешности

1°. Из курса линейной алгебры известно, что система линейных алгебраических уравнений имеет единственное решение при любой правой части тогда и только тогда, когда соответствующая однородная система имеет только нулевое решение. Пусть решение однородной системы Тогда Так как по условию это неравенство возможно только при Следовательно, и тем самым первое утверждение теоремы доказано.

2°. Вычитая из равенства (6.6) равенство получим

Вычисляя норму левой и правой частей этого равенства и используя неравенство имеем Так как это неравенство верно для всех то

Справедливость неравенства (6.9) установлена. Учитывая, что не зависит от при получаем из него, что при

Замечание 1. Теорема 6.1 дает простое достаточное условие (6.8) сходимости метода простой итерации. Грубо это условие можно интерпретировать как условие достаточной малости элементов матрицы В в системе, приведенной к виду (6.2).

Замечание 2. Если условие (6.8) принимает вид

Для метода Якоби это условие в силу равенств эквивалентно условию диагонального преобладания (5.45). Если же воспользоваться условием (6.8) при то Для метода Якоби получим другое условие диагонального преобладания:

Таким образом, для сходимости метода Якоби достаточно, чтобы матрица А была близка к диагональной.

Замечание 3. Из оценки (6.9) следует, что при выполнении условия (6.8) метод простой итерации сходится со скоростью геометрической прогрессии, знаменатель которой Скорость сходимости тем выше, чем меньше величина Хотя метод сходится при любом начальном приближении из оценки (6.9) можно сделать полезный вывод: начальное приближение желательно выбирать близким к решению.

Замечание 4. Оценка погрешности (6.9) является априорной. Ее использование для формулировки критерия окончания итераций затруднительно, так как значение неизвестно, а его грубое оценивание заведомо приведет к завышению необходимого числа итераций.

4. Апостериорная оценка погрешности

Предложение 6.1. Если выполнено условие (6.8), то справедлива апостериорная оценка погрешности

Запишем равенство (6.10) при в виде

Тогда

Для завершения доказательства достаточно заметить, что полученное неравенство эквивалентно неравенству (6.12).

Замечание. Величину, стоящую в правой части неравенства (6.12), можно легко вычислить после нахождения очередного приближения

Если требуется найти решение с точностью то в силу (6.12) следует вести итерации до выполнения неравенства

Таким образом, в качестве критерия окончания итерационного процесса может быть использовано неравенство

где

В практике вычислений иногда используют привлекательный своей простотой критерий окончания

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

Пример 6.1. Используя метод простой итерации в форме Якоби, найдем решение системы

с точностью в норме

Вычисляя коэффициенты по формулам (6.5), приведем систему к виду (6.4)

В последнем уравнении коэффициенты даны с точностью до погрешности округления. Здесь

Достаточное условие сходимости метода простой итерации выполнено, так как

Примем за начальное приближение к решению вектор и будем вести итерации по формуле (6.6) до выполнения критерия окончания (6.13), где в данном случае Значения приближений в табл. 6.1 приводятся с четырьмя цифрами после десятичной точки.

Таблица 6.1 (см. скан)

При условие (6.13) выполняется и можно положить . В данном случае точные значения решения нам известны (см. пример 5.16). Заметим, что в действительности решение с точностью до было получено уже при

5. Система с положительно определенной матрицей.

В случае, когда А — симметричная положительно определенная матрица, систему часто приводят к виду

которому отвечает метод простой итерации:

Здесь и параметр выбирают так, чтобы по возможности сделать минимальной величину

Пусть и — минимальное и максимальное собственные значения матрицы А. Известно, что условие будет выполнено, если взять Оптимальным является выбор . В этом случае принимает минимальное значение, равное

Чаще известны не значения , а их оценки вида Ащах либо вида . В первом случае полагают а во втором (например,

Заметим, что в случае, когда (а так бывает очень часто) при любом выборе имеем и 1. Поэтому в этом случае метод (6.18) сходится очень медленно.

6. Влияние ошибок округления.

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

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

Теорема 6.2. Пусть Предположим, что вычисляемая на ЭВМ с помощью метода простых итераций последовательность удовлетворяет равенствам

где Если вычисления по формулам (6.6) и (6.19) начинаются с одного начального приближения то для всех справедливы следующие оценки погрешности:

Здесь

Таким образом, метод простых итераций устойчив, но гарантированная точность метода ограничена величиной Критерий окончания (6.13) применим, если