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

Основные авторы описания: А.С.Галкина, И.А.Плахов

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

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

Метод Якоби — итерационный алгоритм для вычисления собственных значений и собственных векторов вещественной симметричной матрицы. Карл Густав Якоб Якоби, в честь которого назван этот метод, предложил его в 1846 году, хотя использоваться он начал только в 1950-х годах с появлением компьютеров. Суть алгоритма заключается в том, чтобы по заданной симметрической матрице $A = A_0$ построить последовательность ортогонально подобных матриц $A_1,A_2,...$. Эта последовательность сходится к диагональной матрице, на диагонали которой стоят собственные значения.

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

Исходные данные: симметрическая матрица $A$ (элементы $a_{ij}$).

Вычисляемые данные: диагональная матрица $\Lambda$ (элементы $\lambda_{ij}$).

Матрица $A_{i+1}$ получается из $A_i$ по формуле $A_{i+1}={J_i}^TA_iJ_i$, где $J_i$ — ортогональная матрица, называемая вращением Якоби. При подходящем выборе $J_i$ матрица $A_m$ для больших m будет близка к диагональной матрице $\Lambda$.

Матрица $J_i$ выбирается так, чтобы сделать нулями пару внедиагональных элементов матрицы $A_{i+1}$.

                                                 $j$                         $k$

$J_i = \begin{matrix} \\ \\ \\ j \\ \\ k \\ \\ \\ \\ \end{matrix}$ $\begin{bmatrix} & 1 & & & & & & & & \\ & & 1 & & & & & & & \\ & & & \ddots & & & & & & \\ & & & & \cos(\theta) & & -\sin(\theta) & & & \\ & & & & & \ddots & & & & \\ & & & & \sin(\theta) & & \cos(\theta) & & & \\ & & & & & & & \ddots & & \\ & & & & & & & & 1 & \\ & & & & & & & & & 1 \\ \end{bmatrix}$

Обозначим $s = \sin \theta$ и $c = \cos \theta$. Тогда матрица $A_{i+1}$ состоит из следующих элементов:

$\begin{align} a_{jj}^{(i+1)} &= c^2\, a_{jj}^{(i)} - 2\, s c \,a_{jk}^{(i)} + s^2\, a_{kk}^{(i)} \\ a_{kk}^{(i+1)} &= s^2 \,a_{jj}^{(i)} + 2 s c\, a_{jk}^{(i)} + c^2 \, a_{kk}^{(i)} \\ a_{jk}^{(i+1)} &= a_{kj}^{(i+1)} = (c^2 - s^2 ) \, a_{jk}^{(i)} + s c \, (a_{kk}^{(i)} - a_{jj}^{(i)} ) \\ a_{jm}^{(i+1)} &= a_{mj}^{(i+1)} = c \, a_{jm}^{(i)} - s \, a_{km}^{(i)} & m \ne j,k \\ a_{km}^{(i+1)} &= a_{mk}^{(i+1)} = s \, a_{jm}^{(i)} + c \, a_{km}^{(i)} & m \ne j,k \\ a_{ml}^{(i+1)} &= a_{ml}^{(i)} &m,l \ne j,k \end{align}$

Можно выбрать $\theta$ так, чтобы $a_{jk}^{(i+1)} = 0$ и $a_{kj}^{(i+1)} = 0$. Для этого запишем равенство

$\begin{bmatrix} a_{jj}^{(i+1)} & a_{jk}^{(i+1)} \\ a_{kj}^{(i+1)} & a_{kk}^{(i+1)} \end{bmatrix} = \begin{bmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{bmatrix}^T \begin{bmatrix} a_{jj}^{(i)} & a_{jk}^{(i)} \\ a_{kj}^{(i)} & a_{kk}^{(i)} \end{bmatrix} \begin{bmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{bmatrix} = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix}$

где $\lambda_1$ и $\lambda_2$ - собственные значения подматрицы

$\begin{bmatrix} a_{jj}^{(i+1)} & a_{jk}^{(i+1)} \\ a_{kj}^{(i+1)} & a_{kk}^{(i+1)} \end{bmatrix}$

Опуская индекс $(i)$, с учетом симметрии получим:

$\begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} = \begin{bmatrix} a_{jj}c^2 + a_{kk}s^2 + 2sca_{jk} & sc(a_{kk}-a_{jj})+a_{jk}(c^2-s^2) \\ sc(a_{kk}-a_{jj})+a_{jk}(c^2-s^2) & a_{jj}s^2 + a_{kk}c^2 - 2sca_{jk} \end{bmatrix}$

