Участник:Сорокин Александр/Метод сопряженных градиентов (Решение СЛАУ)

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Метод сопряженных градиентов представляет собой итерационный метод для численного решения системы уравнений с симметричной и положительно определенной матрицей, является итерационным методом Крыловского типа. Основная идея метода заключается в том, чтобы минимизировать на подпространствах Крылова А-норму ошибки.

1.2 Математическое описание алгоритма

Пусть необходимо найти решение системы уравнений [math] Ax = b [/math], где [math] A^* = A \gt 0 [/math].
Рассмотрим функционал [math] \phi (x) = \frac{1}{2}x^T A x - x^T b [/math].
Если [math] x^* [/math] это решение задачи минимизации данного функционала, то в этой точке градиент [math] \bigtriangledown \phi (x^*) = Ax^* - b [/math] должен быть равен нулю. Таким образом, минимизируя функционал [math] \phi (x) [/math] мы получим решение исходной системы.

1.2.1 Метод градиентного спуска

Как известно, градиент [math] \bigtriangledown \phi (x) [/math] является направлением наибольшего роста функции.
Метод градиентного спуска основан на стратегии движения в строну, противоположную возрастанию функционала. Оптимальным направлением в этом случае будет антиградиент [math] -\bigtriangledown \phi (x) [/math] и двигаться по нему нужно будет до тех пор, пока функционал убывает.
Таким образом можно построить следующий итерационный метод:

1. Выберем произвольное начальное приближение [math] x_0 [/math].
2. [math] x_{i+1} = x_{i} + \alpha_i p_i [/math], где [math] p_i [/math] — направление движения, а [math] \alpha_i [/math] — величина шага.
   

Из рассуждений выше понятно что оптимальным является направление [math] p_i = - \bigtriangledown \phi (x_{i}) [/math]. Величина [math] \alpha_i [/math] выбирается из соображений [math] \alpha_i = \underset{\alpha}{\operatorname{argmin}} \phi (x_i + \alpha p_i) [/math]. Аналитическую формулу [math] \alpha_i = \frac{\bigtriangledown\phi (x_i)^T \bigtriangledown\phi (x_i)}{\bigtriangledown\phi (x_i)^T A \bigtriangledown\phi (x_i)} = \frac{r_i ^T r_i}{r_i ^T A r_i} [/math] можно получить из [math] \frac{d}{d\alpha} \phi (x_i + \alpha p_i) = 0 [/math].

1.2.2 Метод сопряженных направлений

Метод градиентного спуска обычно сходится очень долго. Можно построить алгоритм который сходится не больше чем за n шагов.
Предположим что у нас есть n линейно-независимых векторов [math] p_1, ... p_n [/math] таких что [math] (p_i, p_j)_A = (Ap_i, p_j) = 0, i \neq j [/math].
Так как имеется n таких векторов, то они образуют базис пространства и любой вектор можно выразить через них, в том числе [math] x^* - x_0 = \sum \alpha_i p_i [/math]