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)

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

x = A \ b; in Matlab

x = A \ b;

1. Is A square?
   no => use QR to solve least squares problem.
2. Is A triangular or permuted triangular?
   yes => sparse triangular solve
3. Is A symmetric with positive diagonal elements?
   yes => attempt Cholesky after symmetric minimum degree.
4. Otherwise
   => use LU on A (:, colamd(A))