Участник:Dlitvinov/Алгоритм Ланцоша для арифметики с плавающей точкой с выборочной ортогонализацией
Автор статьи: Литвинов Д.А., студент, кафедра исследования операций, 611 группа - все описанные разделы.
| Алгоритм Ланцоша для арифметики с плавающей точкой с выборочной ортогонализацией | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]0[/math] |
| Объём входных данных | [math]0[/math] |
| Объём выходных данных | [math]0[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]0[/math] |
| Ширина ярусно-параллельной формы | [math]0[/math] |
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм Ланцоша применяется для поиска небольшого числа собственных значений большой разреженной симметричной матрицы и объединяет метод Ланцоша для построения крыловского подпространства с процедурой Рэлея-Ритца интерпретации собственных значений некоторой вычисляемой матрицы как приближений к собственным значениям заданной матрицы.
Пусть [math]Q = [Q_k,Q_u][/math] - ортогональная матрица порядка [math]n[/math], причем [math]Q_k[/math] и [math]Q_u[/math] имеют соответственно размеры [math]n \times k[/math] и [math]n \times (n-k)[/math]. Столбцы матрицы [math]Q_k[/math] вычисляются методом Ланцоша. Запишем следующие соотношения:
[math]T = Q^T A Q = [Q_k, Q_u]^T A [Q_k, Q_u] = \left[ \begin{array}{cc} Q_k^T A Q_k & Q_k^T A Q_u\\ Q_u^T A Q_k & Q_u^T A Q_u \end{array} \right] = \left[ \begin{array}{cc} T_{k} & T_{ku}^T\\ T_{ku} & T_{u} \end{array} \right][/math]
Метод Рэлея-Ритца заключается в интерпретации собственных значений матрицы [math]T_k = Q_k^T A Q_k[/math] как приближенных к собственным значениям матрицы [math]A[/math]. Эти приближения называются числами Ритца. Если [math]A = V \Lambda V^T[/math] есть спектральное разложение матрицы [math]T_k[/math], то столбцы матрицы [math]Q_k V[/math] являются приближениями соответствующих собственных векторов и называются векторами Ритца.
Числа и векторы Ритца являются оптимальными приближениями к собственным значениям и собственным векторам матрицы [math]A[/math]: минимум величины [math]\Vert A P_k - P_k D \Vert_2[/math] достигается при [math]P_k = Q_k V[/math] и [math]D = \Lambda[/math] и равен [math]\Vert T_ku \Vert_2[/math].
При применении метода Ланцоша в арифметике с плавающей точкой ортогональность в вычисленных векторах Ланцоша [math]q_k[/math] пропадает из-за ошибок округления. Для того чтобы поддерживать ортогональность, проводится повторный процесс ортогонализации Грама-Шмидта. Доказано, что векторы [math]q_k[/math] теряют ортогональность весьма систематическим образом, приобретая большие компоненты в отношении уже сошедшихся векторов Ритца. Поэтому можно выборочно ортогонализировать векторы [math]q_k[/math] вместо того, чтобы на каждом шаге ортогонализировать вектор ко всем более ранним векторам, как это делается при полной ортогонализации. Таким образом достигается очень высокая степень ортогонализации векторов Ланцоша, и затрачивается очень небольшая дополнительная работа.
1.2 Математическое описание алгоритма
Пусть [math]A[/math] - заданная
