Rozkład QR

Rozkład QR – w algebrze liniowej rozkład macierzy $A$ do postaci iloczynu dwóch macierzy $A=QR,$ gdzie $Q$ jest macierzą ortogonalną $(Q^{T}Q=I)$ i $R$ jest macierzą trójkątną górnąSzablon:Odn. Na bazie rozkładu QR możliwa jest realizacja metody najmniejszych kwadratówSzablon:Odn oraz metod rozwiązywania układów równań liniowychSzablon:Odn.

Metoda Householdera

Metoda Householdera pozwala znaleźć rozkład QR dowolnej macierzy prostokątnej m x n $(m⩾n).$

Transformacja Householdera

Niech $v\in R^m$ i $v\ne \mathrm{𝟎}.$ Wówczas transformacją Householdera nazywamy macierz postaci:

$H=I-Wv{v}^T,W=\frac{2}{v^{T}v}.$

Macierz H jest macierzą symetryczną i ortogonalną (transformacja nie zmienia długości wektora) oraz ma taką własność, że dowolny wektor x wymiaru m jest odbiciem lustrzanym wektora Hx względem hiperpłaszczyzny (wymiaru m-1) prostopadłej do wektora vSzablon:Odn. Łatwo sprawdzić, że tak jest ponieważ:

$H^2={(I-\frac{2v{v}^T}{v^{T}v})}^2=I-\frac{4v{v}^T}{v^{T}v}+4{\left(\frac{v{v}^T}{v^{T}v}\right)}^2=I((v{v}^T)(v^{T}v)=(v{v}^T{)}^2)$

oraz

$H^T={(I-\frac{2v{v}^T}{v^{T}v})}^T=I-{\left(\frac{2v{v}^T}{v^{T}v}\right)}^T=I-\frac{2v{v}^T}{v^{T}v}=H((v{v}^T{)}^T=(v{v}^T)).$

Z drugiej równości wynika symetria, z pierwszej ortogonalność, ponieważ $H^{T}H=HH=I.$ Zatem:

$|Hx|=\sqrt{(Hx{)}^T(Hx)}=\sqrt{x^T(H^{T}H)x}=\sqrt{x^{T}Ix}=|x|.$

Mnożąc dowolny wektor $x\in R^m,$ otrzymujemy:

$Hx=x-\frac{2v{v}^{T}x}{v^{T}v}=x+(-2\frac{v{v}^{T}x}{v^{T}v})=x-2r.$

Wiadomo, że $r=(w^{T}x)w$ jest rzutem prostopadłym wektora x na kierunek w, przy czym wektor w musi być znormalizowany. Zatem w tym wypadku $w=v/\sqrt{v^{T}v}$ co po podstawieniu daje powyższą równość.

Rozkład QR

Transformacja Householdera może zostać wykorzystana w celu przeprowadzenia rozkładu QR macierzy A. Metoda polega na iteracyjnym szukaniu transformacji Householdera dla kolejnych wektorów pod diagonalą macierzy A. Rozważmy k-ty krok algorytmu (x oznacza wartość zależną od macierzy A):

$H_{k-1}{H}_{k-2}\dots H_{1}A=\left(\begin{array}{cccccc}x& x& \cdots & x& x& x\\ 0& x& \cdots & x& x& x\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 0& 0& \cdots & 𝒙& x& x\\ 0& 0& \cdots & 𝒙& x& x\\ 0& 0& \cdots & 𝒙& x& x\end{array}\right)$

W kroku k-tym rozważamy wektor stanowiący część macierzy od k-tego elementu diagonali w dół. Szukamy takiej macierzy ${H_k}^{\prime }\in R^{3\times 3}$ aby spełniona była równość:

${H_k}^{\prime }\left(\begin{array}{c}𝒙\\ 𝒙\\ 𝒙\end{array}\right)=\left(\begin{array}{c}x\\ 0\\ 0\end{array}\right)$

Macierz ${H_k}^{\prime }$ jest macierzą Householdera. Mając ${H_k}^{\prime }$ możemy uzyskać macierz $H_k\in R^{m\times m}:$

