Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Стационарные итерационные методы могут быть сведены к процессу явной или неявной простой итерации. При этом исходное уравнение (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) может значительно расширить область сходимости процесса простой итерации:
,
Дата публикования: 2014-11-02; Прочитано: 964 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!