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

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

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

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

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

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

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

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

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

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

                                                 [math]\displaystyle{ j }[/math]                         [math]\displaystyle{ k }[/math]

[math]\displaystyle{ J_i = \begin{matrix} \\ \\ \\ j \\ \\ k \\ \\ \\ \\ \end{matrix} }[/math] [math]\displaystyle{ \begin{bmatrix} & 1 & & & & & & & & \\ & & 1 & & & & & & & \\ & & & \ddots & & & & & & \\ & & & & \cos(\theta) & & -\sin(\theta) & & & \\ & & & & & \ddots & & & & \\ & & & & \sin(\theta) & & \cos(\theta) & & & \\ & & & & & & & \ddots & & \\ & & & & & & & & 1 & \\ & & & & & & & & & 1 \\ \end{bmatrix} }[/math]

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

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

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

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

где [math]\displaystyle{ \lambda_1 }[/math] и [math]\displaystyle{ \lambda_2 }[/math] - собственные значения подматрицы

[math]\displaystyle{ \begin{bmatrix} a_{jj}^{(i+1)} & a_{jk}^{(i+1)} \\ a_{kj}^{(i+1)} & a_{kk}^{(i+1)} \end{bmatrix} }[/math]

Опуская индекс [math]\displaystyle{ (i) }[/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{ \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 }[/math].

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

Выбор параметров [math]\displaystyle{ j }[/math] и [math]\displaystyle{ k }[/math] производится путем построчного циклического обхода внедиагональных элементов матрицы [math]\displaystyle{ A }[/math].

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

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

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

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

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

Основную часть метода составляет процедура применения вращения к матрице [math]\displaystyle{ A }[/math], которая в дальнейшем будет обозначена как Jakobi-Rotation[math]\displaystyle{ (A,j,k) }[/math]

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

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

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

Процедура Jakobi-Rotation[math]\displaystyle{ (A,j,k) }[/math] — это следующий алгоритм:

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\,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

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

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

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

• [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 }[/math] (элементы [math]\displaystyle{ a_{ij} }[/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 }[/math] (элементы [math]\displaystyle{ \lambda_{ii} }[/math]).

Объём выходных данных: [math]\displaystyle{ n }[/math] (достаточно хранить только диагональные элементы).

Литература

<references \>