QR rozklad

QR rozklad matice $𝑨$ v obecné situaci. Purpurově jsou vyznačené kladné pivoty, žluté šrafování odpovídá nulám. Modře je vyznačena část odpovídající ekonomickému QR rozkladu vzhledem k hodnosti $r$. V matici $𝑸$ jsou naznačeny ortonormální sloupce.

QR rozkladem se v lineární algebře rozumí zápis reálné nebo komplexní matice $𝑨$ jako součin matice $𝑸$ s ortonormálními sloupci a matice $𝑹$ v odstupňovaném tvaru. Bývá nazývaný také QR faktorizace nebo QU rozklad a v literatuře se objevuje v různých podobách podle podmínek kladených na matice $𝑸$ a $𝑹$.

QR rozklad lze získat různými způsoby, např. z Choleského rozkladu, Gramovou–Schmidtovou ortogonalizací, pomocí Householderových reflexí nebo pomocí Givensových rotací.

QR rozklad lze použít k řešení problému lineární regrese a je základem QR algoritmu pro výpočet vlastních čísel.

QR rozklad je speciální případ Iwasawova rozkladu.

Definice

Každou čtvercovou komplexní matici $𝑨$ lze rozložit na součin unitární matice $𝑸$ a horní trojúhelníkové matice $𝑹$ s reálnými nezápornými prvky na diagonále. Tento součin $𝑸𝑹$ se nazývá QR rozkladem matice $𝑨$.

QR rozklad $𝑨=𝑸𝑹$ může zahrnovat i následující obecnější situace:

• $𝑨\in {ℂ}^{m\times n}$, $𝑸\in {ℂ}^{m\times m}$ unitární a $𝑹\in {ℂ}^{m\times n}$ s nezápornými prvky na diagonále a nulami pod diagonálou,
• $𝑨\in {ℂ}^{m\times n}$, kde $m\ge n$ , $𝑸\in {ℂ}^{m\times n}$ s ortonormálními sloupci a $𝑹$ je horní trojúhelníková matice s nezápornými prvky na diagonále, tzv. ekonomický QR rozklad nebo též redukovaný QR rozklad,
• $𝑨\in {ℂ}^{m\times n}$ hodnosti $r$, $𝑸\in {ℂ}^{m\times r}$ s ortonormálními sloupci a $𝑹\in {ℂ}^{r\times n}$ v odstupňovaném tvaru s kladnými pivoty (angl. reduced rank QR decomposition).

QR rozklad reálných matic

Stejným způsobem lze definovat rozklad reálné matice $𝑨$ na součin reálných matic $𝑸$ a $𝑹$. Unitární matice $𝑸$ se v těchto případech stane ortogonální maticí.

Ukázka

QR rozklad reálné matice řádu 3 je např.:

$𝑨=\left(\begin{array}{ccc}2& 2& 3\\ 2& -4& 6\\ -1& -4& 0\end{array}\right)=\left(\begin{array}{ccc}2/3& 1/3& 2/3\\ 2/3& -2/3& -1/3\\ -1/3& -2/3& 2/3\end{array}\right)\left(\begin{array}{ccc}3& 0& 6\\ 0& 6& -3\\ 0& 0& 0\end{array}\right)=𝑸𝑹$

Matice $𝑸$ je ortonormální, protože pro ni platí: ${𝑸}^{𝖳}𝑸={𝑸𝑸}^{𝖳}=𝐈$. Pokud by byla brána jako komplexní matice, je i unitární, protože ${𝑸}^{𝖧}𝑸={𝑸𝑸}^{𝖧}=𝐈$.

Ekonomický QR rozklad téže matice je

$𝑨=\left(\begin{array}{ccc}2& 2& 3\\ 2& -4& 6\\ -1& -4& 0\end{array}\right)=\left(\begin{array}{cc}2/3& 1/3\\ 2/3& -2/3\\ -1/3& -2/3\end{array}\right)\left(\begin{array}{ccc}3& 0& 6\\ 0& 6& -3\end{array}\right)=𝑸𝑹$

Matice $𝑸$ má ortonormální sloupce a stále pro ni platí ${𝑸}^{𝖳}𝑸=𝐈$ . Uvedená matice má však více sloupců než řádků, a proto ${𝑸𝑸}^{𝖳}\ne 𝐈$.

Existence a vlastnosti

Existence QR rozkladu pro regulární matice vyplývá např. z Choleského rozkladu matice ${𝑨}^{𝖧}𝑨$, která je vždy pozitivně definitní. Je-li ${𝑨}^{𝖧}𝑨={𝑹}^{𝖧}𝑹$, potom $𝑸={𝑨𝑹}^{-1}$je unitární, protože:

${𝑸𝑸}^{𝖧}={𝑨𝑹}^{-1}({𝑨𝑹}^{-1}{)}^{𝖧}={𝑨𝑹}^{-1}({𝑹}^{-1}{)}^{𝖧}{𝑨}^{𝖧}=𝑨({𝑹}^{𝖧}𝑹{)}^{-1}{𝑨}^{𝖧}=𝑨({𝑨}^{𝖧}𝑨{)}^{-1}{𝑨}^{𝖧}={𝑨𝑨}^{-1}({𝑨}^{-1}{)}^{𝖧}{𝑨}^{𝖧}=𝐈$

