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

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

x_i^(k+1)=x_i^(k)+ω(z_i^(k+1)- x_i^(k)), (17)

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

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

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

Таким образом, метод релаксации можно понимать как поочерёдное применение формул (3) и (4) при каждом k=0,1,2,…. Действительно, задав начальные значения x₁⁽⁰⁾, x₂⁽⁰⁾,…,x_n⁽⁰⁾ и параметр ω, при k=0, полагая i=1,2,…,n, вычислим z₁⁽¹⁾,x₁⁽¹⁾; z₂⁽¹⁾,x₂⁽¹⁾; …; z_n⁽¹⁾,x_n⁽¹⁾. Далее вычисляем при k=1, также полагая i=1,2,…,n: z₁⁽²⁾,x₁⁽²⁾; z₂⁽²⁾,x₂⁽²⁾; …; z_n⁽²⁾,x_n⁽²⁾, т.д.

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

Для нормальной системы Ax=b метод релаксации, определяемый формулами (17), (18), сходится при любом х⁽⁰⁾ и любом ωε(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) называют сверхрелаксацией.