Editing Inverse iteration (section)

=== Tridiagonalization, [[Hessenberg form]] ===

If it is necessary to perform many iterations (or few iterations, but for many eigenvectors), then it might be wise to bring the matrix to the 
upper [[Hessenberg form]] first (for symmetric matrix this will be [[tridiagonal matrix|tridiagonal form]]).  Which costs <math display="inline">\frac{10}{3} n^3 + 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>{{citation
 | last = Demmel | first = James W. | authorlink = James Demmel
 | mr = 1463942
 | isbn = 0-89871-389-7
 | location = Philadelphia, PA
 | publisher = [[Society for Industrial and Applied Mathematics]]
 | title = Applied Numerical Linear Algebra
 | year = 1997}}.</ref><ref name=Trefethen>Lloyd N. Trefethen and David Bau, ''Numerical Linear Algebra'' (SIAM, 1997).</ref>  (For QR decomposition, the Householder rotations are multiplied only on the left, but for the Hessenberg case they are multiplied on both left and right.) For  [[symmetric matrix|symmetric matrices]] this procedure costs <math display="inline">\frac{4}{3} n^3 + O(n^2)</math> arithmetic operations using  a technique based on Householder reduction.<ref name=Demmel/><ref name=Trefethen/>

Solution of the system of linear equations for the [[tridiagonal matrix]] costs <math>O(n)</math> operations, so the complexity grows like <math>O(n^3) + kO(n)</math>, where <math>k</math> is the iteration number, which is better than for the direct inversion. However, for few iterations such transformation may not be practical.

Also transformation to the [[Hessenberg form]] involves square roots and the division operation, which are not universally supported by hardware.