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\|$?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.$$

Improve this answer
$\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$
    – Iosif Pinelis
    Commented May 31, 2023 at 14:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .