Почему сопряжённые градиенты требуют симметричную положительно определённую матрицу?

СПД делает квадратичную функцию строго выпуклой и задаёт A-скалярное произведение для сопряжённых направлений. Без этих свойств классические гарантии метода не работают.

Почему двумерная система решается за два шага?

В точной арифметике метод минимизирует по растущему подпространству Крылова и завершает работу максимум за n итераций для n-мерной СПД-системы. В двумерном демо решение достигается не более чем за два независимых направления.

Чем сопряжённые градиенты лучше наискорейшего спуска?

Наискорейший спуск идёт вдоль −∇f и на вытянутых эллипсах зигзагает. Сопряжённые направления не повторяют уже выбранные A-направления, поэтому на плохо обусловленной чаше сходимость заметно быстрее.

Метод сопряжённых градиентов

СПД-система Ax=b как минимизация квадратичной формы: линии уровня, сопряжённые градиенты против наискорейшего спуска, норма невязки и число обусловленности.

В точной арифметике CG достигает 2D решения максимум за две итерации. Дополнительные итерации здесь в основном показывают residual на уровне roundoff и отличие траектории от steepest descent.

Графики

О модели

Система Ax = b с симметричной положительно определённой матрицей эквивалентна минимизации f(x) = ½ xᵀ A x − bᵀ x. В двумерном примере линии уровня — эллипсы, точное решение — их центр, невязка равна b − Ax. Метод сопряжённых градиентов выбирает A-сопряжённые направления поиска. Для сравнения из той же точки показан наискорейший спуск: на вытянутых эллипсах он зигзагает. Число обусловленности κ = λ_max/λ_min задаёт вытянутость чаши. В точной арифметике сопряжённые градиенты заканчивают работу не более чем за n шагов для n-мерной СПД-системы.

Для кого: Численная линейная алгебра, научные вычисления, оптимизация и решатели уравнений в частных производных.

Ключевые понятия

сопряжённые градиенты
СПД-матрица
норма невязки
квадратичная минимизация
число обусловленности
наискорейший спуск

Как это работает

Для симметричной положительно определённой матрицы система Ax=b эквивалентна минимизации f(x)=1/2 x^T A x − b^T x. Линии уровня этой функции — эллипсы, а решение x\* лежит в их центре. Метод сопряжённых градиентов строит направления p_k, сопряжённые в скалярном произведении (·,·)_A, и выбирает шаг α_k=(r_k^T r_k)/(p_k^T A p_k). В двумерном случае при точной арифметике достаточно двух итераций; большое κ вытягивает эллипсы и замедляет родственные методы, например наискорейший спуск.

Основные формулы

CG решает Ax=b, минимизируя f(x)=1/2 x^T A x − b^T x для SPD A

α_k=(r_k^T r_k)/(p_k^T A p_k), β_k=(r_{k+1}^T r_{k+1})/(r_k^T r_k)

Часто задаваемые вопросы

Почему сопряжённые градиенты требуют симметричную положительно определённую матрицу?: СПД делает квадратичную функцию строго выпуклой и задаёт A-скалярное произведение для сопряжённых направлений. Без этих свойств классические гарантии метода не работают.
Почему двумерная система решается за два шага?: В точной арифметике метод минимизирует по растущему подпространству Крылова и завершает работу максимум за n итераций для n-мерной СПД-системы. В двумерном демо решение достигается не более чем за два независимых направления.
Чем сопряжённые градиенты лучше наискорейшего спуска?: Наискорейший спуск идёт вдоль −∇f и на вытянутых эллипсах зигзагает. Сопряжённые направления не повторяют уже выбранные A-направления, поэтому на плохо обусловленной чаше сходимость заметно быстрее.

Продолжите с близкими темами в этой категории — или все 85 в «Визуализация математики».

Вся категория →

НовоеШкольные

Градиентный спуск (2D)

Запустить симулятор

Линии уровня f(x, y) и траектория (x, y) ← (x, y) − η∇f; чаша или эллиптическая впадина.

НовоеУниверситет / научные

МКЭ: уравнение Пуассона (2D)

Запустить симулятор

Треугольные P1-элементы для −Δu = f на квадрате: сборка матриц жёсткости, закреплённые узлы Дирихле или естественный поток Неймана, решение методом сопряжённых градиентов, потенциал как цветная мембрана.

НовоеУниверситет / научные

Геометрия PCA / SVD

Запустить симулятор

Эллипс ковариации и понижение размерности через сингулярное разложение: главные компоненты, объяснённая дисперсия и ошибка восстановления ранга 1.

НовоеУниверситет / научные

Оптимизаторы градиентного спуска

Запустить симулятор

Сравнение SGD, момента и Adam на двумерном рельефе функции потерь: шаг обучения, кривизна, устойчивость и траектории итераций.

НовоеУниверситет / научные

Частицы в поле течения

Запустить симулятор

Синтетическое поле v(x, y, t); перенос с периодическими границами; по желанию сетка стрелок.

НовоеУниверситет / научные

Уравнение теплопроводности: конечные разности

Запустить симулятор

Одномерное u_t = αu_xx: явная FTCS и неявная схема Эйлера назад; меняйте r = αΔt/Δx², наблюдайте взрыв явной схемы при r > 1/2 и сравнивайте численную диффузию.

Метод сопряжённых градиентов

Графики

О модели

Как это работает

Основные формулы

Часто задаваемые вопросы

Похожие симуляторы

Градиентный спуск (2D)

МКЭ: уравнение Пуассона (2D)

Геометрия PCA / SVD

Оптимизаторы градиентного спуска

Частицы в поле течения

Уравнение теплопроводности: конечные разности

Метод сопряжённых градиентов

Графики

О модели

Как это работает

Основные формулы

Часто задаваемые вопросы