Участник:Sagak/Алгоритм Ланцоша в арифметике с плавающей точкой: различия между версиями
Sagak (обсуждение | вклад) |
Sagak (обсуждение | вклад) |
||
Строка 8: | Строка 8: | ||
Исходные данные: положительно определённая симметрическая матрица <math>A</math>, вектор <math>b</math>,количество итераций <math>k</math>. | Исходные данные: положительно определённая симметрическая матрица <math>A</math>, вектор <math>b</math>,количество итераций <math>k</math>. | ||
− | Вычисляемые данные: трехдиагональная матрица <math>T_k( | + | Вычисляемые данные: трехдиагональная матрица <math>T_k</math>(элементы <math>t_{ij}</math>) размерности <math>k</math>. |
+ | |||
+ | Формула метода: | ||
+ | |||
+ | :<math> | ||
+ | \begin{align} | ||
+ | q_1&=b/||b||,\beta_0=0,q_o=0. \\ | ||
+ | z&=Aq_j, \\ | ||
+ | \alpha_j&=q_j^Tz, \\ | ||
+ | z& =z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i, \\ | ||
+ | z&=z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i, \\ | ||
+ | z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\ | ||
+ | \beta&=||z||,\\ | ||
+ | q_{j+1}&=z/\beta_j, \quad j \in [1, k]. | ||
+ | \end{align} | ||
+ | </math> |
Версия 20:04, 13 октября 2016
1 Алгоритм Ланцоша
Алгоритм Ланцоша – итерационный метод , созданный Корнелиусом Ланцошем, для нахождения собственных значений и собственных веторов симметричной матрицы. Суть алгоритма в том, что он сводит частичную проблему собственных значений симметричной вещественной матрицы к полной проблеме собственных значений для симметричной трехдиагональной матрицы меньшей размерности. Алгоритм применяется к матрицам большой размерности, к которым не применимы никакие прямые методы. Есть три вида алгоритма: Алгоритм Ланцоша с точной арифметикой, Алгоритм Ланцоша в арифметике с плавающей точкой и Алгоритм Ланцоша с выборочной ортогонализацией. Алгоритм Ланцоша в арифметике с плавающей точкой учитывает округления, возникающие при вычислениях.
Симметричность матрицы позволяет хранить и вычислять только чуть больше половины её элементов, что почти вдвое экономит как необходимые для вычислений объёмы памяти, так и количество операций.Также алгоритм позволяет использовать так называемый режим накопления, обусловленный тем, что значительную часть вычислений составляют вычисления скалярных произведений.
2 Математическое описание алгоритма
Исходные данные: положительно определённая симметрическая матрица [math]A[/math], вектор [math]b[/math],количество итераций [math]k[/math].
Вычисляемые данные: трехдиагональная матрица [math]T_k[/math](элементы [math]t_{ij}[/math]) размерности [math]k[/math].
Формула метода:
- [math] \begin{align} q_1&=b/||b||,\beta_0=0,q_o=0. \\ z&=Aq_j, \\ \alpha_j&=q_j^Tz, \\ z& =z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i, \\ z&=z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i, \\ z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\ \beta&=||z||,\\ q_{j+1}&=z/\beta_j, \quad j \in [1, k]. \end{align} [/math]