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?

  • 2
    $\begingroup$ 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/… $\endgroup$ Mar 12, 2019 at 20:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.