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

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

Опис

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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

Збіжність

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

Складність

Кожне обертання Якобі працює за ${\displaystyle n}$ кроків, якщо відомий опорний елемент ${\displaystyle p}$. З усім тим, пошук ${\displaystyle 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 що уникає тригонометричних функцій