Rozkład QR

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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[edytuj | edytuj kod]

Metoda Householdera pozwala znaleźć rozkład QR dowolnej macierzy prostokątnej m x n

Transformacja Householdera[edytuj | edytuj kod]

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ść.

Rozkład QR[edytuj | edytuj kod]

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].

Przykład[edytuj | edytuj kod]

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.

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]