$H_k=\left(\begin{array}{cc}{I}_{k-1}& 0\\ 0& {H_k}^{\prime }\end{array}\right)$

W ten sposób zerujemy kolejne wektory spod diagonali do momentu aż po $\min (m-1,n)$ krokach otrzymujemy równość:

$H_{min(m-1,n)}\dots H_{1}A=R,$ gdzie R jest szukaną macierzą trójkątną górną.

Macierz $Q=H_1{H}_2\dots H_{min(m-1,n)}$Szablon:Odn.

Przykład

Znajdźmy rozkład QR macierzy A:

$A=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right)$

W pierwszym kroku szukamy takiej macierzy $H_1,$ że $H_1{a}_1=|a_1|e_1,$ gdzie $a_1={\left(\begin{array}{c}12,6,-4\end{array}\right)}^T$ jest wektorem z pierwszej kolumny macierzy A, natomiast $|a_1|e_1={\left(\begin{array}{c}14,0,0\end{array}\right)}^T$ wektorem do którego przekształcamy ortogonalnie wektor $a_1.$ Wektor $|a_1|e_1$ jest jednoznacznie określony poprzez długość i zerowe wartości pozostałych współrzędnych (zawsze istnieje taki obrót wektora $a_1$ że te współrzędne będą zerowe).

Znajdujemy dowolny wektor prostopadły do hiperpłaszczyzny względem której następuje odbicie wektora $a_1:$

$v_1=a_1-|a_1|e_1=(-2,6,-4{)}^T.$

Obliczamy z definicji macierz Householdera:

$H_1=I-\frac{2v_1{v}_1^T}{v_1^T{v}_1}=I-\frac{1}{28}\left(\begin{array}{ccc}4& -12& 8\\ -12& 36& -24\\ 8& -24& 16\end{array}\right)=\left(\begin{array}{ccc}\frac{6}{7}& \frac{3}{7}& -\frac{2}{7}\\ \frac{3}{7}& -\frac{2}{7}& \frac{6}{7}\\ -\frac{2}{7}& \frac{6}{7}& \frac{3}{7}\end{array}\right)$

Zatem otrzymujemy:

$H_{1}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& -49& -14\\ 0& 168& -77\end{array}\right)$

Teraz przechodzimy do drugiej iteracji algorytmu, a więc rozważamy podmacierz o wymiarze 2 × 2 powstałą poprzez usunięcie pierwszego wiersza i pierwszej kolumny. W tym wypadku $a_2={\left(\begin{array}{c}-49,168\end{array}\right)}^T,$ czyli $|a_2|e_2={\left(\begin{array}{c}175,0\end{array}\right)}^T$ i $v_2={\left(\begin{array}{c}-224,168\end{array}\right)}^T.$

${H_2}^{\prime }=I-\frac{2v_2{v}_2^T}{v_2^T{v}_2}=I-\frac{1}{39200}\left(\begin{array}{cc}50176& -37632\\ -37632& 28224\end{array}\right)=\left(\begin{array}{cc}-\frac{7}{25}& \frac{24}{25}\\ \frac{24}{25}& \frac{7}{25}\end{array}\right)$

$H_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& -\frac{7}{25}& \frac{24}{25}\\ 0& \frac{24}{25}& \frac{7}{25}\end{array}\right)$

Zatem otrzymujemy:

$R=H_2{H}_{1}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& -35\end{array}\right)$

$Q=H_1{H}_2=\left(\begin{array}{ccc}\frac{6}{7}& -\frac{69}{175}& \frac{58}{175}\\ \frac{3}{7}& \frac{158}{175}& -\frac{6}{175}\\ -\frac{2}{7}& \frac{6}{35}& \frac{33}{35}\end{array}\right)$

Można sprawdzić, że macierz Q jest ortogonalna $(Q^{T}Q=I),$ R jest macierzą trójkątną górną oraz A = QR. Zatem znaleźliśmy rozkład QR macierzy A.

Zobacz też

• metoda LU
• rozkład Choleskiego

Bibliografia

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę