QR rozklad

QR rozkladem se v lineární algebře rozumí zápis reálné nebo komplexní matice ${\boldsymbol {A}}$ jako součin matice ${\boldsymbol {Q}}$ s ortonormálními sloupci a matice ${\boldsymbol {R}}$ v odstupňovaném tvaru.^[1] Bývá nazývaný také QR faktorizace nebo QU rozklad a v literatuře se objevuje v různých podobách podle podmínek kladených na matice ${\boldsymbol {Q}}$ a ${\boldsymbol {R}}$ .

QR rozklad lze získat různými způsoby, např. z Choleského rozkladu, Gramovou–Schmidtovou ortogonalizací, pomocí Householderových reflexí nebo pomocí Givensových rotací.

QR rozklad lze použít k řešení problému lineární regrese a je základem QR algoritmu pro výpočet vlastních čísel.

QR rozklad je speciální případ Iwasawova rozkladu.

Definice

Každou čtvercovou komplexní matici ${\boldsymbol {A}}$ lze rozložit na součin unitární matice ${\boldsymbol {Q}}$ a horní trojúhelníkové matice ${\boldsymbol {R}}$ s reálnými nezápornými prvky na diagonále.^[2] Tento součin ${\boldsymbol {QR}}$ se nazývá QR rozkladem matice ${\boldsymbol {A}}$ .^{[pozn. 1]}

QR rozklad ${\boldsymbol {A}}={\boldsymbol {Q}}{\boldsymbol {R}}$ může zahrnovat i následující obecnější situace:

${\boldsymbol {A}}\in \mathbb {C} ^{m\times n}$ , ${\boldsymbol {Q}}\in \mathbb {C} ^{m\times m}$ unitární a ${\boldsymbol {R}}\in \mathbb {C} ^{m\times n}$ s nezápornými prvky na diagonále a nulami pod diagonálou,^[1]
${\boldsymbol {A}}\in \mathbb {C} ^{m\times n}$ , kde $m\geq n$ , ${\boldsymbol {Q}}\in \mathbb {C} ^{m\times n}$ s ortonormálními sloupci a ${\boldsymbol {R}}$ je horní trojúhelníková matice s nezápornými prvky na diagonále, tzv. ekonomický QR rozklad^[1] nebo též redukovaný QR rozklad,
${\boldsymbol {A}}\in \mathbb {C} ^{m\times n}$ hodnosti $r$ , ${\boldsymbol {Q}}\in \mathbb {C} ^{m\times r}$ s ortonormálními sloupci a ${\boldsymbol {R}}\in \mathbb {C} ^{r\times n}$ v odstupňovaném tvaru s kladnými pivoty (angl. reduced rank QR decomposition).^[3]

QR rozklad reálných matic

Stejným způsobem lze definovat rozklad reálné matice ${\boldsymbol {A}}$ na součin reálných matic ${\boldsymbol {Q}}$ a ${\boldsymbol {R}}$ .^[4] Unitární matice ${\boldsymbol {Q}}$ se v těchto případech stane ortogonální maticí.

Ukázka

QR rozklad reálné matice řádu 3 je např.:

{\boldsymbol {A}}={\begin{pmatrix}2&2&3\\2&-4&6\\-1&-4&0\end{pmatrix}}={\begin{pmatrix}2/3&1/3&2/3\\2/3&-2/3&-1/3\\-1/3&-2/3&2/3\end{pmatrix}}{\begin{pmatrix}3&0&6\\0&6&-3\\0&0&0\end{pmatrix}}={\boldsymbol {QR}}

Matice ${\boldsymbol {Q}}$ je ortonormální, protože pro ni platí: ${\boldsymbol {Q}}^{\mathsf {T}}{\boldsymbol {Q}}={\boldsymbol {QQ}}^{\mathsf {T}}=\mathbf {I}$ . Pokud by byla brána jako komplexní matice, je i unitární, protože ${\boldsymbol {Q}}^{\mathsf {H}}{\boldsymbol {Q}}={\boldsymbol {QQ}}^{\mathsf {H}}=\mathbf {I}$ .

