Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов
Свойства и структура алгоритма
Общее описание алгоритма
Метод сопряжённых градиентов — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений (СЛАУ) вида [math]\displaystyle{ Ax = b }[/math], где матрица [math]\displaystyle{ A }[/math] является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
Математическое описание алгоритма
Необходимо найти решение СЛАУ [math]\displaystyle{ Ax = b }[/math], где матрица [math]\displaystyle{ A }[/math] является положительно определённой и симметричной ([math]\displaystyle{ A^T = A \gt 0 }[/math]). Данная задача эквивалентна минимизации следующего функционала [math]\displaystyle{ f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle }[/math].
Классически данная задача решается с помощью итерационного метода спуска: [math]\displaystyle{ x_{k+1} = x_{k} + α_{k}d_{k} }[/math].
На каждой итерации выбирается направление спуска [math]\displaystyle{ d_{k} }[/math] и шаг [math]\displaystyle{ α_{k} }[/math], где [math]\displaystyle{ d_{k} }[/math] – антиградиент [math]\displaystyle{ f(x) }[/math], а [math]\displaystyle{ \alpha_k = \arg\min_{\alpha \ge 0} f(x_k + \alpha_k d_k) = -\frac{\langle g_k, d_k \rangle}{\langle A d_k, d_k \rangle}, \quad g_k := A x_k - b. }[/math]
Сопряжённые направления
Главная особенность метода сопряжённых градиентов заключается в выборе направлений [math]\displaystyle{ d_{k} }[/math], которые являются A-сопряжёнными, то есть удовлетворяют условию: [math]\displaystyle{ \langle A d_{i}, d_{j} \rangle = 0 }[/math] для всех [math]\displaystyle{ i ≠ j }[/math].
Общая схема метода сопряжённых градиентов
1. Пусть даны [math]\displaystyle{ d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 }[/math] для [math]\displaystyle{ i ≠ j }[/math]
2. [math]\displaystyle{ d_{k+1} = -g_{k+1} + β_{k}d_{k} }[/math], где [math]\displaystyle{ g_{k+1} = A x_k - b }[/math]
3. [math]\displaystyle{ β_{k} }[/math] ищем исходя из условий на сопряжённость направлений: [math]\displaystyle{ 0 = \langle A d_k, d_{k+1} \rangle= -\,\langle A d_k, g_{k+1} \rangle + \beta_k \langle A d_k, d_k \rangle }[/math]
Отсюда [math]\displaystyle{ β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle} }[/math]
| Инициализация:
[math]\displaystyle{ g_0 = A x_0 - b }[/math] [math]\displaystyle{ d_0 = -g_0 }[/math] [math]\displaystyle{ k = 0 }[/math]
|
Оптимизация метода сопряжённых градиентов
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:
[math]\displaystyle{ 1. }[/math] Метод сопряжённых градиентов построен таким образом, что [math]\displaystyle{ \langle g_{i}, g_{k+1} \rangle = 0 }[/math] и [math]\displaystyle{ \langle g_{k+1}, d_{i} \rangle }[/math] для [math]\displaystyle{ i \lt = k }[/math] (это можно проверить по индукции и использовать свойство сопряжённости направлений)
[math]\displaystyle{ 2. }[/math] [math]\displaystyle{ g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} }[/math]
Отсюда [math]\displaystyle{ Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k}) }[/math]
[math]\displaystyle{
3. }[/math] Значит
[math]\displaystyle{ \beta_k = \dfrac{\langle g_{k+1} - g_k,\; g_{k+1} \rangle}{\langle g_{k+1} - g_k,\; d_k \rangle}= \dfrac{\| g_{k+1} \|^2}{-\langle
g_k,\; d_k \rangle} }[/math]
[math]\displaystyle{ = \dfrac{\| g_{k+1} \|^2}{-\langle -g_k + \beta_{k-1} d_{k-1},\; g_k \rangle}= \dfrac{\| g_{k+1} \|^2}{\| g_k \|^2} }[/math]
[math]\displaystyle{
4. }[/math] Аналогично [math]\displaystyle{
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
}[/math]