Участник:Зиновьев Владимир/Метод Якоби вычисления собственных значений симметричной матрицы ЗП: различия между версиями
| Строка 49: | Строка 49: | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| + | Сначала оценим сложность одной итерации: | ||
| + | |||
1)Так как элементы матрицы никак не упорядоченны, поиск наибольшего элемента линейно зависит от числа элементов над диагональю. | 1)Так как элементы матрицы никак не упорядоченны, поиск наибольшего элемента линейно зависит от числа элементов над диагональю. | ||
Конкретнее, на данном шаге происходит <math>\frac{n*(n-1)}{2} -1</math> сравнение. | Конкретнее, на данном шаге происходит <math>\frac{n*(n-1)}{2} -1</math> сравнение. | ||
| Строка 54: | Строка 56: | ||
2)3 операции деления, 2 операции взятия корня, 4 операции умножения и 4 операции сложения/вычитания. | 2)3 операции деления, 2 операции взятия корня, 4 операции умножения и 4 операции сложения/вычитания. | ||
| − | 3)<math> | + | 3)<math>4*n</math> операций умножения и <math>2*n</math> операций сложения. |
| + | |||
| + | 4) | ||
=== Информационный граф === | === Информационный граф === | ||
Версия 13:18, 7 октября 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 Математическое описание алгоритма
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)
