1_15.ppt

Ланцоша
1.15. Диагонализация больших матриц

12 частиц:

при решении квантовых многочастичных задач редко приходится вычислять все

собственные пары (собственный вектор и отвечающее ему собственное значение) гамильтоновой матрицы
Обычные постановки задач:
Вычисление некоторых собственных значений, принадлежащих некоторому интервалу, или крайних собственных значений (например, низ спектра)
Нахождение некоторых собственных пар
Определение всех собственных значений или большого их количества без вычисления собственных векторов
Одним из самых мощных методов диагонализации симметричных матриц является алгоритм Ланцоша

векторы s1, s2, … :

Множество S называется образующим множеством подпространства

Σ
Образующее множество, содержащее наименьшее количество векторов, называется базисом подпространства, а количество векторов базиса называется размерностью подпространства
Если базисные векторы ортонормированны, то базис называется ортонормированным
Подпространство Σ инвариантно относительно A, если для любого вектора x из Σ следует, что вектор Ax также принадлежит Σ

упорядоченные в виде матрицы Q размера n×m
Матрица Рэлея C –

сужение A на Σ:






Матрица Рэлея является симметричной
Определение собственных пар матрицы A может быть осуществлено путем диагонализации матрицы C меньшего размера:

к собственным парам матрицы A

1. Ортонормализация матрицы Q, вычисление матрицы

Рэлея

Матрица Рэлея H почти инвариантна относительно A
2. Определение требуемого количества собственны пар матрицы H:

3. Полученные значения Ритца ?? будут наилучшими приближениями к собственным значениям матрицы A, а векторы Ритца

– соответствующими приближениями к собственным векторам матрицы A

m подпространство Крылова будет посчти инвариантно относительно A
В этом случае

матрица Рэлея является трехдиагональной, и вычисление пар Ритца существенно упрощается
Столбцы матрицы Q могут быть связаны друг с другом с помощью трехчленных рекуррентных соотношений, позволяющих вычислять новые векторы базиса Q
Алгоритм Ланцоша обычно использует последовательность подпространств Крылова

и вычисляет пары Ритца матрицы A, отвечающие каждому из этих подпространств. Сходимость значений собственных пар обычно оказывается достаточно быстрой:

с использованием априорной информации о собственных векторах матрицы A:

1. Пополнение

ортонормированного базиса:


2. Вычисление промежуточной невязки:

3. Вычисление очередного диагонального элемента:

4. Завершение вычисления невязки:

5. Вычисление нормы невязки:

норма вектора невязки:

Существуют версии алгоритма Ланцоша, предназначенные для отыскания крайних

собственных значений, некоторых внутренних собственных значений и даже всех собственных значений симметричных или эрмитовых матриц очень больших размеров, некоторые версии алгоритма позволяют вычислять и соответствующие собственные векторы
При практической реализации алгоритма Ланцоша возникают погрешности, связанные с машинной точностью обработки чисел двойной точности. Для решения этой проблемы разработаны специальные модификации алгоритма, производящие переортогонализацию векторов в зависимости от величины погрешности

i=m определяется вектор невязки: