Кратко и по сути — сравнение по устойчивости и эффективности.
Общие замечания
- Прямые методы (Гаусс / LU / Cholesky) дают точное (в машинной арифметике — обратно-устойчивое) решение за фиксированное число операций; итерационные дают приближение, сходимость зависит от спектра матрицы и предобуславливания.
- Сложность и память в основном зависят от плотности: для плотной $n\times n$ матрицы прямые методы $O(n^3)$ и память $O(n^2)$. Итерационные шаги обычно стоят $O(\text{nnz})$ (число ненулей в строке) за итерацию и память $O(\text{nnz})$.
Устойчивость
- LU с частичным выбором главного элемента (GEPP) обычно обратно-устойчив: погрешности ограничены машинной точностью умноженной на полиномиальную функцию размера. Cholesky для симметричных положительно-определённых (SPD) матриц стабильна без сдвигов.
- Прямые разложения чувствительны к заполнению (fill‑in), но не к числу итераций — решение получается «одним» факторизованием.
- Итерационные методы (CG, GMRES, BiCGStab и т.п.) не гарантированно устойчивы без предобусловливания: сходимость зависит от условности $\kappa (A)=\Vert A\Vert \Vert A^{-1}\Vert$ и распределения собственных значений. Для CG есть оценка сходимости
$\Vert x_k-x^{\ast }{\Vert }_A\le 2{\left(\frac{\sqrt{\kappa (A)}-1}{\sqrt{\kappa (A)}+1}\right)}^k\Vert x_0-x^{\ast }{\Vert }_A.$ Для GMRES сходимость связана с полиномиальной аппроксимацией спектра, нет простого универсального шага.
Эффективность (малые матрицы)
- Малые плотные (например $n$ до нескольких тысяч, в зависимости от ресурса): LU/Гаусс (с частичным парциальным выбором) или Cholesky (если SPD) — предпочтительны: простота, надёжность, эффективные BLAS-реализации. Если требуется много правых частей, LU разложение особенно выгодно (факторизация один раз, затем $O(n^2)$ на каждый RHS).
- Малые разрежённые: если матрица очень разреженная и fill‑in при факторизации мал — прямой метод OK; если факторизация даёт сильное заполнение — лучше итерационный.
Эффективность (большие разрежённые матрицы)
- Итерационные методы обычно предпочтительны: каждая итерация стоит $O(\text{nnz})$, масштабируют память и время линейно по количеству ненулей. Но число итераций зависит от $\kappa (A)$ и спектра.
- Для SPD: Conjugate Gradient (CG) — стандарт (эффективен, память невысока).
- Для несимметричных: GMRES (с рестартом), BiCGStab, QMR и т.п.; GMRES даёт лучшее приближение, но требует хранить базис (градуирует память), поэтому часто используют GMRES(m) или BiCGStab.
- Предобусловливание критично: ILU/IC (неполное LU/Cholesky), многосеточные методы (AMG/GMG), простые методы (Jacobi, SSOR) — выбор зависит от структуры. Хорошее предобусловливание может значительно уменьшить число итераций и сделать итерационные методы намного быстрее прямых.
Проблемы прямых методов на больших разрежённых матрицах
- Fill‑in: фактор $L,U$ может стать плотным, что ведёт к большой памяти и времени; в худшем случае временная и памятьовые оценки приближаются к плотным $O(n^2)$ и $O(n^3)$.
- Параллелизм: многокритичные структуры (многофронтальная факторизация) параллелятся хуже, чем спарс-матричные операции в итерационных методах в крупном масштабе.
Практические рекомендации
- Малые плотные: LU/Cholesky (используйте высокопроизводительные BLAS/LAPACK).
- Малые разрежённые и/или множество правых частей: если fill‑in небольшой — прямой LU/Cholesky; иначе итерационные.
- Большие разрежённые: итерационные методы с подходящим предобусловливанием. Для PDE/грид‑задач рассмотрите мультигрид/AMG (часто сложность $\approx O(n)$).
- Если матрица SPD — CG + IC/AMG; если несимметричная — GMRES (с рестартом) или BiCGStab + ILU/AMG.
- Если итерационные не сходятся или предобусловливание недоступно, а размер ещё сопоставим с возможностями памяти — рассмотреть разложение LU с минимизацией fill‑in (методы упорядочивания: AMD, METIS).
Коротко по устойчивости/эффективности:
- Прямые: высокая надежность в численной устойчивости (при парциальном выборе) для малых/умеренных задач; плохая масштабируемость по времени/памяти при больших разрежённых матрицах из‑за fill‑in.
- Итерационные: лучше масштабируются для больших разрежённых систем (экономия по памяти и времени на итерацию), но их сходимость и «устойчивость» зависят от условности и качества предобуславливания.
Если нужно, могу порекомендовать конкретные методы/предобуславливатели для вашей задачи при указании: размер $n$, nnz, симметрия и характер коэффициентов.