Участница: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{ \|g_k\| \gt \varepsilon \|b\| }[/math] выполнять: [math]\displaystyle{ \quad 1.\; }[/math] Вычисляем шаг [math]\displaystyle{ \alpha_k = -\dfrac{\langle g_k, d_k \rangle}{\langle A d_k, d_k \rangle} }[/math] [math]\displaystyle{ \quad 2.\; }[/math] Обновляем приближение решения [math]\displaystyle{ x_{k+1} = x_k + \alpha_k d_k }[/math] [math]\displaystyle{ \quad 3.\; }[/math] Обновляем невязку [math]\displaystyle{ g_{k+1} = A x_{k+1} - b }[/math] [math]\displaystyle{ \quad 4.\; }[/math] Вычисляем коэффициент [math]\displaystyle{ \beta_k = \dfrac{\langle g_{k+1}, A d_k \rangle}{\langle A d_k, d_k \rangle} }[/math] [math]\displaystyle{ \quad 5.\; }[/math] Обновляем направление [math]\displaystyle{ d_{k+1} = -g_{k+1} + \beta_k d_k }[/math] [math]\displaystyle{ \quad 6.\; }[/math] Увеличиваем счётчик [math]\displaystyle{ k = k + 1 }[/math] Результат: [math]\displaystyle{ x_k }[/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]

Общая схема эффективного метода сопряжённых градиентов

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

Общая схема эффективного метода сопряжённых градиентов

Инициализация: [math]\displaystyle{ g_0 = A x_0 - b }[/math] [math]\displaystyle{ d_0 = -g_0 }[/math] [math]\displaystyle{ k = 0 }[/math] Цикл: Пока [math]\displaystyle{ \|g_k\| \gt \varepsilon \|b\| }[/math] выполнять: [math]\displaystyle{ \quad 1.\; }[/math] Вычисляем шаг [math]\displaystyle{ \alpha_k = -\dfrac{\langle g_k, d_k \rangle}{\langle A d_k, d_k \rangle} }[/math] [math]\displaystyle{ \quad 2.\; }[/math] Обновляем приближение решения [math]\displaystyle{ x_{k+1} = x_k + \alpha_k d_k }[/math] [math]\displaystyle{ \quad 3.\; }[/math] Обновляем невязку [math]\displaystyle{ g_{k+1} = A x_{k+1} - b }[/math] [math]\displaystyle{ \quad 4.\; }[/math] Вычисляем коэффициент [math]\displaystyle{ \beta_k = \dfrac{\langle g_{k+1}, A d_k \rangle}{\langle A d_k, d_k \rangle} }[/math] [math]\displaystyle{ \quad 5.\; }[/math] Обновляем направление [math]\displaystyle{ d_{k+1} = -g_{k+1} + \beta_k d_k }[/math] [math]\displaystyle{ \quad 6.\; }[/math] Увеличиваем счётчик [math]\displaystyle{ k = k + 1 }[/math] Результат: [math]\displaystyle{ x_k }[/math].