Участник:Odbaev/Нахождение собственных чисел квадратной матрицы методом QR разложения (2): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 59: Строка 59:
 
* [http://www.netlib.org/scalapack/ ScaLAPACK]: функция [http://www.netlib.org/scalapack/explore-html/d6/da2/pdgemm___8c.html PDGEMM] (параллельная реализация)
 
* [http://www.netlib.org/scalapack/ ScaLAPACK]: функция [http://www.netlib.org/scalapack/explore-html/d6/da2/pdgemm___8c.html PDGEMM] (параллельная реализация)
 
* [http://www.mathworks.com MATLAB]: функции [http://www.mathworks.com/help/matlab/ref/mtimes.html mtimes, *]
 
* [http://www.mathworks.com MATLAB]: функции [http://www.mathworks.com/help/matlab/ref/mtimes.html mtimes, *]
−
* [http://www.mathworks.com MATLAB]: функция [https://reference.wolfram.com/language/ref/Dot.html Dot]
+
* [http://www.wolfram.com/mathematica/ Mathematica]: функция [https://reference.wolfram.com/language/ref/Dot.html Dot]
  
 
= Литература =
 
= Литература =
 
<references />
 
<references />

Версия 13:52, 10 октября 2016

Основные авторы описания: О.Д.Баев, А.С.Шевелев

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

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

QR-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел и собственных векторов матрицы. Был разработан в конце 1950-х годов независимо В.Н. Кублановской и Дж. Фрэнсисом.

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

Пусть A — вещественная матрица, для которой мы хотим найти собственные числа и векторы. Положим A0=A. На k-ом шаге (начиная с k = 0) вычислим QR-разложение Ak=QkRk, где Qk — ортогональная матрица (то есть QkT = Qk−1), а Rk — верхняя треугольная матрица. Затем мы определяем Ak+1 = RkQk.

Заметим, что

[math] A_{k+1} = R_k Q_k = Q_k^{-1} Q_k R_k Q_k = Q_k^{-1} A_k Q_k = Q_k^{T} A_k Q_k, [/math]

то есть все матрицы Ak являются подобными и их собственные значения равны.

Пусть все диагональные миноры матрицы A не вырождены. Тогда последовательность матриц Ak при k→∞ сходится по форме к клеточному правому треугольному виду, соответствующему клеткам с одинаковыми по модулю собственными значениями. [1]

Для того, чтобы получить собственные векторы матрицы, нужно перемножить все матрицы Qk.

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

Основными вычислительными ядрами алгоритма являются:

  • QR-разложение
  • Умножение матриц

1.4 Макроструктура алгоритма

QR-алгоритм на каждой итерации использует следующие макрооперации:

  1. QR-разложение
  2. Умножение матриц

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

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

2 Программная реализация алгоритма

2.1 Масштабируемость алгоритма и его реализации

2.2 Существующие реализации алгоритма

Полный алгоритм:

QR-разложение:

Умножение матриц:

3 Литература

  1. ↑ Бахвалов Н.С., Жидков Н.П., Кобельков. Г.М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Odbaev/Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(2)&oldid=5168