The Richardson iteration is an iterative method used to solve a system of linear equations.
It was proposed by Lewis Fry Richardson in 1910.
The method is similar to the Jacobi and Gauss–Seidel methods.
Problem Setup:
Consider a system of linear equations expressed in matrix form:Ax = bwhere:
(A) is the coefficient matrix.
(x) is the vector of unknowns (the solution we seek).
(b) is the right-hand side vector.
Richardson Iteration:
The Richardson iteration updates the solution vector (x) as follows: [x^{(k+1)} = x^{(k)} + \alpha (b – Ax^{(k)})] where:
(x^{(k)}) is the current approximation of the solution.
(\alpha) is a scalar parameter that needs to be chosen for convergence.
The sequence ({x^{(k)}}) converges to the true solution if (\alpha) is appropriately selected.
Convergence:
To ensure convergence, we subtract the exact solution (x^) from both sides of the equation: [e^{(k+1)} = x^{(k+1)} – x^ = (I – \alpha A)(x^{(k)} – x^*)]
Here, (e^{(k+1)}) represents the error in the solution.
The method converges if the spectral radius of ((I – \alpha A)) is less than 1.
For symmetric positive definite matrices (A), choosing (\alpha = 1/\lambda_{\text{max}}(A)) (where (\lambda_{\text{max}}(A)) is the largest eigenvalue of (A)) yields the simplest Chebyshev iteration.
Equivalence to Gradient Descent:
Consider minimizing the function (f(x)). A sufficient condition for optimality is that the gradient is zero: (\nabla f(x) = 0).
Define (g(x) = Ax – b). Gradient descent corresponds to the update: [x^{(k+1)} = x^{(k)} – \beta g(x^{(k)})]
By choosing (\beta = \alpha), the Richardson iteration is equivalent to gradient descent.
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.” Philosophical Transactions of the Royal Society A, 210: 307–357.