Участник:Dlitvinov/Алгоритм Ланцоша для арифметики с плавающей точкой с выборочной ортогонализацией: различия между версиями
Dlitvinov (обсуждение | вклад) |
Dlitvinov (обсуждение | вклад) |
||
Строка 63: | Строка 63: | ||
Величина погрешности <math>\beta_k \Vert v_i(k) \Vert</math> считается малой, если она меньше, чем <math>\sqrt{\epsilon} \Vert A \Vert_2</math>, так как в этом случае, согласно теореме Пейджа, компонента <math>\Vert y_{i,k}^T q_{k+1} \Vert = \Vert y_{i,k}^T z \Vert / \Vert z \Vert_2</math> скорее всего превосходит уровень <math>\sqrt{\epsilon}</math> (на практике используется <math>\Vert T_k \Vert_2</math> вместо <math>\Vert A \Vert_2</math>, так как первое известно, а второе не всегда). | Величина погрешности <math>\beta_k \Vert v_i(k) \Vert</math> считается малой, если она меньше, чем <math>\sqrt{\epsilon} \Vert A \Vert_2</math>, так как в этом случае, согласно теореме Пейджа, компонента <math>\Vert y_{i,k}^T q_{k+1} \Vert = \Vert y_{i,k}^T z \Vert / \Vert z \Vert_2</math> скорее всего превосходит уровень <math>\sqrt{\epsilon}</math> (на практике используется <math>\Vert T_k \Vert_2</math> вместо <math>\Vert A \Vert_2</math>, так как первое известно, а второе не всегда). | ||
+ | |||
+ | == Вычислительное ядро алгоритма == | ||
+ | |||
+ | У описанного алгоритма два ядра, на которые приходится основное время работы алгоритма: | ||
+ | |||
+ | * Вычисление вектора <math>z = A q_j - O(n^2)</math> операций умножения | ||
+ | * Выборочная переортогонализация <math>z = z - (y_{i,k} ^ T z) y_{i,k} - O(n k^2)</math> операций умножения (на практике коэффициент маленький, что обеспечивает бОльшую скорость выполнения алгоритма, чем в случае с полной переортогонализацией) | ||
+ | |||
+ | == Макроструктура алгоритма == | ||
+ | |||
+ | В описанном алгоритме можно выделить следующие макрооперации: | ||
+ | |||
+ | * Умножение матрицы на вектор | ||
+ | * Сложение, перемножение и умножение на число для векторов | ||
+ | * Вычисление скалярного произведения и норм векторов | ||
+ | * Добавление столбца к матрице | ||
+ | |||
+ | == Схема реализации последовательного алгоритма == |
Версия 16:35, 16 ноября 2016
Автор статьи: Литвинов Д.А., студент, кафедра исследования операций, 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] - заданная симметричная матрица, [math]b[/math] - вектор начального приближения метода Ланцоша. Тогда алгоритм Ланцоша вычисления собственных векторов и собственных значений матрицы [math]A[/math] с выборочной ортогонализацией записывается следующим образом:
[math] \begin{align} q_1 = & b / \Vert b \Vert_2, \; \beta_0 = 0,\; q_0 = 0\\ for \; & j = 1 \; to \; k \\ & z = A\,q_j\\ & \alpha_j = q_j^T z\\ & z = z - \alpha_j q_j - \beta_{j-1}q_{j-1}\\ & for \; i \le k \\ & \; \; \; if \; \beta_k \|v_i (k)\| \le \sqrt{\epsilon} \Vert T_k \Vert_2\\ & \; \; \; \; \; \; z = z - (y_{i,k} ^ T z) y_{i,k}\\ & end \; for\\ & \beta_j = \Vert z \Vert_2\\ & if \; \beta_j = 0 \; then\\ & \; \; \; Quit\; the\; algorithm\\ & q_{j+1} = z / \beta_j\\ end \; & for \end{align} [/math]
Где [math]v_i[/math] - это столбцы ортогональной матрицы [math]V[/math] из спектрального разложения [math]T_k = V \Lambda V^T[/math], а [math]y_{k,i} = Q_k v_i[/math] - столбцы матрицы [math]Q_k V[/math] - векторы Ритца.
Согласно теореме Пейджа, [math]y_{k,i}^T q_{k+1} = O(\epsilon \Vert A \Vert_2) / \beta_k \Vert v_i(k) \Vert[/math], то есть компонента [math]y_{k,i}^T q_{k+1}[/math] вычисленного вектора Ланцоша [math]q_{k+1}[/math] в направлении вектора Ритца [math]y_{k,i} = Q_k v_i[/math] обратно пропорциональна величине [math]\beta_k \Vert v_i(k) \Vert[/math], являющейся оценкой погрешности для соответствующего числа Ритца. Поэтому, когда число Ритца сходится, а его оценка погрешности приближается к нулю, вектор Ланцоша приобретает большую компоненту в направлении вектора Ритца [math]q_{k,i}[/math], и следует произвести процедуру переортогонализации.
Величина погрешности [math]\beta_k \Vert v_i(k) \Vert[/math] считается малой, если она меньше, чем [math]\sqrt{\epsilon} \Vert A \Vert_2[/math], так как в этом случае, согласно теореме Пейджа, компонента [math]\Vert y_{i,k}^T q_{k+1} \Vert = \Vert y_{i,k}^T z \Vert / \Vert z \Vert_2[/math] скорее всего превосходит уровень [math]\sqrt{\epsilon}[/math] (на практике используется [math]\Vert T_k \Vert_2[/math] вместо [math]\Vert A \Vert_2[/math], так как первое известно, а второе не всегда).
1.3 Вычислительное ядро алгоритма
У описанного алгоритма два ядра, на которые приходится основное время работы алгоритма:
- Вычисление вектора [math]z = A q_j - O(n^2)[/math] операций умножения
- Выборочная переортогонализация [math]z = z - (y_{i,k} ^ T z) y_{i,k} - O(n k^2)[/math] операций умножения (на практике коэффициент маленький, что обеспечивает бОльшую скорость выполнения алгоритма, чем в случае с полной переортогонализацией)
1.4 Макроструктура алгоритма
В описанном алгоритме можно выделить следующие макрооперации:
- Умножение матрицы на вектор
- Сложение, перемножение и умножение на число для векторов
- Вычисление скалярного произведения и норм векторов
- Добавление столбца к матрице