Algoritmus QR

Algoritmus QR je numerická metoda v lineární algebře pro řešení úplného problému vlastních čísel, tedy nalezení všech vlastních čísel a vlastních vektorů matice . Byl vyvinut koncem 50. let nezávisle na sobě V. N. Kublanovskou a J. Francisem.

Algoritmus

Nechť A je skutečná matice, pro kterou chceme najít vlastní čísla a vektory. Dáme A 0 = A . V k -tém kroku (počínaje k = 0) vypočítejte QR rozklad A k = Q k R k , kde Q k je ortogonální matice (tj. Q k T = Q k −1 ) a R k je horní trojúhelníková matice . Potom definujeme A k +1 = R k Q k .

všimněte si, že

A_{k+1}=R_{k}Q_{k}=Q_{k}^{-1}Q_{k}R_{k}Q_{k}=Q_{k}^{-1} A_{k}Q_{k}=Q_{k}^{T}A_{k}Q_{k},

to znamená, že všechny matice A k jsou podobné , to znamená, že jejich vlastní hodnoty jsou stejné.

Nechť jsou všechny diagonální minory matice A nedegenerované . Poté posloupnost matic A k konverguje ve formě do buněčného pravého trojúhelníkového tvaru odpovídající buňkám s vlastními hodnotami stejného modulu. [jeden] $k\to \infty ,$

Abyste získali vlastní vektory matice, musíte vynásobit všechny matice Q k .

Algoritmus je považován za výpočetně stabilní , protože je produkován ortogonálními podobnostními transformacemi.

Důkaz pro symetrickou pozitivně definitní matici

Předpokládáme, že vlastní hodnoty pozitivně definitní matice A jsou seřazeny v sestupném pořadí:

\lambda _{1}>\lambda _{2}>...>\lambda _{n}>0.

Nechat

\Lambda =\mathrm {diag} \left(\lambda _{1},...,\lambda _{n}\right),

a S je matice složená z vlastních vektorů matice A . Potom lze matici A zapsat jako spektrální rozklad

A=S\Lambda S^{T}.

Najděte výraz pro mocniny původní matice pomocí matic Q k a R k . Na jedné straně podle definice QR algoritmu:

A^{k}=A_{1}^{k}=\left(Q_{1}R_{1}\right)^{k}=Q_{1}\left(R_{1}Q_{ 1}\right)^{k-1}R_{1}=Q_{1}A_{2}^{k-1}R_{1}.

Rekurzivní aplikací tohoto vztahu dostaneme:

{\displaystyle A^{k}=Q_{1}\cdot ...\cdot Q_{k}\cdot R_{k}\cdot ...\cdot R_{1))

Zavedením následující notace:

S_{k}=Q_{1}\cdot ...\cdot Q_{k},

T_{k}=R_{k}\cdot ...\cdot R_{1},

dostaneme

A^{k}=S_{k}T_{k}.

Na druhou stranu:

A^{k}=S\Lambda ^{k}S^{T}.

Porovnáním správných částí posledních dvou vzorců dostaneme:

S\Lambda ^{k}S^{T}=S_{k}T_{k}.

Předpokládejme, že existuje LU rozklad matice S T :

S^{T}=LU,

pak

S\Lambda ^{k}LU=S_{k}T_{k}.

Násobíme zprava maticí inverzní k U a poté maticí inverzní k Λ k :

S\Lambda ^{k}L=S_{k}T_{k}U^{-1},

S\Lambda ^{k}L\Lambda ^{-k}=S_{k}T_{k}U^{-1}\Lambda ^{-k}.

Dá se to ukázat

\Lambda ^{k}L\Lambda ^{-k}\to \mathrm {diag} \left(l_{11},...,l_{nn}\right)=L^{\prime } .

Neboť bez ztráty obecnosti můžeme předpokládat, že na diagonále matice L jsou jednotky $k\to \infty$

S_{k}T_{k}U^{-1}\Lambda ^{-k}\to S.

Označit

P_{k}=T_{k}U^{-1}\Lambda ^{-k},

navíc matice P k je horní trojúhelníková, jako součin horních trojúhelníkových a diagonálních matic.

Tím jsme to dokázali

S_{k}P_{k}\to S

Z jedinečnosti QR rozkladu vyplývá, že pokud součin ortogonální a trojúhelníkové matice konverguje k ortogonální matici, pak trojúhelníková matice konverguje k matici identity . Z toho, co bylo řečeno, vyplývá

S_{k}=Q_{1}\cdot ...\cdot Q_{k}\to S.

To znamená, že matice S k konvergují k matici vlastních vektorů matice A .

Protože

A_{k+1}=Q_{k}^{T}A_{k}Q_{k}=...=\left(Q_{k}^{T}\cdot ...\cdot Q_ {1}^{T}\right)A_{1}\left(Q_{1}\cdot ...\cdot Q_{k}\right)=\left(Q_{1}\cdot ...\cdot Q_{k}\right)^{T}A\left(Q_{1}\cdot ...\cdot Q_{k}\right),

pak

A_{k+1}=S_{k}^{T}AS_{k}.

Překročením limitu dostaneme:

\lim _{k\to \infty }A_{k}=\lim _{k\to \infty }A_{k+1}=S^{T}AS=S^{T}S\Lambda S^{T}S=\Lambda .

