Mathematics - 367 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 Discuss of Error Analysis of Gauss-Jordan Elimination For Linear Algebraic Systems S.Ab. M. Abbas Department Of Mathematics - College Of Science University Of Baghdad Received in:22 January 2012 Accepted in:21 May 2012 Abstract The paper establishes explicit representations of the errors and residuals of approximate solutions of triangular linear systems by Jordan elimination and of general linear algebraic systems by Gauss-Jordan elimination as functions of the data perturbations and the rounding errors in arithmetic floating-point operations. From these representations strict optimal componentwise error and residual bounds are derived. Further, stability estimates for the solutions are discussed. The error bounds for the solutions of triangular linear systems are compared to the optimal error bounds for the solutions by back substitution and by Gaussian elimination with back substitution, respectively. The results confirm in a very detailed form that the errors of the solutions by Jordan elimination and by Gauss-Jordan elimination cannot be essentially greater than the possible maximal errors of the solutions by back substitution and by Gaussian elimination, respectively. Finally, the theoretical results are illustrated by two numerical examples. Key words: Jordan elimination, data perturbations, error bounds, Gaussian elimination. Introduction The Gauss-Jordan algorithm is ideally suited for vector computers [1]. This justifies the study of the numerical stability of the algorithm under data perturbations and rounding errors of floating-point arithmetic. It uses the same direct method of forward analysis as our rounding error analysis of Gaussian elimination in [2]. Both the solution of general linear systems by the Gauss-Jordan algorithm and of upper triangular linear system by Jordan elimination are analyzed[3]. The main results of the paper are optimal componentwise error and residual estimates, bounds for the stability of solutions and residuals, and upper bound for the errors of the solutions of Jordan elimination and Gauss-Jordan elimination in terms of the optimal error bounds for back substitution and Gaussian elimination respectively. The results will prove that the error of the Gauss-Jordan solution cannot be much greater than the possible maximal error of the solution by Gaussian elimination with back substitution. However, the residual bounds of the Gauss-Jordan solution can be big if the solution vector has components with big relative errors. The first step of the error analysis consists in the derivation of explicit analytical representations of the errors and residuals of approximate solutions of linear algebraic systems as functions of the data errors and the rounding errors of the arithmetic floating- operations. Under standard assumptions on the data errors of the problem and the rounding errors of the floating-point arithmetic these error and residual representations readily yield strict componentwise and, save for terms of higher order in the accuracy constant η. optimal error and residual estimates for the solutions of upper triangular linear systems in the following theorem {The residual of the computed approximate solution vector x of the Mathematics - 368 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 triangular linear system is bounded componentwise, optimally with respect to the error distributions by ,RR D D TTTZxU ηηη +=≤− [2] Where U upper triangular linear system, η accuracy constant, 0<ηR< 4/(3n), ηD data accuracy, ηR rounding accuracy in application ηR<<ηD, matrix Z defined in the Jordan algorithm see [1] for the solution of regular triangular linear systems; u11x1+ u12x2+…+ u1nxn = z1 Ux = Z: u22x2+…+ u2nxn = z2 unnxn = zn A general linear systems in the following theorem {the residuals of the approximate solutions x of general linear systems by Gauss-Jordan elimination satisfy the componentwise optimal estimates ,myx ≤−Α [4]. Where Y is column vector,η accuracy constant A basic tool for the formulation of the error and residual bounds are the associated data, rounding, and total condition numbers i R i D i σσσ ,, of the components of the computed solutions ix and j R j D j TTT ,, of the components of the associated residuals jyxA )( − . In addition, using these condition numbers, the stability constants Di R iiw σσ /= of the solutions and D j R jj TT /=ψ of the residuals are formed which measure the ratio of the contribution to the total error bound due to the rounding errors in floating-point operations on the one hand and the data perturbations on the other hand. The size of the possible residuals can be assessed by means of the residual stability constants ψj, for Jordan solutions n, ,… 2, 1, =i,0≠ix of upper triangular linear systems the upper bound R R m R m D j R j j T T ηρ ρ ψ − ≤= 1 , j= 1, 2, …, n,whewe ρmR is the maximal relative rounding condition number of the solution vector, ηR rounding aceurauy [4]. If 1R R m <ηρ . An analagus estimate holds for general linear system. The magnitudes of the possible maximal errors are measured componentwise, using the total condition numbers j,iσ and G,iσ , i= 1, 2, …, n, by 10, ii R iR R iD D ii σσσησησησ +=+= The term D D i ησ is the bound for the contribution of the data perturbations to the total error of the solution, the term R1iR0i , ησησ bound the contributions by eliminations in the lower and in the upper triangle of the coefficient matrix, respectively establishes the estimate. ( ) ]3[,, 1, 2 0 ,, 0 ,, Rjim RGjD D GiRjiD D ji Gpq q ηησ ησησησησ + +≤+ For solutions 0,0 ,, ≠≠ Giji xx i = 1, 2, …, n, For sufficient small accuracy constant ),max( RD ηηη = the constant q is close to 1. 1. The Gauss-Jordan Method The following error analysis deals with the Gauss- Jordan algorithm for solving linear systems Mathematics - 369 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 niyxayx kik n k ,...2,1,: 1 ===Α ∑ = …(1) We shall assume that A=( iKa ) is nonsingular and that rows and columns of A have been ordered such that A possesses a triangular factorization. In [5] we have shown how error and residual estimates are used when pivoting is taken into account. Let A1 = (A, y ) =( 1 iKa )be the n×n+1 coefficient matrix of the linear system (1). The Gauss-Jordan algorithm successively eliminates by means of the pivotal equation t the unknown xt where the vector x= (xℓ, xℓ+1, …, xn) of (1) is obtained simply by niuwx iiii ,...,1 ,/ == from all other equations i= 1, 2, …., n, i≠t, for t=1,…, n. The coefficients tikt aA )(= of the reduced linear systems thus obtained are specified by the equations 1,...,1 ,,...,1,1 += =−=+ n kniumaa tkit t ik t ik …(2) Using the coefficients utk of the pivot equation t and the row multipliers mit, defined by ;1;0;1,...1 ;,...,,2,1, , =≠+= ≠= == tttt tt t it it t tktk munk tiniua mau .….(3) For t=1, …, n. In this way, ntt knikiatik ,...,1,,...,1 ,,...,1,,01 = ==≠=+ …..(4) That is, in the first t columns of the matrix At+1 all off- diagonal entries are zero. Hence the coefficient matrix An+1 has the form An+1= ( D , w ) with an n-by-n diagonal matrix D and the vector w where niaw wWuudiagD n nii inn ,...,1, ),();,...,( 1 1, 11 == == + + …..(5) From the associated reduced linear system ,,...,1, : niw xuwDx i iii = == …..(6) The solution vector x=(x1,…, xn) of (1) is obtained simply by ix = iw /uii,i=1,…,n, [6] The residual of the computed approximate solution vector x of the triangular linear system is bounded componentwise, optimally with respect to the error distribution by R R D D T TTZXU ηηη +=≤− Mathematics - 370 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 If 0x ≠ for i = 1,. . . ,n and 1m <ηρ , the absolute and relative error of the approximate solution x satisfy componentwise, in first order optimal error estimates holds. , 1 ηρ ησ m i ii xx − ≤− n,., . 1,. i , 1 = − ≤ − ηρ ηρ m i i ii x xx [5] …..(7) Lemma: The vector of data condition numbers is bounded from below by: R RD x ησσ −≥ 2 ;[2] The rounding condition numbers can be written in the form n R n x≥σ . Jordan elimination in comparison with back substitution 1. The behaviour of the errors of approximated solutions of triangular linear systems by Jordan elimination (J) will now be compared with that of solutions by Gaussian with back substitution (G) in linear algebra, Jordan elimination brings a matrix to reduced row echelon form, whereas gaussian elimination takes it only as for as row echelon form. Every matrix has a reduced row echelon form, and this algorithm is guaranteed to produced it see [6]. It will be shown that the vectors of data and rounding condition number R j D j σσ , of the Jordan solutions can be bounded from above by the corresponding condition numbers R G D G σσ , of the solutions by back substitution. This result means that the errors of the computed Jordan solutions jx cannot be essentially bigger than the possible maximal errors of the corresponding computed solutions Gx by back substitution. 2. when triangular linear systems are solved by back substitution the associated solution and residual stability constants Giw , , Gj ,ψ of the solutions Gix , are bounded below and above by       ≠ −− −+ ≤≤ + ≠ −− −+ ≤≤ + nj jn jn ni in in w R Gj R R Gi R for , )(2 2 2 1 for , )(2 2 2 1 , , η ω µ ηµ for i,j=1,…,n …..(8) These estimates are obtained from the error and residual bounds in [2] 3. Solving a triangular linear system both by Jordan elimination and by back substitution gives two approximations jx , Gx for the searched solution vector x see [7]. These two approximations satisfy the error estimates of residual of the computed approximate solution vector x of the triangular linear system is bounded componentwise, optimally with respect to the error distributions by RRDD T TTzxu ηηη +=≤− in first order optimal estimates, that is, , ,1 , , , ηρ ηρ j j x xx m i ji iji − ≤ − , ,1 , , , ηρ ηρ G G x xx m i Gi iGi − ≤ − ….(9) Mathematics - 371 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 for i =1, …,n, where 1. 1≠ηρ Gm 2. 1≠ηρ Jm 3. ρi, is defined i i i x σ ρ = , i = 1, . . ., n. 4. 0, ≠jix 5. 0, ≠Gix For comparing the error behavior of the two algorithms .We need the following result Lemma[8]: Let the two approximate solutions jx , Gx have non-vanishing components and let the maximal relative total condition numbers of these solution be bounded by (ρm,j+ ρm,G)η< 2 1 Then the componentwise estimates jGGj xqxxqx ≤≤ , are valid using the constant 01,01 and ,1 11 1/1 ≠−≠− >      − − − −= ηρηρ ηρ ηρ ηρ ηρ Gj G G j j q mm m m m m Lemma: Let the two approximate solutions Gj xx , have nonvanishing components and let the maximal relative total condition numbers of these solutions be bounded by (ρm,j + ρMG) η< 2 1 then the component wise estimates jGGj xqXXqX ≤≤ , are valid Theorem: (under the assumption of above Lemma the estimates 0rdenominado provided , 1 1 ,, 2, ≠ − ≤ Gq q D i R D Gmji D ji σηρω σ . 2 3 , ≤ R jiσ ( ) n , 1, ifor Hold . 1 2 3 3 5 4 3 1 1 , , 2 …=       −++      −+− −+ R Gi R R Gm q qinin in σ ηρ when. Rη is so small that the denominators are positive,[8] Solution of general linear system by Gauss- Jordan elimination The solution of general linear systems yx =Α by Gauss- Jordan elimination will be analyzed. In the context of rounding error analysis the algorithm is considered as being Mathematics - 372 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 composed of Gaussian forward elimination and a subsequent solution of the upper triangular linear system zUx = by Jordan elimination see [3]. The computed trapezoidal factors 1,UL of A1= (A, y) or, under data perturbations, )y ,A( A1 = satisfy, according to [2, 1. (13)], the relation GFAUL += 11 …..(10) With an error matrix FG. Using trapezoidal factorization A1=LU1 of the n-by-(n+1) coefficient matrix, one readily derives from (10) the equation GFAULLU +∆=∆+∆ 111 ….(11) Since 01 =−= ∧ zUxxU …(12) GFAULLU +∆=∆+∆ 111 Implies the representation ˆ)(ˆ 1 1 1 xFALxU G+∆=∆ − …(13) This result establishes the dependence of the errors 1U∆ of the n-by-(n+1) coefficient matrix 1U of the upper triangular linear system, which has to be solved by Jordan elimination, upon the data errors and the rounding errors in forward elimination, where FG denotes the errors matrix of forward elimination in and FJ the errors matrix of the solution by Jordan elimination. Comparsion of Gauss-Jordan elimination with Gaussian elimination The behavior of the error of the solution of general linear system by Gaussian elimination on the one hand and Gauss-Jordan elimination on the other hand will be compared with each other. In both cases we assume the same perturbed data ., yA Then for both methods also computed triangular factors uL, of A and computed coefficients ZU , of the upper triangular factor system are the same. The vector of data and rounding condition numbers of Gaussian elimination are specified by (see [8, 64]). The solution vector Gj xx , of the two method satisfy error estimates of the form .,,1, 1 , 1 ni mx xx m xx i i iii ii = − ≤ − − ≤− ηη ρ ηρ ρ ησ The following equation shows that the total condition numbers ( ),,max,,,1,,,, RDRjiRDjiDji ni ηηηση η σ η η σ ==+=  Of the Gauss – jordan algorithm can be bounded from above by for corresponding total condition number σi,G of Gaussian elimination for sufficiently small accuracy constant η, the condition number σi,j is, in essence, less than or equal to ( )in −+1 2 3 − times σi,j because the constant q and the denominator are close to 1.The condition number σi constitute , save for terms of higher order in η, optimal bounds for the absolute errors .iii xxx −=∆ Hence, the result say that for sufficiently small η the absolute errors ∆xi,j of the solutions by Gauss- Mathematics - 373 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 Jordan elimination cannot be, in absolute value, essentially grater than ( ) timesin −−+1 2 3 the possible maximal errors nxxx iGiGi ,,,1,,, −=∆ of the solution by Gaussian elimination. Numerical example The results of the paper are now illustrated by simple numerical example. The first example is the upper triangular linear system 0.826354 x1+0.432175 x2+0.613256 x3+0.614227 x4 = 0.722872 0.000547x2+0.814712 x3+0.816328 x4 =0.15424 0.915316 x3+0.814275 x4 =0.109844 ….(14) 0.982176 x4 =0.602286 Of Peters-Wilkinson [2].Table 1 contains the condition numbers, stability constants and the solution by Jordan elimination which were computed in high accuracy and then rounded to 6 decimal digits. Table 2 shows the corresponding results of the solution by back substitution. Since the data condition numbers D i D i τρ , in essence, depend on the problem only but not on the algorithm these condition numbers coincide in both algorithms in the first 6 digits. The residual condition number 3343, = R jiτ of the Jordan solution and the corresponding residual stability constant 1699,1 =jψ (see table 1) are much bigger in this example than those of the solution by back substitution where 3.1 , ≤ Gj ψ for j=1,…, 4. (see table 2) In contrast, the relative rounding condition numbers of the solutions and thus the solution stability constants iw do not differ much for the two algorithms. 2. The second example is a linear system with the 5×5 Hilbert matrix A of Wilkinson [10, III, 34] and the right-hand side 1. )1,1,1,1,1(,; 1 10 !10*50 5,...,1, 8 =     + =Α = t ki y ki ….(15) The first 6 digit of the solution, the condition numbers and stability constants for Gauss- Jordan elimination and Gaussian elimination, all computed in high accuracy, are found in table 3 and table 4. The matrix A is ill-conditioned so that the relative data and rounding condition numbers R i D i ρρ , are big in value. The relative error of the computed solution may effect up to 6 decimal digits. Nevertheless, the maximal residual stability constant 5.15, =jiψ of Gauss-Jordan elimination is only about 5.3- times bigger than the maximal residual stability constant 9.2,4 =Gψ of Gaussian elimination. Mathematics - 374 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 The relative rounding condition numbers Riρ of the two algorithms are practically equal. Therefore also the stability constants wi of the two algorithms coincide in the leading decimal digits. Conclusion Error and residual bounds can be computed numerically together with the solutions of the linear systems. The calculated condition numbers and stability constants of the solutions by Gauss-Jordan elimination as well as by Gaussian elimination are determined. The examples show in accordance with the theoretical results that the numerical solutions by the two methods are of comparable accuracy in spite of the ill-conditioning of the two problems. References 1. Schonauer, W. (1987) "Scientific computing on vector computers" Elsevier Science Publish B. V. North-Holland, Amstrdam,. 2. Stummel, F.(1986) "Strict optimal a posterior: error and residual bounds for Gaussian elimination in floating-point arithmetic". Computing, 37: 103-124. 3. Peters, G., and Wilkinson, J. H. (1975) "On the stability of Gauss- Jordan elimination with pivoting", Commun, ACM. 18: 20-24. 4. Stummel, F.,(1985)," Forward errors analysis of Gaussian elimination", Numer, Math. 46: 365-415. 5. Stummel, F.(1985),"FORTRAN-programs for the rounding error analysis of Gaussian elimination". Center for Mathematical Analysis, The Australian national University, Canberra, CMA,. P. 72-85. 6. Neumaier, A., (1990)," Interval Methods for systems of equations", Cambridge university press, Cambridge. 7. Lipschutz, Seymour, and Lipson, (2001) "Schaum's out-lines: Linear Algebra Tata McGraw-Hill edition", Delhi, 9: 568. 8. Stummel, F. (1986) "Strict optimal error and residual estimates for the solution of linear algebraic systems by elimination method in high-accuracy arithmetic", Proc., Symp. Accurate Scientific Computation, Bad Neuenahr 1985, Eds. W. L. Miranker, R. A. Toupin. Lecture Notes in computer scince , 235:119-141. 9. Gilbert, S. (2003),"Siam Introduction to linear algebra", 3rd edition, Wellesley, Massachusetts: wallesely-Cambridge press, Siam, Book Google, P. 74 - 76. 10. Fox, L. (1964)," An introduction to numerical linear algebra", Clarendon Press, Oxford., 11. Wilkinson, J. H. (1963),"Rounding errors in algebraic processes", Prenticel Hall, Englewood cliffs . 12. Stummel, F. (1986),"Strict optimal a posteriori error and residual bounds for Gaussian elimination in floating point arithmetic computing", 37: 103 – 124. 13. Moore, R. E. (1995),"The automatic analysis and control of error in digital computing based on the use of interval numbers, in error in digital computation" New York, 1: 30-61. Mathematics - 375 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 Table(1): condition numbers, stability constants and solution of the Jordan algorithm for triangular linear system (15). i iχ Diρ R iρ iw D iτ R iτ iΨ 1 0.413155 4639 7207 1.55 1.97 3343 1699 2 0.614928 5955 3313 0.56 1.00 3.20 3.19 3 -0.425517 5.13 4.56 0.89 0.99 2.28 2.28 4 0.613216 2.00 1.00 0.50 1.21 0.60 0.50 Table(2): condition numbers, stability constants and solution by back substitution of the triangular linear system (15). i iχ Diρ Riρ iw Diτ Riτ iΨ 1 0.413155 4639 5531 1.19 1.97 2.54 1.29 2 0.614928 5955 7100 1.19 1.00 1.19 1.19 3 -0.425517 5.13 4.56 0.89 0.99 1.28 1.28 4 0.613216 2.00 1.00 0.50 1.21 0.60 0.50 Table(3): condition numbers, stability constants and solution of the “Gauss –Jordan” algorithm for the linear system Ax=y. i iχ D iρ R iρ iw D iτ R iτ iΨ 1 1.65344 1.07 1.36 1.27 1.29 2.00 15.5 2 -2.31481 8.69 1.11 1.28 5.05 1.61 15.3 3 9.25926 7.33 9.38 1.28 8.90 1.32 14.8 4 -1.38889 6.34 8.13 1.28 7.72 1.12 14.5 5 6.94444 5.59 7.18 1.28 6.82 9.69 14.2 Table(4): condition numbers, stability constants and solution of “Gaussian elimination” of the linear system Ax=y. i iχ Diρ Riρ iw Diτ R iτ iΨ 1 1.65344 1.07 1.36 1.27 1.29 1.93 1.50 2 -2.31481 8.69 1.11 1.28 1.05 2.63 2.50 3 9.25926 7.33 9.38 1.28 8.90 2.47 2.77 4 -1.38889 6.34 8.13 1.28 7.72 2.21 2.86 5 6.94444 5.59 7.18 1.29 6.82 1.99 2.92 Mathematics - 376 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 مناقشة تحليل األخطاء لكاوس جوردن للحذف لمنظومة المعادالت الخطية شوقي عبد المطلب عباس جامعة بغداد ،كلية العلوم ، قسم الرياضيات 2012ايار 21 قبل البحث في: 2012كانون الثاني 22استلم البحث في: الخالصة جوردن ةوالبواقي للحلول التقريبية لألنظمة الخطية المثلثية بطريقيتعلق هذا البحث بالتمثيالت الصريحة لألخطاء للبيانات ةجوردن للحذف توصف على أنها دال –. أن حل المعادالت الجبرية الخطية بطريقه كاوس ةلعاماللحذف والطريقة األساسي المتصل باألخطاء ومن هذه التمثيالت تم اشتقاق الجزء ةوعمليات أخطاء التدوير لحساب الفارزة السائب ةالقلق وتحديد البواقي. ن تخمين االستقرار للحلول قد تم شرحه في هذا البحث. كما حددت قيود األخطاء للحلول ومقارنتها مع أفضل الحدود إ النتائج وبشكل مفصل ان الحلول الحذف لكاوس على التوالي. وتؤكد ةلألخطاء التي احتسبت بالتعويض المتراجع وطريق جوردن للحذف هي ليست أساسًا أعظم من األخطاء الكبيرة المحتملة بطريقه –كاوس ةبطريقتي جوردن للحذف وطريق النتائج النظرية بمثالين عددين. تالتعويض المتراجع والحذف لكاوس على التوالي. ولقد وضح جوردن للحذف. –كاوس ةيانات المضطربة، حدود األخطاء، طريقجوردن للحذف، الب ةطريق :ةالكلمات المفتاحي