Алгоритм Ланцоша с выборочной ортогонализацией

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

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

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

Подается вещественная симметричная матрица [math]\displaystyle{ A = A^{T} }[/math],

[math]\displaystyle{ 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]\displaystyle{ b }[/math], являющийся первым приближением собственного вектора, [math]\displaystyle{ k }[/math] - количество собственных значений и собственных векторов, которые мы хотим найти.

На каждой итерации строится матрица [math]\displaystyle{ Q_j = [q_1, q_2, \dots, q_j] }[/math] размерности [math]\displaystyle{ n \times j }[/math], состоящая из ортонормированных векторов Ланцоша. А в качестве приближенных собственных значений берутся числа Ритца, т.е. собственные значения симметричной трехдиагональной матрицы [math]\displaystyle{ T_k = Q^T_k A Q }[/math] размерности [math]\displaystyle{ k \times k }[/math].

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

Он состоит в том, что на каждом шаге проверяется

[math]\displaystyle{  \beta_0=0,q_0=0 }[/math]
[math]\displaystyle{  q_{1} = \frac{b_{j}}{\|b\|_2} }[/math], где [math]\displaystyle{  \|b\|_2 = \sqrt{\sum\limits_{j=1}^{n} b_j^2} }[/math]
[math]\displaystyle{  for\, j=1\,\, to\, \, k\, \, do: }[/math]
    [math]\displaystyle{ z=Aq_j,   }[/math]
    [math]\displaystyle{ \alpha_j=q_j^Tz,  }[/math]
    [math]\displaystyle{ z=z-\alpha_jq_j-\beta_{j-1}q_{j-1},   }[/math]
    [math]\displaystyle{ for\, i=1\,\, to\, \, j-1\, \, do:  }[/math]
        [math]\displaystyle{ if\,  \beta_j|v_i(j)| \leqslant \sqrt{\varepsilon}\|T_j\|  }[/math]
            [math]\displaystyle{ z = z-(y^T_{i,j},z)y_{i,j}  }[/math], где [math]\displaystyle{ y_{i,j} = Q_jv_i }[/math] 
    [math]\displaystyle{ \beta_{j}=\|z\|_2  }[/math]
    [math]\displaystyle{ q_{j+1}=z/\beta_{j},  }[/math]
    Вычисляем собственные значения и собственные векторы полученной матрицы [math]\displaystyle{ T_j }[/math].