Кратко: для плотной симметрической матрицы наиболее надёжный и универсальный подход — ортогональное преобразование в тридиагональный вид + решение спектра тридиагональной матрицы специальным методом (implicit QR с Wilkinson‑сдвигом, divide‑and‑conquer или MRRR). Для разреженных или когда нужны только несколько собственных значений — итеративные методы (Lanczos/ARPACK, LOBPCG, shift‑and‑invert). Далее — предложение алгоритма и анализ по точности, сходимости и численной устойчивости.
Алгоритм (рекомендация для плотной матрицы):
1) Тридиагонализация:
- Преобразовать $A\in {\mathbb{R}}^{n\times n}$ ортогонной подобием с помощью отражений Хаусхолдера: $A=T=Q^{T}AQ$, где $T$ — симметричная тридиагональная.
- Стоимость: $\mathcal{O}(n^3)$ операций (основной вклад).
- Устойчивость: ортогональные преобразования численно стабильны и не увеличивают относительную погрешность; операция назад‑устойчива.
2) Вычисление собственных значений тридиагональной матрицы:
Варианты:
a) implicit symmetric QR с Wilkinson‑сдвигом:
- Стоимость: для всей матрицы обычно $\mathcal{O}(n^2)$ (итерации на тридиагонал).
- Сходимость: быстрый (локально сверхлинейный, на практике быстро дефлирует при малых внедиагональных элементах).
- Устойчивость: метод обратно устойчив для собственных значений.
b) Divide‑and‑Conquer (Cuppen, LAPACK DSTEDC):
- Стоимость: примерно $\mathcal{O}(n^2)$ с большим коэффициентом; эффективен при вычислении всех собственных значений и векторов.
- Преимущества: высокая скорость и хорошая параллелизация; иногда потеря относительной точности для мелких (по модулю) собственных значений.
c) MRRR (multiple relatively robust representations, LAPACK DSTEMR):
- Стоимость: $\mathcal{O}(n^2)$ в среднем.
- Преимущества: обеспечивает хорошую относительную точность особенно для кластеров и малых собственных значений; экономичен по памяти; алгоритм часто предпочтителен при строгих требованиях к относительной погрешности.
Выбор: для общего применения — Householder + MRRR (или divide‑and‑conquer, если важна скорость и нужен набор векторов).
Альтернатива для больших разреженных матриц или когда нужны только несколько экстремальных/внутренних собственных значений:
- Итеративный Lanczos (с явной/частичной или полной реортогонализацией), ARPACK, LOBPCG, или shift‑and‑invert для внутренних значений.
- Стоимость приблизительно $\mathcal{O}(k\cdot \text{cost\_matvec})$ где $k$ — число итераций/искомых значений; память и стабильность зависят от реортогонализации.
- Проблемы: потеря ортогональности приводит к спуффинг‑собственным значениям; требует селективной/полной реортогонализации либо перезапуска; shift‑and‑invert требует решения линейных систем (нужно эффективное предобусловливание).
Точность и теоремы устойчивости:
- Погрешности собственных значений подчиняются оценкам Возврата (Weyl, Hoffman‑Wielandt):
$|{\tilde{\lambda }}_i-{\lambda }_i|\le \Vert E{\Vert }_2$ (Weyl), и
${\sum }_i({\tilde{\lambda }}_i-{\lambda }_i{)}^2\le \Vert E{\Vert }_F^2$ (Hoffman‑Wielandt),
где ${\tilde{\lambda }}_i$ — вычисленные, а $E$ — матрица возмущения.
- В большинстве упомянутых методов вычисленные собственные значения являются точными собственными значениями некоторой матрицы $A+E$ с $\Vert E{\Vert }_2\le Cn\epsilon \Vert A{\Vert }_2$ (где $\epsilon$ — машинный эпсилон, $C$ — умеренный констант). То есть алгоритмы обратно устойчивы по спектру.
- Для относительной точности малых собственных значений предпочтительна MRRR; divide‑and‑conquer и QR гарантируют хорошую абсолютную точность, но могут хуже давать относительную точность для сильно расходящихся спектров.
Сходимость (коротко):
- Тридиагонализация — прямой (конечный) процесс.
- Implicit QR с Wilkinson‑сдвигом обычно быстро сходится и выполняет дефляции; асимптотически сходимость для простых собственных значений сверхлинейная/быстрая.
- Lanczos: сходимость зависит от спектральных зазоров; экстремальные собственные значения сходятся быстро, внутренние — медленнее; shift‑and‑invert улучшает сходимость за счёт трансформации спектра.
Численная стабильность и практические рекомендации:
- Всегда сначала тридиагонализируйте ортогонально (Householder) для плотных матриц — это даёт стабильный вариант входных данных для итераций.
- Для вычисления всех собственных значений: используйте MRRR (DSTEMR) если нужна хорошая относительная точность, или divide‑and‑conquer (DSTEDC) для скорости/параллелизма; implicit QR (DSTEV) — прост и надёжен, но медленнее.
- Для больших разреженных задач и частичного спектра — Lanczos/ARPACK/LOBPCG с контролем реортогонализации и (по возможности) предобусловливанием/shift‑and‑invert.
- Если спектр содержит очень близкие (кластеризованные) собственные значения, ожидайте ухудшение количественной точности; MRRR лучше справляется с кластерами.
- При необходимости улучшения точности — использовать более точную арифметику (quad) или уточнение Рэйли‑Ритца/итеративное уточнение.
Краткая сводка по сложности:
- Тридиагонализация: $\mathcal{O}(n^3)$.
- Решение тридиагонала (все собственные значения): ≈$\mathcal{O}(n^2)$ (implicit QR / DC / MRRR).
- Lanczos для $k$ значений: $\mathcal{O}(k\cdot \text{cost\_matvec})$.
Практическая рекомендация: для плотных больших $n$ — Householder → MRRR (если нужна относительная точность) или → divide‑and‑conquer (если нужна скорость/параллелизация). Для разреженных/частичных спектров — Lanczos/ARPACK/LOBPCG с контролем ортогональности и, при необходимости, shift‑and‑invert.