Ekonomický QR rozklad téže matice je

{\boldsymbol {A}}={\begin{pmatrix}2&2&3\\2&-4&6\\-1&-4&0\end{pmatrix}}={\begin{pmatrix}2/3&1/3\\2/3&-2/3\\-1/3&-2/3\end{pmatrix}}{\begin{pmatrix}3&0&6\\0&6&-3\\\end{pmatrix}}={\boldsymbol {QR}}

Matice ${\boldsymbol {Q}}$ má ortonormální sloupce a stále pro ni platí ${\boldsymbol {Q}}^{\mathsf {T}}{\boldsymbol {Q}}=\mathbf {I}$ . Uvedená matice má však více sloupců než řádků, a proto ${\boldsymbol {QQ}}^{\mathsf {T}}\neq \mathbf {I}$ .

Existence a vlastnosti

Existence QR rozkladu pro regulární matice vyplývá např. z Choleského rozkladu matice ${\boldsymbol {A}}^{\mathsf {H}}{\boldsymbol {A}}$ , která je vždy pozitivně definitní. Je-li ${\boldsymbol {A}}^{\mathsf {H}}{\boldsymbol {A}}={\boldsymbol {R}}^{\mathsf {H}}{\boldsymbol {R}}$ , potom ${\boldsymbol {Q}}={\boldsymbol {AR}}^{-1}$ je unitární, protože:^[5]

{\boldsymbol {QQ}}^{\mathsf {H}}={\boldsymbol {AR}}^{-1}({\boldsymbol {AR}}^{-1})^{\mathsf {H}}={\boldsymbol {AR}}^{-1}({\boldsymbol {R}}^{-1})^{\mathsf {H}}{\boldsymbol {A}}^{\mathsf {H}}={\boldsymbol {A}}({\boldsymbol {R}}^{\mathsf {H}}{\boldsymbol {R}})^{-1}{\boldsymbol {A}}^{\mathsf {H}}={\boldsymbol {A}}({\boldsymbol {A}}^{\mathsf {H}}{\boldsymbol {A}})^{-1}{\boldsymbol {A}}^{\mathsf {H}}={\boldsymbol {AA}}^{-1}({\boldsymbol {A}}^{-1})^{\mathsf {H}}{\boldsymbol {A}}^{\mathsf {H}}=\mathbf {I}

V obecném případě odpovídají sloupce matice ${\boldsymbol {Q}}$ ortonormální bázi sloupcového prostoru matice ${\boldsymbol {A}}$ . Koeficienty lineárních kombinací v Gramově–Schmidtově ortonormalizaci tvoří sloupce matice ${\boldsymbol {R}}$ . Protože jsou sloupce ${\boldsymbol {A}}$ postupně upravovány pomocí lineárních kombinací vůči dříve zpracovaným sloupcům, je matice ${\boldsymbol {R}}$ v odstupňovaném tvaru.

Má-li matice ${\boldsymbol {A}}$ plnou sloupcovou hodnost, čili pokud $\operatorname {rank} {\boldsymbol {A}}=n$ , potom je QR rozklad jednoznačný a matice má ${\boldsymbol {R}}$ kladné prvky na diagonále.^[5]

Unitární matici ${\boldsymbol {Q}}$ pak lze získat rozšířením ortonormální báze sloupcového prostoru matice ${\boldsymbol {A}}$ na ortonormální bázi $\mathbb {C} ^{n}$ a doplněním $m-r$ nulových řádků do matice ${\boldsymbol {R}}$ .

Výpočet QR rozkladu

