Rozkład QR

rozkład macierzy

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 HouseholderaEdytuj

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

Transformacja HouseholderaEdytuj

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 QREdytuj

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ładEdytuj

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

PrzypisyEdytuj

BibliografiaEdytuj