Modified Richardson iteration

Modified Richardson iteration is an iterative method for solving a system of linear equations. Richardson iteration was proposed by Lewis Fry Richardson in his work dated 1910. It is similar to the Jacobi and Gauss–Seidel method.
We seek the solution to a set of linear equations, expressed in matrix terms as
The Richardson iteration is
where formula_3 is a scalar parameter that has to be chosen such that the sequence formula_4 converges.
It is easy to see that the method has the correct fixed points, because if it converges, then formula_5 and formula_4 has to approximate a solution of formula_7.
Convergence.
Subtracting the exact solution formula_8, and introducing the notation for the error formula_9, we get the equality for the errors
Thus,
for any vector norm and the corresponding induced matrix norm. Thus, if formula_12, the method converges.
Suppose that formula_13 is symmetric positive definite and that formula_14 are the eigenvalues of formula_13. The error converges to formula_16 if formula_17 for all eigenvalues formula_18. If, e.g., all eigenvalues are positive, this can be guaranteed if formula_3 is chosen such that formula_20. The optimal choice, minimizing all formula_21, is formula_22, which gives the simplest Chebyshev iteration. This optimal choice yields a spectral radius of 
where formula_24 is the condition number.
If there are both positive and negative eigenvalues, the method will diverge for any formula_3 if the initial error formula_26 has nonzero components in the corresponding eigenvectors.
Equivalence to gradient descent.
Consider minimizing the function formula_27. Since this is a convex function, a sufficient condition for optimality is that the gradient is zero (formula_28) which gives rise to the equation
Define formula_30 and formula_31.
Because of the form of "A", it is a positive semi-definite matrix, so it has no negative eigenvalues.
A step of gradient descent is
which is equivalent to the Richardson iteration by making formula_33.