Участник:AleksLevin/Алгоритм Ланцоша вычисления собственных значений симметричной матрицы для точной арифметики (без переортогонализации): различия между версиями
Нет описания правки |
|||
| Строка 1: | Строка 1: | ||
Основные авторы описания: Левин А.Д. (студент, кафедра вычислительных методов, 604 группа) | |||
= Свойства и структура алгоритмов = | = Свойства и структура алгоритмов = | ||
| Строка 5: | Строка 7: | ||
Данный алгоритм появился в 1950 г. благодаря стараниям венгерского физика и математика Корнелия Ланцоша (венг. Lánczos Kornél). Сам Ланцош указывал, что его метод предназначен для отыскания нескольких собственных векторов симметричных матрицы, хотя к методу сразу было обращено внимание, как к способу приведения всей матрицы к трёхдиагональному виду. Двадцатью годами позже канадский математик Крис Пэж показал, что, несмотря на чувствительность к округлениям, алгоритм Ланцоша - эффективное средство вычисления некоторых внешних собственных чисел и соответствующих им собственных векторов [1, c.276]. | Данный алгоритм появился в 1950 г. благодаря стараниям венгерского физика и математика Корнелия Ланцоша (венг. Lánczos Kornél). Сам Ланцош указывал, что его метод предназначен для отыскания нескольких собственных векторов симметричных матрицы, хотя к методу сразу было обращено внимание, как к способу приведения всей матрицы к трёхдиагональному виду. Двадцатью годами позже канадский математик Крис Пэж показал, что, несмотря на чувствительность к округлениям, алгоритм Ланцоша - эффективное средство вычисления некоторых внешних собственных чисел и соответствующих им собственных векторов [1, c.276]. | ||
Алгоритм Ланцоша для вычисления собственных значений симметричной матрицы | Алгоритм Ланцоша для вычисления собственных значений симметричной матрицы <math style="vertical-align:0%;>A</math> соединяет в себе метод Ланцоша для построения последовательности подпространств Крылова и ортонормированных векторов Ланцоша и процедуру Рэлея-Ритца получения оптимальных приближений собственных значений и соответствующих векторов исходной матрицы <math style="vertical-align:0%;>A</math> [2, с.381]. | ||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
Алгоритм Ланцоша для вычисления собственных значений и собственных векторов матрицы <math style="vertical-align:0%;>A=A^T</math> в точной арифметике: | Алгоритм Ланцоша для вычисления собственных значений и собственных векторов симметричной матрицы <math style="vertical-align:0%;>A=A^T</math> в точной арифметике: [2, с.381] | ||
<math>q_1=\frac{b}{\|b\|_2}, \beta_0=0, q_0=0 </math> | :<math> | ||
\begin{align} | |||
q_1 & = \frac{b}{\|b\|_2}, \beta_0=0, q_0=0 \\ | |||
for\ j\ & = 1 & to & k \\ | |||
z & = Aq_j \\ | |||
\alpha_{j}= q^{T}_{j}\,z \\ | |||
z & = z - \alpha_{j}\,q_j - \beta_{j-1}/,q_{j-1} \\ | |||
\end{align} | |||
</math> | |||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == | ||
Версия от 20:04, 9 ноября 2016
Основные авторы описания: Левин А.Д. (студент, кафедра вычислительных методов, 604 группа)
Свойства и структура алгоритмов
Общее описание алгоритма
Данный алгоритм появился в 1950 г. благодаря стараниям венгерского физика и математика Корнелия Ланцоша (венг. Lánczos Kornél). Сам Ланцош указывал, что его метод предназначен для отыскания нескольких собственных векторов симметричных матрицы, хотя к методу сразу было обращено внимание, как к способу приведения всей матрицы к трёхдиагональному виду. Двадцатью годами позже канадский математик Крис Пэж показал, что, несмотря на чувствительность к округлениям, алгоритм Ланцоша - эффективное средство вычисления некоторых внешних собственных чисел и соответствующих им собственных векторов [1, c.276].
Алгоритм Ланцоша для вычисления собственных значений симметричной матрицы [math]\displaystyle{ A }[/math] соединяет в себе метод Ланцоша для построения последовательности подпространств Крылова и ортонормированных векторов Ланцоша и процедуру Рэлея-Ритца получения оптимальных приближений собственных значений и соответствующих векторов исходной матрицы [math]\displaystyle{ A }[/math] [2, с.381].
Математическое описание алгоритма
Алгоритм Ланцоша для вычисления собственных значений и собственных векторов симметричной матрицы [math]\displaystyle{ A=A^T }[/math] в точной арифметике: [2, с.381]
- [math]\displaystyle{ \begin{align} q_1 & = \frac{b}{\|b\|_2}, \beta_0=0, q_0=0 \\ for\ j\ & = 1 & to & k \\ z & = Aq_j \\ \alpha_{j}= q^{T}_{j}\,z \\ z & = z - \alpha_{j}\,q_j - \beta_{j-1}/,q_{j-1} \\ \end{align} }[/math]
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
[1] Парлетт Б. Симметричная проблема собственных значений. Численные методы //М.: Мир. - 1983. - С. 276-294
[2] James W. Demmel Вычислительная линейная алгебра. Теория и приложения //Мир. - 2001. С. 381-391