Участник:Alexbashirov/Алгоритм Ланцоша для точной арифметики: различия между версиями
| Строка 9: | Строка 9: | ||
Алгоритм Ланцоша является прямым алгоритмом поиска собственных значений симметричной матрицы, разработанным венгерским физиком и математиком XX столетия Корнелием Ланцошем в 1950 году. Алгоритм совмещает в себе два других алгоритма: алгоритм построения подпространства Крылова (который также был создан Ланцошем) и процедуру Рэлея-Ритца приближения собственных значений матрицы. Алгоритм является вариацией степенного метода, позволяющего найти собственные значения и собственные вектора матрицы <math>n</math>-го порядка. Однако в алгоритме число итераций ограничено некоторым <math>k</math>, где <math>k<<n</math>. Несмотря на заявленную вычислительную эффективность, алгоритм не получил широкого применения в своём первоначальном виде, ввиду его неустойчивости. 20 лет спустя, в 1970 году ученые Ojalvo и Newman показали доработанный алгоритм Ланцоша, который теперь стал устойчивым а также предложили способ выбора вектора начального приближения <math>v_0</math>. Полученный последователями Ланцоша алгоритм получил название "Алгоритм Ланцоша с полной переортогонализацией". | Алгоритм Ланцоша является прямым алгоритмом поиска собственных значений симметричной матрицы, разработанным венгерским физиком и математиком XX столетия Корнелием Ланцошем в 1950 году. Алгоритм совмещает в себе два других алгоритма: алгоритм построения подпространства Крылова (который также был создан Ланцошем) и процедуру Рэлея-Ритца приближения собственных значений матрицы. Алгоритм является вариацией степенного метода, позволяющего найти собственные значения и собственные вектора матрицы <math>n</math>-го порядка. Однако в алгоритме число итераций ограничено некоторым <math>k</math>, где <math>k<<n</math>. Несмотря на заявленную вычислительную эффективность, алгоритм не получил широкого применения в своём первоначальном виде, ввиду его неустойчивости. 20 лет спустя, в 1970 году ученые Ojalvo и Newman показали доработанный алгоритм Ланцоша, который теперь стал устойчивым а также предложили способ выбора вектора начального приближения <math>v_0</math>. Полученный последователями Ланцоша алгоритм получил название "Алгоритм Ланцоша с полной переортогонализацией". | ||
| − | + | === Математическое описание алгоритма=== | |
Алгоритм Ланцоша работает с вещественной симметричной матрицей <math>A=A^T</math>, таким образом в памяти достаточно хранить лишь немногим более половины элементов матрицы <math>A</math>. | Алгоритм Ланцоша работает с вещественной симметричной матрицей <math>A=A^T</math>, таким образом в памяти достаточно хранить лишь немногим более половины элементов матрицы <math>A</math>. | ||
| Строка 18: | Строка 18: | ||
Столбцы получившейся матрицы не ортогональны, однако их можно ортогонализировать, применив процесс Грамма-Шмидта. Получившееся вектора будут составлять базис подпространства Крылова <math>K_n</math>. Можно ожидать, что вектора полученного базиса будут достаточно хорошо приближать <math>n</math> собственных векторов, отвечающих <math>n</math> наибольшим собственным значения. | Столбцы получившейся матрицы не ортогональны, однако их можно ортогонализировать, применив процесс Грамма-Шмидта. Получившееся вектора будут составлять базис подпространства Крылова <math>K_n</math>. Можно ожидать, что вектора полученного базиса будут достаточно хорошо приближать <math>n</math> собственных векторов, отвечающих <math>n</math> наибольшим собственным значения. | ||
| − | + | ===Вычислительное ядро алгоритма === | |
Вычислительным ядром алгоритма Ланцоша, то есть наиболее ресурсно-затратной частью алгоритма, является шаг на котором на каждой итерации происходит перемножение матрицы <math>A</math> на вектор <math>q_j</math>, полученный на предыдущей итерации. Полученный в результате умножения вектор обозначается <math>z</math>: | Вычислительным ядром алгоритма Ланцоша, то есть наиболее ресурсно-затратной частью алгоритма, является шаг на котором на каждой итерации происходит перемножение матрицы <math>A</math> на вектор <math>q_j</math>, полученный на предыдущей итерации. Полученный в результате умножения вектор обозначается <math>z</math>: | ||
<math> z=Aq_j</math>. | <math> z=Aq_j</math>. | ||
| − | + | === Макроструктура алгоритма === | |
Как уже говорилось в математическом описании, алгоритм объединяет в себе два алгоритма: метод построения подпространства Крылова и процедуру поиска собственных значений трехдиагональной матрицы (процес Рэлея-Ритца). | Как уже говорилось в математическом описании, алгоритм объединяет в себе два алгоритма: метод построения подпространства Крылова и процедуру поиска собственных значений трехдиагональной матрицы (процес Рэлея-Ритца). | ||
| Строка 31: | Строка 31: | ||
| − | + | === Схема последовательной реализации алгоритма === | |
[[Файл:Ланцош_Схема реализации.png|800px]] | [[Файл:Ланцош_Схема реализации.png|800px]] | ||
| − | + | === Последовательная сложность алгоритма === | |
Посчитаем количество операций, необходимых для поиска <math>k</math> собственных значений и векторов для матрицы <math>A</math> размерности <math>n\times n</math>. | Посчитаем количество операций, необходимых для поиска <math>k</math> собственных значений и векторов для матрицы <math>A</math> размерности <math>n\times n</math>. | ||
Версия 22:31, 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.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].
Столбцы получившейся матрицы не ортогональны, однако их можно ортогонализировать, применив процесс Грамма-Шмидта. Получившееся вектора будут составлять базис подпространства Крылова [math]K_n[/math]. Можно ожидать, что вектора полученного базиса будут достаточно хорошо приближать [math]n[/math] собственных векторов, отвечающих [math]n[/math] наибольшим собственным значения.
1.3 Вычислительное ядро алгоритма
Вычислительным ядром алгоритма Ланцоша, то есть наиболее ресурсно-затратной частью алгоритма, является шаг на котором на каждой итерации происходит перемножение матрицы [math]A[/math] на вектор [math]q_j[/math], полученный на предыдущей итерации. Полученный в результате умножения вектор обозначается [math]z[/math]:
[math] z=Aq_j[/math].
1.4 Макроструктура алгоритма
Как уже говорилось в математическом описании, алгоритм объединяет в себе два алгоритма: метод построения подпространства Крылова и процедуру поиска собственных значений трехдиагональной матрицы (процес Рэлея-Ритца).
Первую составную часть (алгоритм построения подпространства Крылова) представляет итерационный процесс построения матрицы [math]Q_j=[q_1,q_2,...q_k][/math] из [math]j[/math] ортонормированных вектров Ланцоша и последующее формирование трехдиагональной матрицы [math]T_j=Q_j^TAQ_j[/math]. Число таких векторов и, следовательно, размер матрицы растет с каждой итерацией. Итерационный процесс завершается при [math]j=k[/math].
На долю второй части алгоритма приходится поиск собственных значений и соответствующих им собственных векторов матрицы [math]T_j=Q_j^TAQ_j[/math], полученной в первой части.
1.5 Схема последовательной реализации алгоритма
1.6 Последовательная сложность алгоритма
Посчитаем количество операций, необходимых для поиска [math]k[/math] собственных значений и векторов для матрицы [math]A[/math] размерности [math]n\times n[/math].
- [math]n^2[/math] действий для умножения матрицы на вектор
- [math]n[/math] действия для перемножения двух векторов
- [math]n[/math] операций для поэлементного сложения или вычитания двух векторов
- для отыскания нормы вектора помимо [math]n[/math] сложений и [math]n[/math] умножений требуется 1 операция извлечения корня
- для поиска собственный значений и векторов матрицы [math]T_j[/math] требуется [math]O(k^3)[/math] операций.
Суммарно для одной итерации алгоритма требуется совершить [math]O(n^2)+O(k^3)[/math] операций.
