Modified Richardson iteration

Remarks

The error satisfies $e_{k+1} = (I - \omega A) e_k$, and $I - \omega A$ has the eigenvalues $1 - \omega \lambda$ for the eigenvalues $\lambda$ of $A$. All of them lie in $(-1, 1)$ exactly when $0 < \omega \lambda_{\max} < 2$, which gives clause 1. The largest of $\abs{1 - \omega \lambda_{\min}}$ and $\abs{1 - \omega \lambda_{\max}}$ is least when the two are equal, which gives clause 2. Example: if $A$ has eigenvalues $1$ and $3$, the best choice is $\omega = 1/2$, and the error shrinks by the factor $1/2$ at each step. The number $\kappa$ is the condition number of $A$, so the method is slow when $A$ is ill-conditioned.

Going deeper

For a student

Richardson iteration is the simplest stationary iterative method, and the Jacobi method is Richardson iteration applied to the system scaled by the diagonal. With a preconditioner $P$ it becomes $x^{(k+1)} = x^{(k)} + \omega P^{-1} (b - A x^{(k)})$, and the same analysis applies to $P^{-1} A$. For a symmetric positive definite $A$ it is gradient descent with a fixed step on $\frac12 x^T A x - b^T x$. Letting $\omega$ vary with $k$ and choosing the steps as reciprocal Chebyshev nodes leads to Chebyshev iteration.