Rozkład QR – w algebrze liniowej rozkład macierzy
do postaci iloczynu dwóch macierzy
gdzie
jest macierzą ortogonalną
i
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 pozwala znaleźć rozkład QR dowolnej macierzy prostokątnej m x n
Niech
i
Wówczas transformacją Householdera nazywamy macierz postaci:

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ż:

oraz

Z drugiej równości wynika symetria, z pierwszej ortogonalność, ponieważ
Zatem:

Mnożąc dowolny wektor
otrzymujemy:

Wiadomo, że
jest rzutem prostopadłym wektora x na kierunek w, przy czym wektor w musi być znormalizowany. Zatem w tym wypadku
co po podstawieniu daje powyższą równość.
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):

W kroku k-tym rozważamy wektor stanowiący część macierzy od k-tego elementu diagonali w dół. Szukamy takiej macierzy
aby spełniona była równość:

Macierz
jest macierzą Householdera. Mając
możemy uzyskać macierz

W ten sposób zerujemy kolejne wektory spod diagonali do momentu aż po
krokach otrzymujemy równość:
gdzie R jest szukaną macierzą trójkątną górną.
Macierz
[4].
Znajdźmy rozkład QR macierzy A:

W pierwszym kroku szukamy takiej macierzy
że
gdzie
jest wektorem z pierwszej kolumny macierzy A, natomiast
wektorem do którego przekształcamy ortogonalnie wektor
Wektor
jest jednoznacznie określony poprzez długość i zerowe wartości pozostałych współrzędnych (zawsze istnieje taki obrót wektora
że te współrzędne będą zerowe).
Znajdujemy dowolny wektor prostopadły do hiperpłaszczyzny względem której następuje odbicie wektora

Obliczamy z definicji macierz Householdera:

Zatem otrzymujemy:

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
czyli
i


Zatem otrzymujemy:


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