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

Метод обертання Якобі — це чисельний алгоритм розв'язання повної задачі власних значень для симетричної матриці з дійсних чисел. Названий на честь Якобі, який і придумав цей метод у 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.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.