1
$\begingroup$

In conjugate gradient method for solving symmetric positive definite linear system $Ax=b$, which can also be regarded as a convex optimization problem $\dfrac{1}{2} x'Ax - x'b$, the $A$-norm of the error $\|x_k-x_\star\|_A$ at iterate $k$ is monotonically decreasing and converges linearly and we have the classical bound (or more sophisticated analysis)

$$\|x_k-x_\star\|_A \leq 2 \left(\dfrac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}\right)^k \|x_0-x_\star\|_A$$

where $x_\star$ is the solution of the linear system $Ax_{\star}=b$ and $\kappa$ is the condition number of $A$. However, the norm of residuals $r_k = b-A x_k$ is not necessarily monotonically decreasing but it still converges to zero.

My question is: Is there a convergence bound or some qualitative characterization of $\|r_k\|$?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

$$\|r_k\|=\|A(x_*-x_k)\|\le\|A^{1/2}\|\,\|A^{1/2}(x_*-x_k)\| \\ =\|A\|^{1/2}\|x_*-x_k\|_A \le 2\|A\|^{1/2} \left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k \|x_0-x_*\|_A.$$

$\endgroup$
2
  • $\begingroup$ Thanks for the answer! I actually found what I want in this book. Meurant, Gérard. The Lanczos and conjugate gradient algorithms: from theory to finite precision computations. Society for Industrial and Applied Mathematics, 2006. $\endgroup$
    – bernard
    Commented May 31, 2023 at 11:17
  • $\begingroup$ @bernard : Yet, does the answer above answer your question? $\endgroup$ Commented May 31, 2023 at 14:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.