QR rozklad lze provést pomocí klasického nebo modifikovaného Gramova–Schmidtova algoritmu (případně s iteračním zpřesněním), nebo pomocí Householderových nebo Givensových transformačních matic. Při reálném výpočtu (tj. v aritmetice s konečnou přesností) se všechny zmíněné postupy výrazně liší v přesnosti a rychlosti výpočtu. Přesnost je klíčovým faktorem zejména v případě, že matice obsahuje lineárně závislé sloupce.

Aplikace

QR rozklad je základem řady metod numerické matematiky, například pro určení ortogonální nebo unitární báze nebo pro řešení problému lineární regrese. Je nedílnou součástí QR algoritmu pro aproximaci vlastních čísel.

Řešení regulárních nebo přeurčených soustav rovnic

Řešení ${\boldsymbol {x}}\in \mathbb {R} ^{n}$ soustavy lineárních rovnic ${\boldsymbol {Ax}}={\boldsymbol {b}}$ s maticí ${\boldsymbol {A}}\in \mathbb {R} ^{m\times n},\ m\geq n$ je možné získat následujícím postupem:

Provést QR rozklad matice ${\boldsymbol {A}}={\boldsymbol {Q}}{\boldsymbol {R}}$ ,
Určit součin ${\boldsymbol {z}}={\boldsymbol {Q}}^{\mathsf {T}}{\boldsymbol {b}}$ ,
Vyřešit ${\boldsymbol {Rx}}={\boldsymbol {z}}$ zpětnou substitucí.

Pro čtvercové matice (tj. když $m=n$ ) má uvedený výpočet oproti Gaussově eliminaci přibližně dvojnásobnou složitost, ale může být numericky stabilnější.

Soustava s více rovnicemi než proměnnými (tj. když $m>n$ ) je přeurčená. V tomto případě se ${\boldsymbol {x}}$ určí řešením související úlohy metody nejmenších čtverců, viz regresní analýza:

Minimalizovat

\|{\boldsymbol {Ax}}-{\boldsymbol {b}}\|^{2}=\sum _{j=1}^{m}\left(\sum _{k=1}^{n}a_{j,k}x_{k}-b_{j}\right)^{2}

V tomto případě je ${\boldsymbol {A}}^{+}={\boldsymbol {R}}^{+}{\boldsymbol {Q}}^{\mathsf {T}}$ Mooreova–Penroseova pseudoinverze matice ${\boldsymbol {A}}$ . Hledané řešení lze vyjádřit vztahem ${\boldsymbol {x}}={\boldsymbol {A}}^{+}{\boldsymbol {b}}$ , což zobecňuje obvyklé vyjádření ${\boldsymbol {x}}={\boldsymbol {A}}^{-1}{\boldsymbol {b}}$ pro regulární matici ${\boldsymbol {A}}$ .

Řešení nedourčených soustav rovnic

Pro soustavy s méně rovnicemi než proměnnými (tj. když Pro $m<n$ ) platí, že její matice ${\boldsymbol {A}}$ má netriviální jádro. Pokud by ${\boldsymbol {A}}$ měla plnou řádkovou hodnost, potom množina řešení soustavy ${\boldsymbol {Ax}}={\boldsymbol {b}}$ tvoří afinní podprostor. Jinak lze řešení s nejmenší normou nalézt v ortogonálním doplňku jádra. Numericky je lze určit pomocí QR rozkladu ${\boldsymbol {A}}^{\mathsf {T}}$ následujícím postupem:

Určit QR rozklad matice ${\boldsymbol {A}}^{\mathsf {T}}={\boldsymbol {QR}}$ ,
Vyřešit ${\boldsymbol {R}}^{\mathsf {T}}{\boldsymbol {z}}={\boldsymbol {b}}$ dopřednou substitucí,
Spočítat součin ${\boldsymbol {x}}={\boldsymbol {Qz}}$ .

I v tomto případě je ${\boldsymbol {A}}^{+}={\boldsymbol {Q}}({\boldsymbol {R}}^{\mathsf {T}})^{+}$ Mooreova–Penroseova pseudoinverze matice ${\boldsymbol {A}}$ a pro řešení s nejmenší normou opět platí ${\boldsymbol {x}}={\boldsymbol {A}}^{+}{\boldsymbol {b}}$ .

