Участник:Зиновьев Владимир/Метод Якоби вычисления собственных значений симметричной матрицы ЗП

Разложение Холецкого
Последовательный алгоритм
Последовательная сложность	[math][/math]
Объём входных данных	[math][/math]
Объём выходных данных	[math][/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math][/math]
Ширина ярусно-параллельной формы	[math][/math]

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

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

1.1.1 Симметричность и положительная определённость матрицы

Симметричность матрицы позволяет хранить и вычислять только чуть больше половины её элементов, что почти вдвое экономит как необходимые для вычислений объёмы памяти, так и количество операций в сравнении с, например, разложением по методу Гаусса.

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)