QR algoritmus

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

Využití rozkladu

Nechť ${\boldsymbol {A}}={\boldsymbol {QR}}$, kde ${\boldsymbol {Q}}$ je ortogonální matice a ${\boldsymbol {R}}$ je horní trojúhelníková matice. Pak matice ${\boldsymbol {B}}={\boldsymbol {RQ}}$ je podobná matici ${\boldsymbol {A}}$, protože:

${\boldsymbol {B}}={\boldsymbol {RQ}}\implies {\boldsymbol {BQ}}^{-1}={\boldsymbol {R}}\implies {\boldsymbol {A}}={\boldsymbol {QBQ}}^{-1}={\boldsymbol {QBQ}}^{\mathrm {T} }$

Stejným způsobem je možné vyjádřit matici ${\boldsymbol {B}}={\boldsymbol {Q}}^{\mathrm {T} }{\boldsymbol {AQ}}$. 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

${\boldsymbol {A}}={\boldsymbol {QHQ}}^{\mathrm {T} },\qquad {\text{kde}}\qquad {\boldsymbol {H}}={\begin{pmatrix}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 &\vdots \\&&&h_{n,n-1}&h_{n,n}\\\end{pmatrix}}$,

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$, ${\boldsymbol {A}}_{0}:={\boldsymbol {A}}$ je zadaná matice, případně matice ${\boldsymbol {H}}$ v horním Hessenbergově tvaru,
2. vypočteme QR rozklad ${\boldsymbol {A}}_{k}={\boldsymbol {Q}}_{k}{\boldsymbol {R}}_{k}$,
3. vypočteme novou matici ${\boldsymbol {A}}_{k+1}:={\boldsymbol {R}}_{k}{\boldsymbol {Q}}_{k}$ (z předchozích úvah je zřejmé, že ${\boldsymbol {A}}_{k+1}={\boldsymbol {Q}}_{k}^{\mathrm {T} }{\boldsymbol {A}}_{k}{\boldsymbol {Q}}_{k}$),
4. pokud je ${\boldsymbol {A}}_{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 ${\boldsymbol {Q}}_{k}$ přímo maticí z QR rozkladu, v jistém smyslu tedy eliminuje všechny poddiagonální prvky matice ${\boldsymbol {A}}_{k}$. Jednotlivé iterace je ale možné dělat „jemněji“, resp. postupně. Matice ${\boldsymbol {Q}}_{k}$ může být volena tak, aby byl eliminovala jeden nenulový prvek matice ${\boldsymbol {A}}_{k}$ pod diagonálou. (Možným postupem je volit ${\boldsymbol {Q}}_{k}$ jako Givensovu rotaci ${\boldsymbol {G}}(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 ${\boldsymbol {A}}_{k}\;\longmapsto \;{\boldsymbol {A}}_{k+1}$ popsané v bodech 2 a 3, tedy je-li ${\boldsymbol {A}}_{0}$ v horním Hessenbergově tvaru, jsou také všechny matice ${\boldsymbol {A}}_{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 ${\boldsymbol {A}}$, 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 ${\boldsymbol {A}}_{k}$, ${\boldsymbol {Q}}_{k}$, ${\boldsymbol {R}}_{k}$ reálné (nezávisle na tom, zda matice ${\boldsymbol {Q}}_{k}$ a ${\boldsymbol {R}}_{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 ${\boldsymbol {A}}_{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 ${\boldsymbol {A}}$, 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 ${\boldsymbol {A}}$ symetrická. Při volbě ${\boldsymbol {Q}}_{k}={\boldsymbol {G}}(i,j,\theta )$ dochází k eliminaci nejen prvku ${\boldsymbol {A}}_{ij}$, ale také prvku ${\boldsymbol {A}}_{ji}$. Výsledkem je pak diagonální matice podobná ${\boldsymbol {A}}$.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku QR algorithm na anglické Wikipedii.

Literatura

• DUINTJER TEBBENS, Erik Jurjen; HNĚTYNKOVÁ, Iveta; PLEŠINGER, Martin; STRAKOŠ, Zdeněk; TICHÝ, Petr. Analýza metod pro maticové výpočty: Základní metody. 1. vyd. Praha: Matfyzpress, 2012. xvi+308 s. ISBN 978-80-7378-201-6. 
• HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5. 
• OLŠÁK, Petr. Lineární algebra [online]. Praha: 2007 [cit. 2023-02-20]. Dostupné online. 

Související články

• Ortogonální matice
• QR rozklad

Portály: Matematika