Неполное разложение Холецкого
Неполное разложение Холецкого.
Вернемся к пробреме построения предобуславливателя для итерационных методов. Скорость сходимости итераций для задачи зависит от спектральных свойств матрицы . Идея предобусавливания состоит в замене исходного уравнения на эквивалентное, например
у которого то же решение , но сперктральные свойства матрицы коэффициентов лучше. При конструировании предобуславливателя мы сталкиваемся с противоречивой проблемой: матрица должна аппроксимировать и в то же время быть легко обратимой.
Левое и правое предобуславливание.
Обсуждаемая трансформация редко используется на практике, потому что большинство методов (например, 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) единственное, что требуется определить, ‑ это диагональ . Условия, на которых будут построены конкретные , в той или иной степени отражают требование .
В этом случае решение задачи строится так:
.