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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Опис[ред.ред. код]

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

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

A'=G^\top A G \,

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

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

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

де 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{2 A_{ij}}{A_{jj} - A_{ii}}

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

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

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

Збіжність[ред.ред. код]

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

Складність[ред.ред. код]

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


Література[ред.ред. код]

Посилання[ред.ред. код]