Modified Richardson iteration

Modified Richardson iteration is an iterative method for solving a system of linear equations. Richardson iteration was proposed by Lewis Richardson in his work dated 1910. It is similar to the Jacobiand Gauss–Seidel method.

We seek the solution to a set of linear equations, expressed in matrix terms as

The Richardson iteration is

where ω is a scalar parameter that has to be chosen such that the sequence x^(k) converges.

It is easy to see that the method is correct, because if it converges, then  and x^(k) has to approximate a solution of Ax = b.

Convergence

Subtracting the exact solution x, and introducing the notation for the error , we get the equality for the errors

e^{(k + 1)} = e^(k) − ωAe^(k) = (I − ωA)e^(k).

Thus,

for any vector norm and the corresponding induced matrix norm. Thus, if  the method convergences.

Suppose that A is diagonalizable and that (λ_j,v_j) are the eigenvalues and eigenvectors of A. The error converges to 0 if | 1 − ωλ_j | < 1 for all eigenvalues λ_j. If, e.g., all eigenvalues are positive, this can be guaranteed if ω is chosen such that 0 < ω < 2 / λ_max(A). The optimal choice, minimizing all | 1 − ωλ_j | , is ω = 2 / (λ_min(A) + λ_max(A)), which gives the simplest Chebyshev iteration.

If there are both positive and negative eigenvalues, the method will diverge for any ω if the initial error e⁽⁰⁾ has nonzero components in the corresponding eigenvectors.

References

• Richardson, L.F. (1910). "The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam".Philos. Trans. Roy. Soc. London Ser. A 210: 307–357.
• Vyacheslav Ivanovich Lebedev (2002). "Chebyshev iteration method". Springer. Retrieved 2010-05-25. Appeared in Encyclopaedia of Mathematics (2002), Ed. by Michiel Hazewinkel, Kluwer - ISBN 1402006098
• Extremal polynomials with application to Richardson iteration for indefinite linear systems (Technical summary report / Mathematics Research Center, University of Wisconsin--Madison)

Inverse iteration

From Wikipedia, the free encyclopedia

In numerical analysis, inverse iteration is an iterative eigenvalue algorithm. It allows to find an approximate eigenvector when an approximation to a corresponding eigenvalue is already known. The method is conceptually similar to the power method and is also known as the inverse power method.

http://en.wikipedia.org/wiki/Inverse_iteration

Rayleigh quotient iteration

From Wikipedia, the free encyclopedia

Rayleigh quotient iteration is an eigenvalue algorithm which extends the idea of the inverse iteration by using the Rayleigh quotient to obtain increasingly accurate eigenvalue estimates.

Rayleigh quotient iteration is an iterative method, that is, it must be repeated until it converges to an answer (this is true for all eigenvalue algorithms). Fortunately, very rapid convergence is guaranteed and no more than a few iterations are needed in practice. The Rayleigh quotient iteration algorithm converges cubically, given an initial vector that is sufficiently close to an eigenvector of thematrix that is being analyzed.

http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration

Lanczos algorithm

From Wikipedia, the free encyclopedia

The Lanczos algorithm is an iterative algorithm invented by Cornelius Lanczos that is an adaptation of power methods to findeigenvalues and eigenvectors of a square matrix or the singular value decomposition of a rectangular matrix. It is particularly useful for finding decompositions of very large sparse matrices. In Latent Semantic Indexing, for instance, matrices relating millions of documents to hundreds of thousands of terms must be reduced to singular-value form.

Peter Montgomery published in 1995 an algorithm, based on the Lanczos algorithm, for finding elements of the nullspace of a large sparse matrix over GF(2); since the set of people interested in large sparse matrices over finite fields and the set of people interested in large eigenvalue problems scarcely overlap, this is often also called the block Lanczos algorithm without causing unreasonable confusion. See Block Lanczos algorithm for nullspace of a matrix over a finite field.

http://en.wikipedia.org/wiki/Lanczos_algorithm

Conjugate gradient method

From Wikipedia, the free encyclopedia

A comparison of the convergence ofgradient descent with optimal step size (in green) and conjugate gradient (in red) for minimizing a quadratic function associated with a given linear system. Conjugate gradient, assuming exact arithmetics, converges in at most n steps where n is the size of the matrix of the system (here n=2).

In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix issymmetric and positive-definite. The conjugate gradient method is an iterative method, so it can be applied to sparse systems that are too large to be handled by direct methods such as the Cholesky decomposition. Such systems often arise when numerically solvingpartial differential equations.

The conjugate gradient method can also be used to solve unconstrained optimizationproblems such as energy minimization.

The biconjugate gradient method provides a generalization to non-symmetric matrices. Various nonlinear conjugate gradient methods seek minima of nonlinear equations.

http://en.wikipedia.org/wiki/Conjugate_gradient_method

Krylov subspace

From Wikipedia, the free encyclopedia

In linear algebra, the order-r Krylov subspace generated by an n-by-n matrix A and a vector b of dimension n is the linear subspacespanned by the images of b under the first r powers of A (starting from A⁰ = I), that is,

It is named after Russian applied mathematician and naval engineer Alexei Krylov, who published a paper on this issue in 1931.^[1]

Modern iterative methods for finding one (or a few) eigenvalues of large sparse matrices or solving large systems of linear equations avoid matrix-matrix operations, but rather multiply vectors by the matrix and work with the resulting vectors. Starting with a vector, b, one computes Ab, then one multiplies that vector by A to find A²b and so on. All algorithms that work this way are referred to as Krylov subspace methods; they are among the most successful methods currently available in numerical linear algebra.

Because the vectors tend very quickly to become almost linearly dependent, methods relying on Krylov subspace frequently involve some orthogonalization scheme, such as Lanczos iteration for Hermitian matrices or Arnoldi iteration for more general matrices.

The best known Krylov subspace methods are the Arnoldi, Lanczos, Conjugate gradient, GMRES (generalized minimum residual),BiCGSTAB (biconjugate gradient stabilized), QMR (quasi minimal residual), TFQMR (transpose-free QMR), and MINRES (minimal residual) methods.

References

• Nevanlinna, Olavi (1993). Convergence of iterations for linear equations. Lectures in Mathematics ETH Zürich. Basel: Birkhäuser Verlag. pp. viii+177 pp.. MR1217705. ISBN 3-7643-2865-7.
• Saad, Yousef (2003). Iterative methods for sparse linear systems (2nd ed.). SIAM. ISBN 0898715342. OCLC 51266114.

1. ^ Mike Botchev (2002). "A.N.Krylov, a short biography".