= Condition-number bound for preconditioned steepest descent
{title2=$E_{k+1}\le((\kappa-1)/(\kappa+1))^2E_k$}
Let $m=\lambda_{\min}(B)>0$, $L=\lambda_{\max}(B)$ and $\kappa=L/m=\kappa_2(B)$ for the transformed <symmetric positive-definite matrix>. Then <preconditioned steepest descent> satisfies
$$
E_{k+1}\le\left(\frac{\kappa-1}{\kappa+1}\right)^2E_k.
$$
This is a worst-case bound, not necessarily the actual rate. For our scaled example the bound is $(1/50)^2=0.0004$, slightly above its computed factor $q_M\approx0.000384321291$. If the initial transformed error is an <eigenvector>, <exact line search for a positive-definite quadratic> removes it in one step, regardless of the full <condition number>.
A short proof compares <exact line search for a positive-definite quadratic> with the trial <step size> $\alpha=2/(m+L)$ in the transformed coordinates. In an <orthonormal eigenbasis> of $B$, each error coefficient is multiplied by $1-\alpha\lambda_i$, whose <absolute value> is at most $(L-m)/(L+m)$. Summing $\lambda_i$ times the squared coefficients bounds the trial energy by the square of this factor. The exact minimizing <step size> does at least as well. This also explains the terminating case $m=L$: the trial step removes the entire error in one iteration.
Back to article page
