Non-monotonic decrease of residuals in Conjugate Gradients:

Question

In some of my numerical programming using conjugate gradient solvers, I noticed an alarming problem: The residuals were not monotonically decreasing to zero, but were sometimes increasing. In this document, the author writes

About fifteen years ago enough experience had been gained with matrix preconditoning that variants on the Conjugate Gradient method had come into wide use. Evolution of this methodology has continued with the introduction of several variations on the basic algorithm. The most popular of these is currently Sonneveld's conjugate gradient squared (CGS) algorithm. This class of methods has a rate of convergence that is generally very good, but is not monotonic. Plots of residual versus iteration count can show oscillations.

So I guess it might not be an error in my code. However, given the structure of the CG algorithm and the principles on which it was based, I cannot understand why the residuals don't decrease monotonically with iteration number. Is it finite arithmetic?

Answer 1

The residual $\|Ax-b\|$ is not necessarily monotonically decreasing.

Check out Stephen Boyd's slides on the conjugate gradient method. He shows an example where it increases (slide 22). http://see.stanford.edu/materials/lsocoee364b/11-conj_grad_slides.pdf

However, the distance from the solution (in terms of the inner product defined by $A$) $$\|x-x^{\star}\|_{A}^{2} = (x-x^{\star})^{T} A (x-x^{\star})$$ is monotonically decreasing. This implies that the objective $f(x) = x^{T} A x - 2 b^{T} x$ is also monotonically decreasing since $$\|x-x^{\star}\|_{A}^{2} = x^{T} A x - 2 b^{T} x + \|x^{\star}\|_{A}^{2}$$ where $x^{\star}$ satisfies $A x^{\star} = b$.

Note the difference between the objective above and the squared residual $$\|A x - b\|^2 = x^T A^T A x - 2 b^T A x + b^T b$$

Answer 2

I suppose you want to solve $Ax=b$ with $A$ being a symmetric, positive definite matrix.

Convergence of CG is monotonic -- with respect to the norm that is induced by the $A$-weighted scalar product. That is, if $r_k:=Ax_k-b$ is the current residual, then $\|x_k-x\|_A = \|r_k\|_{A^{-1}}^2 := r_k^*A^{-1}r_k$ is a decreasing sequence.

At the same time $\|r_k\|^2=r_k^*r_k$ need not be monotonically decreasing.

As CG is a stable method, the influence of rounding errors is only recognizable when the norm residuals is close to machine precision.

However, I don't know about the CGS methods you mentioned...

---

I made an EDIT to my answer to correct a wrong statement. Actually, in the $A$ norm, only the errors decrease monotonically but not the residuals. Thanks to @fieres who pointed this out in his answer.

Answer 3

There's a mistake in the accepted answer by Jan.

It says $r_k^T Ar_k$ is monotonically decreasing. Really it should say $r_k^T A^{-1}r_k$ is monotonically decreasing. This quantity, however, cannot be tracked in practice since $A^{-1}$ is unknown. To check whether the algorithm works correctly, you should check the objective function $F(x_k)=1/2 x_k^T A x_k - k_x^T b$, which does decrease monotonically, too.

See http://see.stanford.edu/materials/lsocoee364b/11-conj_grad_slides.pdf for details.

I think pterojacktyl's answer should be the accepted one. It's correct and comprehensive.

Answer 4

Have a look at Table 5.1 in this article: http://www.stanford.edu/group/SOL/reports/SOL-2011-2R.pdf

According to it, $||Ax_k-b||$ is not monotonic. Only the error $||x^*-x_k||$ is monotonically decreasing.