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ť , QR rozkladem nazýváme vztah

,

kde má vzájemně ortonormální sloupce (tj. ) a je v horním trojúhelníkovém tvaru (tj. pro všechna ).

Lineárně nezávislé sloupce [editovat | editovat zdroj]

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

,

kde je unitární (v reálném případě ortogonální) matice, a je horní trojúhelníková regulární matice.

Označme , sloupce matic , platí

,

přičemž značí lineární obal. Tedy a obsahuje ortonormální bázi prostoru generovaného sloupci matice .

Pokud navíc volíme diagonální prvky matice kladné, je QR pak rozklad

jednoznačný. Je-li , tedy je-li regulární, pak a nulový blok v matici neexistují, , a tedy i QR rozklad lze volit jednoznačný.

Lineárně závislé sloupce [editovat | editovat zdroj]

Pokud má rozkládaná matice lineárně závislé sloupce, QR rozklad zpravidla uvažujeme tak, aby i nadále platilo . Nechť , pak

,

kde oproti předchozímu případu a je v horním schodovitém tvaru (pokud je pak blok a nulový blok v matici neexistují).

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

,

kde 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 nazveme transponovaný a komplexně sdružený (tzv. hermitovsky sdružený) QR rozklad matice . Tedy, je-li

,

kde je v dolním trojúhelníkovém tvaru, představuje LQ rozklad matice .