QR algoritmus

QR algoritmus je numerická metoda pro výpočet vlastních čísel obecné čtvercové $𝑨$ založená na principu QR rozkladu. Výhodou algoritmu je numerická stabilita.

Využití rozkladu

Nechť $𝑨=𝑸𝑹$, kde $𝑸$ je ortogonální matice a $𝑹$ je horní trojúhelníková matice. Pak matice $𝑩=𝑹𝑸$ je podobná matici $𝑨$, protože:

$𝑩=𝑹𝑸⟹{𝑩𝑸}^{-1}=𝑹⟹𝑨={𝑸𝑩𝑸}^{-1}={𝑸𝑩𝑸}^{\mathrm{T}}$

Stejným způsobem je možné vyjádřit matici $𝑩={𝑸}^{\mathrm{T}}𝑨𝑸$. Z podobnosti plyne, že obě matice mají shodná vlastní čísla.

Algoritmus

Finitní transformace na horní Hessenberův tvar (preprocessing)

Iteračnímu QR algoritmu zpravidla předchází transformace matice typicky do horního Hessenbergova tvaru

$𝑨={𝑸𝑯𝑸}^{\mathrm{T}},\text{kde}𝑯=\left(\begin{array}{ccccc}{h}_{11}& h_{12}& h_{13}& \cdots & h_{1n}\\ h_{21}& h_{22}& h_{23}& \cdots & h_{2n}\\ & h_{32}& h_{33}& \cdots & h_{3n}\\ & & \ddots & \ddots & ⋮\\ & & & h_{n,n-1}& h_{n,n}\end{array}\right)$,

tedy do „skoro trojúhelníkového“ tvaru, až na obecně nenulovou první poddiagonálu. Tuto transformaci lze provést v konečném počtu kroků (tj. pomocí konečného počtu elementárních aritmetických operací sčítání, odečítání, násobení, dělení a výpočtu druhé odmocniny), např. pomocí tzv. Arnoldiho algoritmu.

Vlastní iterační algoritmus

Samotný iterační QR algoritmus konverguje limitně (pokud konverguje)

1. $k:=0$, ${𝑨}_0:=𝑨$ je zadaná matice, případně matice $𝑯$ v horním Hessenbergově tvaru,
2. vypočteme QR rozklad ${𝑨}_k={𝑸}_k{𝑹}_k$,
3. vypočteme novou matici ${𝑨}_{k+1}:={𝑹}_k{𝑸}_k$ (z předchozích úvah je zřejmé, že ${𝑨}_{k+1}={𝑸}_k^{\mathrm{T}}{𝑨}_k{𝑸}_k$),
4. pokud je ${𝑨}_{k+1}$ trojúhelníková matice, má vlastní čísla na diagonále. Jinak položíme $k:=k+1$ a pokračujeme druhým krokem algoritmu.

V právě popsaném algoritmu je matice ${𝑸}_k$ přímo maticí z QR rozkladu, v jistém smyslu tedy eliminuje všechny poddiagonální prvky matice ${𝑨}_k$. Jednotlivé iterace je ale možné dělat „jemněji“, resp. postupně. Matice ${𝑸}_k$ může být volena tak, aby byl eliminovala jeden nenulový prvek matice ${𝑨}_k$ pod diagonálou. (Možným postupem je volit ${𝑸}_k$ jako Givensovu rotaci $𝑮(i,j,\theta )$, kde $i$ a $j$ jsou indexy řádku a sloupce eliminovaného prvku; k tomu je potřeba nalézt úhel $\theta$, pod kterým lze prvek eliminovat.)

Horního Hessenbergova tvar má hned několik výhod: Tento tvar je invariantní vůči transformaci ${𝑨}_k⟼{𝑨}_{k+1}$ popsané v bodech 2 a 3, tedy je-li ${𝑨}_0$ v horním Hessenbergově tvaru, jsou také všechny matice ${𝑨}_k$ v horním Hessenbergově tvaru. V matici navíc potřebujeme eliminovat pouze $n-1$ nenulových poddiagonálních prvků, k výpočtu QR rozkladu tedy potřebujeme pouze $n-1$ Givensových rotací.

Pořadí eliminovaných prvků může být např. podle indexů nebo podle velikosti prvku v absolutní hodnotě (vždy ten největší) atp. Další výhodou horního Hessenbergova tvaru je triviální pozorování, že se s každou úspěšnou eliminací poddiagonálního prvku:

• buď zmenší efektivní rozměr matice o jedna přičemž zároveň dojde k identifikaci jednoho vlastního čísla (když dojde k eliminaci prvního, nebo posledního poddiagonálního prvku),
• nebo se úloha rozpadne na dvě menší zcela nezávislé podúlohy, což je možné využít k paralelizaci (ve všech ostatních případech).

Poznámka ke konvergenci

Zde prezentovaný QR algoritmus nemusí vždy konvergovat ke trojúhelníkové matici. V praxi se (nejen) proto používá řada sofistikovaných „triků“, které chování algoritmu vylepšují.

Pro příklad, kdy shora uvedený algoritmus nebude konvergovat, stačí uvažovat reálnou čtvercovou matici $𝑨$, která má alespoň jedno vlastní číslo s nenulovou imaginární složkou (pro jednoduchost budeme říkat komplexní vlastní číslo). V důsledku jsou zřejmě všechny matice ${𝑨}_k$, ${𝑸}_k$, ${𝑹}_k$ reálné (nezávisle na tom, zda matice ${𝑸}_k$ a ${𝑹}_k$ (viz krok 2) pocházejí přímo z QR rozkladu, nebo zda mají původ jen v jediné Givensově rotaci; součiny reálných matic ${𝑨}_{k+1}$ (viz krok 3) jsou opět pouze reálné matice). Trojúhelníková matice, ke které bychom rádi dokonvergovali (viz krok 4), má ale na diagonále vlastní čísla matice $𝑨$, je tedy nutně komplexní.

Jacobiova diagonalizace

Speciálním případem QR algoritmu je Jacobiova diagonalizace pojmenovaná po matematikovi Carlu Gustavu Jacobu Jacobiovi. Tento případ nastává, pokud je matice $𝑨$ symetrická. Při volbě ${𝑸}_k=𝑮(i,j,\theta )$ dochází k eliminaci nejen prvku ${𝑨}_{ij}$, ale také prvku ${𝑨}_{ji}$. Výsledkem je pak diagonální matice podobná $𝑨$.

Odkazy

Literatura

• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace elektronické monografie

Související články

• Ortogonální matice
• QR rozklad