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

Метод Якоби вычисления собственных значений симметричной матрицы
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n^3) }[/math]
Объём входных данных	[math]\displaystyle{ \frac{n (n + 1)}{2} }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]

Основные авторы описания: А. Тамеева, А. Кухтинов.

ЧАСТЬ. Свойства и структура алгоритмов

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

Метод Якоби вычисления собственных значений симметричной матрицы — итерационный алгоритм, названный в честь предложившего его для конкретной матрицы 7 × 7 в 1846 году Карла Густава Якоба Якоби. Исторически старейший метод для решения симметрической проблемы собственных значений получил широкое применение только в 1950-х годах с появлением компьютеров. Преимуществом метода является более точное вычисление малых собственных значений по сравнению с конкурирующими алгоритмами.

Суть алгоритма — приведение симметрической матрицы к диагональной с собственными значениями на диагонали путем вращения.

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

Исходные данные: симметрическая матрица [math]\displaystyle{ A=\{a_{ij}\} }[/math].

Вычисляемые данные: диагональная матрица [math]\displaystyle{ \Lambda=\{\lambda_{ii}\} }[/math]. Диагональные элементы [math]\displaystyle{ \Lambda }[/math] — собственные значения матрицы [math]\displaystyle{ A }[/math], столбцы — приближенные собственные вектора матрицы [math]\displaystyle{ A }[/math].

По заданной матрице [math]\displaystyle{ A=A_0 }[/math] строится последовательность ортогонально подобных матриц [math]\displaystyle{ A_1, A_2,\ldots, A_m }[/math], сходящихся к [math]\displaystyle{ \Lambda }[/math].

[math]\displaystyle{ A_{i+1}={J_i}^TA_iJ_i }[/math], где [math]\displaystyle{ J_i }[/math] — ортогональная матрица, называемая вращением Якоби.

Матрица [math]\displaystyle{ J_i }[/math] выбирается так, чтобы обнулить элементы [math]\displaystyle{ (j,k) }[/math] и [math]\displaystyle{ (k,j) }[/math] матрицы [math]\displaystyle{ A_{i+1} }[/math]:

[math]\displaystyle{ \begin{matrix}j & & & & & & & & k \end{matrix} }[/math]

[math]\displaystyle{ \begin{align} J_i = R(j,k,\theta) = \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} \end{align} }[/math]

Для угла вращения [math]\displaystyle{ \theta }[/math]:

[math]\displaystyle{ \begin{bmatrix}a^{(i+1)}_{jj} & a^{(i+1)}_{jk} \\ a^{(i+1)}_{kj} & a^{(i+1)}_{kk}\end{bmatrix}= \begin{bmatrix}\cos\theta & -\sin\theta \\ \sin\theta &\cos\theta\end{bmatrix}^{T} \begin{bmatrix}a^{(i)}_{jj} & a^{(i)}_{jk} \\ a^{(i)}_{kj} & a^{(i)}_{kk}\end{bmatrix} \begin{bmatrix}\cos\theta & -\sin\theta \\ \sin\theta &\cos\theta\end{bmatrix}= \begin{bmatrix}\lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix}, }[/math] где [math]\displaystyle{ \lambda_1 }[/math] и [math]\displaystyle{ \lambda_2 }[/math] — собственные значения подматрицы [math]\displaystyle{ \begin{bmatrix}a^{(i)}_{jj} & a^{(i)}_{jk} \\ a^{(i)}_{kj} & a^{(i)}_{kk}\end{bmatrix} }[/math].

Вычислим [math]\displaystyle{ s = \sin \theta }[/math] и [math]\displaystyle{ c = \cos \theta }[/math], исходя из предыдущего матричного равенства:

[math]\displaystyle{ \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} }[/math].

Приравняем внедиагональный элемент нулю: [math]\displaystyle{ \dfrac{a_{jj}-a_{kk}}{2a_{jk}}=\dfrac{c^2-s^2}{2sc}=\dfrac{\cos2\theta}{\sin2\theta}=\operatorname{ctg}2\theta\equiv\tau }[/math]

