Algorytm podstawowy

Algorytm znajdowania wartości własnych QR wymaga aby dana macierz $A$ , była macierzą kwadratową $n \times n$ określoną na liczbach rzeczywistych. Algorytm polega na iteracyjnym wykonywaniu określonych czynnosci aż do otrzymania macierzy trojkątniej górnej podobnej do macierzy$A$ która na diagonali zawiera wartości własne.
W pierwszym kroku definiujemy macierz $\widehat{Q_0}$ równą macierzy jednostkowej

$$\widehat{Q_0} = I$$

oraz macierz $D_1$ równą macierzy $A$

$$D_1 = A$$

następnie wykonujemy dekompozycję macierzy $A$ za pomocą algorytmu dekompozycji QR, otrzymujemy

$$A=\widehat{Q_1}R_1$$ (1)

gdzie macierz $\widehat{Q_1}$ jest macierzą ortogonalną, natomiast $R_1$ jest macierzą trójkątną górną. Mając daną macierz $\widehat{Q_1}$ oraz traktując ją jako macierz przejścia znajdujemy za pomocą transformacji macierzy podobnej macierz $A_1$ podobną do macierzy A.

$$A_1 = {Q_1}^{-1}AQ_1$$ (2)

mnożąc obustronnie (1) przez ${Q_1}^{-1}$ otrzymujemy:

$${Q_1}^{-1}A = R_1$$ (3)

łącząc (2) z (3) otrzymujemy

$$A_1 = R_1Q_1$$

Jeżeli otrzymana macierz $A_1$ nie jest macierzą trójkątną górną (z zadanym przybliżeniem) to musimy przejść do kolejnego kroku iteracyjnego, w którym przyjmujemy, że

$$D_2 = A{Q_1}$$

Ponieważ macierz $D_2$ oraz $A_1$ są macierzami tego samego odwzorowana, różnią się jedynie bazami. w następnym kroku dokonujemy dekompozycji QR obu tych macierzy, w wyniku której otrzymujemy rownania

$$D_2 = \widehat{Q_2}R_2$$

$$A_1=Q_2R_2$$

gdzie macierz $R_2$ w obu przypadkach jest taka sama. Wykonując proste obliczenia otrzymujemy macierz $A_2$

$${Q_2}^{-1}A_1=R_2$$

$$A_2 = {Q_2}^{-1} A_1 Q_2 = R_2 Q_2$$

Jeżeli otrzymana macierz $A_2$ nie jest macierzą trójkątną górną kontynuujemy interacje. Przechodząc do m-tego kroku mamy daną macierz $A_{m-1}$ , a następnie wykonując te same operacje otrzymujemy równania

$$A_{m-1} = Q_m R_m$$

$$A_m = R_m Q_m$$

gdzie

$$\widehat{Q}^{m} = Q_1 Q_2 Q_3 \ldots Q_m$$

natomiast $Q_i$ reprezentuje zmianę współrzędnych w i-tym kroku.

Cały algorytm można zapisać w postaci uproszczonej. Przyjmujemy sobie w kroku zerowym, macierz $A_0$ równą macierzy $A$ , następnie otrzymujemy

$$A_1 = Q_1 R_1 = \widehat{Q_1} R_1$$

$$A_2 = Q_1 R_1 Q_1 R_1 = Q_1 Q_2 R_2 R_1 = \widehat{Q_2} R_2$$

$$\ldots$$

$$A_m = (\prod_{i = 1}^{m} Q_i ) (\prod_{k = m}^{1} R_k ) = \widehat{Q_m} R_m$$

Przedstawiony powyżej algorytm ma jedną poważną wadę - jest mało wydajny, algorytm ten wymaga $O(n^3)$ operacji mnożenia, istnieje jednak kilka ulepszeń, które znacznie poprawiaja jego szybkość. Metody usprawniające działanie tego algorytmu są wyjaśnione w dalszej części pracy.
przykład:
Mając dana macierz $P$ wykonujemy kolejne kroki w algorytmie.

$$\left[ \begin{array}{ccc} 1 & 2 & 5 \cr 5 & 8 & 6 \cr 8 & 6 & 7 \cr \end{array} \right],$$

dokonujemy dekompozycji QR macierzy $A$

$$A = Q_1R_1 = \left[ \begin{array}{ccc} -0.1054 & -0.2673 & -0.95... ...5922 \cr 0 & -3,7417 & -2,4054 \cr 0 & 0 & -3,4933 \cr \end{array} \right]$$

Następnie znajdujemy macierz $A_1$ podobną do macierzy $A$ względem macierzy przejścia $Q_1$ , powinna być ona równa macierzy otrzymanej z $R_1A_1$ .

$$A_1 = Q_1^{-1}AQ_1 = \left[ \begin{array}{ccc} 14.0889 & 5.0146 ... ... & -0.9186 \cr 2.9458 & -1.8672 & 0.1968 \cr \end{array} \right] \equiv R_1Q_1$$

Ponieważ macierz $A_1$ nie jest macierzą trójkątną górną przechodzimy do następnej iteracji. Rozdzielamy używając dekompozycji QR macierz $A_1$ na macierz unitarną $Q_2$ oraz macierz trójkątkną górną $R_2$

$$A_1 = Q_2R_2 = \left[ \begin{array}{ccc} -0.9431 & -0.1624 & -0.... ... -6.3517 \cr 0 & -2.8877 & -0.8025 \cr 0 & 0 & -2.8744 \cr \end{array} \right]$$

następnie obliczamy macierz $A_2$

$$A_2 = Q_2^{-1}A_1Q_2 = R_2Q_2 = \left[ \begin{array}{ccc} 16.632... ...15 & -0.3594 & -2.8259 \cr 0.5668 & -2.8047 & -0.2727 \cr \end{array} \right]$$

Wykonując te same obliczenia za każdym krokiem iteracyjnym macierz $A_n$ dązy do macierzy trójkątnej górnej, która na diagonali posiada wartości własne. W powyższym przypadku wykonując 68 iteracji otrzmymamy wartości własne z dokladnością do 4 cyfry po przecinku.

$$\overline{\lambda} = [ 16.4536, -2.9814, 2.5278 ]$$