Kapitola 13
Jacobiho metoda pro vlastní čísla reálné symetrické matice
Základní myšlenka
Jacobiho metoda je základní jednoduchá metoda pro výpočet vlastních čísel reálných symetrických matic. Její základní myšlenkou je nulování mimodiagonálních prvků pomocí rotace, tedy pomocí ortogonální transformace.
Matici typu \(2 \times 2\) lze diagonalizovat přesně. Máme
\[ A = \begin{pmatrix} a & d \\ d & b \end{pmatrix} \]a hledáme matici
\[ J = \begin{pmatrix} c & s \\ -s & c \end{pmatrix} , \qquad \begin{aligned} c &= \cos\varphi , \\ s &= \sin\varphi , \end{aligned} \]takovou, aby platilo
\[ J^T A J = \begin{pmatrix} x & 0 \\ 0 & y \end{pmatrix} . \]Dostaneme podmínku
\begin{equation}\label{eq:12a:podminka_2x2} d\,(c^2 - s^2) - cs\,(b-a) = 0 , \end{equation}neboli
\begin{equation}\label{eq:12a:tg_2fi} \mathrm{tg}\, 2\varphi = \frac{2d}{b-a} . \end{equation}Nulování mimodiagonálních prvků obecné matice
Pro větší matice nulujeme prvky pod diagonálou a nad diagonálou iteračně, a to pomocí matic typu
\begin{equation}\label{eq:12a:matice_p} P = \begin{pmatrix} 1 & \ddots & & & & 0 \\ & & c & 0 & s & \\ & & 0 & 1 & 0 & \\ & & -s & 0 & c & \\ 0 & & & & \ddots & 1 \end{pmatrix} . \end{equation}Použitím takovéto matice sice vynulujeme prvek na příslušném řádku a v příslušném sloupci, ale zároveň zrušíme nuly z předchozích iterací. Přesto to funguje: provádíme-li toto nulování postupně několikrát pro všechny mimodiagonální prvky, dostaneme nakonec diagonální matici.
Nulujeme-li prvek \(a_{pq}\) (a tedy též \(a_{qp}\)) na \(p\)-tém řádku a v \(q\)-tém sloupci, změní se \(p\)-tý a \(q\)-tý řádek a sloupec takto:
\begin{equation}\label{eq:12a:zmena_radku} \begin{aligned} a'_{rp} &= a'_{pr} = c\,a_{rp} - s\,a_{rq} \\ a'_{rq} &= a'_{qr} = c\,a_{rq} + s\,a_{rp} \end{aligned} \qquad \text{pro } r \neq p \text{ a } r \neq q , \end{equation}a dále
\begin{align*} a'_{pp} &= c^2 a_{pp} + s^2 a_{qq} - 2cs\,a_{pq} , \\ a'_{qq} &= s^2 a_{pp} + c^2 a_{qq} + 2cs\,a_{pq} , \\ a'_{pq} &= a'_{qp} = (c^2 - s^2)\,a_{pq} + cs\,(a_{pp} - a_{qq}) = 0 . \end{align*}Z poslední podmínky plyne, že musí být
\begin{equation}\label{eq:12a:cotg_2fi} \mathrm{cotg}\,(2\varphi) = \frac{c^2 - s^2}{2cs} = \frac{a_{qq} - a_{pp}}{2a_{pq}} . \end{equation}Numericky stabilní formulace
Tato základní verze se ovšem kvůli stabilitě nepoužívá. Zaokrouhlovací chyby se projeví méně, pokud vše přepíšeme následujícím způsobem.
Označme
\begin{equation}\label{eq:12a:theta} t = \frac{s}{c} , \qquad \Theta = \mathrm{cotg}\,(2\varphi) = \frac{c^2 - s^2}{2sc} = \frac{1 - t^2}{2t} . \end{equation}Veličinu \(t\) lze vyjádřit přímo pomocí \(\Theta = \dfrac{a_{qq} - a_{pp}}{2a_{pq}}\) řešením kvadratické rovnice
\begin{equation}\label{eq:12a:kvadraticka} t^2 + 2t\Theta - 1 = 0 \quad \Rightarrow \quad t = -\Theta \pm \sqrt{\Theta^2 + 1} , \end{equation}přičemž se ukazuje, že stabilnější volbou je menší ze dvou kořenů:
\begin{equation}\label{eq:12a:volba_t} t = \begin{cases} -\Theta + \sqrt{\Theta^2+1} = \dfrac{1}{\Theta + \sqrt{\Theta^2+1}} & \text{pro } \Theta > 0 , \\[3mm] -\Theta - \sqrt{\Theta^2+1} = \dfrac{-1}{-\Theta + \sqrt{\Theta^2+1}} & \text{pro } \Theta < 0 , \end{cases} \end{equation}tedy dohromady
\begin{equation}\label{eq:12a:t_sign} t = \frac{\mathrm{sign}(\Theta)}{|\Theta| + \sqrt{\Theta^2+1}} . \end{equation}Vyjádření kořenů pomocí zlomků v \eqref{eq:12a:volba_t} se používá kvůli odečítání dvou blízkých čísel ve jmenovateli pro velké \(\Theta\). Je-li \(\Theta\) příliš velké, takže by \(\Theta^2\) přeteklo, klademe \(t = \dfrac{1}{2\Theta}\).
Hodnoty \(s\) a \(c\) lze z \(t\) vyjádřit takto:
\begin{equation}\label{eq:12a:s_a_c} t^2 = \frac{1 - c^2}{c^2} \quad \Rightarrow \quad c = \frac{1}{\sqrt{t^2+1}} \; , \quad s = tc . \end{equation}S využitím vztahu \(a_{qq} = a_{pp} + \dfrac{c^2 - s^2}{cs}\,a_{pq}\) dostaneme nakonec
\begin{align*} a'_{pq} &= a'_{qp} = 0 & \qquad a'_{rp} &= a'_{pr} = a_{rp} - s\,(a_{rq} + \tau\,a_{rp}) \\ a'_{pp} &= a_{pp} - t\,a_{pq} & \qquad a'_{rq} &= a'_{qr} = a_{rq} + s\,(a_{rp} - \tau\,a_{rq}) \\ a'_{qq} &= a_{qq} + t\,a_{pq} & \qquad \text{kde } \tau &= \frac{s}{1+c} \; . \end{align*}Konvergence a náročnost
Lze spočítat, že suma mimodiagonálních prvků
\begin{equation}\label{eq:12a:suma_s} S = \sum_{r \neq s} |a_{rs}|^2 \end{equation}se změní na
\begin{equation}\label{eq:12a:zmena_s} S' = S - 2|a_{pq}|^2 , \end{equation}tedy se zmenší. Postupně tak zmenšujeme \(S\) na nulu; je-li \(a_{pq}\) „malé“, vynechává se.
Jak rychle konvergence probíhá?
Pokud bychom vždy volili největší \(a_{pq} > \dfrac{S}{n^2}\), pak by platilo
\begin{equation}\label{eq:12a:odhad_s} S' < \left(1 - \frac{1}{n^2}\right)S \quad \Rightarrow \quad S^{(k)} < \left(1 - \frac{1}{n^2}\right)^k S , \end{equation}a protože každý krok vyžaduje \(\mathcal{O}(n)\) operací, bude celkem potřeba \(\mathcal{O}(n^3)\) operací. Obecně je ovšem tato diskuze o něco delší.
Vlastní vektory
Vlastní vektory lze získat jako sloupce matice
\begin{equation}\label{eq:12a:vlastni_vektory} V = \jednotkovamatice \cdot P_1 P_2 \dots P_k , \end{equation}kterou počítáme postupnou změnou matice \(V = \jednotkovamatice\) pomocí vztahů
\begin{align*} v'_{rs} &= v_{rs} \; , \quad s \neq p \, , \; s \neq q , \\ v'_{rp} &= c\,v_{rp} - s\,v_{rq} = v_{rp} - s\,(v_{rq} + \tau v_{rp}) , \\ v'_{rq} &= s\,v_{rp} + c\,v_{rq} = v_{rq} + s\,(v_{rp} - \tau v_{rq}) . \end{align*}