Участница: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]

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

1. [math]\displaystyle{ g_k = A x_k - b }[/math] 2. [math]\displaystyle{ \alpha_k = -\dfrac{\langle g_k, d_k \rangle}{\langle A d_k, d_k \rangle} }[/math] 3. [math]\displaystyle{ x_{k+1} = x_k + \alpha_k d_k }[/math] 4. [math]\displaystyle{ g_{k+1} = A x_{k+1} - b }[/math] 5. [math]\displaystyle{ \beta_k = \dfrac{\langle g_{k+1}, A d_k \rangle}{\langle A d_k, d_k \rangle} }[/math] 6. [math]\displaystyle{ d_{k+1} = -g_{k+1} + \beta_k d_k }[/math]

Метод сопряжённых градиентов (эффективная версия)

Предпосылки	\(A\in S^{n}_{++}\) (симметричная положительно определённая), задан \(b\), задано начальное \(x_0\), допуск \(\varepsilon>0\).
Инициализация	Невязка: \(r_0 = b - A x_0\). Направление: \(d_0 = r_0\). Счётчик: \(k=0\).
Цикл	r_k\|/\|b\| > \varepsilon\ \) делать: [math]\displaystyle{ q = A d_k }[/math]   (умножение матрицы на вектор) [math]\displaystyle{ \alpha_k = \dfrac{\langle r_k, r_k\rangle}{\langle d_k, q\rangle} }[/math] [math]\displaystyle{ x_{k+1} = x_k + \alpha_k d_k }[/math] [math]\displaystyle{ r_{k+1} = r_k - \alpha_k q }[/math] [math]\displaystyle{ \beta_k = \dfrac{\langle r_{k+1}, r_{k+1}\rangle}{\langle r_k, r_k\rangle} }[/math] [math]\displaystyle{ d_{k+1} = r_{k+1} + \beta_k d_k }[/math] [math]\displaystyle{ k \leftarrow k+1 }[/math]
Выход	Возвратить \(x_k\).
Примечание	\(r_k\) — невязка, \(d_k\) — направление поиска, \(\langle\ Вычислительное ядро алгоритма