Метод верхней релаксации

Метод последовательной верхней релаксации

Лекция 6. Метод релаксации

Большинство итерационных методов решения СЛАУ:

(6.1)

Основаны на идее расщепления матрицы системы. Если представить матрицу в виде:

, (6.2)

систему (6.1) можно переписать в виде:

(6.3)

и, на основании (6.3) использовать для итераций следующую формулу:

(6.4)

Здесь сразу возникает два вопроса:

1. Не будет ли решение системы (6.4) слишком сложной задачей?

2. Будет ли последовательность сходиться к точному решению системы (6.1)?

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

Например, если матрицу

(6.5)

расщепить следующим образом:

(6.6)

то формула (6.4) определит уже известный нам метод Якоби.

Если же выбрать нижней треугольной, а ‑ верхней строго треугольной:

(6.7)

формула (6.4) будет определять метод Гаусса-Зейделя.

Для того, чтобы прояснить ответ на второй вопрос, вычтем из уравнения (6.3) уравнение (6.4):

(6.8)

Здесь

(6.9)

вектор ошибки, представляющий отклонение -го приближения от точного решения.

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

. (6.10)

То, что методы Якоби и Гаусса-Зейделя могут сходиться медленно, объясняется тем, что максимальное собственное значение матрицы для решаемой задачи оказывается близко по модулю к 1.

Если же окажется, что , то итерационный метод будет расходиться.

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

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

Идею метода можно наглядно пояснить следующим образом. Еще во времена, когда вычисления производились вручную, было замечено, что при применении метода Гаусса-Зейделя итерации сходятся монотонно. Можно сказать, что «приближения остаются с одной и той же стороны от решения x» .

Последнюю фразу несколько трудно понять применительно к вектору хпроизвольной размерности. Однако можно проиллюстрировать схемой для известных итерационных методов для уравнения (см рис.6.1).

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

(6.11)

Для разных методов способ этой поправки может быть свой.

Но в любом случае очередное приближение может быть записано в виде (6.11).

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

, (6.12)

где ‑ некоторое число, большее 1.

В упомянутой диссертации Янга эта идея распространена на системы линейных уравнений. Итерационная формула, аналогичная (6.4), при этом принимает вид :

(6.13)

где

(6.14)

Остается вопрос, какое значение следует принять для ? В общем случае это достаточно сложная проблема. Но, во всяком случае, известно, что это число должно быть больше 1, но меньше 2. При (6.13) превращается в метод Гаусса-Зейделя. При не выполняется условие сходимости (6.10).

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

Литература

6.1. Стренг Г. Линейная алгебра и ее применения. – М.: Мир, 1980. – 454с.

Рассмотрим одно обобщение метода Зейделя, позволяющее иногда в несколько раз ускорить сходимость итерационной последовательности. Пусть zi(k) – обозначение i-й компоненты k-го приближения к решению системы (1) по методу Зейделя, а обозначение xi(k) будем использовать для i-й компоненты k-го приближения новым методом. Этот метод определим равенством

xi(k+1)=xi(k)+ω(zi(k+1)- xi(k)), (17)

где i=1,2,…,n; k=0,1,2,…; xi(0) – задаваемые начальные значения; ω – числовой параметр, называемый параметром релаксации. Очевидно, при ω=1 метод (3), называемый методом релаксации (ослабления) совпадает с методом Зейделя.

Пользуясь ведёнными здесь обозначениями, запишем на основе метода Зейделя дополнительное к (17) равенство для выражения компонент векторов z(k)=(zi(k))ni=1 через компоненты векторов x(k)= (xi(k))ni=1:

, i=1,2,…, n. (18)

Таким образом, метод релаксации можно понимать как поочерёдное применение формул (3) и (4) при каждом k=0,1,2,…. Действительно, задав начальные значения x1(0), x2(0),…,xn(0) и параметр ω, при k=0, полагая i=1,2,…,n, вычислим z1(1),x1(1); z2(1),x2(1); …; zn(1),xn(1). Далее вычисляем при k=1, также полагая i=1,2,…,n: z1(2),x1(2); z2(2),x2(2); …; zn(2),xn(2), т.д.

Теорема о сходимости метода релаксации (теорема Островского-Рейча).

Для нормальной системы Ax=b метод релаксации, определяемый формулами (17), (18), сходится при любом х(0) и любом ωε(0;2).

Система Ax=bназывается нормальной, если матрица А – симметричная (A¢=A) и положительно определённая ((Ax,x)>0 для любого x¹0). Поскольку итерационный процесс (17), (18) содержит параметр, естественно распорядится им так, чтобы сходимость последовательности (х(k)) была наиболее быстрой.

Исследование показывает, что оптимальное значение параметра релаксации лежит в интервале ωε(1;2). При этом метод (17),(18) называют методом последовательной верхней релаксации (ПВР). Ввиду неэффективности метода при ωε(0;1), называемого в этом случае методом нижней релаксации, название метод ПВР в последнее время относят ко всему семейству методов (17),(18), т.е. для любых ωε(0;2). При этом случай ωε(1;2) называют сверхрелаксацией.

Добавить комментарий

Закрыть меню