Неполное разложение Холецкого

Неполное разложение Холецкого.

Вернемся к пробреме построения предобуславливателя для итерационных методов. Скорость сходимости итераций для задачи  зависит от спектральных свойств матрицы . Идея предобусавливания состоит в замене исходного уравнения на эквивалентное, например

у которого то же решение , но сперктральные свойства матрицы коэффициентов  лучше. При конструировании предобуславливателя мы сталкиваемся с противоречивой проблемой: матрица  должна аппроксимировать  и в то же время быть легко обратимой.

Левое и правое предобуславливание.

Обсуждаемая трансформация  редко используется на практике, потому что большинство методов (например, CG) требуют, чтобы матрица метода была симметричной. Но даже если  и  симметричны, их произведение не будет таковым. Практичный подход состоит в факторизации  и  записи уравнения в виде

                                                                                  (1)

Матрицы  и  - это левый и правый предобуславливатель. Для задачи (1) из-за симметрии можно использовать обычный CG-метод без предобуславливания. Только два дополнительных действия надо сделать:

1) Перед итерациями надо перевычислить невязку

Рекомендуемые материалы

2) После итераций перевычислить решение 

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

1. Берем конкретный итерационный предобусловленный метод и заменяем  на .

2. Заменяем все входждения  на .

3. Перед итерациями перевычисляем начальную невязку .

4. Окончательное решение получаем по формуле

Предобуславливатель Якоби.

Оно определяется простой формулой

                                                                                                   (2)

Требует мало места (памяти), легко реализуется. Среди всех диагональных он самый лучший в смысле уменьшенния числа обусловленности.

Предобуславливатель SSOR.

Если разложить симметричную матрицу , то матрица итераций симметричного метода последовательной верхней релаксации выражается как

                                                      (3)

Здесь  - параметр релаксации, такой же как в методе .

Предобуславливатель неполного разложения ILU.

Разложение матрицы  на треугольные множители называем неполным, если в процессе факторизации игнорируется часть заполнения. В частности, факторизация ILU(0) вообще игнорирует все заполнение, т.е. портрет суммы множителей совпадает с портретом исходной матрицы.

Пусть требуется решить задачу

                                                   ,                                         (4)

и мы используем итерационный процесс

                                                  .                                        (5)

На каждом шаге метода (5) необходимо решить задчу вида

                                                      (6)

Очевидно, что при  получаем точное решение  за одну итерацию, надо только уметь обращать исходную матрицу. В общем случае ускорение сходимости достигается за счет приближения спектральных свойств предобуславливателя  и исходной матрицы , при этом стараются строить  так, чтобы было легко находить  в процессе (6), вычисляя .

Неполное разложение записывают в форме

                                              ,                                   (7)

где

                                              (8)

суть строго нижняя и верхняя треугольные подматрицы в разложении

Вместе с этой лекцией читают "Часть 3".

                                                      (9)

Таким образом, в предобуславливателе (7) единственное, что требуется определить, ‑ это диагональ . Условия, на которых будут построены конкретные , в той или иной степени отражают требование .

В этом случае решение задачи  строится так:

                              .