Итерационные методы (метод Якоби, метод Зейделя, метод релаксации)

Итерационные методы решения СЛАУ позволяют найти решение лишь с заданной точностью. Пусть требуется решить систему Ax=f. Представим матрицу A в виде A=L+D+U, где L - нижнетреугольная матрица, D - диагональная матрица, U - верхнетреугольная матрица.

Запишем систему (6.1) в развернутом виде:

где ( i=1, 2, …, n ), и приведем к виду

Обозначим

В векторно-матричном виде система запишется в виде:

x=B x+C,

где B={b_ij}_{i, j=1, …, n}, C={c_i}_{i=1, …, n}, x=(x₁, x₂, …, x_n)^Т.

Построим итерационный процесс по формуле

x^(k+1)=B x^(k)+C,

где x⁰ - задано, k - номер итерации, x^(k)=(x₁^k, x₂^k, …, x_n^k)^Т.

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

,

где e - заданная точность вычисления.

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

или условие диагонального преобладания матрицы A, т. е.

Необходимым и достаточным условием сходимости итерационных методов является условие max|li(B)| < 1. Оценка погрешности итерационного процесса запишется в виде:

,

где x^*- точное решение. Определяя необходимое число итераций для достижений заданной точности из формулы, получим

Итерационная формула метода Якоби имеет вид:

,

где

Для метода Зейделя каждый вычисленный элемент вектора x на (k+1) -й итерации используется при вычислении следующего элемента:

В общем виде получим:

.

Для метода релаксации введем числовой параметр w так, что

при w > 1 будет метод верхней релаксации,

при w = 1 - метод полной релаксации (метод Зейделя),

при w < 1 - метод нижней релаксации.

Если A=A^* > 0, a w такое, что 0< w < 2, то метод релаксации сходится. Параметр w выбирается из условия минимума спектрального радиуса оператора перехода от итерации к итерации.

Оптимизация скорости сходимости итерационного процесса

Рассмотрим канонический вид итерационной схемы:

, А=А^T > 0. (6.3)

Если B=E, то схема называется явной:

.

Если t_k+1 =t , то схема называется стационарной. При этом параметр t выбирается из минимума нормы разрешающего оператора T_{n, 0} = S_n× S_n-1× …× S₁, где x⁽ⁿ⁾=T_{n, 0} × x⁰, S_i - оператор перехода от (i-1) к (i) итерации. Имеет место оценка

.

Итерационные параметры выбираются из условия , где P_n(t)= - это полином, построенный по параметрам t_k на отрезке [g₁, g₂].

Оптимальным значением параметра t является

,

где - собственные значения матрицы А.

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

Рассмотрим канонический вид итерационной схемы (6.3).

Введем понятия невязки r^(k)=A x^(k) - f и погрешности v^(k) = D^1/2 (x^(k)-x^*), где x^* - точное решение и D - самосопряженный, положительно определенный оператор в вещественном гильбертовом пространстве H.

Назовем w^(k) = B^-1 r^(k) поправкой.

Будем выбирать параметр t_k+1 из условия минимума нормы погрешности при переходе от одной итерации к другой. Умножим итерационную схему на D^1/2 :

D^1/2 x^(k+1)=D^1/2 x^(k)-t_k+1(D^1/2 Ax^(k)-D^1/2 Ax^*),

v^(k+1)=v^(k)-t_k+1(D^1/2 A D ^-1/2 D^1/2(x^(k)-x^*)),

v^(k+1)=v^(k)-t_k+1 C v^(k),

где обозначено C=D^1/2 A D ^-1/2.

Имеем

.

Из условия найдем .

Рассмотрим следующие методы.

Mетод скорейшего спуска

Неявная схема: B=B^*> 0, D=A, А=А^T> 0.

.

Явная схема: B=E,

.

Метод минимальных невязок

Явная схема: B=E, D=A^* A, А> 0.

Если A=A^*, то D^1/2=A и C=A.

v^(k+1)=D^1/2(x^(k)-x^*)=A (x^(k)-x^*)=A x^(k)-f = r^(k),

.

Метод минимальных поправок

Неявная схема: B=B^*> 0, D=A^* B^-1 A, А> 0,

.

Метод минимальных погрешностей

Неявная схема: B=(A^*)^-1B₀, D=B₀> 0, B₀= B₀^T, B₀w^(k)=A^*r^(k),

.

Явная схема: B=E, A^*=B₀,

.

Методы сопряженных направлений

Рассмотрим схему

. (6.4)

В каноническом виде (6.4) итерационные параметры t_k+1, α _k+1 выбираются из условия минимума нормы разрешающего оператора, а не оператора перехода от итерации к итерации.

Запишем итерационные формулы в общем виде:

где

r^(k)=Ax^(k) - f – невязка,

w^(k)=B^-1r^(k) – поправка,

z^(k)=x^(k) - x^* - погрешность,

x^* - точное решение.

Если B=E, то схема является явной и имеет вид

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

Метод сопряженных градиентов (явная схема): D=A,

.

Метод сопряженных невязок (явная схема): D=A^*A,

.

Метод сопряженных погрешностей (неявная схема):

D=B₀> 0, B=(A^*)^-1B₀,

Задания

1. Найти число обусловленности заданной матрицы A.

2. Найти решение СЛАУ Ax=f, используя точные методы: метод Гаусса и метод Гаусса с выбором главного элемента.

3. Найти определитель матрицы A и обратную матрицу A^-1, используя метод Гаусса и метод Гаусса с выбором главного элемента.

4. Найти приближенное решение СЛАУ Ax=f с заданной точностью ε, используя

а) один из итерационных методов:

- метод Якоби,

- метод Зейделя,

- метод релаксации;

б) один из методов вариационного типа:

- явный метод скорейшего спуска,

- неявный метод скорейшего спуска,

- метод минимальных невязок,

- метод минимальных поправок,

- метод минимальных погрешностей;

в) один из трехслойных методов:

- метод сопряженных градиентов,

- метод сопряженных невязок,

- метод сопряженных погрешностей.

5. Привести пример плохо обусловленной матрицы A и проверить устойчивость методов к ошибкам округления правой части f.

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. Итерационные и рекурсивные алгоритмы. Реккурентные соотношения.