Rozklady typu LQ, RQ a QL

LQ rozkladem matice ${\boldsymbol {A}}$ je hermitovsky transponovaný rozklad matice ${\boldsymbol {A}}^{\mathsf {H}}$ . Z rozkladu ${\boldsymbol {A}}^{\mathsf {H}}={\boldsymbol {Q}}{\boldsymbol {R}}$ pak vyplývá ${\boldsymbol {A}}={\boldsymbol {LQ}}^{\mathsf {H}}$ , kde ${\boldsymbol {L}}={\boldsymbol {R}}^{\mathsf {H}}$ znamená matici s nulami nad diagonálou (z angl. left nebo lower), a pokud ${\boldsymbol {Q}}$ není čtvercová, pak má ortonormální řádky.

Pomocí sloupcových operací lze analogickým způsobem získat rozklady typu RQ a QL. Například Gramova–Schmidtova ortogonalizace řádků ${\boldsymbol {A}}$ prováděná v pořadí od posledního řádku k prvnímu poskytuje RQ rozklad.

Odkazy

Poznámky

↑ Značení součinu zkratkou QR zavedl J. G. F. Francis ve svém článku z roku 1961 aby jej použil pro QR transformaci jako nástroj pro numericky stabilní aproximační výpočet vlastních čísel asymetrických matic. Symbol R pochází z angl. right triangular.

Reference

V tomto článku byly použity překlady textů z článků QR-Zerlegung na německé Wikipedii a QR decomposition na anglické Wikipedii.

↑ ^a ^b ^c 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. S. 47-48.
↑ FRANCIS, J. G. F. The QR Transformation A Unitary Analogue to the LR Transformation—Part 1. The Computer Journal. 1961-01-01, roč. 4, čís. 3, s. 265–271. Dostupné online [cit. 2025-01-05]. ISSN 0010-4620. doi:10.1093/comjnl/4.3.265.
↑ Uniqueness of the reduced rank QR decomposition. MathOverflow [online]. [cit. 2025-01-06]. Dostupné online. (anglicky)
↑ HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5. S. 39.
↑ ^a ^b GOLUB, Gene H.; VAN LOAN, Charles F. Matrix computations. 3rd ed. vyd. Baltimore: Johns Hopkins University Press 694 s. (Johns Hopkins studies in the mathematical sciences). ISBN 978-0-8018-5413-2, ISBN 978-0-8018-5414-9. S. 230, Theorem 5.2.2.

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. S. 39.

Související články

[3] Značení součinu zkratkou QR zavedl J. G. F. Francis ve svém článku z roku 1961 aby jej použil pro QR transformaci jako nástroj pro numericky stabilní aproximační výpočet vlastních čísel asymetrických matic. Symbol R pochází z angl. right triangular.

[TrebbensHPST-1] 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. S. 47-48.

[Francis-2] FRANCIS, J. G. F. The QR Transformation A Unitary Analogue to the LR Transformation—Part 1. The Computer Journal. 1961-01-01, roč. 4, čís. 3, s. 265–271. Dostupné online [cit. 2025-01-05]. ISSN 0010-4620. doi:10.1093/comjnl/4.3.265.

[4] Uniqueness of the reduced rank QR decomposition. MathOverflow [online]. [cit. 2025-01-06]. Dostupné online. (anglicky)

[5] HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5. S. 39.

[GolubVanLoan-6] GOLUB, Gene H.; VAN LOAN, Charles F. Matrix computations. 3rd ed. vyd. Baltimore: Johns Hopkins University Press 694 s. (Johns Hopkins studies in the mathematical sciences). ISBN 978-0-8018-5413-2, ISBN 978-0-8018-5414-9. S. 230, Theorem 5.2.2.

[1]

[2]

[pozn. 1]

[3]

[4]

[5]