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:
Stejným způsobem je možné vyjádřit matici . 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
- ,
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)
- , je zadaná matice, případně matice v horním Hessenbergově tvaru,
- vypočteme QR rozklad ,
- vypočteme novou matici (z předchozích úvah je zřejmé, že ),
- pokud je trojúhelníková matice, má vlastní čísla na diagonále. Jinak položíme a pokračujeme druhým krokem algoritmu.
V právě popsaném algoritmu je matice přímo maticí z QR rozkladu, v jistém smyslu tedy eliminuje všechny poddiagonální prvky matice . Jednotlivé iterace je ale možné dělat „jemněji“, resp. postupně. Matice může být volena tak, aby byl eliminovala jeden nenulový prvek matice pod diagonálou. (Možným postupem je volit jako Givensovu rotaci , kde a jsou indexy řádku a sloupce eliminovaného prvku; k tomu je potřeba nalézt úhel , pod kterým lze prvek eliminovat.)
Horního Hessenbergova tvar má hned několik výhod: Tento tvar je invariantní vůči transformaci popsané v bodech 2 a 3, tedy je-li v horním Hessenbergově tvaru, jsou také všechny matice v horním Hessenbergově tvaru. V matici navíc potřebujeme eliminovat pouze nenulových poddiagonálních prvků, k výpočtu QR rozkladu tedy potřebujeme pouze 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 , , reálné (nezávisle na tom, zda matice a (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 (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ě dochází k eliminaci nejen prvku , ale také prvku . Výsledkem je pak diagonální matice podobná .
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