### Paper Menu >>

### Journal Menu >>

Applied Mathematics, 2010, 1, 211-214 doi:10.4236/am.2010.13025 Published Online September 2010 (http://www.SciRP.org/journal/am) Copyright © 2010 SciRes. AM On the Behavior of the Residual in Conjugate Gradient Method Teruyoshi Washizawa Analysis Technology Center, Canon Inc., Tokyo, Japan E-mail: washizawa.teruyoshi@canon.co.jp 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 Copyright © 2010 SciRes. AM 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 Copyright © 2010 SciRes. AM 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 Copyright © 2010 SciRes. AM 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. |