Algortym z wykorzystaniem macierzy Hessenberga

Bardzo prostym ulepszeniem algorytmu podstawowego QR jest użycie w nim macierzy Hessenberg'a. Ogromną zaletą macierzy Hessenberga jest fakt, iż ilość operacji mnożenia w pojedyńczej iteracji w algorytmie QR wynosi $O(n^2)$ zamiast $O(n^3)$ , oraz to, że macierz Hessenberga zachowuje swoją postać podczas kolejnych iteracji QR.

Twierdzenie 1. Dla dowolnej macierzy $A$ $n \times n$ istnieje podobna unitarnie do niej macierz Hessenberga, która może być skonstruowana kosztem $5n^3/3$ operacji mnożenia. Jeżeli dodatkowo macierz $A$ jest macierzą Hermite'a to kosz maleje do poziomu $2n^3/3$ oraz ilość operacji mnożenia w jednej iteracji w algorytmie QR maleje o jeden rząd, czyli wynosi $O(n)$ .