Метод обертання Якобі

Метод обертання Якобі — це чисельний алгоритм розв'язання повної задачі власних значень для симетричної матриці з дійсних чисел. Названий на честь Якобі, який і придумав цей метод у 1846 році.

Опис

Метод застосовується до симетричної матриці $A=A^{T}$, і полягає в виконанні ітераційних перетворень, які зводять її до діагонального виду: $\Lambda =UAU^{T}={\mbox{diag}}(\lambda _{i})$ — власні числа.

Нехай $A$ — симетрична матриця, а $G=G(i,j,\Theta )$ — матриця повороту Ґівенса. Тоді матриця:

$A'=G^{\top }AG\,$

симетрична та подібна до $A$.

Елементи матриці $A'$ можна обчислити за формулами:

${\begin{aligned}A'_{ii}&=c^{2}\,A_{ii}-2\,sc\,A_{ij}+s^{2}\,A_{jj}\\A'_{jj}&=s^{2}\,A_{ii}+2sc\,A_{ij}+c^{2}\,A_{jj}\\A'_{ij}&=A'_{ji}=(c^{2}-s^{2})\,A_{ij}+sc\,(A_{ii}-A_{jj})\\A'_{ik}&=A'_{ki}=c\,A_{ik}-s\,A_{jk}&k\neq i,j\\A'_{jk}&=A'_{kj}=s\,A_{ik}+c\,A_{jk}&k\neq i,j\\A'_{kl}&=A_{kl}&k,l\neq i,j\end{aligned}}$

де $s=\sin(\Theta )$ та $c=\cos(\Theta )$.

Оскільки вони подібні, то $A$ та $A'$ мають однакову норму Фробеніуса (суму квадратів всіх компонент), з усім тим, ми можемо обрати таке $\Theta$, що $A'_{ij}=0$, і $A'$ має більшу суму квадратів на діагоналі:

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

Якщо прирівняти до нуля, і провести перетворення:

$\tan(2\theta )={\frac {2A_{ij}}{A_{jj}-A_{ii}}}$

Щоб оптимізувати цей ефект, $A_{ij}$ обирають найбільшим за модулем недіагональним елементом, що називають опорним.

Метод Якобі постійно повторює обертання поки матриця не стане майже діагональною. Тоді елементи на діагоналі стають наближеннями власних значень $A$.

Наближені значення власних векторів є стовпцями матриці $U=\prod _{k=1}^{n}G_{k}$.

Збіжність

Метод збігається, оскільки кожна ітерація зменшує недіагональні елементи.

Складність

Кожне обертання Якобі працює за $n$ кроків, якщо відомий опорний елемент $p$. З усім тим, пошук $p$ вимагає перегляд всіх недіагональних елементів матриці.

Література

• Jacobi, C. G. J. (1846). ber ein leichtes Verfahren, die in der Theorie der Skularstrungen vorkommenden Gleichungen numerisch aufzulsen. Crelle's Journal (German) . 30: 51\u201394.

Посилання

• Метод Якобі
• Ітерація Якобі для власних векторів
• Реалізація алгоритму мовою Matlab що уникає тригонометричних функцій