Алговики - Вклад [ru]

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T20:15:16Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

== Ссылки ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2" для задач размерности <math> N \in \{2000, 5000\}.</math>

Число процессов изменялось в диапазоне <math>P \in \{ 1, 2, 4, 8, 16, 32, 48, 56\}</math>.

На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.
По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 эффективность масштабирования постепенно снижается:ускорение остаётся заметным, но уже не таким выраженным. Для большого числа процессов (начиная с <math>P = 48</math> в случае <math>N=5000</math>) время выполнения перестаёт уменьшаться и даже слегка возрастает. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.

Реализация демонстрирует хорошую масштабируемость вплоть до десятков процессов, а наблюдаемые ограничения соответствуют теоретическим особенностям параллельного метода сопряжённых градиентов.

[[Файл:Cg time surface new.png|thumb|center|800px|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

На рис.2 показана [[Глоссарий#Эффективность распараллеливания|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для <math>N=2000</math> эффективность падает относительно медленно, тогда как для <math>N=5000</math> спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях
P в сравнении с задачей меньшей размерности.

[[Файл:Cg eff surface new.png|thumb|center|700px|Рис.2 Эффективность распараллеливания МСГ E(N,P) от числа процессов P и размера матрицы N.]]

== Динамические характеристики и эффективность реализации алгоритма ==
== Результаты прогонов ==

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T20:09:46Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

== Ссылки ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2" для задач размерности <math> N \in \{2000, 5000\}.</math>

Число процессов изменялось в диапазоне <math>P \in \{ 1, 2, 4, 8, 16, 32, 48, 56\}</math>.

На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.
По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 эффективность масштабирования постепенно снижается:ускорение остаётся заметным, но уже не таким выраженным. Для большого числа процессов (начиная с <math>P = 48</math> в случае <math>N=5000</math>) время выполнения перестаёт уменьшаться и даже слегка возрастает. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.

Реализация демонстрирует хорошую масштабируемость вплоть до десятков процессов, а наблюдаемые ограничения соответствуют теоретическим особенностям параллельного метода сопряжённых градиентов.

[[Файл:Cg time surface new.png|700px|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

На рис.2 показана [[Глоссарий#Эффективность распараллеливания|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для <math>N=2000</math> эффективность падает относительно медленно, тогда как для <math>N=5000</math> спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях
P в сравнении с задачей меньшей размерности.

[[Файл:Cg eff surface new.png|700px|Рис.2 Эффективность МСГ E(N,P) от числа процессов P и размера матрицы N.]]

== Динамические характеристики и эффективность реализации алгоритма ==
== Результаты прогонов ==

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T20:01:35Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

== Ссылки ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2" для задач размерности <math> N \in \{2000, 5000\}.</math>

Число процессов изменялось в диапазоне <math>P \in \{ 1, 2, 4, 8, 16, 32, 48, 56\}</math>.

На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.
По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 время уменьшается не так эффективно, а начиная с <math>P = 48</math> (в случае <math>N=5000</math>) время работы алгоритма начинает возрастать. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.

[[Файл:Cg time surface new.png|700px|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

На рис.2 показана [[Глоссарий#Эффективность распараллеливания|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для <math>N=2000</math> эффективность падает относительно медленно, тогда как для <math>N=5000</math> спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях
P в сравнении с задачей меньшей размерности.

[[Файл:Cg eff surface new.png|700px|Рис.2 Эффективность МСГ E(N,P) от числа процессов P и размера матрицы N.]]

== Динамические характеристики и эффективность реализации алгоритма ==
== Результаты прогонов ==

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T20:00:32Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

== Ссылки ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2" для задач размерности <math> N \in \{2000, 5000\}.</math>

Число процессов изменялось в диапазоне <math>P \in \{ 1, 2, 4, 8, 16, 32, 48, 56\}</math>.

На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.
По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 время уменьшается не так эффективно, а начиная с <math>P = 48</math> (в случае <math>N=5000</math>) время работы алгоритма начинает возрастать. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.

[[Файл:Cg time surface new.png|700px|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

На рис.2 показана [[Глоссарий#Эффективность распараллеливания|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для <math>N=2000</math> эффективность падает относительно медленно, тогда как для <math>N=5000</math> спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях
P в сравнении с задачей меньшего размерности.

[[Файл:Cg eff surface new.png|700px|Рис.2 Эффективность МСГ E(N,P) от числа процессов P и размера матрицы N.]]

== Динамические характеристики и эффективность реализации алгоритма ==
== Результаты прогонов ==

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T19:45:48Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T16:50:29Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T16:50:05Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T16:48:26Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T16:06:33Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T15:53:02Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T15:39:42Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Файл:Cg time surface new.png

2025-12-08T15:33:27Z

Larisayaryzheva:

Рис. 1. Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T15:26:41Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T15:25:07Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T15:24:38Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T14:20:29Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T14:18:37Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T14:15:38Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T14:11:13Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Файл:Cg eff surface new.png

2025-12-08T14:10:18Z

Larisayaryzheva:

Рис. 2. График зависимости параллельной эффективности алгоритма E(N,P) от числа процессов P и размеров матрицы N.

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T13:45:12Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T13:44:19Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T13:42:02Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T13:28:02Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T13:21:25Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

== Ссылки ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2".
[[Файл:Cg time surface.png]]

== Динамические характеристики и эффективность реализации алгоритма ==
== Результаты прогонов ==

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T13:20:53Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

== Ссылки ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2".
[[Файл:Cg time surface.png]обрамить]

== Динамические характеристики и эффективность реализации алгоритма ==
== Результаты прогонов ==

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T10:34:08Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

== Ссылки ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2".
[[Файл:Cg time surface.png]{: width="500px" height="300px"}]

== Динамические характеристики и эффективность реализации алгоритма ==
== Результаты прогонов ==

Файл:Cg time surface.png

2025-12-08T10:26:41Z

Larisayaryzheva:

Параллельная реализация стабилизированного метода сопряжённых градиентов. Изменение производительности в зависимости от числа процессов и размера матрицы.

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T10:08:09Z

Larisayaryzheva: /* Масштабируемость алгоритма и его реализации */

== Ссылки ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2".

== Динамические характеристики и эффективность реализации алгоритма ==
== Результаты прогонов ==

Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов

2025-12-08T09:50:08Z

Larisayaryzheva: Новая страница: «== Ссылки == == Локальность данных и вычислений == == Масштабируемость алгоритма и его реализации == == Динамические характеристики и эффективность реализации алгоритма == == Результаты прогонов ==»

== Ссылки ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Результаты прогонов ==

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-12-06T19:55:15Z

Larisayaryzheva: /* Программная реализация алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Метод сопряжённых градиентов''' — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений ('''СЛАУ''') вида <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
=== Математическое описание алгоритма ===

Необходимо найти решение '''СЛАУ''' <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной (<math> A^T = A > 0 </math>).
Данная задача эквивалентна минимизации следующего функционала <math> f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle </math>.

Классически данная задача решается с помощью итерационного метода спуска: <math> x_{k+1} = x_{k} + α_{k}d_{k} </math>.

На каждой итерации выбирается направление спуска <math> d_{k} </math> и шаг <math>α_{k}</math>, где <math> d_{k} </math> – антиградиент <math> f(x) </math>, а <math> \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> d_{k} </math>, которые являются '''A-сопряжёнными''', то есть удовлетворяют условию: <math> \langle A d_{i}, d_{j} \rangle = 0 </math> для всех <math> i ≠ j </math>.

==== Общая схема метода сопряжённых градиентов ====
1. Пусть даны <math> d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 </math> для <math> i ≠ j </math>

2. <math> d_{k+1} = -g_{k+1} + β_{k}d_{k} </math>, где <math> g_{k+1} = A x_k - b </math>

3. <math> β_{k} </math> ищем исходя из условий на сопряжённость направлений: <math> 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> β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle}</math>

{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

==== Оптимизация метода сопряжённых градиентов ====
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:

<math>1.</math> Метод сопряжённых градиентов построен таким образом, что <math> \langle g_{i}, g_{k+1} \rangle = 0 </math> и <math> \langle g_{k+1}, d_{i} \rangle </math> для <math> i <= k </math> (это можно проверить по индукции и использовать свойство сопряжённости направлений)

<math>2.</math> <math> g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} </math>

Отсюда <math> Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k})</math>

<math>
3. </math> Значит <math>\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> = \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>
4.</math> Аналогично <math>
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
</math>

==== Общая схема эффективного метода сопряжённых градиентов ====
Теперь можем записать эффективную версию метода сопряжённых градиентов, использующий всего одно матрично-векторное произведение.
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро метода сопряжённых градиентов включает в себя выполнение одной матрично-векторной операции, вычисление скалярных произведений, а также векторных обновлений на каждой итерации.

=== Макроструктура алгоритма ===
Алгоритм метода сопряжённых градиентов представляет собой итерационный процесс, включающий следующие макрооперации:

1. Вычисление невязки текущего приближения

2. Вычисление матрично-векторного произведения

3. Вычисление скалярных произведений и норм векторов

4. Обновление текущего приближения и направлений поиска

5. Проверка условия останова

=== Схема реализации последовательного алгоритма ===
Подробная схема реализации метода сопряжённых градиента и эффективного метода сопряженных градиентов представлена в соответствующих разделах [[#Общая схема метода сопряжённых градиентов|Общая схема метода сопряжённых градиентов]] и [[#Общая схема эффективного метода сопряжённых градиентов|Общая схема эффективного метода сопряжённых градиентов]].

=== Последовательная сложность алгоритма ===

На каждой итерации метода сопряжённых градиентов выполняются линейно-алгебраические операции. Их стоимостная оценка даёт итоговую асимптотическую сложность итерации.

* Сложение двух векторов размерности <math>n</math> требует <math>n</math> операций сложения: сложность <math>O(n)</math>.
* Скалярное произведение двух векторов требует <math>n</math> умножений и <math>n</math> сложений: сложность <math>O(n)</math>.
* Вычисление нормы вектора <math>\|a\|</math> эквивалентно вычислению скалярного произведения <math>\langle a, a\rangle</math> с последующим извлечением корня: сложность <math>O(n)</math>.
* Матрично-векторное произведение <math>A x</math> для плотной матрицы размера <math>n \times n</math> требует <math>n^2</math> умножений и <math>n^2</math> сложений: сложность <math>O(n^2)</math>.

Так как на каждой итерации алгоритма выполняется ровно одно матрично-векторное произведение <math>A d_k</math>, а остальные операции имеют линейную сложность <math>O(n)</math>, общая стоимость одной итерации определяется наиболее дорогой операцией: <math>O(n^2).</math>
Следовательно, последовательная сложность метода при <math>k</math> итерациях составляет: <math>O(k n^2)</math>

=== Информационный граф ===
Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
[[Файл:Информационный граф итерации метода сопряжённых градиентов.png|900px]]

=== Ресурс параллелизма алгоритма ===

Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(\log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

=== Входные и выходные данные алгоритма ===

Входными данными метода сопряжённых градиентов являются матрица системы <math>A \in \mathbb{R}^{n \times n}</math>, вектор правой части <math>b \in \mathbb{R}^n</math> и начальное приближение решения <math>x_0</math>. Матрица <math>A</math> должна быть симметричной и положительно определённой, что гарантирует сходимость метода и корректность вычисления сопряжённых направлений. В практических задачах матрица может быть как плотной, так и разреженной. Структурные свойства <math>A</math> (диагональное преобладание, блочная структура) могут дополнительно уменьшать вычислительные затраты и повышать эффективность параллельной реализации.

Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаётся параметр остановки: допустимая погрешность <math>\varepsilon</math>.

Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\|r_k\| \le \varepsilon\|b\|</math> метод считается сошедшимся.

=== Свойства алгоритма ===

Метод сопряжённых градиентов обладает рядом особенностей, важных при его практической реализации. Алгоритм включает регулярную последовательность операций, из которых основная вычислительная сложность приходится на вычисление матричного произведения <math> Ad_{k} </math>. Остальные операции имеют координатный параллелизм и могут эффективно вычисляться на параллельных архитектурах. Несмотря на то что последовательная сложность одной итерации составляет <math> O(n^2) </math>, большая часть вычислений хорошо векторизуется, а редукции, возникающие при подсчёте норм и скалярных произведений, имеют логарифмическую параллельную сложность.

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Результаты прогонов ===
=== Выводы для классов архитектур ===

== Литература ==
Метод сопряжённых градиентов // BaseGroup Labs. https://basegroup.ru/community/articles/conjugate

Метод сопряжённых градиентов (дополнительный материал к курсу «Методы оптимизации»).
ВМК, 2018. http://www.machinelearning.ru/wiki/images/4/4d/MOMO18_Extra3.pdf

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-12-05T07:51:35Z

Larisayaryzheva: /* Свойства алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Метод сопряжённых градиентов''' — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений ('''СЛАУ''') вида <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
=== Математическое описание алгоритма ===

Необходимо найти решение '''СЛАУ''' <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной (<math> A^T = A > 0 </math>).
Данная задача эквивалентна минимизации следующего функционала <math> f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle </math>.

Классически данная задача решается с помощью итерационного метода спуска: <math> x_{k+1} = x_{k} + α_{k}d_{k} </math>.

На каждой итерации выбирается направление спуска <math> d_{k} </math> и шаг <math>α_{k}</math>, где <math> d_{k} </math> – антиградиент <math> f(x) </math>, а <math> \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> d_{k} </math>, которые являются '''A-сопряжёнными''', то есть удовлетворяют условию: <math> \langle A d_{i}, d_{j} \rangle = 0 </math> для всех <math> i ≠ j </math>.

==== Общая схема метода сопряжённых градиентов ====
1. Пусть даны <math> d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 </math> для <math> i ≠ j </math>

2. <math> d_{k+1} = -g_{k+1} + β_{k}d_{k} </math>, где <math> g_{k+1} = A x_k - b </math>

3. <math> β_{k} </math> ищем исходя из условий на сопряжённость направлений: <math> 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> β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle}</math>

{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

==== Оптимизация метода сопряжённых градиентов ====
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:

<math>1.</math> Метод сопряжённых градиентов построен таким образом, что <math> \langle g_{i}, g_{k+1} \rangle = 0 </math> и <math> \langle g_{k+1}, d_{i} \rangle </math> для <math> i <= k </math> (это можно проверить по индукции и использовать свойство сопряжённости направлений)

<math>2.</math> <math> g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} </math>

Отсюда <math> Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k})</math>

<math>
3. </math> Значит <math>\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> = \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>
4.</math> Аналогично <math>
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
</math>

==== Общая схема эффективного метода сопряжённых градиентов ====
Теперь можем записать эффективную версию метода сопряжённых градиентов, использующий всего одно матрично-векторное произведение.
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро метода сопряжённых градиентов включает в себя выполнение одной матрично-векторной операции, вычисление скалярных произведений, а также векторных обновлений на каждой итерации.

=== Макроструктура алгоритма ===
Алгоритм метода сопряжённых градиентов представляет собой итерационный процесс, включающий следующие макрооперации:

1. Вычисление невязки текущего приближения

2. Вычисление матрично-векторного произведения

3. Вычисление скалярных произведений и норм векторов

4. Обновление текущего приближения и направлений поиска

5. Проверка условия останова

=== Схема реализации последовательного алгоритма ===
Подробная схема реализации метода сопряжённых градиента и эффективного метода сопряженных градиентов представлена в соответствующих разделах [[#Общая схема метода сопряжённых градиентов|Общая схема метода сопряжённых градиентов]] и [[#Общая схема эффективного метода сопряжённых градиентов|Общая схема эффективного метода сопряжённых градиентов]].

=== Последовательная сложность алгоритма ===

На каждой итерации метода сопряжённых градиентов выполняются линейно-алгебраические операции. Их стоимостная оценка даёт итоговую асимптотическую сложность итерации.

* Сложение двух векторов размерности <math>n</math> требует <math>n</math> операций сложения: сложность <math>O(n)</math>.
* Скалярное произведение двух векторов требует <math>n</math> умножений и <math>n</math> сложений: сложность <math>O(n)</math>.
* Вычисление нормы вектора <math>\|a\|</math> эквивалентно вычислению скалярного произведения <math>\langle a, a\rangle</math> с последующим извлечением корня: сложность <math>O(n)</math>.
* Матрично-векторное произведение <math>A x</math> для плотной матрицы размера <math>n \times n</math> требует <math>n^2</math> умножений и <math>n^2</math> сложений: сложность <math>O(n^2)</math>.

Так как на каждой итерации алгоритма выполняется ровно одно матрично-векторное произведение <math>A d_k</math>, а остальные операции имеют линейную сложность <math>O(n)</math>, общая стоимость одной итерации определяется наиболее дорогой операцией: <math>O(n^2).</math>
Следовательно, последовательная сложность метода при <math>k</math> итерациях составляет: <math>O(k n^2)</math>

=== Информационный граф ===
Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
[[Файл:Информационный граф итерации метода сопряжённых градиентов.png|900px]]

=== Ресурс параллелизма алгоритма ===

Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(\log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

=== Входные и выходные данные алгоритма ===

Входными данными метода сопряжённых градиентов являются матрица системы <math>A \in \mathbb{R}^{n \times n}</math>, вектор правой части <math>b \in \mathbb{R}^n</math> и начальное приближение решения <math>x_0</math>. Матрица <math>A</math> должна быть симметричной и положительно определённой, что гарантирует сходимость метода и корректность вычисления сопряжённых направлений. В практических задачах матрица может быть как плотной, так и разреженной. Структурные свойства <math>A</math> (диагональное преобладание, блочная структура) могут дополнительно уменьшать вычислительные затраты и повышать эффективность параллельной реализации.

Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаётся параметр остановки: допустимая погрешность <math>\varepsilon</math>.

Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\|r_k\| \le \varepsilon\|b\|</math> метод считается сошедшимся.

=== Свойства алгоритма ===

Метод сопряжённых градиентов обладает рядом особенностей, важных при его практической реализации. Алгоритм включает регулярную последовательность операций, из которых основная вычислительная сложность приходится на вычисление матричного произведения <math> Ad_{k} </math>. Остальные операции имеют координатный параллелизм и могут эффективно вычисляться на параллельных архитектурах. Несмотря на то что последовательная сложность одной итерации составляет <math> O(n^2) </math>, большая часть вычислений хорошо векторизуется, а редукции, возникающие при подсчёте норм и скалярных произведений, имеют логарифмическую параллельную сложность.

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

== Программная реализация алгоритма ==

== Литература ==
Метод сопряжённых градиентов // BaseGroup Labs. https://basegroup.ru/community/articles/conjugate

Метод сопряжённых градиентов (дополнительный материал к курсу «Методы оптимизации»).
ВМК, 2018. http://www.machinelearning.ru/wiki/images/4/4d/MOMO18_Extra3.pdf

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-12-05T07:48:52Z

Larisayaryzheva: /* Входные и выходные данные алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Метод сопряжённых градиентов''' — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений ('''СЛАУ''') вида <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
=== Математическое описание алгоритма ===

Необходимо найти решение '''СЛАУ''' <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной (<math> A^T = A > 0 </math>).
Данная задача эквивалентна минимизации следующего функционала <math> f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle </math>.

Классически данная задача решается с помощью итерационного метода спуска: <math> x_{k+1} = x_{k} + α_{k}d_{k} </math>.

На каждой итерации выбирается направление спуска <math> d_{k} </math> и шаг <math>α_{k}</math>, где <math> d_{k} </math> – антиградиент <math> f(x) </math>, а <math> \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> d_{k} </math>, которые являются '''A-сопряжёнными''', то есть удовлетворяют условию: <math> \langle A d_{i}, d_{j} \rangle = 0 </math> для всех <math> i ≠ j </math>.

==== Общая схема метода сопряжённых градиентов ====
1. Пусть даны <math> d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 </math> для <math> i ≠ j </math>

2. <math> d_{k+1} = -g_{k+1} + β_{k}d_{k} </math>, где <math> g_{k+1} = A x_k - b </math>

3. <math> β_{k} </math> ищем исходя из условий на сопряжённость направлений: <math> 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> β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle}</math>

{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

==== Оптимизация метода сопряжённых градиентов ====
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:

<math>1.</math> Метод сопряжённых градиентов построен таким образом, что <math> \langle g_{i}, g_{k+1} \rangle = 0 </math> и <math> \langle g_{k+1}, d_{i} \rangle </math> для <math> i <= k </math> (это можно проверить по индукции и использовать свойство сопряжённости направлений)

<math>2.</math> <math> g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} </math>

Отсюда <math> Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k})</math>

<math>
3. </math> Значит <math>\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> = \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>
4.</math> Аналогично <math>
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
</math>

==== Общая схема эффективного метода сопряжённых градиентов ====
Теперь можем записать эффективную версию метода сопряжённых градиентов, использующий всего одно матрично-векторное произведение.
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро метода сопряжённых градиентов включает в себя выполнение одной матрично-векторной операции, вычисление скалярных произведений, а также векторных обновлений на каждой итерации.

=== Макроструктура алгоритма ===
Алгоритм метода сопряжённых градиентов представляет собой итерационный процесс, включающий следующие макрооперации:

1. Вычисление невязки текущего приближения

2. Вычисление матрично-векторного произведения

3. Вычисление скалярных произведений и норм векторов

4. Обновление текущего приближения и направлений поиска

5. Проверка условия останова

=== Схема реализации последовательного алгоритма ===
Подробная схема реализации метода сопряжённых градиента и эффективного метода сопряженных градиентов представлена в соответствующих разделах [[#Общая схема метода сопряжённых градиентов|Общая схема метода сопряжённых градиентов]] и [[#Общая схема эффективного метода сопряжённых градиентов|Общая схема эффективного метода сопряжённых градиентов]].

=== Последовательная сложность алгоритма ===

На каждой итерации метода сопряжённых градиентов выполняются линейно-алгебраические операции. Их стоимостная оценка даёт итоговую асимптотическую сложность итерации.

* Сложение двух векторов размерности <math>n</math> требует <math>n</math> операций сложения: сложность <math>O(n)</math>.
* Скалярное произведение двух векторов требует <math>n</math> умножений и <math>n</math> сложений: сложность <math>O(n)</math>.
* Вычисление нормы вектора <math>\|a\|</math> эквивалентно вычислению скалярного произведения <math>\langle a, a\rangle</math> с последующим извлечением корня: сложность <math>O(n)</math>.
* Матрично-векторное произведение <math>A x</math> для плотной матрицы размера <math>n \times n</math> требует <math>n^2</math> умножений и <math>n^2</math> сложений: сложность <math>O(n^2)</math>.

Так как на каждой итерации алгоритма выполняется ровно одно матрично-векторное произведение <math>A d_k</math>, а остальные операции имеют линейную сложность <math>O(n)</math>, общая стоимость одной итерации определяется наиболее дорогой операцией: <math>O(n^2).</math>
Следовательно, последовательная сложность метода при <math>k</math> итерациях составляет: <math>O(k n^2)</math>

=== Информационный граф ===
Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
[[Файл:Информационный граф итерации метода сопряжённых градиентов.png|900px]]

=== Ресурс параллелизма алгоритма ===

Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(\log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

=== Входные и выходные данные алгоритма ===

Входными данными метода сопряжённых градиентов являются матрица системы <math>A \in \mathbb{R}^{n \times n}</math>, вектор правой части <math>b \in \mathbb{R}^n</math> и начальное приближение решения <math>x_0</math>. Матрица <math>A</math> должна быть симметричной и положительно определённой, что гарантирует сходимость метода и корректность вычисления сопряжённых направлений. В практических задачах матрица может быть как плотной, так и разреженной. Структурные свойства <math>A</math> (диагональное преобладание, блочная структура) могут дополнительно уменьшать вычислительные затраты и повышать эффективность параллельной реализации.

Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаётся параметр остановки: допустимая погрешность <math>\varepsilon</math>.

Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\|r_k\| \le \varepsilon\|b\|</math> метод считается сошедшимся.

=== Свойства алгоритма ===

Метод сопряжённых градиентов обладает рядом особенностей, важных при его практической реализации. Алгоритм включает регулярную последовательность операций, из которых основная вычислительная сложность приходится на вычисление матричного произведения <math> Ad_{k} </math>. Остальные операции имеют координатный параллелизм и могут эффективно вычисляться на параллельных архитектурах. Несмотря на то что последовательная сложность одной итерации составляет <math> O(n^2) </math>, большая часть вычислений хорошо векторизуется, а редукции, возникающие при подсчёте норм и скалярных произведений, имеют логарифмическую параллельную сложность.

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

== Литература ==
Метод сопряжённых градиентов // BaseGroup Labs. https://basegroup.ru/community/articles/conjugate

Метод сопряжённых градиентов (дополнительный материал к курсу «Методы оптимизации»).
ВМК, 2018. http://www.machinelearning.ru/wiki/images/4/4d/MOMO18_Extra3.pdf

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-12-05T07:24:56Z

Larisayaryzheva: /* Входные и выходные данные алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Метод сопряжённых градиентов''' — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений ('''СЛАУ''') вида <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
=== Математическое описание алгоритма ===

Необходимо найти решение '''СЛАУ''' <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной (<math> A^T = A > 0 </math>).
Данная задача эквивалентна минимизации следующего функционала <math> f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle </math>.

Классически данная задача решается с помощью итерационного метода спуска: <math> x_{k+1} = x_{k} + α_{k}d_{k} </math>.

На каждой итерации выбирается направление спуска <math> d_{k} </math> и шаг <math>α_{k}</math>, где <math> d_{k} </math> – антиградиент <math> f(x) </math>, а <math> \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> d_{k} </math>, которые являются '''A-сопряжёнными''', то есть удовлетворяют условию: <math> \langle A d_{i}, d_{j} \rangle = 0 </math> для всех <math> i ≠ j </math>.

==== Общая схема метода сопряжённых градиентов ====
1. Пусть даны <math> d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 </math> для <math> i ≠ j </math>

2. <math> d_{k+1} = -g_{k+1} + β_{k}d_{k} </math>, где <math> g_{k+1} = A x_k - b </math>

3. <math> β_{k} </math> ищем исходя из условий на сопряжённость направлений: <math> 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> β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle}</math>

{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

==== Оптимизация метода сопряжённых градиентов ====
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:

<math>1.</math> Метод сопряжённых градиентов построен таким образом, что <math> \langle g_{i}, g_{k+1} \rangle = 0 </math> и <math> \langle g_{k+1}, d_{i} \rangle </math> для <math> i <= k </math> (это можно проверить по индукции и использовать свойство сопряжённости направлений)

<math>2.</math> <math> g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} </math>

Отсюда <math> Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k})</math>

<math>
3. </math> Значит <math>\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> = \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>
4.</math> Аналогично <math>
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
</math>

==== Общая схема эффективного метода сопряжённых градиентов ====
Теперь можем записать эффективную версию метода сопряжённых градиентов, использующий всего одно матрично-векторное произведение.
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро метода сопряжённых градиентов включает в себя выполнение одной матрично-векторной операции, вычисление скалярных произведений, а также векторных обновлений на каждой итерации.

=== Макроструктура алгоритма ===
Алгоритм метода сопряжённых градиентов представляет собой итерационный процесс, включающий следующие макрооперации:

1. Вычисление невязки текущего приближения

2. Вычисление матрично-векторного произведения

3. Вычисление скалярных произведений и норм векторов

4. Обновление текущего приближения и направлений поиска

5. Проверка условия останова

=== Схема реализации последовательного алгоритма ===
Подробная схема реализации метода сопряжённых градиента и эффективного метода сопряженных градиентов представлена в соответствующих разделах [[#Общая схема метода сопряжённых градиентов|Общая схема метода сопряжённых градиентов]] и [[#Общая схема эффективного метода сопряжённых градиентов|Общая схема эффективного метода сопряжённых градиентов]].

=== Последовательная сложность алгоритма ===

На каждой итерации метода сопряжённых градиентов выполняются линейно-алгебраические операции. Их стоимостная оценка даёт итоговую асимптотическую сложность итерации.

* Сложение двух векторов размерности <math>n</math> требует <math>n</math> операций сложения: сложность <math>O(n)</math>.
* Скалярное произведение двух векторов требует <math>n</math> умножений и <math>n</math> сложений: сложность <math>O(n)</math>.
* Вычисление нормы вектора <math>\|a\|</math> эквивалентно вычислению скалярного произведения <math>\langle a, a\rangle</math> с последующим извлечением корня: сложность <math>O(n)</math>.
* Матрично-векторное произведение <math>A x</math> для плотной матрицы размера <math>n \times n</math> требует <math>n^2</math> умножений и <math>n^2</math> сложений: сложность <math>O(n^2)</math>.

Так как на каждой итерации алгоритма выполняется ровно одно матрично-векторное произведение <math>A d_k</math>, а остальные операции имеют линейную сложность <math>O(n)</math>, общая стоимость одной итерации определяется наиболее дорогой операцией: <math>O(n^2).</math>
Следовательно, последовательная сложность метода при <math>k</math> итерациях составляет: <math>O(k n^2)</math>

=== Информационный граф ===
Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
[[Файл:Информационный граф итерации метода сопряжённых градиентов.png|900px]]

=== Ресурс параллелизма алгоритма ===

Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(\log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

=== Входные и выходные данные алгоритма ===

Входными данными метода сопряжённых градиентов являются матрица системы <math>A \in \mathbb{R}^{n \times n}</math>, вектор правой части <math>b \in \mathbb{R}^n</math> и начальное приближение решения <math>x_0</math>. Матрица <math>A</math> должна быть симметричной и положительно определённой, что гарантирует сходимость метода и корректность вычисления сопряжённых направлений. В практических задачах матрица может быть как плотной, так и разреженной. Структурные свойства <math>A</math> (диагональное преобладание, блочная структура) могут дополнительно уменьшать вычислительные затраты и повышать эффективность параллельной реализации.

Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаётся параметр остановки: допустимая погрешность <math>\varepsilon</math>.

Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\|r_k\| \le \varepsilon\|b\|</math> метод считается сошедшимся.

== Литература ==
Метод сопряжённых градиентов // BaseGroup Labs. https://basegroup.ru/community/articles/conjugate

Метод сопряжённых градиентов (дополнительный материал к курсу «Методы оптимизации»).
ВМК, 2018. http://www.machinelearning.ru/wiki/images/4/4d/MOMO18_Extra3.pdf

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-12-05T07:23:49Z

Larisayaryzheva: /* Входные и выходные данные алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Метод сопряжённых градиентов''' — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений ('''СЛАУ''') вида <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
=== Математическое описание алгоритма ===

Необходимо найти решение '''СЛАУ''' <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной (<math> A^T = A > 0 </math>).
Данная задача эквивалентна минимизации следующего функционала <math> f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle </math>.

Классически данная задача решается с помощью итерационного метода спуска: <math> x_{k+1} = x_{k} + α_{k}d_{k} </math>.

На каждой итерации выбирается направление спуска <math> d_{k} </math> и шаг <math>α_{k}</math>, где <math> d_{k} </math> – антиградиент <math> f(x) </math>, а <math> \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> d_{k} </math>, которые являются '''A-сопряжёнными''', то есть удовлетворяют условию: <math> \langle A d_{i}, d_{j} \rangle = 0 </math> для всех <math> i ≠ j </math>.

==== Общая схема метода сопряжённых градиентов ====
1. Пусть даны <math> d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 </math> для <math> i ≠ j </math>

2. <math> d_{k+1} = -g_{k+1} + β_{k}d_{k} </math>, где <math> g_{k+1} = A x_k - b </math>

3. <math> β_{k} </math> ищем исходя из условий на сопряжённость направлений: <math> 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> β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle}</math>

{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

==== Оптимизация метода сопряжённых градиентов ====
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:

<math>1.</math> Метод сопряжённых градиентов построен таким образом, что <math> \langle g_{i}, g_{k+1} \rangle = 0 </math> и <math> \langle g_{k+1}, d_{i} \rangle </math> для <math> i <= k </math> (это можно проверить по индукции и использовать свойство сопряжённости направлений)

<math>2.</math> <math> g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} </math>

Отсюда <math> Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k})</math>

<math>
3. </math> Значит <math>\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> = \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>
4.</math> Аналогично <math>
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
</math>

==== Общая схема эффективного метода сопряжённых градиентов ====
Теперь можем записать эффективную версию метода сопряжённых градиентов, использующий всего одно матрично-векторное произведение.
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро метода сопряжённых градиентов включает в себя выполнение одной матрично-векторной операции, вычисление скалярных произведений, а также векторных обновлений на каждой итерации.

=== Макроструктура алгоритма ===
Алгоритм метода сопряжённых градиентов представляет собой итерационный процесс, включающий следующие макрооперации:

1. Вычисление невязки текущего приближения

2. Вычисление матрично-векторного произведения

3. Вычисление скалярных произведений и норм векторов

4. Обновление текущего приближения и направлений поиска

5. Проверка условия останова

=== Схема реализации последовательного алгоритма ===
Подробная схема реализации метода сопряжённых градиента и эффективного метода сопряженных градиентов представлена в соответствующих разделах [[#Общая схема метода сопряжённых градиентов|Общая схема метода сопряжённых градиентов]] и [[#Общая схема эффективного метода сопряжённых градиентов|Общая схема эффективного метода сопряжённых градиентов]].

=== Последовательная сложность алгоритма ===

На каждой итерации метода сопряжённых градиентов выполняются линейно-алгебраические операции. Их стоимостная оценка даёт итоговую асимптотическую сложность итерации.

* Сложение двух векторов размерности <math>n</math> требует <math>n</math> операций сложения: сложность <math>O(n)</math>.
* Скалярное произведение двух векторов требует <math>n</math> умножений и <math>n</math> сложений: сложность <math>O(n)</math>.
* Вычисление нормы вектора <math>\|a\|</math> эквивалентно вычислению скалярного произведения <math>\langle a, a\rangle</math> с последующим извлечением корня: сложность <math>O(n)</math>.
* Матрично-векторное произведение <math>A x</math> для плотной матрицы размера <math>n \times n</math> требует <math>n^2</math> умножений и <math>n^2</math> сложений: сложность <math>O(n^2)</math>.

Так как на каждой итерации алгоритма выполняется ровно одно матрично-векторное произведение <math>A d_k</math>, а остальные операции имеют линейную сложность <math>O(n)</math>, общая стоимость одной итерации определяется наиболее дорогой операцией: <math>O(n^2).</math>
Следовательно, последовательная сложность метода при <math>k</math> итерациях составляет: <math>O(k n^2)</math>

=== Информационный граф ===
Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
[[Файл:Информационный граф итерации метода сопряжённых градиентов.png|900px]]

=== Ресурс параллелизма алгоритма ===

Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(\log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

=== Входные и выходные данные алгоритма ===

Входными данными метода сопряжённых градиентов являются матрица системы <math>A \in \mathbb{R}^{n \times n}</math>, вектор правой части <math>b \in \mathbb{R}^n</math> и начальное приближение решения <math>x_0</math>. Матрица <math>A</math> должна быть симметричной и положительно определённой, что гарантирует сходимость метода и корректность вычисления сопряжённых направлений. В практических задачах матрица может быть как плотной, так и разреженной. Структурные свойства <math>A</math> (диагональное преобладание, блочная структура) могут дополнительно уменьшать вычислительные затраты и повышать эффективность параллельной реализации.

Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаются параметры остановки: допустимая погрешность <math>\varepsilon</math> и максимальное число итераций <math>k_{\max}</math>.

Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\|r_k\| \le \varepsilon\|b\|</math> метод считается сошедшимся.

== Литература ==
Метод сопряжённых градиентов // BaseGroup Labs. https://basegroup.ru/community/articles/conjugate

Метод сопряжённых градиентов (дополнительный материал к курсу «Методы оптимизации»).
ВМК, 2018. http://www.machinelearning.ru/wiki/images/4/4d/MOMO18_Extra3.pdf

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-12-05T07:20:43Z

Larisayaryzheva: /* Ресурс параллелизма алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Метод сопряжённых градиентов''' — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений ('''СЛАУ''') вида <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
=== Математическое описание алгоритма ===

Необходимо найти решение '''СЛАУ''' <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной (<math> A^T = A > 0 </math>).
Данная задача эквивалентна минимизации следующего функционала <math> f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle </math>.

Классически данная задача решается с помощью итерационного метода спуска: <math> x_{k+1} = x_{k} + α_{k}d_{k} </math>.

На каждой итерации выбирается направление спуска <math> d_{k} </math> и шаг <math>α_{k}</math>, где <math> d_{k} </math> – антиградиент <math> f(x) </math>, а <math> \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> d_{k} </math>, которые являются '''A-сопряжёнными''', то есть удовлетворяют условию: <math> \langle A d_{i}, d_{j} \rangle = 0 </math> для всех <math> i ≠ j </math>.

==== Общая схема метода сопряжённых градиентов ====
1. Пусть даны <math> d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 </math> для <math> i ≠ j </math>

2. <math> d_{k+1} = -g_{k+1} + β_{k}d_{k} </math>, где <math> g_{k+1} = A x_k - b </math>

3. <math> β_{k} </math> ищем исходя из условий на сопряжённость направлений: <math> 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> β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle}</math>

{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

==== Оптимизация метода сопряжённых градиентов ====
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:

<math>1.</math> Метод сопряжённых градиентов построен таким образом, что <math> \langle g_{i}, g_{k+1} \rangle = 0 </math> и <math> \langle g_{k+1}, d_{i} \rangle </math> для <math> i <= k </math> (это можно проверить по индукции и использовать свойство сопряжённости направлений)

<math>2.</math> <math> g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} </math>

Отсюда <math> Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k})</math>

<math>
3. </math> Значит <math>\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> = \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>
4.</math> Аналогично <math>
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
</math>

==== Общая схема эффективного метода сопряжённых градиентов ====
Теперь можем записать эффективную версию метода сопряжённых градиентов, использующий всего одно матрично-векторное произведение.
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро метода сопряжённых градиентов включает в себя выполнение одной матрично-векторной операции, вычисление скалярных произведений, а также векторных обновлений на каждой итерации.

=== Макроструктура алгоритма ===
Алгоритм метода сопряжённых градиентов представляет собой итерационный процесс, включающий следующие макрооперации:

1. Вычисление невязки текущего приближения

2. Вычисление матрично-векторного произведения

3. Вычисление скалярных произведений и норм векторов

4. Обновление текущего приближения и направлений поиска

5. Проверка условия останова

=== Схема реализации последовательного алгоритма ===
Подробная схема реализации метода сопряжённых градиента и эффективного метода сопряженных градиентов представлена в соответствующих разделах [[#Общая схема метода сопряжённых градиентов|Общая схема метода сопряжённых градиентов]] и [[#Общая схема эффективного метода сопряжённых градиентов|Общая схема эффективного метода сопряжённых градиентов]].

=== Последовательная сложность алгоритма ===

На каждой итерации метода сопряжённых градиентов выполняются линейно-алгебраические операции. Их стоимостная оценка даёт итоговую асимптотическую сложность итерации.

* Сложение двух векторов размерности <math>n</math> требует <math>n</math> операций сложения: сложность <math>O(n)</math>.
* Скалярное произведение двух векторов требует <math>n</math> умножений и <math>n</math> сложений: сложность <math>O(n)</math>.
* Вычисление нормы вектора <math>\|a\|</math> эквивалентно вычислению скалярного произведения <math>\langle a, a\rangle</math> с последующим извлечением корня: сложность <math>O(n)</math>.
* Матрично-векторное произведение <math>A x</math> для плотной матрицы размера <math>n \times n</math> требует <math>n^2</math> умножений и <math>n^2</math> сложений: сложность <math>O(n^2)</math>.

Так как на каждой итерации алгоритма выполняется ровно одно матрично-векторное произведение <math>A d_k</math>, а остальные операции имеют линейную сложность <math>O(n)</math>, общая стоимость одной итерации определяется наиболее дорогой операцией: <math>O(n^2).</math>
Следовательно, последовательная сложность метода при <math>k</math> итерациях составляет: <math>O(k n^2)</math>

=== Информационный граф ===
Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
[[Файл:Информационный граф итерации метода сопряжённых градиентов.png|900px]]

=== Ресурс параллелизма алгоритма ===

Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(\log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

=== Входные и выходные данные алгоритма ===

Входными данными метода сопряжённых градиентов являются матрица системы <math>A \in \mathbb{R}^{n \times n}</math>, вектор правой части <math>b \in \mathbb{R}^n</math> и начальное приближение решения <math>x_0</math>. Матрица <math>A</math> должна быть симметричной и положительно определённой, что гарантирует сходимость метода и корректность вычисления сопряжённых направлений. В практических задачах матрица может быть как плотной, так и разреженной. Структурные свойства <math>A</math> (диагональное преобладание, блочная структура) могут дополнительно уменьшать вычислительные затраты и повышать эффективность параллельной реализации.

Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаются параметры остановки: допустимая погрешность <math>\varepsilon</math> и максимальное число итераций <math>k_{\max}</math>.

Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>, последняя невязка <math>r_k = b - A x_k</math>, число выполненных итераций и значение нормы невязки в момент остановки. При достижении заданной точности <math>\|r_k\| \le \varepsilon\|b\|</math> метод считается сошедшимся.

== Литература ==
Метод сопряжённых градиентов // BaseGroup Labs. https://basegroup.ru/community/articles/conjugate

Метод сопряжённых градиентов (дополнительный материал к курсу «Методы оптимизации»).
ВМК, 2018. http://www.machinelearning.ru/wiki/images/4/4d/MOMO18_Extra3.pdf

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-12-05T07:12:35Z

Larisayaryzheva: /* Ресурс параллелизма алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Метод сопряжённых градиентов''' — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений ('''СЛАУ''') вида <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
=== Математическое описание алгоритма ===

Необходимо найти решение '''СЛАУ''' <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной (<math> A^T = A > 0 </math>).
Данная задача эквивалентна минимизации следующего функционала <math> f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle </math>.

Классически данная задача решается с помощью итерационного метода спуска: <math> x_{k+1} = x_{k} + α_{k}d_{k} </math>.

На каждой итерации выбирается направление спуска <math> d_{k} </math> и шаг <math>α_{k}</math>, где <math> d_{k} </math> – антиградиент <math> f(x) </math>, а <math> \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> d_{k} </math>, которые являются '''A-сопряжёнными''', то есть удовлетворяют условию: <math> \langle A d_{i}, d_{j} \rangle = 0 </math> для всех <math> i ≠ j </math>.

==== Общая схема метода сопряжённых градиентов ====
1. Пусть даны <math> d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 </math> для <math> i ≠ j </math>

2. <math> d_{k+1} = -g_{k+1} + β_{k}d_{k} </math>, где <math> g_{k+1} = A x_k - b </math>

3. <math> β_{k} </math> ищем исходя из условий на сопряжённость направлений: <math> 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> β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle}</math>

{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

==== Оптимизация метода сопряжённых градиентов ====
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:

<math>1.</math> Метод сопряжённых градиентов построен таким образом, что <math> \langle g_{i}, g_{k+1} \rangle = 0 </math> и <math> \langle g_{k+1}, d_{i} \rangle </math> для <math> i <= k </math> (это можно проверить по индукции и использовать свойство сопряжённости направлений)

<math>2.</math> <math> g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} </math>

Отсюда <math> Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k})</math>

<math>
3. </math> Значит <math>\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> = \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>
4.</math> Аналогично <math>
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
</math>

==== Общая схема эффективного метода сопряжённых градиентов ====
Теперь можем записать эффективную версию метода сопряжённых градиентов, использующий всего одно матрично-векторное произведение.
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро метода сопряжённых градиентов включает в себя выполнение одной матрично-векторной операции, вычисление скалярных произведений, а также векторных обновлений на каждой итерации.

=== Макроструктура алгоритма ===
Алгоритм метода сопряжённых градиентов представляет собой итерационный процесс, включающий следующие макрооперации:

1. Вычисление невязки текущего приближения

2. Вычисление матрично-векторного произведения

3. Вычисление скалярных произведений и норм векторов

4. Обновление текущего приближения и направлений поиска

5. Проверка условия останова

=== Схема реализации последовательного алгоритма ===
Подробная схема реализации метода сопряжённых градиента и эффективного метода сопряженных градиентов представлена в соответствующих разделах [[#Общая схема метода сопряжённых градиентов|Общая схема метода сопряжённых градиентов]] и [[#Общая схема эффективного метода сопряжённых градиентов|Общая схема эффективного метода сопряжённых градиентов]].

=== Последовательная сложность алгоритма ===

На каждой итерации метода сопряжённых градиентов выполняются линейно-алгебраические операции. Их стоимостная оценка даёт итоговую асимптотическую сложность итерации.

* Сложение двух векторов размерности <math>n</math> требует <math>n</math> операций сложения: сложность <math>O(n)</math>.
* Скалярное произведение двух векторов требует <math>n</math> умножений и <math>n</math> сложений: сложность <math>O(n)</math>.
* Вычисление нормы вектора <math>\|a\|</math> эквивалентно вычислению скалярного произведения <math>\langle a, a\rangle</math> с последующим извлечением корня: сложность <math>O(n)</math>.
* Матрично-векторное произведение <math>A x</math> для плотной матрицы размера <math>n \times n</math> требует <math>n^2</math> умножений и <math>n^2</math> сложений: сложность <math>O(n^2)</math>.

Так как на каждой итерации алгоритма выполняется ровно одно матрично-векторное произведение <math>A d_k</math>, а остальные операции имеют линейную сложность <math>O(n)</math>, общая стоимость одной итерации определяется наиболее дорогой операцией: <math>O(n^2).</math>
Следовательно, последовательная сложность метода при <math>k</math> итерациях составляет: <math>O(k n^2)</math>

=== Информационный граф ===
Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
[[Файл:Информационный граф итерации метода сопряжённых градиентов.png|900px]]

=== Ресурс параллелизма алгоритма ===

Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(\log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

== Литература ==
Метод сопряжённых градиентов // BaseGroup Labs. https://basegroup.ru/community/articles/conjugate

Метод сопряжённых градиентов (дополнительный материал к курсу «Методы оптимизации»).
ВМК, 2018. http://www.machinelearning.ru/wiki/images/4/4d/MOMO18_Extra3.pdf

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-12-05T07:10:10Z

Larisayaryzheva: /* Ресурс параллелизма алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Метод сопряжённых градиентов''' — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений ('''СЛАУ''') вида <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
=== Математическое описание алгоритма ===

Необходимо найти решение '''СЛАУ''' <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной (<math> A^T = A > 0 </math>).
Данная задача эквивалентна минимизации следующего функционала <math> f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle </math>.

Классически данная задача решается с помощью итерационного метода спуска: <math> x_{k+1} = x_{k} + α_{k}d_{k} </math>.

На каждой итерации выбирается направление спуска <math> d_{k} </math> и шаг <math>α_{k}</math>, где <math> d_{k} </math> – антиградиент <math> f(x) </math>, а <math> \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> d_{k} </math>, которые являются '''A-сопряжёнными''', то есть удовлетворяют условию: <math> \langle A d_{i}, d_{j} \rangle = 0 </math> для всех <math> i ≠ j </math>.

==== Общая схема метода сопряжённых градиентов ====
1. Пусть даны <math> d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 </math> для <math> i ≠ j </math>

2. <math> d_{k+1} = -g_{k+1} + β_{k}d_{k} </math>, где <math> g_{k+1} = A x_k - b </math>

3. <math> β_{k} </math> ищем исходя из условий на сопряжённость направлений: <math> 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> β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle}</math>

{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

==== Оптимизация метода сопряжённых градиентов ====
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:

<math>1.</math> Метод сопряжённых градиентов построен таким образом, что <math> \langle g_{i}, g_{k+1} \rangle = 0 </math> и <math> \langle g_{k+1}, d_{i} \rangle </math> для <math> i <= k </math> (это можно проверить по индукции и использовать свойство сопряжённости направлений)

<math>2.</math> <math> g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} </math>

Отсюда <math> Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k})</math>

<math>
3. </math> Значит <math>\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> = \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>
4.</math> Аналогично <math>
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
</math>

==== Общая схема эффективного метода сопряжённых градиентов ====
Теперь можем записать эффективную версию метода сопряжённых градиентов, использующий всего одно матрично-векторное произведение.
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро метода сопряжённых градиентов включает в себя выполнение одной матрично-векторной операции, вычисление скалярных произведений, а также векторных обновлений на каждой итерации.

=== Макроструктура алгоритма ===
Алгоритм метода сопряжённых градиентов представляет собой итерационный процесс, включающий следующие макрооперации:

1. Вычисление невязки текущего приближения

2. Вычисление матрично-векторного произведения

3. Вычисление скалярных произведений и норм векторов

4. Обновление текущего приближения и направлений поиска

5. Проверка условия останова

=== Схема реализации последовательного алгоритма ===
Подробная схема реализации метода сопряжённых градиента и эффективного метода сопряженных градиентов представлена в соответствующих разделах [[#Общая схема метода сопряжённых градиентов|Общая схема метода сопряжённых градиентов]] и [[#Общая схема эффективного метода сопряжённых градиентов|Общая схема эффективного метода сопряжённых градиентов]].

=== Последовательная сложность алгоритма ===

На каждой итерации метода сопряжённых градиентов выполняются линейно-алгебраические операции. Их стоимостная оценка даёт итоговую асимптотическую сложность итерации.

* Сложение двух векторов размерности <math>n</math> требует <math>n</math> операций сложения: сложность <math>O(n)</math>.
* Скалярное произведение двух векторов требует <math>n</math> умножений и <math>n</math> сложений: сложность <math>O(n)</math>.
* Вычисление нормы вектора <math>\|a\|</math> эквивалентно вычислению скалярного произведения <math>\langle a, a\rangle</math> с последующим извлечением корня: сложность <math>O(n)</math>.
* Матрично-векторное произведение <math>A x</math> для плотной матрицы размера <math>n \times n</math> требует <math>n^2</math> умножений и <math>n^2</math> сложений: сложность <math>O(n^2)</math>.

Так как на каждой итерации алгоритма выполняется ровно одно матрично-векторное произведение <math>A d_k</math>, а остальные операции имеют линейную сложность <math>O(n)</math>, общая стоимость одной итерации определяется наиболее дорогой операцией: <math>O(n^2).</math>
Следовательно, последовательная сложность метода при <math>k</math> итерациях составляет: <math>O(k n^2)</math>

=== Информационный граф ===
Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
[[Файл:Информационный граф итерации метода сопряжённых градиентов.png|900px]]

=== Ресурс параллелизма алгоритма ===

Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(log\quad n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

В итоге общая параллельная сложность метода равна <math> O(k\quad log \quad n ) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

== Литература ==
Метод сопряжённых градиентов // BaseGroup Labs. https://basegroup.ru/community/articles/conjugate

Метод сопряжённых градиентов (дополнительный материал к курсу «Методы оптимизации»).
ВМК, 2018. http://www.machinelearning.ru/wiki/images/4/4d/MOMO18_Extra3.pdf

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-12-05T07:06:35Z

Larisayaryzheva: /* Ресурс параллелизма алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Метод сопряжённых градиентов''' — это итерационный численный метод, предназначенный для решения систем линейных алгебраических уравнений ('''СЛАУ''') вида <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной . Основная идея алгоритма заключается в минимизации квадратичного функционала, соответствующего данной системе.
=== Математическое описание алгоритма ===

Необходимо найти решение '''СЛАУ''' <math> Ax = b </math>, где матрица <math> A </math> является положительно определённой и симметричной (<math> A^T = A > 0 </math>).
Данная задача эквивалентна минимизации следующего функционала <math> f(x) = \frac{1}{2} \langle A x, x \rangle - \langle b, x \rangle </math>.

Классически данная задача решается с помощью итерационного метода спуска: <math> x_{k+1} = x_{k} + α_{k}d_{k} </math>.

На каждой итерации выбирается направление спуска <math> d_{k} </math> и шаг <math>α_{k}</math>, где <math> d_{k} </math> – антиградиент <math> f(x) </math>, а <math> \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> d_{k} </math>, которые являются '''A-сопряжёнными''', то есть удовлетворяют условию: <math> \langle A d_{i}, d_{j} \rangle = 0 </math> для всех <math> i ≠ j </math>.

==== Общая схема метода сопряжённых градиентов ====
1. Пусть даны <math> d_{0},...,d_{k}: \langle A d_{i}, d_{j} \rangle = 0 </math> для <math> i ≠ j </math>

2. <math> d_{k+1} = -g_{k+1} + β_{k}d_{k} </math>, где <math> g_{k+1} = A x_k - b </math>

3. <math> β_{k} </math> ищем исходя из условий на сопряжённость направлений: <math> 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> β_k = \frac{\langle A d_k, g_{k+1} \rangle}{\langle A d_k, d_k \rangle}</math>

{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

==== Оптимизация метода сопряжённых градиентов ====
Выше приведённая схема метода сопряжённых градиентов включает в себя вычисление двух матрично-векторных произведений за один прогон цикла. Данную неэффективность можно устранить, используя следующие факты:

<math>1.</math> Метод сопряжённых градиентов построен таким образом, что <math> \langle g_{i}, g_{k+1} \rangle = 0 </math> и <math> \langle g_{k+1}, d_{i} \rangle </math> для <math> i <= k </math> (это можно проверить по индукции и использовать свойство сопряжённости направлений)

<math>2.</math> <math> g_{k+1} = Ax_{k+1} - b = A(x_{k} + α_{k}d_{k}) - b = g_{k} + α_{k}Ad_{k} </math>

Отсюда <math> Ad_{k} = α_{k}^{-1}(g_{k+1} - g_{k})</math>

<math>
3. </math> Значит <math>\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> = \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>
4.</math> Аналогично <math>
\alpha_k =
\dfrac{\| g_k \|^2}{\langle A d_k,\; d_k \rangle}
</math>

==== Общая схема эффективного метода сопряжённых градиентов ====
Теперь можем записать эффективную версию метода сопряжённых градиентов, использующий всего одно матрично-векторное произведение.
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:70%;"
|+
|-
| '''Инициализация:'''
<math>g_0 = A x_0 - b</math>

<math>d_0 = -g_0</math>

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро метода сопряжённых градиентов включает в себя выполнение одной матрично-векторной операции, вычисление скалярных произведений, а также векторных обновлений на каждой итерации.

=== Макроструктура алгоритма ===
Алгоритм метода сопряжённых градиентов представляет собой итерационный процесс, включающий следующие макрооперации:

1. Вычисление невязки текущего приближения

2. Вычисление матрично-векторного произведения

3. Вычисление скалярных произведений и норм векторов

4. Обновление текущего приближения и направлений поиска

5. Проверка условия останова

=== Схема реализации последовательного алгоритма ===
Подробная схема реализации метода сопряжённых градиента и эффективного метода сопряженных градиентов представлена в соответствующих разделах [[#Общая схема метода сопряжённых градиентов|Общая схема метода сопряжённых градиентов]] и [[#Общая схема эффективного метода сопряжённых градиентов|Общая схема эффективного метода сопряжённых градиентов]].

=== Последовательная сложность алгоритма ===

На каждой итерации метода сопряжённых градиентов выполняются линейно-алгебраические операции. Их стоимостная оценка даёт итоговую асимптотическую сложность итерации.

* Сложение двух векторов размерности <math>n</math> требует <math>n</math> операций сложения: сложность <math>O(n)</math>.
* Скалярное произведение двух векторов требует <math>n</math> умножений и <math>n</math> сложений: сложность <math>O(n)</math>.
* Вычисление нормы вектора <math>\|a\|</math> эквивалентно вычислению скалярного произведения <math>\langle a, a\rangle</math> с последующим извлечением корня: сложность <math>O(n)</math>.
* Матрично-векторное произведение <math>A x</math> для плотной матрицы размера <math>n \times n</math> требует <math>n^2</math> умножений и <math>n^2</math> сложений: сложность <math>O(n^2)</math>.

Так как на каждой итерации алгоритма выполняется ровно одно матрично-векторное произведение <math>A d_k</math>, а остальные операции имеют линейную сложность <math>O(n)</math>, общая стоимость одной итерации определяется наиболее дорогой операцией: <math>O(n^2).</math>
Следовательно, последовательная сложность метода при <math>k</math> итерациях составляет: <math>O(k n^2)</math>

=== Информационный граф ===
Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
[[Файл:Информационный граф итерации метода сопряжённых градиентов.png|900px]]

=== Ресурс параллелизма алгоритма ===

Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

В итоге общая параллельная сложность метода равна <math> O(k logn) </math>, где k – число операций.

== Литература ==
Метод сопряжённых градиентов // BaseGroup Labs. https://basegroup.ru/community/articles/conjugate

Метод сопряжённых градиентов (дополнительный материал к курсу «Методы оптимизации»).
ВМК, 2018. http://www.machinelearning.ru/wiki/images/4/4d/MOMO18_Extra3.pdf

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T19:24:31Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T19:15:16Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T19:13:44Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T19:12:26Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T19:05:29Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T18:53:23Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T18:52:31Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T18:50:31Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T18:49:06Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T18:48:32Z

Larisayaryzheva: /* Информационный граф */

Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов

2025-11-29T18:47:29Z

Larisayaryzheva: /* Информационный граф */