41. Алгоритм метода Зейделя.

Исходные данные:

А – квадратная матрица коэффициентов порядка n,

b – столбец свободных членов,

х⁽⁰⁾- столбец начальных значений,

n – порядок системы,

k_max- предельное число итераций (страховка от зацикливания),

 - требуемая точность.

Результаты:

х – вектор решений,

begin

i=1,n

x _i←x_i⁽⁰⁾

p_i←1/a_ii

k =1,k_max

k _end←k

i=1,n

t←b_i

j =1,n

ij

t=t-a_ijx

Xnew←t*pi

_x_new-x_i>

k_end=0

XI← xnew

k_end0

exit

end

k_end – фактическое количество итераций (если достигнута точность ), если точность не достигнута за . k_max итераций, то k_end= 0.

Вспомогательные переменные:

t – переменная суммирования для накопления очередной компоненты,

x_new – переменная для временного хранения очередной компоненты решения в новом приближении.

Тело алгоритма состоит из двух последовательных циклов: первый играет вспомогательную роль (назначает начальные значения элементам столбца из неизвестных, вычисляет обратные величины диагональных элементов), второй – он троекратный, реализует процесс Зейделя. Во внешнем цикле (цикл «по ε») меняется значение счётчика k от единицы с шагом, равным единице, до заданного предельного числа итераций k_max. В конце его при истинном неравенстве |x_i^(k+1)-x^(k)_i|≤ε (тогда k_end=0) выполняется возврат к точке вызова данного алгоритма. В цикле «по строкам» (цикл «по i») вычисляются компоненты очередного приближения x_i^(k+1) (которые предварительно записываются в переменной x_new) и анализируется условие |x_i^(k+1)-x_i^(k)|≤. Если хотя бы для одной компоненты оно не выполняется, то переменной k_end присваивается нуль. Самый внутренний цикл (цикл «по j») служит для для реализации вычислений по формуле (15); в нем из правых частей уравнений системы (16) вычитаются левые части, содержащие все неизвестные кроме i-го.

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

Рассмотрим одно обобщение метода Зейделя, позволяющее иногда в несколько раз ускорить сходимость итерационной последовательности.

Пусть 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) называют сверхрелаксацией.