Почему CG требует symmetric positive definite матрицу?

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

Почему CG решает 2D систему за два шага?

В точной арифметике CG минимизирует по растущему Krylov subspace и завершает работу максимум за n итераций для n-мерной SPD системы. В 2D демо решение достигается не более чем за два независимых направления.

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

SPD система Ax=b как минимизация квадратичной формы: контуры, CG vs steepest descent, residual norm и condition number.

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

Графики

О модели

Метод сопряжённых градиентов (CG) решает симметричные положительно определённые системы Ax=b через минимизацию квадратичной функции f(x)=1/2 x^T A x - b^T x. Симулятор использует 2D SPD matrix, поэтому геометрия видна напрямую: эллипсы — уровни квадратичной формы, точное решение — центр эллипсов, residual равен b-Ax, а CG выбирает A-conjugate направления поиска. Для сравнения из той же стартовой точки показан steepest descent, так что легко увидеть zig-zag и влияние condition number.

Для кого: Numerical linear algebra, scientific computing, optimization, PDE solvers и курсы прикладной математики.

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

Conjugate gradient
SPD matrix
Residual norm
Quadratic minimization
Condition number
Steepest descent

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

Для symmetric positive definite матрицы система Ax=b эквивалентна минимизации f(x)=1/2 x^T A x − b^T x. Контуры этой функции — эллипсы, а решение x\* находится в их центре. Conjugate gradient строит направления p_k, сопряжённые в A-inner product, и выбирает шаг α_k=(r_k^T r_k)/(p_k^T A p_k). В 2D точной арифметики достаточно двух итераций; большой κ растягивает эллипсы и замедляет похожие методы вроде steepest descent.

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

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)

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

Почему CG требует symmetric positive definite матрицу?: SPD делает квадратичную функцию строго выпуклой и задаёт A-inner product для сопряжённых направлений. Без этих свойств классические гарантии CG не работают.
Почему CG решает 2D систему за два шага?: В точной арифметике CG минимизирует по растущему Krylov subspace и завершает работу максимум за n итераций для n-мерной SPD системы. В 2D демо решение достигается не более чем за два независимых направления.

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

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

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

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

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

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

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

FEM-решатель Пуассона (2D)

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

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

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

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

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

Ковариационный эллипс и SVD-понижение размерности: главные компоненты, explained variance и ошибка rank-1 reconstruction.

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

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

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

Сравнение SGD, momentum и Adam на 2D loss landscape: learning rate, curvature, устойчивость и траектории итераций.

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

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

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

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

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

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

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

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

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

Графики

О модели

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

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

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

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

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

FEM-решатель Пуассона (2D)

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

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

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

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

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

Графики

О модели

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

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

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