Участник:Danyanya/Алгоритм Ланцоша для точной арифметики (без переортогонализации)

Алгоритм Ланцоша для точной арифметики (без переортогонализации)

Основные авторы описания: Д.Р.Слюсарь

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм Ланцоша поиска собственных значений был опубликован Корнелием Ланцошем в 1950 году [1]. Этот итерационный алгоритм применим только к эрмитовым матрицам [math]A[/math]. Метод позволяет за [math]k[/math] итераций вычислять [math]k[/math]-ое приближение собственных значений и собственных векторов исходной матрицы [math]A[/math].

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

На вход алгоритма подается вещественная эрмитова матрица [math]A = A^\dagger[/math] (в вещественном случае - симметрических) ,

[math] A = \begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1\ n-1} & a_{1\ n} \\ a_{12} & a_{22} & a_{23} & \cdots & a_{2\ n-1} & a_{2\ n} \\ a_{13} & a_{23} & a_{33} & \cdots & a_{3\ n-1} & a_{3\ n} \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ a_{1\ n-1} & \cdots & \cdots & a_{n-2\ n-1} & a_{n-1\ n-1} & a_{n-1\ n} \\ a_{1\ n} & \cdots & \cdots & a_{n-2\ n} & a_{n-1\ n} & a_{n\ n} \\ \end{pmatrix} [/math]

Алгоритм Ланцоша соединяет в себя метод Ланцоша построения крыловского подпространства с процедурой Релея-Ритца. Иными словами, из оргонормированных векторов Ланцоша [??] на каждой итерации строится матрица [math]Q_k = [q_1, q_2, \dots, q_k][/math] размерности [math]n \times k[/math]. В качестве приближенных собственных значений матрицы [math]A[/math] берутся числа Ритца, т.е. собственные значения симметричной трехдиагональной матрицы [math]T_k = Q^T_k A Q[/math].

[math] T_k = \begin{pmatrix} \alpha_1 & \beta_1 & 0 & \dots & 0 \\ \beta_1 & \alpha_2 & \beta_2 & \dots & 0 \\ 0 & \beta_2 & \ddots & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & \beta_{k-1} \\ 0 & \dots & \dots & \beta_{k-1} & \alpha_k \end{pmatrix} [/math]

Данный алгоритм является неустойчивым, вследствие чего на практике применяется модифицированный алгоритм Ланцоша с полной переортогонализацией.

1.2 Математическое описание алгоритма

Описание алгоритма на псевдокоде:

 [math]v_1 \leftarrow \, [/math] ортонормированный случайный вектор .
 [math]v_0 \leftarrow 0 \, [/math]
 [math]\beta_1 \leftarrow 0 \, [/math]
 
 for [math]j = 1,2,\cdots,m-1\, [/math]
   [math] w_j \leftarrow A v_j \, [/math]
   [math] \alpha_j \leftarrow  w_j' \cdot v_j  \, [/math]
   [math] w_j \leftarrow w_j' - \alpha_j v_j   - \beta_j v_{j-1} \, [/math]
   [math] \beta_{j+1} \leftarrow \left\| w_j \right\|  \, [/math]
   [math] v_{j+1} \leftarrow w_j / \beta_{j+1}  \, [/math]
 endfor
 
 [math] w_m  \leftarrow A v_m \, [/math]
 [math] \alpha_m \leftarrow  w_m \cdot v_m  \, [/math]
 return

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

1. The IETL Project [2]

2. MatLab

3 Литература

1. Алгоритм Ланцоша (Википедия) [3]

2. Деммель Д. Вычислительная линейная алгебра/Пер. с англ. ХД Икрамова. – 2001.