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.)

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

${\displaystyle A=QR}$,

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

Pokud má matice ${\displaystyle A}$ lineárně nezávislé sloupce, pak

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

kde ${\displaystyle 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, ${\displaystyle Q_{1}\in \mathbb {F} ^{m\times n},\;R\in \mathbb {F} ^{m\times n}}$ a ${\displaystyle R_{1}\,\in \mathbb {F} ^{n\times n}}$ je horní trojúhelníková regulární matice.

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

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

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

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

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

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

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

${\displaystyle 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 ${\displaystyle Q_{1}\in \mathbb {F} ^{m\times r}}$ a ${\displaystyle R_{1}\in \mathbb {F} ^{r\times n}}$ je v horním schodovitém tvaru (pokud je ${\displaystyle m\leq n}$ pak blok ${\displaystyle Q_{2}}$ a nulový blok v matici ${\displaystyle R}$ neexistují).

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

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

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 rozkladem matice ${\displaystyle A}$ nazveme transponovaný a komplexně sdružený (tzv. hermitovsky sdružený) QR rozklad matice ${\displaystyle A^{H}}$. Tedy, je-li

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

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

• 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.