Refleksja Householdera

Metoda Householdera zwana również transformacją Householdera lub refleksją (odbiciem) Housoldera jest najczęściej używaną metodą dekompozycji QR. Kluczowym obiektem jest tutaj macierz oznaczona symbolicznie $H$ - symetryczna i ortogonalna zwana macierzą Householdera. Jest to macierz przekształcenia wektora, które odbija go względem pewnej płaszczyzny. Macierz ma następującą postać:

$$H=I-2xx^T$$

gdzie $I$ jest macierzą jednostkową oraz $x$ jest znormalizowanym wektorem spełniającym równanie:

$$\Vert x \Vert ^2 = x^Tx = 1$$.

Użyta tutaj norma jest normą euklidesową czyli po prostu długościa wektora (jeśli jego współrzędne są rzeczywiste). Transformacja Householdera zeruje $m-1$ ostatnich elementów w wektorze (kolumnie) poniżej pierwszego elementu:

$$\left [ \begin{matrix} v_1 \cr v_2 \cr \vdots \cr v_m \end{matrix... ...ightarrow \left [ \begin{matrix} c \cr 0 \cr \vdots \cr 0 \end{matrix}\right ]$$

gdzie:

$$c=\pm \vert v \vert = \pm \sqrt{\sum^m_{i=1}v_i^2}$$.

Łatwo sprawdzić, że:

$$x=f \left [ \begin{matrix} v_1-c \cr v_2 \cr \vdots \cr v_m \end{matrix}\right ]$$

gdzie:

$$f=\frac{1}{\sqrt{2c(c-v_1)}}$$.$$$$

Aby zastosować dekompozycję dla macierzy $A=QR$ o wymiarach $m \times n$ ($m\geq n$ ) kontruujemy macierz $H^{(1)}$ o wymiarach $m \times m$ by zamienić $m-1$ ostatnich elementów pierwszej kolumny na zera. Podobnie skontruowana macierz $G^{(2)}$ o wymiarach $(m-1) \times (m-1)$ zamieni $m-2$ elementów drugiej kolumny na zera. Za pomocą macierzy $G^{(2)}$ tworzymy macierz $m \times m$ :

$$H^{(2)}= \left [ \begin{matrix} 1 & 0 & \dots & 0 \crcr 0 \crcr \vdots && G^{(2)} \crcr 0 \crcr \end{matrix}\right ]$$.

Po $n$ takich ortogonalnych przekształceniach ($n-1$ w przypadku, gdy $m=n$ ) otrzymamy:

$$R=H^{(n)}\dots H^{(2)}H^{(1)}A$$.

R jest górną macierzą trójkątną; ortogonalną macierz Q otrzymamy z iloczynu:

$$Q=H^{(1)}H^{(2)}\dots H^{(n)}$$.

Z równości:

$$A=QR=H^{(1)}H^{(2)}\dots H^{(n)}H^{(n)}\dots H^{(2)}H^{(1)}$$

wyraźnie widać dlaczego metoda zwana jest też refleksją. W praktyce macierze $H^{(i)}$ nigdy nie są jawnie liczone.