Приравнивая внедиагональный элемент нулю, получаем

$\frac{a_{jj}^{(i)} - a_{kk}^{(i)}}{2 a_{jk}^{(i)}} = \frac{c^2 - s^2}{2sc} = \frac{\cos 2\theta}{\sin 2\theta} = \operatorname{tg}(2\theta) \equiv \tau$.

Положим $t = \frac{s}{c} = \operatorname{ctg}(\theta)$ и заметим, что $t^2 - 2t\tau + 1 = 0$. Решая квадратное уравнение, находим $t = \frac{\operatorname{sign}(\tau)}{|\tau| + \sqrt{1+\tau^2}}, c = \frac{1}{\sqrt{1+t^2}}, s = tc$.

Выбор параметров $j$ и $k$ производится путем построчного циклического обхода внедиагональных элементов матрицы $A$.

1.3 Вычислительное ядро алгоритма

Вычислительное ядро составляют множественные вычисления элементов матрицы $a_{jm}^{(i+1)} = a_{mj}^{(i+1)}$   и   $a_{km}^{(i+1)} = a_{mk}^{(i+1)}$   в процессе применения матрицы поворота $J$ к матрице $A$:

$\begin{align} a_{jm}^{(i+1)} &= a_{mj}^{(i+1)} = c \, a_{jm}^{(i)} - s \, a_{km}^{(i)} & m \ne j,k \\ a_{km}^{(i+1)} &= a_{mk}^{(i+1)} = s \, a_{jm}^{(i)} + c \, a_{km}^{(i)} & m \ne j,k \\ \end{align}$

каждое из которых повторяется по $(n-2)$ раза.

1.4 Макроструктура алгоритма

Основную часть метода составляет процедура применения вращения к матрице $A$, которая в дальнейшем будет обозначена как Jakobi-Rotation$(A,j,k)$

1.5 Схема реализации последовательного алгоритма

Алгоритм можно описать следующим образом:

repeat
    for [math]j=1[/math] to [math]n-1[/math]
        for [math]k=j+1[/math] to [math]n[/math]
            выполнить процедуру Jakobi-Rotation[math](A,j,k)[/math]
        end for
    end for
пока [math]A[/math] не достаточно близка к диагональной матрице

Процедура Jakobi-Rotation$(A,j,k)$ — это следующий алгоритм:

if [math]|a_{jk}|[/math] не слишком мал
    [math]\begin{align}
      \tau &= \frac{a_{jj}-a_{kk}}{2\,a_{jk}} \\
      t &= \frac{sign(\tau)}{|\tau|+\sqrt{1+\tau^2}} \\
      c &= \frac{1}{\sqrt{1+t^2}} \\
      s &= c\,t \\
      A &= R^T(j,k,\theta)\cdot A\cdot R(j,k,\theta), \qquad J_i = R(j,k,\theta),\ c = \cos \theta,\ s = \sin \theta 
     \end{align}[/math]
end if

1.6 Последовательная сложность алгоритма

Для вычисления собственных значений вещественной симметричной матрицы порядка n методом Якоби требуется:

Для вычислительного ядра —

• $2\,n(n-1)(n-2)$ умножений,
• $n(n-1)(n-2)$ сложений.

Для остальной части алгоритма —

• $\frac{3\,n(n-1)}{2}$ умножений,
• $\frac{3\,n(n-1)}{2}$ делений,
• $\frac{5\,n(n-1)}{2}$ сложений (вычитаний),
• $n(n-1)$ операций извлечения квадратного корня.

Умножения и сложения (вычитания) составляют основную часть алгоритма.

Таким образом, при классификации по последовательной сложности метод Якоби вычисления собственных значений симметричной матрицы относится к алгоритмам с кубической сложностью.

1.9 Входные и выходные данные алгоритма

Входные данные: матрица $A$ (элементы $a_{ij}$). Дополнительные ограничения:

• $A$ – симметрическая матрица, т. е. $a_{ij}= a_{ji}, i, j = 1, \ldots, n$.

Объём входных данных: $\frac{n (n + 1)}{2}$ (в силу симметричности достаточно хранить только диагональ и над/поддиагональные элементы). В разных реализациях эта экономия хранения может быть выполнена разным образом.

Выходные данные: диагональная матрица $\Lambda$ (элементы $\lambda_{ii}$).

Объём выходных данных: $n$ (достаточно хранить только диагональные элементы).