Math 2.0

Numerical analysis Iterative methods for linear systems Proposition

Arnoldi iteration

Builds on Krylov subspaceHessenberg matrixGram–Schmidt processHermitian matrixTridiagonal matrixEigenvalueLanczos algorithm

Statement

Let AA be a complex n×nn \times n matrix and let b∈ℂnb \in \C^n be nonzero. The Arnoldi iteration sets q1=b/∥b∥q_1 = b / \norm{b} and, for j=1,2,…j = 1, 2, \dots, computes hij=qi∗Aqj (1≤i≤j),wj=Aqj−∑i=1jhijqi,hj+1,j=∥wj∥,qj+1=wj/hj+1,j.h_{ij} = q_i^* A q_j \ (1 \le i \le j), \quad w_j = A q_j - \sum_{i=1}^{j} h_{ij} q_i, \quad h_{j+1, j} = \norm{w_j}, \quad q_{j+1} = w_j / h_{j+1, j}. Here ∥⋅∥\norm{\cdot} is the Euclidean norm. Suppose hj+1,j≠0h_{j+1, j} \ne 0 for j=1,…,mj = 1, \dots, m. Let QmQ_m be the n×mn \times m matrix with columns q1,…,qmq_1, \dots, q_m. Let H~m\tilde{H}_m be the (m+1)×m(m+1) \times m matrix of the hijh_{ij}, with hij=0h_{ij} = 0 for i>j+1i > j + 1, and let HmH_m be its first mm rows. Then:

  1. q1,…,qm+1q_1, \dots, q_{m+1} is an orthonormal basis of the Krylov subspace 𝒦m+1(A,b)\mathcal{K}_{m+1}(A, b);
  2. AQm=Qm+1H~mA Q_m = Q_{m+1} \tilde{H}_m, and Hm=Qm∗AQmH_m = Q_m^* A Q_m is an upper Hessenberg matrix;
  3. if hm+1,m=0h_{m+1, m} = 0 instead, the iteration stops at step mm, 𝒦m(A,b)\mathcal{K}_m(A, b) is invariant under AA, and every eigenvalue of HmH_m is an eigenvalue of AA.

Remarks

The iteration is the Gram–Schmidt process, in its modified form in practice, applied to the vectors b,Aq1,Aq2,…b, A q_1, A q_2, \dots. Since AqjA q_j lies in 𝒦j+1(A,b)\mathcal{K}_{j+1}(A, b), clause 1 follows by induction, and clause 2 is the matrix form of the defining recurrence. Clause 3 holds because AQm=QmHmA Q_m = Q_m H_m when hm+1,m=0h_{m+1, m} = 0. The eigenvalues of HmH_m are the Ritz values; the extreme ones often approximate eigenvalues of AA well for mm much smaller than nn. Example: if bb is an eigenvector of AA for λ\lambda, then w1=0w_1 = 0, the iteration stops at m=1m = 1, and H1=(λ)H_1 = (\lambda). If AA is Hermitian, then HmH_m is Hermitian and Hessenberg, hence tridiagonal. Then the recurrence has only three terms, and it becomes the Lanczos algorithm.

Going deeper

For a student

Arnoldi is the engine of GMRES for nonsymmetric linear systems and of the implicitly restarted Arnoldi method for eigenvalues. Its cost grows with mm: step jj needs one product with AA and jj inner products, and all qjq_j must be stored. This is why practical codes restart after a fixed number of steps. The relation AQm=Qm+1H~mA Q_m = Q_{m+1} \tilde{H}_m reduces large problems on 𝒦m\mathcal{K}_m to small problems with H~m\tilde{H}_m.

Reading path

To understand this page from the ground up, read these 18 pages in order. The foundations come first.

Show the path as a graph
Eigenvalue, concept, no evidence levelEigenvalueconceptHermitian matrix, concept, no evidence levelHermitian matrixconceptHessenberg matrix, concept, no evidence levelHessenberg matrixconceptKrylov subspace, concept, no evidence levelKrylov subspaceconceptOrthonormal basis, concept, no evidence levelOrthonormal basisconceptSymmetric matrix, concept, no evidence levelSymmetric matrixconceptTridiagonal matrix, concept, no evidence levelTridiagonal matrixconceptVector space, definition, no evidence levelVector spacedefinitionLanczos algorithm, statement, no evidence levelLanczos algorithmstatementInner product, definition, no evidence levelInner productdefinitionLinear combination, definition, no evidence levelLinear combinationdefinitionLinear subspace, definition, no evidence levelLinear subspacedefinitionOrthogonal vectors, definition, no evidence levelOrthogonal vectorsdefinitionLinear independence, definition, no evidence levelLinear independencedefinitionLinear span, definition, no evidence levelLinear spandefinitionOrthonormal family, definition, no evidence levelOrthonormal familydefinitionGram–Schmidt process, concept, no evidence levelGram–Schmidt processconceptArnoldi iteration, statement, no evidence levelArnoldi iterationstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Eigenvalue concept
  2. Hermitian matrix concept
  3. Hessenberg matrix concept
  4. Krylov subspace concept
  5. Orthonormal basis concept
  6. Symmetric matrix concept
  7. Tridiagonal matrix concept
  8. Vector space definition
  9. Lanczos algorithm statement
  10. Inner product definition
  11. Linear combination definition
  12. Linear subspace definition
  13. Orthogonal vectors definition
  14. Linear independence definition
  15. Linear span definition
  16. Orthonormal family definition
  17. Gram–Schmidt process concept
  18. Arnoldi iteration statement

Where this leads

5 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Arnoldi_iteration
About this page
TagCJ5EC820S7
URIm2://CJ5EC820S7
Kindstatement, proposition
WritingW0 stub
MSC65F15, 65F10, 65F25
StatusThis copy of the site has no build data. Run m2 status CJ5EC820S7.
AboutKrylov subspace, Hessenberg matrix
UsesKrylov subspace, Hessenberg matrix, Gram–Schmidt process, Hermitian matrix, Tridiagonal matrix, Eigenvalue, Lanczos algorithm
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by