Положим [math]\displaystyle{ tg\theta=t=\dfrac{s}{c} }[/math]. Тогда [math]\displaystyle{ t^2+2t\tau-1=0 }[/math].

Решая квадратное уравнение, получим: [math]\displaystyle{ t=\dfrac{\operatorname{sign}\tau}{\left|\tau\right|+\sqrt{1+\tau^2}}, c=\dfrac{1}{\sqrt{1+t^2}}, s=t\cdot c. }[/math]

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

Вычислительное ядро состоит из вычислений элементов матрицы [math]\displaystyle{ a_{jl}^{(i+1)} = a_{lj}^{(i+1)} }[/math] и [math]\displaystyle{ a_{kl}^{(i+1)} = a_{lk}^{(i+1)} }[/math] в процессе применения матрицы поворота [math]\displaystyle{ J }[/math] к матрице [math]\displaystyle{ A }[/math]:

[math]\displaystyle{ a_{jl}^{(i+1)} = a_{lj}^{(i+1)} = c \, a_{jl}^{(i)} - s \, a_{kl}^{(i)}, l \ne j,k }[/math]

[math]\displaystyle{ a_{kl}^{(i+1)} = a_{lk}^{(i+1)} = s \, a_{jl}^{(i)} + c \, a_{kl}^{(i)}, l \ne j,k, }[/math]

каждое из которых повторяется по [math]\displaystyle{ (n-2) }[/math] раза.

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

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

repeat
 выбрать пару индексов j, k
 обратиться к процедуре JacobiRotation(A,j,k)
пока А не станет достаточно близка к диагональной матрице

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

В классическом алгоритме Якоби для обнуления на текущей итерации выбирался наибольший элемент [math]\displaystyle{ a_{jk} }[/math]. Поиск наибольшего элемента слишком замедляет процесс вычислений (нужно провести поиск среди [math]\displaystyle{ \dfrac{n^2-n}{2} }[/math] элементов, прежде чем выполнить вращение стоимостью в [math]\displaystyle{ O(n) }[/math] флопов), поэтому для практических вычислений выбор параметров [math]\displaystyle{ j }[/math] и [math]\displaystyle{ k }[/math] производится путем построчного циклического обхода внедиагональных элементов матрицы [math]\displaystyle{ A }[/math].

Таким образом, алгоритм можно описать так:

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

Процедура JacobiRotation(A, j, k):

if [math]\displaystyle{ |a_{jk}| }[/math] не слишком мал
   [math]\displaystyle{ \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\cdot t \\
      A &= J_i^T\cdot A\cdot J_i, \qquad
      J_i = R(j,k,\theta),\ c = \cos \theta,\ s = \sin \theta 
     \end{align}
 }[/math]
end if

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

Для вычисления собственных значений вещественной симметричной матрицы порядка [math]\displaystyle{ n }[/math] методом Якоби требуется:

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

• [math]\displaystyle{ 2\,n(n-1)(n-2) }[/math] умножений,
• [math]\displaystyle{ n(n-1)(n-2) }[/math] сложений.

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

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

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

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

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

Входные данные: плотная матрица [math]\displaystyle{ A=\{a_{ij}\}, A\in\R^{n\times n} }[/math]. Дополнительные ограничения:

• [math]\displaystyle{ A }[/math] — симметрическая матрица, т. е. [math]\displaystyle{ a_{ij}= a_{ji}, i, j = 1, \ldots, n }[/math].

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

Выходные данные: вектор собственных значений [math]\displaystyle{ \lambda_{i} }[/math] длины [math]\displaystyle{ n }[/math].

Объём выходных данных: [math]\displaystyle{ n }[/math]

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

Алгоритм почти полностью детерминирован, так как основан на умножении плотных матриц.

ЧАСТЬ. Программная реализация алгоритма

Существующие реализации алгоритма

Библиотека JACOBI_EIGENVALUE содержит последовательную реализацию алгоритма.