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