Участник:Alexbashirov/Алгоритм Ланцоша для точной арифметики

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

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

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

1.1.1 История

Алгоритм Ланцоша является прямым алгоритмом поиска собственных значений симметричной матрицы, разработанным венгерским физиком и математиком XX столетия Корнелием Ланцошем в 1950 году. Алгоритм совмещает в себе два других алгоритма: алгоритм построения подпространства Крылова (который также был создан Ланцошем) и процедуру Рэлея-Ритца приближения собственных значений матрицы. Алгоритм является вариацией степенного метода, позволяющего найти собственные значения и собственные вектора матрицы $n$-го порядка. Однако в алгоритме число итераций ограничено некоторым $k$, где $k\lt \lt n$. Несмотря на заявленную вычислительную эффективность, алгоритм не получил широкого применения в своём первоначальном виде, ввиду его неустойчивости. 20 лет спустя, в 1970 году ученые Ojalvo и Newman показали доработанный алгоритм Ланцоша, который теперь стал устойчивым а также предложили способ выбора вектора начального приближения $v_0$. Полученный последователями Ланцоша алгоритм получил название "Алгоритм Ланцоша с полной переортогонализацией".

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

Алгоритм Ланцоша работает с вещественной симметричной матрицей $A=A^T$, таким образом в памяти достаточно хранить лишь немногим более половины элементов матрицы $A$.

Прежде чем переходить к описанию алгоритма, следует упомянуть следующие понятия: подпространство Крылова и процесс Рэлея-Ритца, о которых уже было сказано в исторической справке выше. Подпространством Крылова называется набор векторов$K_n =[b,Ab,A^2b,...,A^{n-1}b]$. Начав свою работу с произвольного вектора $b_0$, степенной метод вычисляет вектора $Ab, A^2b,...,A^{n-1}b$ итерационно сохраняя полученный результат в вектор $b$. Полученная последовательность векторов сходится к собственному вектору, отвечающему максимальному собственному значению $\lambda_1$. Однако, использование лишь последнего полученного вектора и потеря всех предшествующих посчитанных величин не всегда является наилучшим выбором. Поэтому сохранив все вектора и объединим их в одну матрицу мы получим так называемую матрицу Крылова:

$K_n = [b,Ab,A^2b,...,A^{n-1}b]$.

Столбцы получившейся матрицы не ортогональны, однако их можно ортогонализировать, применив процесс Грамма-Шмидта. Получившееся вектора будут составлять базис подпространства Крылова $K_n$. Можно ожидать, что вектора полученного базиса будут достаточно хорошо приближать $n$ собственных векторов, отвечающих $n$ наибольшим собственным значения.

1.1.3 Вычислительное ядро алгоритма

Вычислительным ядром алгоритма Ланцоша, то есть наиболее ресурсно-затратной частью алгоритма, является шаг на котором на каждой итерации происходит перемножение матрицы $A$ на вектор $q_j$, полученный на предыдущей итерации. Полученный в результате умножения вектор обозначается $z$:

$z=Aq_j$.

1.1.4 Макроструктура алгоритма

Как уже говорилось в математическом описании, алгоритм объединяет в себе два алгоритма: метод построения подпространства Крылова и процедуру поиска собственных значений трехдиагональной матрицы (процес Рэлея-Ритца).

Первую составную часть (алгоритм построения подпространства Крылова) представляет итерационный процесс построения матрицы $Q_j=[q_1,q_2,...q_k]$ из $j$ ортонормированных вектров Ланцоша и последующее формирование трехдиагональной матрицы $T_j=Q_j^TAQ_j$. Число таких векторов и, следовательно, размер матрицы растет с каждой итерацией. Итерационный процесс завершается при $j=k$.

На долю второй части алгоритма приходится поиск собственных значений и соответствующих им собственных векторов матрицы $T_j=Q_j^TAQ_j$, полученной в первой части.