Оценки скорости сходимости стационарных итерационных методов

Итерационные методы решения СЛАУ

 

Необходимое и достаточное условие сходимости стационарных итерационных методов

Рассмотрим стационарные итерационные методы

, (6.25)

в которых матрица и числовой параметр не зависят от номера итерации .

Погрешность итерационного метода (6.25) , где точное решение системы (6.16), удовлетворяет уравнению (доказать)

, , (6.26)

которое отличается от уравнения (6.25) лишь тем, что является однородным.

Сходимость итерационного метода (6.25) означает, что в некоторой норме при . Переписывая уравнение (6.26) в разрешенной относительно форме

, (6.27)

где (доказать)

, (6.28)

видим, что свойство сходимости итерационного метода целиком определяется матрицей . Матрица называется матрицей перехода от -й итерации к -й итерации.

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

или

.

Норму вектора в пространстве можно ввести различным образом. Нам прежде всего потребуется норма

.

Подчиненная ей норма матрицы выражается через элементы матрицы следующим образом:

.

Докажем это утверждение. Для любого вектора справедливо неравенство

,

т.е.

. (6.29)

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

, (6.30)

Где .

Без доказательства.

 

Оценки скорости сходимости стационарных итерационных методов

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

Оценку (6.30) можно переписать в виде

, , (6.31)

где . Если для погрешности итерационного метода выполняются оценки вида (6.31), то говорят, что метод сходится со скоростью геометрической прогрессии со знаменателем .

Используя оценку (6.31), можно определить число итераций, достаточное для того, чтобы начальная погрешность уменьшилась в заданное число раз. Действительно, зададим произвольное и потребуем, чтобы , т.е. чтобы

. (6.32)

Тогда из (6.31) получим, что

,

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

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

Оценим скорость сходимости в случае симметричных матриц и . По-прежнему будем рассматривать стационарный одношаговый итерационный метод (6.25).

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

Теорема 2. Пусть и симметричные положительно определенные матрицы, для которых справедливы неравенства

, (6.33)

где положительные постоянные, .

При

(6.34)

итерационный метод (6.25) сходится и для погрешности справедливы оценки

, , (6.35)

, , (6.36)

где , и

, .

Без доказательства.

Сделаем необходимые замечания и приведем следствия из этой теоремы.

Рассмотрим обобщенную задачу на собственные значения

. (6.37)

Если для матриц и выполнены неравенства (6.33), то из (6.37) для любого собственного вектора получим неравенства

.

Отсюда следует, что

, , (6.38)

где и минимальное и максимальное собственные числа задачи (6.37).

Таким образом, наиболее точными константами, с которыми выполняются неравенства (6.33), являются константы

, .

В этом случае параметр

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

,

при , на множестве всех положительных , удовлетворяющих условиям (6.38).

Пусть и соответственно минимальное и максимальное собственные значения матрицы .

Следствие 1. Если , то для метода простой итерации

(6.39)

при справедлива оценка

, (6.40)

где , .

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

.

Из условия получаем, что , где

,

и при малых имеем

. (6.41)

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

Использование неявных итерационных методов (6.25) объясняется тем, что при соответствующем выборе матрицы отношение для обобщенной задачи на собственные значения (6.37) будет больше, чем отношение

.