Editing QR algorithm (section)

===Using Hessenberg form===
In the above crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix {{mvar|A}} to upper [[Hessenberg form]] (which costs <math display="inline">\tfrac{10}{3} n^3 + \mathcal{O}(n^2)</math> arithmetic operations using a technique based on [[Householder transformation|Householder reduction]]), with a finite sequence of orthogonal similarity transforms, somewhat like a two-sided QR decomposition.<ref name=Demmel>{{cite book |first=James W. |last=Demmel |author-link=James W. Demmel |title=Applied Numerical Linear Algebra |publisher=SIAM |year=1997 }}</ref><ref name=Trefethen>{{cite book |first1=Lloyd N. |last1=Trefethen |author-link=Lloyd N. Trefethen |first2=David |last2=Bau |title=Numerical Linear Algebra |publisher=SIAM |year=1997 }}</ref>  (For QR decomposition, the Householder reflectors are multiplied only on the left, but for the Hessenberg case they are multiplied on both left and right.) Determining the QR decomposition of an upper Hessenberg matrix costs <math display="inline">6 n^2 + \mathcal{O}(n)</math> arithmetic operations.  Moreover, because the Hessenberg form is already nearly upper-triangular (it has just one nonzero entry below each diagonal), using it as a starting point reduces the number of steps required for convergence of the QR algorithm.

If the original matrix is [[symmetric matrix|symmetric]], then the upper Hessenberg matrix is also symmetric and thus [[tridiagonal matrix|tridiagonal]], and so are all the {{math|''A''<sub>''k''</sub>}}. In this case reaching Hessenberg form costs <math display="inline">\tfrac{4}{3} n^3 + \mathcal{O}(n^2)</math> arithmetic operations using a technique based on Householder reduction.<ref name=Demmel/><ref name=Trefethen/> Determining the QR decomposition of a symmetric tridiagonal matrix costs <math>\mathcal{O}(n)</math> operations.<ref>{{cite journal |first1=James M. |last1=Ortega |first2=Henry F. |last2=Kaiser |title=The ''LL<sup>T</sup>'' and ''QR'' methods for symmetric tridiagonal matrices |journal=The Computer Journal |volume=6 |issue=1 |pages=99–101 |year=1963 |doi=10.1093/comjnl/6.1.99 |doi-access=free }}</ref>