Блочные Крыловские методы

Общий проекционный метод для решения линейной системы

Ax=b, (1)

Извлекает приближенное решение Xm из линейного многообразия размерности m с помощью условия Петрова-Галеркина

, (2)

где – еще одно подпространство размерности m. Здесь есть произвольное начальное приближение к решению. Метод крыловского подпространства – это метод, в котором в качестве берется крыловское подпространство

(3)

Где . Там, где это не вызовет недоразумений, будем писать вместо . Разные методы крыловских подпространств соответствуют различным выборам подпространства и разным способам предобуславливания системы.

Хотя все крыловские методы находят полиноминальные приближения одного и того же типа, выбор подпространства оказывает серьезное воздействие на итерационный метод. Два популярных выбора этого подпространства приводят к самым разным методам. Для методов обеих групп имеются блочные обобщения называемые блочными методам крыловского подпространства. Эти методы как раз-таки были рассмотрены в ходе работы.

.

2.1. GMRES.

Рассмотрим решение СЛАУ сильной разряжености.

Ах = b, (4)

где A∊ и x, b∊ . Итерационные методы часто выбираются для решения таких СЛАУ, и, когда A несимметричен, обычно выбирается алгоритм GMRES. GMRES (от the generalized minimal residual method) - это метод Крыловского подпространства, поэтому он находит приближенное решение ∈ + ,, где
обозначает m-мерное подпространство Крылова, – начальная невязка, - начальное приближение, а ≡ . Алгоритм GMRES требует чтобы минимальная невязка системы, было минимумом для всех z ∈ или, что эквивалентно, чтобы невязка после m итераций удовлетворял условию .

На практике ресурсы, требуемые стандартному алгоритму GMRES, могут быть непрактичными, поскольку требования к памяти и вычислительным ресурсам увеличиваются с каждой итерацией. В этом случае обычно используется перезапущенная версия. В перезапускаемом GMRES (GMRES (m)) параметр перезапуска m обозначает фиксированный максимальный размер для подпространства Крылова. Поэтому, если сходимости не произошло после m итераций, алгоритм перезапускается с = . Мы называем группу m итераций между последовательными перезапусками циклом. Число перезапуска мы обозначаем нижним индексом: - невязка после i-циклов или m×i полных итераций. После i циклов невязка представляет собой многочлен в A, умноженный на невязку от предыдущего цикла: = , где )- степень m многчлена невязки.

2.2. Блочный алгоритм GMRES. Часто возникают случаи, в которых необходимо решить несколько линейных систем с одинаковой матрицей A, но различными правыми частями (например, см. [55, 8]). Эти линейные системы могут быть записаны как СЛАУ вида:

AX = B, (5)

где A∊ , X, B∊ , а столбцы B - разные правые части. О'Лири впервые представил блочные итерационные методы решения СЛАУ для блочных СЛАУ с симметричной матрицей A с алгоритмом BCG(Block Conjugate Gradient) и других связанных алгоритмов. Для несимметричной матрицы A блочная версия алгоритма GMRES (BGMRES) была впервые описана в [57]. Подробные описания также можно найти в [53], [54] и [49].

BGMRES по существу идентичен стандартному GMRES, за исключением того, что операции выполняются с несколькими, а не с одиночными векторами. Для справки: один цикл перезапуска (i) BGMRES (m) приведен на Алгоритма 1. Итерация Арнольди теперь является процессом ортогонализации блока, создавая основу для блочного метода Крыловского подпространства Ks m (A, Ri) = Span {Ri, ARi,..., Am − 1Ri}, где s обозначает размер блока, а Ri задается в строке 1 на Алгоритме 1. Поскольку линейная система блока (2) имеет s правых частей, подпространство решения теперь имеет размерность Миз. Как и в случае стандартного алгоритма GMRES, на практике обычно используется перезапущенная версия алгоритма BGMRES (BGMRES (m)).

Алгоритм 1. BGMRES (м) для цикла перезапуска i

A.H. BAKER, J.M. DENNIS, AND E.R. JESSUP

