Editing Eigenvalue algorithm (section)

==Iterative algorithms==
Iterative algorithms solve the eigenvalue problem by producing sequences that converge to the eigenvalues. Some algorithms also produce sequences of vectors that converge to the eigenvectors. Most commonly, the eigenvalue sequences are expressed as sequences of similar matrices which converge to a triangular or diagonal form, allowing the eigenvalues to be read easily. The eigenvector sequences are expressed as the corresponding similarity matrices.

{| class="wikitable" style="text-align: center"
|-
! Method !! Applies to !! Produces !!Cost per step !! Convergence !! Description
|-
| [[Lanczos algorithm]] || Hermitian || {{math| ''m'' }} largest/smallest eigenpairs ||  ||  || align="left" |
|-
| [[Power iteration]] || general || eigenpair with largest value || {{math|''O''(''n''<sup>2</sup>)}} || linear || align="left" |Repeatedly applies the matrix to an arbitrary starting vector and renormalizes.
|-
| [[Inverse iteration]] || general  || {{nowrap|eigenpair with value closest to ''μ''}} ||  || linear ||  align="left" |Power iteration for {{math|(''A'' − ''μI'')<sup>−1</sup>}}
|-
| [[Rayleigh quotient iteration]] || Hermitian || any eigenpair ||  || cubic ||  align="left" |Power iteration for {{math|(''A'' − ''μ''<sub>''i''</sub>''I'')<sup>−1</sup>}}, where {{math|''μ''<sub>''i''</sub>}} for each iteration is the Rayleigh quotient of the previous iteration.
|-
| width="200" | [[Preconditioned inverse iteration]]<ref>{{Citation
| last=Neymeyr
| first=K.
| title=A geometric theory for preconditioned inverse iteration IV: On the fastest convergence cases.
| journal=Linear Algebra Appl.
| volume=415
| issue=1
| pages=114–139
| year=2006
| doi=10.1016/j.laa.2005.06.022
| doi-access=free
}}</ref> or [[LOBPCG|LOBPCG algorithm]] || [[Positive-definite matrix|positive-definite]] real symmetric || eigenpair with value closest to ''μ'' ||  ||  || align="left" | Inverse iteration using a [[preconditioner]] (an approximate inverse to {{math|''A''}}).
|-
| [[Bisection eigenvalue algorithm|Bisection method]] || real symmetric tridiagonal  || any eigenvalue ||  || linear || align="left" | Uses the [[bisection method]] to find roots of the characteristic polynomial, supported by the Sturm sequence.
|-
| [[Laguerre iteration]] || real symmetric tridiagonal  || any eigenvalue || || cubic<ref>{{Citation
| last1=Li
| first1=T. Y.
| last2=Zeng
| first2=Zhonggang
| title=Laguerre's Iteration In Solving The Symmetric Tridiagonal Eigenproblem - Revisited
| journal=[[SIAM Journal on Scientific Computing]]
| year=1992
}}</ref> || align="left" | Uses [[Laguerre's method]] to find roots of the characteristic polynomial, supported by the Sturm sequence.
|-
| rowspan="2" | [[QR algorithm]] ||rowspan="2" | Hessenberg|| all eigenvalues ||  {{math|''O''(''n''<sup>2</sup>)}} ||rowspan="2" | cubic || align="left" rowspan="2" | Factors ''A'' = ''QR'', where ''Q'' is orthogonal and ''R'' is triangular, then applies the next iteration to ''RQ''.
|-
| all eigenpairs || {{math|6''n''<sup>3</sup> + ''O''(''n''<sup>2</sup>)}}
|-
| [[Jacobi eigenvalue algorithm]] || real symmetric || all eigenvalues ||{{math|''O''(''n''<sup>3</sup>)}} || quadratic || align="left" | Uses Givens rotations to attempt clearing all off-diagonal entries. This fails, but strengthens the diagonal.
|-
| rowspan="2" | [[Divide-and-conquer eigenvalue algorithm|Divide-and-conquer]] || rowspan="2" | Hermitian tridiagonal || all eigenvalues || {{math|''O''(''n''<sup>2</sup>)}} || rowspan="2" | || align="left" rowspan="2" | Divides the matrix into submatrices that are diagonalized then recombined.
|-
| all eigenpairs || {{math|({{frac|4|3}})''n''<sup>3</sup> + ''O''(''n''<sup>2</sup>)}}
|-
| [[Homotopy method]] || real symmetric tridiagonal || all eigenpairs || {{math|''O''(''n''<sup>2</sup>)<ref>{{Citation
| last=Chu
| first=Moody T.
| title=A Note on the Homotopy Method for Linear Algebraic Eigenvalue Problems
| journal=Linear Algebra Appl.
| volume=105
| pages=225–236
| year=1988
| doi=10.1016/0024-3795(88)90015-8
| doi-access=free
}}</ref>}} ||  || align="left" | Constructs a computable homotopy path from a diagonal eigenvalue problem.
|-
| [[Folded spectrum method]] || real symmetric || eigenpair with value closest to ''μ'' ||  ||  || align="left" | Preconditioned inverse iteration applied to {{math|(''A'' − ''μI'')<sup>2</sup>}}
|-
| [[MRRR algorithm]]<ref>{{Citation
| last1=Dhillon
| first1=Inderjit S.
| last2=Parlett
| first2=Beresford N.
| last3=Vömel
| first3=Christof
| title=The Design and Implementation of the MRRR Algorithm
| journal=[[ACM Transactions on Mathematical Software]]
| volume=32
| issue=4
| pages=533–560
| year=2006
| doi=10.1145/1186785.1186788
| s2cid=2410736
| url=http://www.cs.utexas.edu/users/inderjit/public_papers/DesignMRRR_toms06.pdf
}}</ref> || real symmetric tridiagonal || some or all eigenpairs || {{math|''O''(''n''<sup>2</sup>)}} ||  || align="left" | "Multiple relatively robust representations" – performs inverse iteration on a [[Cholesky decomposition|''LDL''<sup>T</sup> decomposition]] of the shifted matrix.
|-
| [[Gram iteration]]<ref>{{Citation
| last1=Delattre
| first1=B.
| last2=Barthélemy
| first2=Q.
| last3=Araujo
| first3=A.
| last4=Allauzen
| first4=A.
| title=Efficient Bound of Lipschitz Constant for Convolutional Layers by Gram Iteration
| journal=Proceedings of the 40th International Conference on Machine Learning
| year=2023
| pages=7513–7532
| url=https://proceedings.mlr.press/v202/delattre23a.html
}}</ref> || general || Eigenpair with largest eigenvalue ||  || super-linear || align="left" |Repeatedly computes the Gram product and rescales, deterministically.

|}