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

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

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

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

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

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

1.2 Математическое описание алгоритма

Пусть [math]A[/math] — симметричная матрица, а [math]G = G(i, j, \theta)[/math] — матрица вращения. Тогда

[math]A'=G^\top A G[/math]

симметрична и подобна матрице [math]A[/math].

Более того, [math]A'[/math] содержит следующие компоненты:

[math]\begin{align} A'_{ii} &= c^2\, A_{ii} - 2\, s c \,A_{ij} + s^2\, A_{jj} \\ A'_{jj} &= s^2 \,A_{ii} + 2 s c\, A_{ij} + c^2 \, A_{jj} \\ A'_{ij} &= A'_{ji} = (c^2 - s^2 ) \, A_{ij} + s c \, (A_{ii} - A_{jj} ) \\ A'_{ik} &= A'_{ki} = c \, A_{ik} - s \, A_{jk} & k \ne i,j \\ A'_{jk} &= A'_{kj} = s \, A_{ik} + c \, A_{jk} & k \ne i,j \\ A'_{kl} &= A_{kl} &k,l \ne i,j \end{align}[/math]

где [math]s = \sin \theta[/math] и [math]c = \cos \theta[/math].

Поскольку [math]G[/math] — ортогональная матрица, у матриц [math]A[/math] и [math]A'[/math] равны фробениусовы нормы [math]||\cdot||_F[/math] (корни из сумм квадратов всех компонент), причём мы можем выбрать [math]\theta[/math] так, чтобы [math]A'_{ij} = 0[/math], и в этом случае [math]A'[/math] будет иметь бóльшую сумму квадратов диагональных элементов:

[math] A'_{ij} = \cos(2\theta) A_{ij} + \tfrac{1}{2} \sin(2\theta) (A_{ii} - A_{jj}) [/math]

Приравнивая это нулю, получим

[math] \operatorname{tg}(2\theta) = \frac{2 A_{ij}}{A_{jj} - A_{ii}} [/math]

Если [math] A_{jj} = A_{ii} [/math], то

[math] \theta = \frac{\pi} {4} . [/math]

Чтобы достичь оптимального эффекта, необходимо потребовать, чтобы [math]A_{ij}[/math] был наибольшим по модулю внедиагональным элементом, т. н. опорным элементом.

Метод Якоби для собственных значений производит вращения до тех пор, пока матрица не станет почти диагональной. Тогда элементы на диагонали аппроксимируют собственные значения матрицы [math]A[/math].

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.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]N[/math].