1.

2.

3. for j = 1: m

4. Uj = AVj

5. for i = 1: j

6. Hi,j = Uj

7. Uj = Uj – ViHi,j

8. end

9. Uj = Vj+1Hj+1,j

10. end

11. Wm = [V1,V2,...,Vm], Hm =

12. find Ym s.t is minimized

13. Xi+1 = Xi +

В дополнение к возможности решения систем с множеством правых частей, BGMRES является эффективным с точки зрения снижения затрат памяти. Решая блочную СЛАУ (в отличие от решения s систем по отдельности), теперь матрица A работает с мультивектором вместо одного вектора на каждой итерации. Поэтому к матрице A обращаются из памяти реже, чем если бы каждая система была решена индивидуально.

Варианты метода Block GMRES были разработаны как для множественных, так и для одиночных систем с правой частью. Для нескольких правосторонних систем гибридный блочный метод GMRES представлен в [53]. Этот блочный метод аналогичен гибридному методу GMRES для систем с одной правой частью, описанному в [41], и часто решает блочную систему быстрее, чем решение систем с одной правой частью, частично из-за меньшего обращения к памяти. Кроме того, в [27] описывается расширение блочного GMRES Моргана с помощью шаблона собственных векторов [39] для нескольких правосторонних систем, а сам Морган разработал расширение блока GMRES-DR (GMRES с принудительным перезапуском) [40]. 38]. Такие методы, как методы Моргана, которые дополняют пространство аппроксимации оценками собственных векторов, особенно полезны для умеренно ненормальных матриц с несколькими конкретными собственными значениями (обычно малыми по величине), которые препятствуют сходимости.

2.3. Реализация. Реализация B-LGMRES (m, k) аналогична реализации BGMRES, приведенной в Алгоритме 1. Основное отличие состоит в том, что B-LGMRES находит приближение при каждом цикле решения одиночных систем с правой частью (1), в отличие от блочной системы (2). Цикл расчета (i) B-LGMRES (m, k) приведен в Алгоритме 2.

Хотя мы говорим о ошибках приближения , j = (i − k +1): i как о дополнительных правых векторах, мы решаем только одну правую систему и нам не нужно сохранять приближенные решения блока .

Алгоритм 2. B-LGMRES (m, k) для цикла перезапуска i.

1. = b − A , β =

2. = [ri,zi,...,zi−k+1]

3. =

4. for j = 1: m

5. = A

6. for i = 1: j

7. =

8. = −

9. end

10. =

11. end

12. Wm = [V1,V2,...,Vm], Hm =

13. find Ym s.t is minimized

14. =

15. = +

Вместо этого мы добавляем k последних ошибки приближения к начальной невязке, чтобы сформировать блочную невязку , как видно в строке 2 Алгоритма 2. Мы нормализуем ошибоку приближения ( / ), чтобы каждый столбец исходной блочной невязки был единичной длины. В течение каждого цикла решения генерируется ортогональный базис для блочного Крыловского пространства . Oртогональные блочные матрицы размера n × s, Vj образуют ортогональную матрицу размерности n × m • s, где Wm = [V1, V2,..., Vm]. представляет собой матрицу Гессенберга размера (m +1)s ×m•s с s субдиагоналями, и имеет место следующее стандартное соотношение:

, (6)

Поскольку B-LGMRES находит минимальную невязку приближенного решения для Ax = b, шаг решения наименьших квадратов (строка 13) отличается от шага стандартного BGMRES (который минимизирует блочную невязку). B-LGMRES находит таким образом, что = , где - размерности m • s × 1. В результате треугольную матрицу R из разложения QR в строке 3 не нужно сохранять, так как наименее для решения квадратов требуется только β = . Как и в случае с BGMRES, B-LGMRES все еще требует применения поворотов на каждой итерации для преобразования в верхнюю треугольную матрицу (подробнее см. [49]). Однако теперь на каждом шаге к правой части задачи наименьших квадратов (βe1) необходимо применять только s поворотов.