Участник:Зиновьев Владимир/Метод Якоби вычисления собственных значений симметричной матрицы ЗП: различия между версиями
Строка 22: | Строка 22: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Пусть <math>A = A_0</math> — симметричная матрица. В методе Якоби для <math>A_0</math> строится последовательность ортогонально подобных матриц <math>A_1, A_2,...</math>, которая в конечном счёте сходится к диагональной матрице, у которой диагональными элементами являются все собственные значения матрицы <math>A</math>. Матрица <math>A_{i}</math> получается из матрицы <math>A_{i-1}</math> по формуле | Пусть <math>A = A_0</math> — симметричная матрица. В методе Якоби для <math>A_0</math> строится последовательность ортогонально подобных матриц <math>A_1, A_2,...</math>, которая в конечном счёте сходится к диагональной матрице, у которой диагональными элементами являются все собственные значения матрицы <math>A</math>. Матрица <math>A_{i}</math> получается из матрицы <math>A_{i-1}</math> по формуле | ||
− | <math>A_{i}=J^{T}_iA_{i-1}</math> | + | <math>A_{i}=J^{T}_iA_{i-1}J_i</math> |
+ | ,где <math>J_i</math> - ортогональная матрица, называемая ''вращением Якоби'' | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === |
Версия 23:15, 10 октября 2016
Разложение Холецкого | |
Последовательный алгоритм | |
Последовательная сложность | [math][/math] |
Объём входных данных | [math][/math] |
Объём выходных данных | [math][/math] |
Параллельный алгоритм | |
Высота ярусно-параллельной формы | [math][/math] |
Ширина ярусно-параллельной формы | [math][/math] |
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
1.1.1 Симметричность и положительная определённость матрицы
Симметричность матрицы позволяет хранить и вычислять только чуть больше половины её элементов, что почти вдвое экономит как необходимые для вычислений объёмы памяти, так и количество операций в сравнении с, например, разложением по методу Гаусса.
1.2 Математическое описание алгоритма
Пусть [math]A = A_0[/math] — симметричная матрица. В методе Якоби для [math]A_0[/math] строится последовательность ортогонально подобных матриц [math]A_1, A_2,...[/math], которая в конечном счёте сходится к диагональной матрице, у которой диагональными элементами являются все собственные значения матрицы [math]A[/math]. Матрица [math]A_{i}[/math] получается из матрицы [math]A_{i-1}[/math] по формуле
[math]A_{i}=J^{T}_iA_{i-1}J_i[/math]
,где [math]J_i[/math] - ортогональная матрица, называемая вращением Якоби
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1)Находится максимальный наддиагональный элемент [math]a_{jk}[/math] матрицы [math]A[/math].
2)Вычисляются параметры вращения Якоби:
[math]\tau= \frac{(a_{jj}-a_{kk})}{2a_{jk}}[/math] [math]t=sign(\tau)(|\tau|+\sqrt{1+\tau^2})[/math] [math]c= \frac{1}{1+\sqrt{1+\tau^2}}[/math] [math]s=c*t[/math]
3)К текущей матрице А применяются вращения с вычисленными параметрами:
[math]A=R^T(j,k,\theta)*A*R(j,k,\theta)[/math]
Стоит отметить, что вычисленные на предыдущем шаге [math]c[/math] и [math]s[/math] есть [math]\cos {\theta}[/math] и [math]\sin {\theta}[/math] соответственно.
4)Если матрица А не достаточно близка к диагональной, происходит переход к шагу 1.
Стоит отметить, что за [math]\frac{n*(n-1)}{2}[/math] итераций алгоритма гарантируется получение результата, т.к. сумма квадратов наддиагональных элементов матрицы А на каждой итерации уменьшается на [math]a_{jk}^2[/math].
1.6 Последовательная сложность алгоритма
Сначала оценим сложность одной итерации:
1)Так как элементы матрицы никак не упорядоченны, поиск наибольшего элемента линейно зависит от числа элементов над диагональю. Конкретнее, на данном шаге происходит [math]\frac{n*(n-1)}{2} -1[/math] сравнение.
2)3 операции деления, 2 операции взятия корня, 4 операции умножения и 4 операции сложения/вычитания.
3)[math]4*n[/math] операций умножения и [math]2*n[/math] операций сложения.
4)операция сравнения
В наиболее неудачном случае количество итераций равняется числу наддиагональных элементов, т.е. [math]\frac{n*(n-1)}{2}[/math]. Таким образом, суммарная сложность алгоритма составляет [math]O(N^4)[/math] сравнений, и [math]O(N^3)[/math] сложений и умножений.
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
Входные данные: плотная матрица [math]A[/math] (элементы [math]a_{ij}[/math]); при этом [math]A[/math] – симметрическая матрица, т. е. [math]a_{ij}= a_{ji}, i, j = 1, \ldots, n[/math]..
Объём входных данных: [math]\frac{n (n + 1)}{2}[/math] (в силу симметричности достаточно хранить только диагональ и над/поддиагональные элементы). Конкретный вариант хранения данных зависит от реализации. В качестве примеров можно привести хранение в одномерном массиве длины [math]\frac{n (n + 1)}{2}[/math] по строкам своей нижней части, хранение в виде так называемого ступенчатого массива (такой вариант двумерного массива, в котором каждая строка имеет свой размер).
Выходные данные: вектор собственных значений [math]\Lambda[/math] (элементы [math]\lambda_{ij}[/math]) длины [math]n[/math].