Algorytm z wykorzystaniem przesunięć wartości własnych

Chociaż algorytm bazujący na macierzach Hessenberga działa znacznie szybciej od algorytmu QR w formie podstawowej to mimo wszystko w niektórych przypadkach współczynnik zbiegania się elementów znajdujących się na poddiagonali jest zbyt wolne. Dla elementu $a_{i,i+1}^{(k)}$ w k-tym kroku ów współczynnik wynosi $(\frac{\lambda_i}{\lambda_{i-1}})^{k}$ , co w przypadku gdy wartości własne $\lambda_i$ oraz $\lambda_{i-1}$ mają zbliżone wartości jest przyczyną powolnego zbiegania się algorytmu QR do szukanych wartości. Aby uniknąć powyższej sytuacji stosuje się w każdym kroku iteracyjnym przesunięcia wektorów własnych

$$A_k - \vartheta_k I = Q_k R_k$$

$$A_{k+1} = R_k Q_k + \vartheta_k I$$

dzięki czemu współczynnik $\psi^{(k)}$ zbiegania się elementu $a_{i,i+1}^{(k)}$ pod diagonalą jest równy

$$\psi^{(k)} = \frac{\lambda_{i+1} - \vartheta_k}{\lambda_{i} - \vartheta_k}$$

Łatwo można zauważyć, że jeżeli wartość współczynnika zbieżności $\psi^{(k)}$ dąży do 0 to $\vartheta_k$ dąży do $\lambda_{i}$ .

$$\lim_{n \to \infty} \psi^{(k)} = 0 \Rightarrow \lim_{n \to \infty} \vartheta_k = \lambda_{i}$$

Oczywistym wnioskiem, który można wyciągnąć z powyższej zależności jest możliwość osiągnięcia zbieżności liniowej, a nawet kwadratowej. Algorytm polega na tym, że najpierw skupiamy się na wartości własnej $\lambda_n$ i na jego podstawie obliczamy współczynnik $\psi^{(k)}$ . Jeżeli $\lambda_n$ zostanie obliczona z zadowalającą nas precyzją to przechodzimy do obliczania wartości $\lambda_{n-1}$ , operacje powtarzamy aż do uzyskania wszystkich wartości własnych. Początkowo za element $\psi^{(k)}$ wybierano element $a_{nn}^{(k)}$ macierzy, jednakże Wilkinson w 1965 roku zauważył, żę lepszym rozwiązaniem będzie wybranie wartości własnej z minora o wymiarach $2 \times 2$ zawierającego na diagonali wartości $a_{n-1,n-1}^{(k)}$ oraz $a_{n,n}^{(k)}$ . Konsekwencją wyboru algorytmu z przesunięciami wartości własnych jest brak uporządkowania wartości własnych na diagonali, zazwyczaj największe wartości własne są na początku.

$$\left[ \begin{array}{ccc} a_{n-1,n-1}^{(k)} & a_{n-1, n}^{(k)} \cr a_{n, n-1}^{(k)} & a_{n,n}^{(k)} \cr \end{array} \right]$$

Algorytm QR z przesunięciami dla wcześniej zaprezentowanego przykładu oblicza wartości własne z precyzją do 4 miejsc po przecinku w 6 iteracjach co jest ponad 10 krotnym przyspieszeniem i to jedynie dla macierzy 4 wymiarowej.