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

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

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

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

История

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

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

Алгоритм Ланцоша работает с вещественной симметричной матрицей [math]\displaystyle{ A=A^T }[/math], таким образом в памяти достаточно хранить лишь немногим более половины элементов матрицы [math]\displaystyle{ A }[/math].

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

[math]\displaystyle{ K_n = [b,Ab,A^2b,...,A^{n-1}b] }[/math].

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

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

Вычислительным ядром алгоритма Ланцоша, то есть наиболее ресурсно-затратной частью алгоритма, является шаг на котором на каждой итерации происходит перемножение матрицы [math]\displaystyle{ A }[/math] на вектор [math]\displaystyle{ q_j }[/math], полученный на предыдущей итерации. Полученный в результате умножения вектор обозначается [math]\displaystyle{ z }[/math].