Предобуславливатели — Метод конечных элементов

Скорость сходимости метода сопряжённых градиентов определяется числом обусловленности матрицы $A$ . Чем оно больше, тем медленнее метод сходится — для получения приемлемой точности требуется много итераций. Предобуславливатель $P$ призван улучшить это число, заменяя исходную систему эквивалентной с матрицей $P^{-1} \cdot A$ , собственные значения которой должны сгруппироваться в узкой окрестности единицы.

На практике явно строить $P^{-1} \cdot A$ не нужно: на каждой итерации достаточно уметь решать вспомогательную задачу

P \cdot z_k = r_k,

(3.11)

используя $z_k$ вместо исходного остатка $r_k$ — см. формулы (3.7)–(3.8). Рассмотрим три варианта.

1. Без предобуславливания ( $P = I$ ). В этом случае $z_k = r_k$ , и метод совпадает с классическим методом сопряжённых градиентов. Вариант полезен для отладки, но для плохо обусловленных систем сходится медленно.

2. Предобуславливатель Якоби. В качестве $P$ берётся диагональная часть матрицы $A$

P = \operatorname{diag}(A) = \operatorname{diag}(a_{11}, a_{22}, \ldots, a_{nn}).

(3.12)

Применение сводится к поэлементному делению

z_{k,\,i} = \frac{r_{k,\,i}}{a_{ii}}.

(3.13)

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

3. Неполное разложение Холецкого (IC). Для симметричной положительно определённой матрицы строится приближённое разложение

A \approx L \cdot L^T,

(3.14)

где $L$ — нижнетреугольная матрица. В отличие от полного разложения Холецкого, элементы заполнения в позициях исходных нулей отбрасываются — структура ненулевых элементов $L$ совпадает со структурой нижнего треугольника $A$ . После построения $L$ применение предобуславливателя состоит из двух треугольных подстановок

L \cdot y = r_k,

(3.15)

L^T \cdot z_k = y.

(3.16)

Три варианта предобуславливателя для метода сопряжённых градиентов — **Рис. 3.3.** Предобуславливатели: единичный ( $P = I$ ), Якоби ( $P = \operatorname{diag}(A)$ ) и неполный Холецкий ( $A \approx L \cdot L^T$ ).

В задачах МКЭ неполное разложение Холецкого, как правило, даёт наилучший компромисс: оно дороже диагонального предобуславливателя (построение $L$ и два треугольных прохода на итерацию), однако заметно сокращает число итераций. Для несимметричных или неопределённых систем, выходящих за рамки стандартных задач теплопроводности, следует обратиться к методам GMRES или BiCGSTAB с соответствующими предобуславливателями.

На этом с решением разреженных систем закончим — дальше поговорим о разбиении геометрии на симплексы.

Метод решения Сегментация