Applied Mathematics, 2010, 1, 211-214
doi:10.4236/am.2010.13025 Published Online September 2010 (http://www.SciRP.org/journal/am)
On the Behavior of the Residual in Conjugate
Gradient Method
Teruyoshi Washizawa
Analysis Technology Center, Canon Inc., Tokyo, Japan
Received March 21, 2010; revised July 22, 2010; accepted July 24, 2010
Abstract
In conjugate gradient method, it is well known that the recursively computed residual differs from true one
as the iteration proceeds in finite arithmetic. Some work have been devoted to analyze this behavior and to
evaluate the lower and the upper bounds of the difference. This paper focuses on the behavior of these two
kinds of residuals, especially their lower bounds caused by the loss of trailing digit, respectively.
Keywords: Conjugate Gradient, Residual, Convergence, Finite Arithmetic, Lower Bound
1. Introduction
Conjugate gradient (CG) method and its varieties are
popular as one of the best unsteady iterative methods for
solving the following linear system:
A
xb (1)
In CG method, an approximate solution xk is expected
to approach the exact solution x*. For the symmetric
positive definite A, it is proved that the A-norm of the
error monotonically decreases as the iteration proceeds in
exact arithmetic. This will be called as A-norm mono-
tonicity of the error in the remaining part of this article.
It is obvious that we cannot calculate directly such a
norm of the error without the solution. Therefore, almost
algorithms employ the residual which is easily calculated
as the difference between the left hand side (LHS) and
the right hand side (RHS) of (1), rk : = b-Axk. In practice,
the residual is calculated by the recursion formula be-
cause of the computational complexity of the matrix
vector product Axk [1,2].
However, this recursion formula causes another prob-
lem in which the recursive residual differs from the true
residual as the iteration proceeds. It can be also observed
that the recursive residual decreases after the true one
seams to reach its lower bound. We should terminate the
CG steps just before the difference is too large to be ne-
glected.
Ginsburg has proposed a simple criterion [1]:
For the true residual calculated as the difference be-
tween LHS and RHS of a linear system and the recursive
residual calculated by using the recursion formula, the
procedure is terminated when the 2-norm of their differ-
ence is greater than the 2-norm of the recursive residual:

2
exp
kkk
rknsr


where n is dimensionarity of a linear system.
Several researchers have proposed the estimations of
the lower and the upper bound of the norm of the error
and the residual. Woźniakowski investigated the nume-
rical stabilities and good-behaviors of three stationary
iterative methods and CG method using the true residual
b-Axk [3,4]. Woźniakowski gave the upper bound of the
ultimately attainable accuracies of the A-norm and the
2-norm of the error, and 2-norm of the true residual. Bo-
llen gives the round-off error analysis of descent me-
thods and lead a general result on the attainable accuracy
of the approximate solution in finite arithmetic [2]. It has
also shown that the general result is applied to the
Gauss-Southwell method and the gradient method to
obtain the decreasing rates of the A-norm of the error in
finite arithmetic. Greenbaum have shown that for tiny
perturbation εM, the eigenvalues and the A-norm of the
error vectors generated over a fixed number of perturbed
iterative steps are approximately the same as those quan-
tities generated by the exact recurrences applied to a
“nearby” matrix [5]. The lower bound of the true residual
is pointed out in [6]. Two kinds of the estimates of the
A-norm of the error at every step in CG algorithm has
been proposed and verified that those estimates are the
lower and the upper bound in [7]. The lower and the up-
per bounds of the A-norm of the error have been also
given by Meurant [7] and Strakoš and Tichý [8]. Strakoš

T. WASHIZAWA
212
and Tichý have proposed the tight estimate for the lower
bound of both the A-norm and the 2-norm of the error in
every step. This stepwise lower bound, however, keeps
decreasing after the error reaches its ‘global’ lower
bound. Therefore, the terminating criteria by using this
stepwise lower bound cannot detect the global lower
bound of the error. Calvetti et al. has proposed the esti-
mates of the lower and upper bound of the A-norm of the
error in CG method [9]. Those previous studies give the
stepwise lower and the upper bound of the error and the
residual but the global bounds.
In the remaining part of this article, we will first show
that the true and the recursive residual almost monotoni-
cally decrease as the iteration proceeds. Then, these
lower bounds will be shown.
2. Notations
We shall give the notations appeared throughout this
article. A and b is, respectively, a coefficient matrix and a
constant vector in a linear system. |||| in connection with
a vector and a matrix, respectively, stands for the 2-norm
and spectral norm, ||||A in connection with a vector
stands for the norm under the metric tensor A. The exact
value of a variable x is denoted as
x
. The floating point
representation of a variable x is denoted simply as x. The
computational error caused by the floating point repre-
sentation is denoted as an operator ():
M
x
xx

.
The exact solution of (1) is denoted as x* which is de-
scribed formally as x*=A-1b. At the k-th step, an ap-
proximate solution, the error, the true residual, and the
recursive residual is, respectively, described as xk, ek, sk,
and rk. They are computed in CG method as follows:
1
1
:,:,
:,:
kkkkk k
kkkkk
x
xpexx
s
bAxrr Ap





 
 
Since A is a constant matrix and ||εM(A)||/||A|| is almost
equal to εM without the dependence on the number of
iterations, εM(A) is out of our concern as well as εM(b).
3. Almost Monotonicity of Residuals in
Finite Arithmetic
In this section, we will see the true and the recursive re-
sidual has the 2-norm almost monotonicity in finite ari-
thmetic, respectively.
3.1. The 2-Norm Almost Monotonicity of True
Residual
The true residual is calculated as the difference between
LHS and RHS. This is equivalent to multiplication of A
to the error in finite arithmetic,


kk kk
s
bAxbAx xAxAe

 
The behavior of true residual sk is, therefore, equiva-
lent to Aek.
The A-norm monotonicity of the error in finite arith-
metic has been proved in theorem-3.1 of [2]. The fol-
lowing theorem shows the error has the 2-norm almost
monotonicity.
Theorem-1. If ek has the A-norm monotonicity, ek has
the 2-norm almost monotonicity for a regular matrix A,
,kj kje e (2)
Proof. The relationship between 2-norm and A-norm
of error is
1/2 1/2
kk k
A
A
eAe Ae

 (3)
Similarly,
1/2 1/2
kk k
A
eAeAe (4)
Substituting (3) and (4) into (2) and we yield
1
1/2 1/2
kj
AA
A
eAe

 (5)
Equation (5) holds if k exists to satisfy the following
relation

1
1/2
kj
AA
eAe 

 (6)
where
 (A) is the condition number of a matrix A. From
the A-norm monotonicity of the error ek, since the fol-
lowing relation holds for any positive value a,
,kj
AA
kje ae
there exists k > j that satisfies (6) and consequently (2).
We have to notice that (2) does not hold when a = 0, i.e.,
the inverse of the coefficient matrix A is singular.
Theorem-1 leads to the 2-norm almost monotonicity of
the true residual using the relationship kk
s
Ae.
Theorem-2. If ek has the 2-norm almost monotonicity,
sk has the 2-norm almost monotonicity for a regular ma-
trix A,
, kj kjs s (7)
Proof. The relationship between the 2-norm of the er-
ror and that of the residual is
kk k
s
AeA e (8)
Similarly,
11
j
jj
eAsAs

 (9)
Substituting (8) and (9) into (7) and we yield

T. WASHIZAWA
213
1
1
kj
A
eAe


 (10)
Equation (10) holds if k exists to satisfy the following
relation

1
kj
eAe 

 (11)
From the 2-norm almost monotonicity of the error ek,
since the following relation holds for any positive value
a,
,kj kje ae (12)
there exists k > j that satisfies (11) and consequently (7).
3.2. The 2-Norm Almost Monotonicity of
Recursive Residual
Before the proof of almost monotonicity of recursive
residual in finite arithmetic, we first give the proof of
almost monotonicity of recursive residual in exact arith-
metic.
From the A-norm monotonicity of the error in exact
arithmetic, the 2-norm almost monotonicity of the resid-
ual in exact arithmetic can be proved. We have to notice
that the recursive residual
j
r is identical to the true re-
sidual
j
s
in exact arithmetic.
Theorem-3. If 1 ,nn
AA
ne e

, then the following
proposition holds for a regular matrix A:
,kj kjr r (13)
Proof. The relationship between the error and the re-
sidual gives:
1/2
kk k
A
rAeAe (14)
Then we yield the lower and the upper bound of the
2-norm of the true residual:
1
1/2 1/2
kk k
AA
A
erAe

 (15)
From above equation, the sufficient condition for (13)
can be given as follows:
1
1/ 21/ 2
kj
AA
A
eAe


 (16)
that is, the equation holds if there exists k > j so that

1
1/2
kj
AA
eAe 

 (17)
From the A-norm monotonicity of the error k e, the
following equation holds for any positive value a,
,kj
AA
kje ae (18)
and (13) holds.
Now we show the almost monotonicity of the recur-
sive residual in finite arithmetic.
Theorem-4. If the recursive residual has 2-norm al-
most monotonicity in exact arithmetic, then the recursive
residual has the 2-norm almost monotonicity in finite
arithmetic:
,kj kjr r (19)
Proof. Equation (19) is rewritten as
 
,kMk jMj kjrr rr    (20)
The following relationship is one of its sufficient con-
ditions
 
max min
kMk jMj
rr rr 





The evaluation of the maximum value of LHS is

max 1
kMk
rr  
 (21)
Similarly, the minimum value of RHS is evaluated as

min 1
j
Mj
rr 


 (22)
Substituting (21) and (22) into (20), the sufficient con-
dition of (20) is given as

 
,1 1
kMMj
kjr r   (23)
There exists k > j for

11 0
MM
  from
theorem-3 and (23) holds.
4. Lower Bounds of Error and Residual in
Finite Arithmetic
It has been shown that the 2-norm of two kinds of re-
siduals, respectively, decreases almost monotonically in
finite arithmetic in the previous section.
Now we consider whether if the 2-norm of each vari-
able stops decreasing before the approximate xk does not
reach its target x*.
4.1. Lower Bound of Error
Theoem-1 shows the approximate solution xj approaches
the exact solution almost monotonically in finite arith-
metic. The correction of the recursion formula of xk,
however, vanishes by the loss of trailing digits so that the
error stops changing, i.e.,




1
s
topstopMstopstop
x
nx nxx 


where xk (n) is the n-th component of xk.
On the other hand, the solution in finite arithmetric x*
is not always identical to that in exact arithmetic *
x
.
Therefore, the target for iterative algorithms in finite

T. WASHIZAWA
214
arithmetic should not be *
x
but x*. The error caused by
the loss of trailing digits is described formally as
s
top
x
x
. Since the true residual is given by multiplying
A to the error, the lower bound of the true residual is
given as

s
top
Ax x
.
4.2. Lower Bound of Recursive Residual
Theorem-4 shows the recursive residual reduces its 2-
norm almost monotonically. The next theorem proves
that the change of the recursive residual stops only when
||rk+1|| < εM ||rk||. It decreases almost monotonically until
then.
Theorem-5. The recursive residual never have a lower
bound caused by the loss of trailing digits.
Proof. The recursion formula of the residual is in gen-
eral described as
1kkk
rrr
 (24)
where ∆rk := αkApk. The residual reaches its lower bound
rk if the following condition is satisfied:


kMk
rr   (25)
We will show the condition of (25) never be satisfied
in not only exact but also finite arithmetic.
In exact arithmetic, (24) satisfies the following relation-
ship:


222 2
1
22
1
222 22
2,
2,
2
kkkkkkk
kkkkk
kkk kk
rrrrrrr
rrrrr
rrr rr


 
 
 
where using

1
,0
kk
rr
.
Therefore, three vectors in above recursion formula
forms the right triangle so that the following relationship
holds in exact arithmetic :
kk
rr (26)
This shows that (25) never be satisfied in exact arith-
metic.
Now we evaluate above in finite arithmetic.




min
max
12
1
11
kMk
k
kkMk
M
kk
M
MkM k
rr
r
rrr
rr
rr





 




  




According to (26), we yield
 
12 1
kkM M
rr  
and prove that the recursive residual never have a lower
bound caused by the loss of trailing digits.
The termination of the iterations is caused only when
1kMk
rr 
 by the significant decrease of the recur-
sive residual for kkk
A
pr


.
5. Conclusions
In this article, the convergence behaviors of true and
recursive residual have been analyzed.
The results obtained are summarized below:
1) In finite arithmetic, the 2-norm of the error and the
residual, respectively, almost monotonically decreases.
2) 2-norm of the error has the lower bound in finite
arithmetic as well as the true residual.
3) 2-norm of the recursive residual never has a non-
zero lower bound caused by the loss of trailing digits in
finite arithmetic.
6. References
[1] T. Ginsburg, “The Conjugate Gradient Method,” Nu-
merische Mathematik, Vol. 5, No. 1, 1963, pp. 191-200.
[2] J. A. M. Bollen, “Numerical Stability of Descenet Meth-
ods for Solving Linear Equations,” Numerische Mathe-
matik, Vol. 43, No. 3, 1984, pp. 361-377.
[3] H. Woźniakowski, “Round-off Error Analysis of Iterati-
nos for Large Linear Systems,” Numeriche Mathematik,
Vol. 30, No. 3, 1978, pp. 301-314.
[4] H. Woźniakowski, “Roundoff Error Analysis of New
Class of Conjugate-Gradient Algorithms,” Linear Alge-
bra and its Applications, Vol. 29, 1980, pp. 507-529.
[5] A. Greenbaum, “Behavior of Slightly Perturbed Lanczos
and Conjugate-Gradient Recurrences,” Linear Algebra
and its Applications, Vol. 113, 1989, pp. 7-63.
[6] A. Greenbaum, “Estimating the Attainable Accuracy of
Recursively Computed Residual Methods,” SIAM Jour-
nal on Matrix Analysis and Applications, Vol. 18, No. 3,
1997, pp. 535- 551.
[7] G. Meurant, “The Computation of Bounds for the Norm
of the Error in the Conjugate Gradient Algorithm,” Nu-
merical Algorithms, Vol. 16, No. 3-4, 1997, pp. 77-87.
[8] Z. Strakoš and P. Tichý, “On Error Estimation in the
Conjugate Gradient Method and Why it Works in Finite
Precision Computations,” Electronic Transactions on
Numerical Analysis, Vol. 13, 2002, pp. 56-80.
[9] D. Calvetti, S. Morigi, L. Reichel and F. Sgallari, “Com-
putable Error Bounds and Estimates for the Conjugate
Gradient Method,” Numerical Algorithms, Vol. 25, No.
1-4, 2000, pp. 75-88.