Метод квадрата сопряженного градиента

В числовой линейной алгебре метод сопряженного градиента-квадрата (CGS) — итерационный алгоритм решения систем линейных уравнений вида $A{\mathbf {x}}={\mathbf {b}}$, особенно в тех случаях, когда вычисление транспонирования $A^{T}$ непрактично. Метод CGS был разработан как усовершенствование метода бисопряженных градиентов .

Фон

Система линейных уравнений $A{\mathbf {x}}={\mathbf {b}}$ состоит из известной матрицы $A$ и известный вектор ${\mathbf {b}}$. Решить систему – значит найти значение неизвестного вектора. ${\mathbf {x}}$. Прямой метод решения системы линейных уравнений заключается в использовании обратной матрицы $A$, затем вычислить ${\mathbf {x}}=A^{-1}{\mathbf {b}}$. Однако вычисление обратного процесса требует больших вычислительных затрат. Поэтому обычно используются итерационные методы. Итеративные методы начинаются с предположения ${\mathbf {x}}^{(0)}$, и на каждой итерации предположение улучшается. Как только разница между последовательными предположениями становится достаточно малой, метод сходится к решению.

Как и в случае с методом сопряженного градиента , методом двусопряженного градиента и аналогичными итерационными методами решения систем линейных уравнений, метод CGS можно использовать для поиска решений задач оптимизации с несколькими переменными , таких как анализ потока мощности , оптимизация гиперпараметров и лицевая оптимизация. признание .

Алгоритм

Алгоритм следующий:

1. Выберите первоначальное предположение ${\mathbf {x}}^{(0)}$
2. Вычислить остаток ${\mathbf {r}}^{(0)}={\mathbf {b}}-A{\mathbf {x}}^{(0)}$
3. Выбирать ${\tilde {\mathbf {r}}}^{(0)}={\mathbf {r}}^{(0)}$
4. Для $i=1,2,3,\dots$ делать:
   1. $\rho ^{(i-1)}={\tilde {\mathbf {r}}}^{T(i-1)}{\mathbf {r}}^{(i-1)}$
   2. Если $\rho ^{(i-1)}=0$, метод не работает.
   3. Если $i=1$:
      1. ${\mathbf {p}}^{(1)}={\mathbf {u}}^{(1)}={\mathbf {r}}^{(0)}$
   4. Еще:
      1. $\beta ^{(i-1)}=\rho ^{(i-1)}/\rho ^{(i-2)}$
      2. ${\mathbf {u}}^{(i)}={\mathbf {r}}^{(i-1)}+\beta _{i-1}{\mathbf {q}}^{(i-1)}$
      3. ${\mathbf {p}}^{(i)}={\mathbf {u}}^{(i)}+\beta ^{(i-1)}({\mathbf {q}}^{(i-1)}+\beta ^{(i-1)}{\mathbf {p}}^{(i-1)})$
   5. Решать $M{\hat {\mathbf {p}}}={\mathbf {p}}^{(i)}$, где $M$ является предварительным кондиционером.
   6. ${\hat {\mathbf {v}}}=A{\hat {\mathbf {p}}}$
   7. $\alpha ^{(i)}=\rho ^{(i-1)}/{\tilde {\mathbf {r}}}^{T}{\hat {\mathbf {v}}}$
   8. ${\mathbf {q}}^{(i)}={\mathbf {u}}^{(i)}-\alpha ^{(i)}{\hat {\mathbf {v}}}$
   9. Решать $M{\hat {\mathbf {u}}}={\mathbf {u}}^{(i)}+{\mathbf {q}}^{(i)}$
   10. ${\mathbf {x}}^{(i)}={\mathbf {x}}^{(i-1)}+\alpha ^{(i)}{\hat {\mathbf {u}}}$
   11. ${\hat {\mathbf {q}}}=A{\hat {\mathbf {u}}}$
   12. ${\mathbf {r}}^{(i)}={\mathbf {r}}^{(i-1)}-\alpha ^{(i)}{\hat {\mathbf {q}}}$
   13. Проверьте сходимость: если есть сходимость, завершите цикл и верните результат.

См. также

• Метод бисопряженного градиента
• Метод стабилизации бисопряженного градиента
• Обобщенный метод минимальной невязки