Dokázali jsme tedy, že algoritmus QR nám umožňuje vyřešit úplný problém vlastních čísel pro symetrickou pozitivně definitní matici.

Implementace QR algoritmu

Za určitých podmínek posloupnost matic konverguje k trojúhelníkové matici, Schurově rozkladu matice . V tomto případě jsou vlastní hodnoty trojúhelníkové matice umístěny na její diagonále a problém nalezení vlastních hodnot je považován za vyřešený. V testech konvergence není praktické vyžadovat přesné nuly v nulové části matice, ale lze použít Gershgorinův teorém , který nastavuje meze chyb. $A_k$ $A$

V počátečním stavu matice (bez dodatečných transformací) jsou náklady na iterace poměrně vysoké. Náklady na algoritmus lze snížit tak, že se matice nejprve převede do tvaru horní Hessenbergovy matice (náklady na její získání metodou založenou na Householderově transformaci se odhadují jako aritmetické operace) a poté se použije konečná posloupnost ortogonálních podobnostní transformace. Tento algoritmus je poněkud podobný oboustrannému rozkladu QR. (Při obvyklém QR rozkladu je matice odrazu domácnosti násobena originálem pouze vlevo, zatímco v případě použití Hessenbergovy formy je matice odrazu násobena originálem jak vlevo, tak i vpravo.) Nalezení QR rozkladu horní Hessenbergovy matice je vyhodnoceno jako aritmetické operace. Vzhledem k tomu, že tvar Hessenbergovy matice je téměř horní trojúhelníkový (má pouze jeden subdiagonální prvek, který se nerovná nule), je možné okamžitě snížit počet iterací potřebných pro konvergenci QR algoritmu. . $A$ ${10 \over 3}n^{3}+O(n^{2})$ $6n^{2}+O(n)$

Pokud je původní matice symetrická, horní Hessenbergova matice je také symetrická a tedy tridiagonální. Celá posloupnost matic má stejnou vlastnost . V tomto případě se náklady na postup odhadují jako aritmetické operace s použitím metody založené na transformaci domácnosti. Nalezení QR rozkladu symetrické tridiagonální matice se vyhodnocuje jako operace. $A_k$ ${4 \over 3}n^{3}+O(n^{2})$ $Na)$

Rychlost konvergence závisí na stupni separace vlastních hodnot a v praktické implementaci se „posuny“ používají explicitně nebo implicitně ke zvýšení separace vlastních hodnot a k urychlení konvergence. Algoritmus QR ve své typické formě pro symetrické matice přesně najde jednu vlastní hodnotu (snížení rozměru matice) v jedné nebo dvou iteracích, díky čemuž je tento přístup účinný a robustní.

Implicitní implementace QR algoritmu

V moderní výpočetní praxi je QR algoritmus implementován pomocí jeho implicitní verze, která zjednodušuje přidávání více „posunů“. Zpočátku je matice redukována na formu horní Hessenbergovy matice , stejně jako v explicitní verzi. Poté se v každém kroku první sloupec transformuje pomocí nízkorozměrné transformace podobnosti domácnosti na první sloupec (nebo ), kde je polynom stupně , který určuje strategii „posunů“ (obvykle , kde a jsou dvě vlastní čísla zbytkové submatice 2×2 se jedná o tzv. implicitní dvojitý posun). Poté se provedou postupné Householderovy transformace dimenze , aby se pracovní matice vrátila do formy horní Hessenbergovy matice. $A_{0}=QAQ^{T}$ $A_k$ $p(A_{k})$ ${\displaystyle p(A_{k})e_{1))$ $p(A_{k})$ $r$ $p(x)=(x-\lambda )(x-{\bar {\lambda )))$ $\lambda$ ${\bar {\lambda ))$ $A_k$ $r+1$ $A_k$

Poznámky

↑ Numerické metody / N. S. Bakhvalov, N. P. Zhidkov, G. M. Kobelkov. - 3. vyd. - M. : BINOM, Knowledge Laboratory, 2004. - S. 321. - 636 s. — ISBN 5-94774-175-X .

Odkazy

Peter Olver's Notes on ortogonal Bases and QR Algorithm

Vektory a matice

vektory

Základní pojmy	Vektor v geometrii Základ Ortogonální základ Vektorové souřadnice Kolinearita Ortogonalita Lineární závislost Prostor sloupců
Druhy vektorů	Jednotkový vektor Axiální vektor izotropní vektor Normální Kolinearita Nulový vektor Vektor poloměru Vlastní vektor
Operace s vektory	Skalární součin vektorový produkt smíšený produkt Pseudoskalární produkt Dvojitý křížový produkt
Typy prostoru	vektorový prostor afinní prostor Euklidovský prostor Pseudoeuklidovský prostor Normovaný prostor Minkowského prostor

matrice

Základní pojmy	Maticové násobení Transponovaná matice Hermitovská konjugovaná matice Symetrická matice inverzní matice Vlastní hodnota Charakteristický polynom matice
Speciální matrice	Matice identity Nulová matice Diagonální matice lambda matrice
Maticové rozklady	LU rozklad Choleský rozklad QR rozklad rozklad LUP singulární rozklad hodnoty Spektrální rozklad matice

jiný