Dekompozycja QR (QR factorization)

Dekompozycja macierzy polega na przedstawieniu jej w postaci iloczynu dwóch innych specyficznych macierzy. Istnieje kilka takich dekompozycji, które znalazły szczególne zastosowania. Jedną z takich dekompozycji jest na przykład faktoryzacja LU:

$$A=L\cdot U$$.

Macierz $A$ jest przedstawiona tutaj jako iloczyn dolnej macierzy trójkątnej $L$ oraz górnej macierzy trójkątnej $R$ . Dodatkowo jeśli macierz $L$ ma na przekątnej tylko jedynki faktoryzacja ta zwana jest dekompozycją Doolittle'a. Dodatkowo jeśli również macierz $R$ ma na diagonali same jedynki jest to faktoryzacja Crout'a. Ponadto jeśli $L=U^T$ jest to dekompozycja Cholesky'iego. Jak łatwo zauważyć dekompozycji może być nieskończenie wiele jednak, mało które są do czegokolwiek przydatne, dlatego nawet drobne, subtelne różnice jak w tym przykladzie dekompozycji LU maja swoje zastosowania stąd też mają one nawet inne nazwy choć w rzeczywistości są prawie identyczne (implementacja zaś z koleji jest całkiem różna). Na przykład dekompozycja PA jest niczym innym jak dekompozycją LU jednakże z zastosowaniem pivotingu. Zainteresowanych bliżej zagadnieniami dekompozycji odsyłamy do odpowiedniej literatury. Istnieje inna bardzo przydatna dekompozycja, tak zwana faktoryzacja QR.

Dekompozycja QR macierzy rzeczywistej $A$ jest dekompozycją na dwie inne macierze oznaczone odpowiednio $Q$ oraz $R$ , gdzie macierz Q jest ortogonalna, natomiast $R$ jest górną macierzą trójkątną, co można zapisać:

$$A=Q \cdot R$$.

Przy dodatkowym zalożeniu, że elementy na diagonali macierzy R powinny być dodatnie faktoryzacja QR jest jednoznaczna. Dekompozycja QR jest często używana do rozwiązywania liniowego problemu najmniejszych kwadratów, jest również podstawą do iteracyjnego liczenia wartości własnych macierzy.
Istnieje kilka metod w jaki można rozłożyć macierz na odpowiednie macierze Q oraz R. Kolejno zostaną przedstawione najbardziej użyteczne.