2
$\begingroup$

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?

$\endgroup$
  • 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$ – Richard Zhang Mar 12 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.