Rozkład QR

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

Metoda Householdera

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

Transformacja Householdera

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

${\displaystyle 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^[3]. Łatwo sprawdzić, że tak jest ponieważ:

${\displaystyle 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

${\displaystyle 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ż ${\displaystyle H^{T}H=HH=I.}$ Zatem:

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

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

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

Wiadomo, że ${\displaystyle 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 ${\displaystyle 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):

${\displaystyle 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 ${\displaystyle H_{k}'\in R^{3\times 3}}$ aby spełniona była równość:

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

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

${\displaystyle 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 ${\displaystyle \min(m-1,n)}$ krokach otrzymujemy równość:

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

Macierz ${\displaystyle Q=H_{1}H_{2}\dots H_{min(m-1,n)}}$^[4].

Przykład

Znajdźmy rozkład QR macierzy A:

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

W pierwszym kroku szukamy takiej macierzy ${\displaystyle H_{1},}$ że ${\displaystyle H_{1}a_{1}=|a_{1}|e_{1},}$ gdzie ${\displaystyle a_{1}={\begin{pmatrix}12,6,-4\end{pmatrix}}^{T}}$ jest wektorem z pierwszej kolumny macierzy A, natomiast ${\displaystyle |a_{1}|e_{1}={\begin{pmatrix}14,0,0\end{pmatrix}}^{T}}$ wektorem do którego przekształcamy ortogonalnie wektor ${\displaystyle a_{1}.}$ Wektor ${\displaystyle |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 ${\displaystyle 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 ${\displaystyle a_{1}{:}}$

${\displaystyle v_{1}=a_{1}-|a_{1}|e_{1}=(-2,6,-4)^{T}.}$

Obliczamy z definicji macierz Householdera:

${\displaystyle 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:

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

${\displaystyle 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}}}$

${\displaystyle 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:

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

${\displaystyle 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 ${\displaystyle (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

Przypisy

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.