QR rozklad

QR rozklad dané matice je způsob, jak zapsat jistou matici A s lineárně nezávislými sloupci jako součin dvou matic, z nichž sloupce matice Q tvoří ortonormální posloupnost (Q není nutně ortogonální) a matice R je v horním trojúhelníkovém tvaru. (Pozor, nezaměňovat QR rozklad s QR algoritmem, který slouží k výpočtu vlastních čísel čtvercové matice.)

Definice

Nechť $A\in \mathbb {F} ^{m\times n},\;(\mathbb {F} \in \{\mathbb {R} ,\mathbb {C} \})$, QR rozkladem nazýváme vztah

$A=QR$,

kde $Q$ má vzájemně ortonormální sloupce (tj. $Q^{H}Q=I$) a $R$ je v horním trojúhelníkovém tvaru (tj. $r_{k,j}=0$ pro všechna $k>j$).

Lineárně nezávislé sloupce A

Pokud má matice $A$ lineárně nezávislé sloupce, pak

$A=QR=[Q_{1},Q_{2}]\left[{\begin{array}{c}R_{1}\\0\end{array}}\right]=Q_{1}R_{1}$,

kde $Q\in \mathbb {F} ^{m\times m},\;Q^{H}Q=QQ^{H}=I_{m}$ je unitární (v reálném případě ortogonální) matice, $Q_{1}\in \mathbb {F} ^{m\times n},\;R\in \mathbb {F} ^{m\times n}$ a $R_{1}\,\in \mathbb {F} ^{n\times n}$ je horní trojúhelníková regulární matice.

Označme $a_{j},\;q_{j},\;j=1,\ldots ,n$, sloupce matic $A,\;Q_{1}$, platí

$\mathrm {span} (a_{1},\ldots ,a_{j})=\mathrm {span} (q_{1},\ldots ,q_{j}),\quad j=1,\ldots ,n$,

přičemž $\mathrm {span} (\cdot )$ značí lineární obal. Tedy ${\mathcal {R}}(A)={\mathcal {R}}(Q_{1})$ a $Q_{1}$ obsahuje ortonormální bázi prostoru generovaného sloupci matice $A$.

Pokud navíc volíme diagonální prvky matice $R_{1}$ kladné, je QR pak rozklad

$A=Q_{1}R_{1}$

jednoznačný. Je-li $m=n$, tedy je-li $A$ regulární, pak $Q_{2}$ a nulový blok v matici $R$ neexistují, $Q_{1}=Q,\;R_{1}=R$, a tedy i QR rozklad $A=QR$ lze volit jednoznačný.

Lineárně závislé sloupce A

Pokud má rozkládaná matice lineárně závislé sloupce, QR rozklad zpravidla uvažujeme tak, aby i nadále platilo ${\mathcal {R}}(A)={\mathcal {R}}(Q_{1})$. Nechť $A\in \mathbb {F} ^{m\times n},\;\mathrm {rank} (A)=r$, pak

$A=QR=[Q_{1},Q_{2}]\left[{\begin{array}{c}R_{1}\\0\end{array}}\right]=Q_{1}R_{1}$,

kde oproti předchozímu případu $Q_{1}\in \mathbb {F} ^{m\times r}$ a $R_{1}\in \mathbb {F} ^{r\times n}$ je v horním schodovitém tvaru (pokud je $m\leq n$ pak blok $Q_{2}$ a nulový blok v matici $R$ neexistují).

Vždy existuje permutace sloupců matice $A$ realizovaná permutační maticí $\Pi$ tak, že

$A\Pi =QR=[Q_{1},Q_{2}]\left[{\begin{array}{c}R_{1}\\0\end{array}}\right]=[Q_{1},Q_{2}]\left[{\begin{array}{cc}R_{11}&R_{12}\\0&0\end{array}}\right]=Q_{1}[R_{11},R_{12}]$,

kde $R_{11}\in \mathbb {F} ^{r\times r}$ je horní trojúhelníková regulární matice, kterou lze volit tak, že její diagonální prvky jsou kladné.

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.

LQ rozklad

LQ rozkladem matice $A$ nazveme transponovaný a komplexně sdružený (tzv. hermitovsky sdružený) QR rozklad matice $A^{H}$. Tedy, je-li

$A^{H}=QR,\quad {\text{pak}}\quad A=LQ^{H}$,

kde $L=R^{H}$ je v dolním trojúhelníkovém tvaru, představuje LQ rozklad matice $A$.

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.