Участник:Alexbashirov/Алгоритм Ланцоша для точной арифметики: различия между версиями
| Строка 13: | Строка 13: | ||
Прежде чем переходить к описанию алгоритма, следует упомянуть следующие понятия: подпространство Крылова и процесс Рэлея-Ритца, о которых уже было сказано в исторической справке выше. Подпространством Крылова называется набор векторов<math>K_n =[b,Ab,A^2b,...,A^{n-1}b]</math>. Начав свою работу с произвольного вектора <math>b_0</math>, степенной метод вычисляет вектора <math>Ab, A^2b,...,A^{n-1}b</math> итерационно сохраняя полученный результат в вектор <math>b</math>. Полученная последовательность векторов сходится к собственному вектору, отвечающему максимальному собственному значению <math>\lambda_1</math>. Однако, использование лишь последнего полученного вектора и потеря всех предшествующих посчитанных величин не всегда является наилучшим выбором. Поэтому сохранив все вектора и объединим их в одну матрицу мы получим так называемую '''матрицу Крылова''': | Прежде чем переходить к описанию алгоритма, следует упомянуть следующие понятия: подпространство Крылова и процесс Рэлея-Ритца, о которых уже было сказано в исторической справке выше. Подпространством Крылова называется набор векторов<math>K_n =[b,Ab,A^2b,...,A^{n-1}b]</math>. Начав свою работу с произвольного вектора <math>b_0</math>, степенной метод вычисляет вектора <math>Ab, A^2b,...,A^{n-1}b</math> итерационно сохраняя полученный результат в вектор <math>b</math>. Полученная последовательность векторов сходится к собственному вектору, отвечающему максимальному собственному значению <math>\lambda_1</math>. Однако, использование лишь последнего полученного вектора и потеря всех предшествующих посчитанных величин не всегда является наилучшим выбором. Поэтому сохранив все вектора и объединим их в одну матрицу мы получим так называемую '''матрицу Крылова''': | ||
| − | <math>K_n = [b,Ab,A^2b,...,A^{n-1}b]</math>. | + | <math>K_n = [b,Ab,A^2b,...,A^{n-1}b]</math>. |
| − | + | ||
| + | Столбцы получившейся матрицы не ортогональны, однако теоретически их можно ортогонализировать, применив процесс Грамма-Шмидта. Получившееся вектора будут составлять базис подпространства Крылова | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
== Литература == | == Литература == | ||
Версия 19:53, 15 октября 2016
| Алгоритм Ланцоша для точной арифметики |
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
1.1.1 История
Алгоритм Ланцоша является прямым алгоритмом поиска собственных значений симметричной матрицы, разработанным венгерским физиком и математиком XX столетия Корнелием Ланцошем в 1950 году. Алгоритм совмещает в себе два других алгоритма: алгоритм построения подпространства Крылова (который также был создан Ланцошем) и процедуру Рэлея-Ритца приближения собственных значений матрицы. Алгоритм является вариацией степенного метода, позволяющего найти собственные значения и собственные вектора матрицы [math]n[/math]-го порядка. Однако в алгоритме число итераций ограничено некоторым [math]k[/math], где [math]k\lt \lt n[/math]. Несмотря на заявленную вычислительную эффективность, алгоритм не получил широкого применения в своём первоначальном виде, ввиду его неустойчивости. 20 лет спустя, в 1970 году ученые Ojalvo и Newman показали доработанный алгоритм Ланцоша, который теперь стал устойчивым а также предложили способ выбора вектора начального приближения [math]v_0[/math]. Полученный последователями Ланцоша алгоритм получил название "Алгоритм Ланцоша с полной переортогонализацией".
1.1.2 Описание
Алгоритм Ланцоша работает с вещественной симметричной матрицей [math]A=A^T[/math], таким образом в памяти достаточно хранить лишь немногим более половины элементов матрицы [math]A[/math].
Прежде чем переходить к описанию алгоритма, следует упомянуть следующие понятия: подпространство Крылова и процесс Рэлея-Ритца, о которых уже было сказано в исторической справке выше. Подпространством Крылова называется набор векторов[math]K_n =[b,Ab,A^2b,...,A^{n-1}b][/math]. Начав свою работу с произвольного вектора [math]b_0[/math], степенной метод вычисляет вектора [math]Ab, A^2b,...,A^{n-1}b[/math] итерационно сохраняя полученный результат в вектор [math]b[/math]. Полученная последовательность векторов сходится к собственному вектору, отвечающему максимальному собственному значению [math]\lambda_1[/math]. Однако, использование лишь последнего полученного вектора и потеря всех предшествующих посчитанных величин не всегда является наилучшим выбором. Поэтому сохранив все вектора и объединим их в одну матрицу мы получим так называемую матрицу Крылова: [math]K_n = [b,Ab,A^2b,...,A^{n-1}b][/math].
Столбцы получившейся матрицы не ортогональны, однако теоретически их можно ортогонализировать, применив процесс Грамма-Шмидта. Получившееся вектора будут составлять базис подпространства Крылова
