QR rozklad

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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.