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

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

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

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

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