Явный метод простой итерации

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

(1)

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

(2)

Здесь - неизвестный вектор, - заданный вектор правой части, - заданная матрица коэффициентов или оператор (в случае оператора процесс воздействия его на вектор может не описываться процессом умножения какой-либо матрицы на вектор). Например, если задана СЛАУ (1), то непосредственно принимая

, (3)

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

Процесс простой итерации строится следующим образом:

, (4)

Поэтому матрица (оператор) в (2,4) называется матрицей (оператором) перехода (от предыдущей итерации к последующей). В качестве начального приближения можно принять . Если матрица постоянна (не зависит от номера итерации ), то такой итерационный процесс называется стационарным. В случае, если - явно представленная заданная матрица коэффициентов (как, например, в случае (3)), то процесс (4) – явный одношаговый метод простой итерации.

Заметим, что переход от (1) к (2) может быть выполнен не единственным способом, что приводит к различным модификациям метода простой итерации. Так, метод (4) с преобразованием (3) известен в литературе как частный случай одношагового метода простой итерации Ричардсона [1] или метод простой итерации Ричардсона. Другие методы простой итерации (явные и неявные) будут рассмотрены в следующих разделах.

Процесс простой итерации может быть формально записан также в виде ряда по степеням оператора , то есть в виде, так называемого, ряда Неймана

Пусть - «гипотетическое» точное решение, строго удовлетворяющее уравнению , а - вектор ошибки на -м шаге. Подставляя в формулу простой итерации получаем для соотношения ошибок на и -м шаге . Подчиненная норма матрицы мультипликативна (см.В.6). Поэтому для любой подчиненной нормы справедливо:

.

Отсюда следует Лемма.

Лемма. Достаточное условие сходимости процесса простой итерации:

, (5)

где - любая подчиненная норма .

Действительно, тогда

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

Спектральным радиусом матрицы (конечномерного оператора) называется , где - собственные числа оператора (см. Гл.3).

Теорема. Необходимым и достаточным условием сходимости процесса простой итерации (4) является

, (6)

при этом итерации сходятся не хуже геометрической прогрессии со знаменателем .

Необходимость и достаточность (6) доказана для произвольной матрицы, не имеющей полной системы базисных векторов [2-4], и, более того, для произвольного линейного оператора [9], для которого спектральный радиус определен как , где - спектральное множество линейного оператора (может быть дискретным и непрерывным континуумом).

Докажем Теорему для случая матрицы простой структуры.

Достаточность.

Для любой нормы матрицы простой структуры справедливо соотношение , то есть спектральный радиус есть минимальная из норм матрицы (см.В.7) и совпадает с ее евклидовой нормой. Поэтому рассматривая доказательство Леммы в евклидовой норме, получаем доказательство достаточности Теоремы.

Необходимость.

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

(7)

Из условия сходимости метода и (7) следует, что , ч.т.д.

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

Условия (5)─(6) являются, как правило, сильным ограничением при непосредственном применении метода (4), к решению заданной СЛАУ. Замена оператора на новый оператор с оптимальным в смысле минимума (6) спектром при эквивалентности нового уравнения исходной системе (1) может значительно расширить область сходимости процесса простой итерации:

,