# Richardson's Iteration, Gradient Method and Spectral Radius

Richardson's iteration introduce a scalar $$\alpha$$ to the update formula:

$$\textbf{x}^{(k+1)} = \textbf{x}^{(k)} + \alpha \textbf{r}^{(k)}$$

And compute $$\alpha$$ by minimizing the spectral radius:

$$\min_{\omega}\,\rho(B) = \min_{\omega}\, \rho(I-\omega A)\, .$$

As $$I$$, and $$A$$ do not change over the iterations, it might seem it exists only one (i.e. equal for all the iterations) $$\omega$$ making the max eigenvalue minimal, hence the spectral radius minimal. Since I know gradient method and conjugate gradient perform better by setting $$\alpha$$ dynamically, I am wondering what am I missing here. Is there any way to see through the spectral radius expression that gradient and conjugate gradient iterations converge faster?

• The key insight is that the spectral radius of $I-\omega A$ is a conservative measure of convergence rate. One can show that picking the optimal $\omega$ over $k$ iterations amounts to solving an order-$k$ polynomial minimization problem over $\|Ax-b\|$ subject to $x = p(A)b$. You might find my answer on MO helpful: mathoverflow.net/questions/232132/… – Richard Zhang Mar 12 '19 at 20:36