Участник:Зиновьев Владимир/Метод Якоби вычисления собственных значений симметричной матрицы ЗП: различия между версиями
(Новая страница: «{{algorithm | name = Разложение Холецкого | serial_complexity = <math></math> | pf_height = <math></math> | pf_width…») |
|||
| Строка 33: | Строка 33: | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| + | 1)Находится максимальный наддиагональный элемент <math>a_{jk}</math> матрицы <math>A</math>. Сложность данной операции составляет <math>\frac{n*(n+1)}{2}</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> соответственно. Кроме того, из структуры матрицы <math>R</math> можно заметить, что сложность этой операции линейна(изменяются только сроки и столбцы с индексами <math>j</math> и <math>k</math>). | ||
| + | |||
| + | 4)Если матрица А не достаточно близка к диагональной, происходит переход к шагу 1. | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Версия 12:39, 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]. Сложность данной операции составляет [math]\frac{n*(n+1)}{2}[/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] соответственно. Кроме того, из структуры матрицы [math]R[/math] можно заметить, что сложность этой операции линейна(изменяются только сроки и столбцы с индексами [math]j[/math] и [math]k[/math]).
4)Если матрица А не достаточно близка к диагональной, происходит переход к шагу 1.