V obecném případě odpovídají sloupce matice $𝑸$ ortonormální bázi sloupcového prostoru matice $𝑨$. Koeficienty lineárních kombinací v Gramově–Schmidtově ortonormalizaci tvoří sloupce matice $𝑹$. Protože jsou sloupce $𝑨$ postupně upravovány pomocí lineárních kombinací vůči dříve zpracovaným sloupcům, je matice $𝑹$ v odstupňovaném tvaru.

Má-li matice $𝑨$ plnou sloupcovou hodnost, čili pokud $\mathrm{rank}𝑨=n$, potom je QR rozklad jednoznačný a matice má $𝑹$ kladné prvky na diagonále.

Unitární matici $𝑸$ pak lze získat rozšířením ortonormální báze sloupcového prostoru matice $𝑨$ na ortonormální bázi ${ℂ}^n$a doplněním $m-r$ nulových řádků do matice $𝑹$.

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.

Aplikace

QR rozklad je základem řady metod numerické matematiky, například pro určení ortogonální nebo unitární báze nebo pro řešení problému lineární regrese. Je nedílnou součástí QR algoritmu pro aproximaci vlastních čísel.

Řešení regulárních nebo přeurčených soustav rovnic

Řešení $𝒙\in {ℝ}^n$ soustavy lineárních rovnic $𝑨𝒙=𝒃$ s maticí $𝑨\in {ℝ}^{m\times n},m\ge n$ je možné získat následujícím postupem:

1. Provést QR rozklad matice $𝑨=𝑸𝑹$,
2. Určit součin $𝒛={𝑸}^{𝖳}𝒃$,
3. Vyřešit $𝑹𝒙=𝒛$ zpětnou substitucí.

Pro čtvercové matice (tj. když $m=n$) má uvedený výpočet oproti Gaussově eliminaci přibližně dvojnásobnou složitost, ale může být numericky stabilnější.

Soustava s více rovnicemi než proměnnými (tj. když $m>n$) je přeurčená. V tomto případě se $𝒙$ určí řešením související úlohy metody nejmenších čtverců, viz regresní analýza:

Minimalizovat $\Vert 𝑨𝒙-𝒃{\Vert }^2=\sum _{j=1}^m{(\sum _{k=1}^n{a}_{j,k}{x}_k-b_j)}^2$

V tomto případě je ${𝑨}^{+}={𝑹}^{+}{𝑸}^{𝖳}$Mooreova–Penroseova pseudoinverze matice $𝑨$. Hledané řešení lze vyjádřit vztahem $𝒙={𝑨}^{+}𝒃$, což zobecňuje obvyklé vyjádření $𝒙={𝑨}^{-1}𝒃$ pro regulární matici $𝑨$.

Řešení nedourčených soustav rovnic

Pro soustavy s méně rovnicemi než proměnnými (tj. když Pro $m<n$) platí, že její matice $𝑨$ má netriviální jádro. Pokud by $𝑨$ měla plnou řádkovou hodnost, potom množina řešení soustavy $𝑨𝒙=𝒃$ tvoří afinní podprostor. Jinak lze řešení s nejmenší normou nalézt v ortogonálním doplňku jádra. Numericky je lze určit pomocí QR rozkladu ${𝑨}^{𝖳}$následujícím postupem:

1. Určit QR rozklad matice ${𝑨}^{𝖳}=𝑸𝑹$,
2. Vyřešit ${𝑹}^{𝖳}𝒛=𝒃$ dopřednou substitucí,
3. Spočítat součin $𝒙=𝑸𝒛$ .

I v tomto případě je ${𝑨}^{+}=𝑸({𝑹}^{𝖳}{)}^{+}$Mooreova–Penroseova pseudoinverze matice $𝑨$ a pro řešení s nejmenší normou opět platí $𝒙={𝑨}^{+}𝒃$.

Rozklady typu LQ, RQ a QL

LQ rozkladem matice $𝑨$ je hermitovsky transponovaný rozklad matice ${𝑨}^{𝖧}$. Z rozkladu ${𝑨}^{𝖧}=𝑸𝑹$ pak vyplývá $𝑨={𝑳𝑸}^{𝖧}$, kde $𝑳={𝑹}^{𝖧}$ znamená matici s nulami nad diagonálou (z angl. left nebo lower), a pokud $𝑸$ není čtvercová, pak má ortonormální řádky.

Pomocí sloupcových operací lze analogickým způsobem získat rozklady typu RQ a QL. Například Gramova–Schmidtova ortogonalizace řádků $𝑨$ prováděná v pořadí od posledního řádku k prvnímu poskytuje RQ rozklad.

Odkazy

Literatura

• Šablona:Citace monografie

• Šablona:Citace monografie

Související články

• Gaussova eliminace
• Choleského rozklad
• Mooreova–Penroseova pseudoinverze matice
• Singulární rozklad