Участник: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{ 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)} & a_{jk}^{(i)} \\ a_{kj}^{(i)} & a_{kk}^{(i)} \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+t^2}}, c = \frac{1}{\sqrt{1+t^2}}, s = tc }[/math].