QR rozklad

Technology

12 hours ago

Author

Albert Flores

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^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. +more 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.