Участник:Зиновьев Владимир/Метод Якоби вычисления собственных значений симметричной матрицы ЗП: различия между версиями
Строка 33: | Строка 33: | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
− | 1)Находится максимальный наддиагональный элемент <math>a_{jk}</math> матрицы <math>A</math>. | + | 1)Находится максимальный наддиагональный элемент <math>a_{jk}</math> матрицы <math>A</math>. |
− | |||
2)Вычисляются параметры вращения Якоби: | 2)Вычисляются параметры вращения Якоби: | ||
<math>\tau= \frac{(a_{jj}-a_{kk})}{2a_{jk}}</math> | <math>\tau= \frac{(a_{jj}-a_{kk})}{2a_{jk}}</math> | ||
Строка 43: | Строка 42: | ||
3)К текущей матрице А применяются вращения с вычисленными параметрами: | 3)К текущей матрице А применяются вращения с вычисленными параметрами: | ||
<math>A=R^T(j,k,\theta)*A*R(j,k,\theta)</math> | <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>c</math> и <math>s</math> есть <math>\cos {\theta}</math> и <math>\sin {\theta}</math> соответственно. |
4)Если матрица А не достаточно близка к диагональной, происходит переход к шагу 1. | 4)Если матрица А не достаточно близка к диагональной, происходит переход к шагу 1. |
Версия 12:48, 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].