QR algoritmus

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

Využití rozkladu

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

${\displaystyle {\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 ${\displaystyle {\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

${\displaystyle {\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. ${\displaystyle k:=0}$, ${\displaystyle {\boldsymbol {A}}_{0}:={\boldsymbol {A}}}$ je zadaná matice, případně matice ${\displaystyle {\boldsymbol {H}}}$ v horním Hessenbergově tvaru,
2. vypočteme QR rozklad ${\displaystyle {\boldsymbol {A}}_{k}={\boldsymbol {Q}}_{k}{\boldsymbol {R}}_{k}}$,
3. vypočteme novou matici ${\displaystyle {\boldsymbol {A}}_{k+1}:={\boldsymbol {R}}_{k}{\boldsymbol {Q}}_{k}}$ (z předchozích úvah je zřejmé, že ${\displaystyle {\boldsymbol {A}}_{k+1}={\boldsymbol {Q}}_{k}^{\mathrm {T} }{\boldsymbol {A}}_{k}{\boldsymbol {Q}}_{k}}$),
4. pokud je ${\displaystyle {\boldsymbol {A}}_{k+1}}$ trojúhelníková matice, má vlastní čísla na diagonále. Jinak položíme ${\displaystyle k:=k+1}$ a pokračujeme druhým krokem algoritmu.

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

Horního Hessenbergova tvar má hned několik výhod: Tento tvar je invariantní vůči transformaci ${\displaystyle {\boldsymbol {A}}_{k}\;\longmapsto \;{\boldsymbol {A}}_{k+1}}$ popsané v bodech 2 a 3, tedy je-li ${\displaystyle {\boldsymbol {A}}_{0}}$ v horním Hessenbergově tvaru, jsou také všechny matice ${\displaystyle {\boldsymbol {A}}_{k}}$ v horním Hessenbergově tvaru. V matici navíc potřebujeme eliminovat pouze ${\displaystyle n-1}$ nenulových poddiagonálních prvků, k výpočtu QR rozkladu tedy potřebujeme pouze ${\displaystyle 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 ${\displaystyle {\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 ${\displaystyle {\boldsymbol {A}}_{k}}$, ${\displaystyle {\boldsymbol {Q}}_{k}}$, ${\displaystyle {\boldsymbol {R}}_{k}}$ reálné (nezávisle na tom, zda matice ${\displaystyle {\boldsymbol {Q}}_{k}}$ a ${\displaystyle {\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 ${\displaystyle {\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 ${\displaystyle {\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 ${\displaystyle {\boldsymbol {A}}}$ symetrická. Při volbě ${\displaystyle {\boldsymbol {Q}}_{k}={\boldsymbol {G}}(i,j,\theta )}$ dochází k eliminaci nejen prvku ${\displaystyle {\boldsymbol {A}}_{ij}}$, ale také prvku ${\displaystyle {\boldsymbol {A}}_{ji}}$. Výsledkem je pak diagonální matice podobná ${\displaystyle {\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