QR rozklad

Tento článek potřebuje úpravy.

Můžete Wikipedii pomoci tím, že ho vylepšíte. Jak by měly články vypadat, popisují stránky Vzhled a styl, Encyklopedický styl a Odkazy.

QR rozklad dané matice je způsob, jak zapsat tuto matici jako součin dvou matic z nichž jedna je ortogonální, případně má alespoň vzájemně ortonormální sloupce, a druhá 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^HQ=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_1R_1$,

kde $Q\in\mathbb{F}^{m\times m},\;Q^HQ=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_1R_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_1R_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$.