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ą. Na bazie rozkładu QR możliwa jest realizacja metody najmniejszych kwadratów oraz metod rozwiązywania układów równań liniowych.

Metoda Householdera

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

Transformacja Householdera

Niech $v\in R^{m}$ i $v\neq \mathbf {0} .$ Wówczas transformacją Householdera nazywamy macierz postaci:

$H=I-Wvv^{T},\qquad 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 v. Łatwo sprawdzić, że tak jest ponieważ:

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

oraz

$H^{T}=\left(I-{\frac {2vv^{T}}{v^{T}v}}\right)^{T}=I-\left({\frac {2vv^{T}}{v^{T}v}}\right)^{T}=I-{\frac {2vv^{T}}{v^{T}v}}=H\qquad ((vv^{T})^{T}=(vv^{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 {2vv^{T}x}{v^{T}v}}=x+(-2{\frac {vv^{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={\begin{pmatrix}x&x&\cdots &x&x&x\\0&x&\cdots &x&x&x\\\cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\0&0&\cdots &{\boldsymbol {x}}&x&x\\0&0&\cdots &{\boldsymbol {x}}&x&x\\0&0&\cdots &{\boldsymbol {x}}&x&x\end{pmatrix}}$

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

$H_{k}'{\begin{pmatrix}{\boldsymbol {x}}\\{\boldsymbol {x}}\\{\boldsymbol {x}}\end{pmatrix}}={\begin{pmatrix}x\\0\\0\end{pmatrix}}$

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

$H_{k}={\begin{pmatrix}I_{k-1}&0\\0&H_{k}'\end{pmatrix}}$

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)}$.

Przykład

Znajdźmy rozkład QR macierzy A:

$A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}$

W pierwszym kroku szukamy takiej macierzy $H_{1},$ że $H_{1}a_{1}=|a_{1}|e_{1},$ gdzie $a_{1}={\begin{pmatrix}12,6,-4\end{pmatrix}}^{T}$ jest wektorem z pierwszej kolumny macierzy A, natomiast $|a_{1}|e_{1}={\begin{pmatrix}14,0,0\end{pmatrix}}^{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}}{\begin{pmatrix}4&-12&8\\-12&36&-24\\8&-24&16\end{pmatrix}}={\begin{pmatrix}{\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{pmatrix}}$

Zatem otrzymujemy:

$H_{1}A={\begin{pmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{pmatrix}}$

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}={\begin{pmatrix}-49,168\end{pmatrix}}^{T},$ czyli $|a_{2}|e_{2}={\begin{pmatrix}175,0\end{pmatrix}}^{T}$ i $v_{2}={\begin{pmatrix}-224,168\end{pmatrix}}^{T}.$

$H_{2}'=I-{\frac {2v_{2}v_{2}^{T}}{v_{2}^{T}v_{2}}}=I-{\frac {1}{39200}}{\begin{pmatrix}50176&-37632\\-37632&28224\end{pmatrix}}={\begin{pmatrix}-{\frac {7}{25}}&{\frac {24}{25}}\\{\frac {24}{25}}&{\frac {7}{25}}\end{pmatrix}}$

$H_{2}={\begin{pmatrix}1&0&0\\0&-{\frac {7}{25}}&{\frac {24}{25}}\\0&{\frac {24}{25}}&{\frac {7}{25}}\end{pmatrix}}$

Zatem otrzymujemy:

$R=H_{2}H_{1}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{pmatrix}}$

$Q=H_{1}H_{2}={\begin{pmatrix}{\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{pmatrix}}$

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

• William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling: Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, 1992. ISBN 978-0-521-43108-8.
• Gene H. Golub, Charles F. Van Loan: Matrix Computations. Johns Hopkins University Press, 2012. ISBN 978-1-4214-0794-4.