Итерационные методы

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

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

Рассмотрим несколько итерационных методов решения линейных уравнений.

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

В методе простой итерации система (2.1) линейных алгебраических уравнений Ax = b приводится к эквивалентной системе вида

. (2.9)

Решение системы (2.9) и, следовательно, решение исходной системы (2.1) ищется как предел последовательности векторов при :

k = 0, 1, 2,…, (2.10)

где - начальное приближение для вектора решения.

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

ТЕОРЕМА 1. Если какая-либо норма матрицы , согласованная с рассматриваемой нормой вектора , меньше единицы ( ), то последовательность в методе простой итерации сходится к точному решению системы (2.9) со скоростью, не меньшей скорости геометрической прогрессии со знаменателем при любом начальном приближении .

ДОКАЗАТЕЛЬСТВО. Для доказательства теоремы введем погрешность . Вычитая из соотношения равенство (2.10), получаем . Переходя к нормам, имеем

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

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

, i =1,2, …, n,

, j = 1, 2, …, n. (2.11)

Простейшим и распространенным способом приведения системы Ax= b к виду (2.9), удобному для итераций, является выделение диагональных элементов, при этом каждое i-е уравнение разрешается относительно i-го неизвестного:

, i = 1, 2, …, n, (2.12)

и метод простой итерации запишется в виде

Матрица при этом имеет вид

.

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

i = 1, 2, …, n.

Еще раз подчеркнем, что рассмотренные формы условия сходимости метода итерации являются лишь достаточными. Их выполнение гарантирует сходимость метода, но их невыполнение в общем случае не означает, что метод простой итерации расходится. Необходимым и достаточным условием сходимости метода простой итерации является условие того, что целая часть (где -максимальное по модулю собственное значение матрицы А); это условие редко используется в практике вычислений.

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

ТЕОРЕМА 2. Если какая-либо норма матрицы , согласованная с рассматриваемой нормой вектора х, меньше единицы ( ), то имеет место следующая оценка погрешности:

. (2.13)

ДОКАЗАТЕЛЬСТВО. Вычтем из равенства равенство (2.10):

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

Перейдя к нормам, получим

или

Так как по условию теоремы , то

Используя соотношение из которого следует, что окончательно получим:

ТЕОРЕМА 3. Если какая-либо норма матрица , согласованная с рассматриваемой нормой вектора х, меньше единицы ( ), то имеет место следующая оценка погрешности:

Сделаем два замечания. Во-первых, соотношение (2.13) может быть записано в виде

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

Погрешности последовательных итераций связаны соотношением

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

Итак, на примере метода простой итерации продемонстрированы три этапа итерационных методов: построение последовательности векторов, порождаемой формулой (1.10); определение условия сходимости по теореме 1 и оценка скорости сходимости с помощью теорем 2 и 3.

Метод Зейделя

В методе простой итерации не используется кажущаяся очевидной возможность улучшения сходимости итерационного процесса – немедленное введение в расчет вновь вычисленных компонент вектора . Эта возможность используется в итерационном методе Зейделя. Итерационный процесс для системы (2.9) выполняется при этом по соотношению

i = 1, 2, …, n (2.14)

или для системы (1.1)

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

Отметим, что метод Зейделя сходится, если матрица А положительно определенная и симметричная.

Покажем, что метод итераций Зейделя эквивалентен некоторому методу простой итерации со специальным образом построенной матрицей и вектором в соотношении (2.10). Для этого запишем систему (2.14) в виде где F-верхняя треугольная матрица из коэффициентов матрицы , а Перепишем систему в виде где E-единичная матрица. Матрица (Е-Н) - нижняя треугольная матрица с диагональными элементами, равными единице. Следовательно, определитель этой матрицы отличен от нуля (равен единице) и она имеет обратную матрицу . Тогда

Сопоставляя это соотношение с решением (2.10), можем заключить, что действительно метод итераций Зейделя эквивалентен методу простой итерации в том смысле, что для установления условия и критерия сходимости метода итераций Зейделя можно воспользоваться теоремами, приведенными для метода простой итерации, если положить Итерационный процесс для системы (2.12) записывают и в более общей форме, а именно

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

Итерационный процесс при w > 1 называют МЕТОДОМ ВЕРХНЕЙ РЕЛАКСАЦИИ, при w = 1 (метод Зейделя)-методом ПОЛНОЙ РЕЛАКСАЦИИ и при w < 1 - методом НИЖНЕЙ РЕЛАКСАЦИИ.

В простом случае при специально выбранном w можно дать оценку числа операций N, необходимых для достижения заданной точности . В методе простой итерации методе Зейделя методе верхней релаксации Очевидно, что число итераций тем больше, чем больше порядок системы; при этом имеет место квадратичная зависимость в первых двух методах и линейная зависимость в методе верхней релаксации. Очевидно также, что число итераций тем больше, чем меньше .

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

Можно дать наиболее общую запись итерационного процесса для системы (1.1). Имеем

(2.15)

где - некоторая матрица, выбираемая для обеспечения быстрой сходимости метода. Во многом она определяется конкретной системой (2.1) и искусством вычислителя. Говорят, что итерационный процесс стационарный, если и не зависят от k; в дальнейшем индекс k при B и опускается. Из (2.15) очевидно, что если итерационный процесс сходится, т. е. то он сходится к решению системы (2.1).

Пусть матрицы D и L определены следующим образом:

,

Тогда метод простой итерации есть частный случай процесса(2.15) при B = D и метод Зейделя – частный случай при B = D + L, а метод релаксации – частный случай при B = D + wL,

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

3. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ И СИСТЕМ