Метод решения — Метод конечных элементов

Для разреженных матриц большого размера прямые методы, строящие полное разложение матрицы, как правило, невыгодны: в процессе разложения в позициях исходных нулей возникают новые ненулевые элементы — так называемое заполнение. В результате теряется главное преимущество разреженной матрицы — малый объём памяти и малое число арифметических операций.

Мы будем решать систему (3.1) итерационным предобусловленным методом сопряжённых градиентов (PCG, preconditioned conjugate gradient). Метод применим к симметричным положительно определённым матрицам — именно такие возникают в задачах МКЭ с эллиптическими операторами и в неявных схемах теплопроводности. Распишем алгоритм по шагам.

Пусть $x_0 = 0$ — начальное приближение. Начальный остаток примет вид

r_0 = b - A \cdot x_0.

(3.2)

Начальное направление поиска и вектор предобуславливания имеют вид

P \cdot z_0 = r_0, \qquad p_0 = z_0,

(3.3)

где $P$ — матрица предобуславливателя: она приближает $A$ , но системы с ней решаются существенно дешевле. Далее на каждой итерации $k = 0, 1, 2, \ldots$ вычисляем

\alpha_k = \frac{r_k^T \cdot z_k}{p_k^T \cdot A \cdot p_k},

(3.4)

x_{k+1} = x_k + \alpha_k \cdot p_k,

(3.5)

r_{k+1} = r_k - \alpha_k \cdot A \cdot p_k,

(3.6)

P \cdot z_{k+1} = r_{k+1},

(3.7)

\beta_k = \frac{r_{k+1}^T \cdot z_{k+1}}{r_k^T \cdot z_k},

(3.8)

p_{k+1} = z_{k+1} + \beta_k \cdot p_k.

(3.9)

Итерации продолжаются, пока квадрат нормы остатка не опустится ниже заданного порога

r_{k+1}^T \cdot r_{k+1} < \varepsilon.

(3.10)

Основная вычислительная стоимость каждой итерации — одно умножение разреженной матрицы на вектор $A \cdot p_k$ . Именно поэтому перед началом итераций матрица конвертируется из COO в CSR: в этом формате умножение строки на вектор проходит только по ненулевым элементам.

Схема одной итерации предобусловленного метода сопряжённых градиентов — **Рис. 3.2.** Одна итерация PCG: шаг $A \cdot p_k$ — самый дорогостоящий.

Далее поговорим о предобуславливателях.

Структуры хранения Предобуславливатели