Решение систем линейных алгебраических уравнений для больших разреженных матриц (стр. 5 из 6)
Здесь ω – параметр релаксации, ω ∈ [0,2]. При ω > 1 говорят о верхней релаксации, при ω < 1 – о нижней, а при ω = 1 метод SOR сводится к методу Гаусса–Зейделя. Удачный выбор параметра релаксации позволяет на порядки понизить число итераций для достижения требуемой точности.
Матричная форма (6) имеет вид
x(k+1) = Lωx(k) + gω,
где Lω = (E − ωL)−1(ωU + (1 − ω)E), gω = (E − ωL)−1ωD−1b.
В общем случае метод несимметризуем. Сходимость гарантирована для положительно определенной симметричной матрицы.
3.6 Метод симметричной последовательной верхней релаксации (SSOR)
Этот метод по числу итераций сходится в два быстрее, чем предыдущий, но итерации являются более сложными и даются соотношениями
; 
1;Здесь ω – параметр релаксации, ω ∈ [0,2].
Если A – положительно определенная симметричная матрица, то метод SSOR симметризуем.
Упражнение. Найдите матрицу перехода.
ТЕСТ РУБЕЖНОГО КОНТРОЛЯ № 2
1. Проверьте сходимость предыдущих методов для матриц
(a)
A
;  | 0 0 0 0 | −1 0 0 0 | 0−1 0 0 | −1 0−1 0 | 4 0 0 4 0 −1 −1 0 | 0 0 4 −1 |  | |
| (c) |  | 0 4 | 0 0 | 0 0 | 0 0 | −1 −1 −1 0 | 0 −1 |  |
0 0 0(b)
41 0 −1 0 0 0 0 0
−1 4 −1 0 −1 0 0 0 0
01 4 0 01 0 0 0
−1 0 0 4 −1 0
A = 01 0 −1 41 0 ;
0 0 4 0 0 −1 −1 −1 −1 0 0 0 4 0 0 −1 0 −1
A 0 0 0 0 4 0 0 −1 −1 .
−1 −1 0 0 4 0 0 0
1 0 −1 −1 0 0 4 0 0
−1 −1 0 −1 0 0 4 0
0 0 −1 −1 −1 0 0 0 4
2. A является симметричной и положительно определенной. Какие из методов являются симметризуемыми?
(a) простой итерации;
(b) Якоби;
(c) Гаусса–Зейделя;
(d) SOR;
(e) SSOR.
3. Необходимым и достаточным условием сходимости итерационного метода является
(a) положительная определенность матрицы перехода G;
(b) симметричность матрицы перехода G;
(c) неравенство kGk < 1;
(d) неравенство ρ(G) < 1.
4. Матрица симметризации – это
(a) симметричная матрица;
(b) единичная матрица;
(c) такая матрица W, что W(E−G)W−1 – положительно определенная и симметричная матрица;
(d) такая матрица W, что W(G−E)W−1 – положительно определенная и симметричная матрица.
5. При ω = 1 метод SOR переходит в метод (выберите один из ответов)
(a) Якоби;
(b) SSOR;
(c) простой итерации; (d) Гаусса–Зейделя.
6. Параметр релаксации ω лежит в диапазоне (выберите один из ответов)
(a) [0,1];
(b) [0,2]; (c) (0,2);
(d) [−1,1].
4 Методы подпространств Крылова
4.1 Инвариантные подпространства
Для понижения размерности исходной задачи воспользуемся понятием инвариантного подпространства.
Определение 10. Подпространство L инвариантно относительно матрицы A, если для любого вектора x из L вектор Ax также принадлежит L.
Примером инвариантного подпространства, является подпространство, образованное линейными комбинациями нескольких собственных векторов A.
Предположим, что нам известен базис L, образованный векторами q1, q2, ..., qm, m ≤ n. Образуем из этих векторов матрицу Q = [q1,q2,...,qm] размерности n×m. Вычислим AQ. Это матрица также размерности n×m, причем ее столбцы есть линейные комбинации q1, q2, ... qm. Другими словами, столбцы AQ принадлежат инвариантному подпространству L. Указанные столбцы удобно записать в виде
QC, где C – квадратная матрица размерности m×m. Действительно,
AQ = A[q1,q2,...qm].
Вектор Aqi ∈ L, следовательно, Aqi представим в виде линейной комбинации q1, q2, ... qm:
Aqi = ci1q1 + ci2q2 + ... + cimqm, i = 1,...,m.
Таким образом, выполняется равенство
AQ = QC. (8)
Матрица C называется сужением A на подпространстве L. Более наглядно (8) можно представить в виде
n m m m
| A | Q | = | Q |
C m
n
Рассмотрим случай, когда q1, q2, ..., qm – ортонормированы. Тогда
QTQ = Em,
где Em – единичная матрица размерности m×m. Из (8) вытекает, что
C = QTAQ.
Рассмотрим решение СЛАУ
Cy = d,
где d ∈ Rm. Умножая это уравнение на Q слева получим, что
QCy = AQy = Qd.
То есть вектор Qy является решением исходной задачи, если b = Qd. Таким образом, знание инвариантного подпространства позволяет свести решение СЛАУ для матрицы A к двум СЛАУ меньшей размерности, которые могут быть решены независимо друг от друга. Проблема состоит в том, что априори инвариантные подпространства матрицы A неизвестны. Вместо инвариантных подпространств можно использовать “почти” инвариантные подпространства, например, подпространства Крылова.
4.2 Степенная последовательность и подпространства Крылова
Определение 11. Подпространством Крылова Km(b) называется подпространство, образованное всеми линейными комбинациями векторов степенной последовательности
b, Ab, A2b, ..., Am−1b,
то есть линейная оболочка, натянутая на эти векторы
Km(b) = span(b, Ab, A2b, ..., Am−1b).
Рассмотрим свойства степенной последовательности
b, Ab, A2b, A3b,...Akb,...,
где b – некоторый произвольный ненулевой вектор.
Рассмотрим случай, когда A – симметричная матрица. Следовательно, ее собственные векторы ek образуют базис в Rn. Соответствующие собственные числа A обозначим через λk:
Aek = λkek.
Для определенности примем, что λk упорядочены по убыванию:
|λ1| ≥ |λ2| ≥ ... ≥ |λn|.
Произвольный вектор b можно представить в виде разложения по ek:
b = b1e1 + b2e2 + ... + bnen.
Имеют место формулы:
b = b1e1 + b2e2 + ... + bnen,
Ab = λ1b1e1 + λ2b2e2 + ... + λnbnen, A
,...
A 
,
...
Сделаем дополнительное предположение. Пусть |λ1| > |λ2|. Другими словами, λ1 – максимальное собственное число по модулю: λ1 = λmax. Тогда Akb можно записать следующим образом:
A
. (9)Поскольку все
, то если b1 6= 0, то все слагаемые в скобках в уравнении (9) кроме первого будут убывать при k → ∞: