Задача: решить систему $Ax=b$, где $A$ — квадратная матрица. Кратко о методах, стоимости и численной устойчивости.
1) Обратная матрица
- Формула: $x=A^{-1}b$.
- Стоимость: вычисление $A^{-1}$ — $\mathcal{O}(n^3)$; умножение на $b$ — $\mathcal{O}(n^2)$.
- Устойчивость: вычисление явной $A^{-1}$ обычно менее устойчиво и избыточно; ошибки при обращении могут сильно усилиться. Не рекомендуется для прямого решения; допустимо только если действительно нужен сам $A^{-1}$ и число правых частей очень велико (хотя и в этом случае предпочтут факторизацию).
2) Метод Гаусса (прямое исключение)
- Выполнение на расширенной матрице $[A|b]$ с последовательным исключением.
- Схема с частичным пивотированием (GEPP) — стандарт: делает метод практически устойчивым (backward stable).
- Стоимость: $\mathcal{O}(n^3)$.
- Устойчивость: GEPP даёт небольшую обратную погрешность: вычисленное решение $\hat{x}$ удовлетворяет $(A+\Delta A)\hat{x}=b$ с $\Vert \Delta A\Vert /\Vert A\Vert =O(\epsilon )$. Относительная ошибка ограничивается примерно $\kappa (A)\epsilon$ (см. ниже).
3) LU‑разложение
- Факторизация: либо $A=LU$, либо с пивотом $PA=LU$. Решение для одной правой части: сначала $Ly=Pb$, затем $Ux=y$.
- Стоимость: факторизация $\mathcal{O}(n^3)$; каждая последующая подстановка — $\mathcal{O}(n^2)$.
- Устойчивость: LU с частичным пивотированием эквивалентен GEPP по устойчивости (backward stable). LU без пивотирования может быть неустойчивой, но безопасна для диагонально доминирующих или специально структурированных матриц.
- Предпочтение: если нужно решить систему для многих правых частей, факторизация $LU$ выгоднее, чем повторный Гаусс или вычисление $A^{-1}$.
4) Специализированные методы
- Холеcкий для симметричных положительно определённых $A$: $A=R^{T}R$. Стоимость ~$\frac{1}{3}{n}^3$, более точный и стабильный выбор для SPD матриц.
- SVD / псевдообратная: $A=U\Sigma V^T$, даёт наилучшую устойчивость при плохо обусловленных матрицах и позволяет корректно обработать вырожденные случаи; дорого ($\mathcal{O}(n^3)$).
- Итеративные методы (CG, GMRES и др.): предпочтительны для больших разреженных систем; устойчивость и скорость зависят от предобуславливания.
5) Условность и оценка ошибок
- Число обусловленности: $\kappa (A)=\Vert A\Vert \Vert A^{-1}\Vert$.
- При backward‑stable методе относительная ошибка примерно ограничена $\frac{\Vert \hat{x}-x\Vert }{\Vert x\Vert }\lesssim \kappa (A){\epsilon }_{\mathrm{mach}}$. При больших $\kappa (A)$ решения плохо определены независимо от метода.
- Если $A$ плохо обусловлена, предпочтительнее SVD или регуляризация, а не явное обращение.
Краткие рекомендации по выбору:
- Общая задача, плотная матрица, одна или несколько правых частей: LU с частичным пивотированием (или Гаусс с пивотированием) — стандартный выбор.
- Много правых частей: факторизация $LU$ (или Cholesky для SPD).
- $A$ симметрична и положительно определённа: Cholesky.
- Плохо обусловлена или вырожденна: SVD/псевдообратная (регуляризация).
- Большие разреженные системы: итеративные методы с предобуславливателем.
- Никогда не вычисляйте $A^{-1}$ просто для решения $Ax=b$ — решайте через факторизацию; вычисление обратной матрицы хуже по устойчивости и обычно дороже по памяти.