Simultaneous Linear Algebraic Equations 4.1 INTRODUCTION Simultaneous linear algebraic equations are very common in various fields of Engineering and Science. We use matrix inversion method or Cramer’s rule to solve these equations in general. But these methods prove to be tedious when the system of equations contain a large number of unknowns. To solve such equations there are other numerical methods, which are particularly suited for computer operations. These are of two type: direct and iterative. Gauss elimination method, Gauss-Jordan method, Triangularisation method and Crout’s method are direct methods whereas Gauss—Jacobi method, Gauss-Seidel iterative method and Relaxation method are iferative methods. These methods are explained in the following sections. 4.2. GAUSS ELIMINATION METHOD In this method, the unknowns are eliminated successively by transforming the given system into an equivalent system with upper triangular coefficient matrix (ie. a matrix in which all the elements below the principal diagonal are zero) by means of elementary row operations, from which the unknowns are found by back substitution. Here, we shall explain it by considering a system of three equations in three unknowns. Consider the system axtby+tez=d, (4.14) a,xtbytc,z =d, (4.18) ax+by+c,z =, (G.le) Scanned with CamScanner4,2 Numerical Methods where x, », z are unknowns. The system in matrix form is AX= B, where a be x d, dela & G|x=[9] and B=] 4 ay by cy 2 dy Consider the argumented matrix [4|B] ab ald [aip]= 42: |r (4.2) a, by olds Now Eqn (4.2) is to be reduced to an upper triangular matrix. Let a, #0. Then R>R-2R [a 4 4/4 / a [0b elas 4, (43) ROR-ER Lo wy olds ql Here, a, iscalled the first pivot and b,’,¢,',d,,,',c,',d, aré transformed elements. Now take b,' as the pivot (6', #0). Then aw [th ala ROR-FR~| 0H olds as 0 0 clay E Now, if c," # 0, from Eqn (4.4), the given system of linear equations is equivalent toa,x+by+cz=d, by toyz az Using back substitution, z= qi 1 ton to" git. ’ ” = a bgey {ibd Os" — yd 0," + bye, dy" b, ,d,"} Scanned with CamScannerSimultaneous Linear Algebraic Equations 4.3, Note; 1. This method fails if any one of the pivots d, In such cases, pivots. if 1 b,!,0r¢,"" becomes zero. by interchanging the rows we can get the non-zero Partial pivoting: From the first column of Eqn (4.2) [called the pivot column if a, # 0, i= 1, 2, 3], select the component with the largest absolute value. This is called the pivot. Then at the second stage, i.e. from the second column of Eqn (4.3), select once again the component with the largest absolute value as the pivot. Continue this process. This procedure is called partial pivoting [refer to Example 1.1]. LR Complete pivoting: If we are not interested in the elimination of x, y, Z in a particular order, then we can choose at each stage the numerically largest coefficient of the entire coefficient matrix. This requires an interchange of equations and also an interchange of position of the variables, Example 4.1 Solve the system of equations 3x + y—z= 3, 2x-8y+z=-5, x—2y + 9z=8 using Gauss elimination method. ; (MU, B.E., 1992) 3 1 -I)fx] [3 Solution The given system is equivalent to|2_ -8 1 || y)=|-5 . 1-2 9flz 8 A X= B <. The argumented matrix is 3°41 -1/3 2-8 1/-5 [A\B] = Url 1-2 9/8 Now we will make A as upper triangular choosing ‘3’ as pivot, 301 -1/3 ~ laa 3 28 2B) 4 : 8 26 ‘Now choosing — 73 the pivot from the second column, Scanned with CamScanner44° Numetical Methods and so $B-yts}edp-14n-1 See yal Example 4.2. Solve the system of equations, 28x + 4y—2= 32, x + 3y + 102 = 24 and 2x + I7y + 42 = 35 by Gauss elimination method. (M.U, 1990,1992) Solution The given system is equivalent to 28 4 -I)[x] [32 1 3 10/|y|=/24 2 17 4||z} [3s 4 X=B- The argumented matrix is 28 4 1/32 [aj=|1 3 10/24 2°17 4/35 ‘Now we will make A as upper triangular choosing 28 as pivot. 2 4 = «-1 | 32 R BOR og | | 30 281 | 640 & 28 «28 | 28 BoBag |. 234 37 | ase 14 14 14 Scanned with CamScannerSimultaneous Linear Algebraic Equations 4.5 Now the pivot is Es 28 4° « -1 | 32 <. R(23) ~| 0 234 57 | 458 14 14 | 14 o 80 281 | 640 28 «428 | 28 2% 4 -1 | 32 20 23457 | 458 R, > R; -— RR, ~ a — b> Rh 4 14 | 14 30597 | 56560 1638 | 1638 From this, we get 28x + dy—2=32 2B4y+57z =458 and 305972 = 56560 Now by back substitution, we get 56560 27 5p5o7 7 18485472 — 57: y ae 5069778 c 3 and =n eee =0.9935941 Example 4.3 Using Gauss elimination method, solve the system 3.15 x- 1.96 y + 3.85 2.95 213 x+ 5.12 y-2.89 61 5.92x+3.05 y+ 2.15 z= 6.88 (M.K.U,1981) Scanned with CamScanner= 4.8 Numerical Methods Solution The given system is equivalent to 315 -196 385 |[x 12.95 213 512 -289})» -861 $92 305 2.15 }[z, 688 A X= B 31S -196 385 | 12.95 213 $12 -289 | -8.61 592 3.05 215 | 688 Now we will make A as upper triangular, choosing 3.15 as pivot 2 [A/B}= 31S -196 3.85 12.95 ~| 0 64453-54933] -17.3667 0 6.7335 -5.0855| -17.4578 Choosing 6.4453 as pivot 315 -196 385 | 1295 0 64453 -5.4933| —173667 0 0 0.6534 | 0.6853. From this, we get 3.15 x- 1.96 y+3.85z =12.95 6.4453 y— 5.4933 z =~ 17.3667 0.6534 z = 0.6853 By back substitution 0.6853 06534 = 1.0488215 5.49332 — 173667 ass ~~ 18005692 196y - 3852 +1295 . and 22. LO, 315 Example 4.4 Solve the system of equations, x, +x, +x, +%,=2, x, +2, + 3x,-2x,=-6 2x, +3x,-x,+2x,=7, x, 42x, +x,-x,5-2 by Gauss elimination method. (MU, BE, 1986) Scanned with CamScannerSimultaneous Linear Algebraic Equations 4.7 Solution The given system in matrix form is | ryt 1] [x 2 1103-2] |x, -6 23-1 2] Ja} 717 12 1 1) by -2. A xX = B The argumented matrix [4|B] is Pilot a2 11 3 -2|-6 [iB]=|2 3.-1 2] 7 12 1 -1|-2 Choose 1 of first column as pivot. Then ’ BBB 4 a ols ROR-M~\) 1 5 | 5 R,>R-R 01 0 -2|-4 Since the element in 2nd row, 2nd column is zero, interchange 2nd and 3rd rows to get pivot element 1. That is, +4 0 RQ3)~ |o 0 RRR ~ Now the pivot is 2, therefore, ROR -5 i 1 jf 1-3 0} 3 o 2 -3|-8 1 0 -2|-4 11 1| 2 01-3 0/3 00 2 -3\-8 00 3 -2|-7 rid to 01-3 0|3 00 2 -3{- v0 ot Ss 215 Scanned with CamScanner4.8 Numerical Methods From this we get, x, +x, 43,42, @ x,- 3x (0) 2x, -3x,=-8 (ity (3) 422 (vy 2 Now, from Eqn (iv), x,=2 from Eqn (iii), 1 1 %= 78+ 3x) 78 +6)=-1 from Eqn (ii), x,=3+3x,=3-3=0 and from Eqn (i), x,=2-x,-3,-2,=2-0-(1)-2=1 2.x, = 1x, =0,x,=-1,x,=2 4.3 GAUSS-JORDAN METHOD This method is a modified form of Gauss elimination method. In this method, the coefficient matrix A of AX= Bis reduced toa diagonal matrix or unit matrix by making all the elements above and below to the principal diagonal of 4 aseero, The labour of back substitution is saved here even though it involves additional computations. Example 4.5 Solve the equations 1Ox-++y+2=12, 2x+ 10y+z= 13 and x+y+52=7 by Gauss-Jordan method. (MU, 1991) Solution The given system in matrix form is 10 1 I}fx] fiz 2 10 1}/y} f13 11 site} [7 A X =B 10 1 ayia sfapy-|2 10 1/13 1 i s|9, Scanned with CamScannerSimultaneous Linear Algebraic Equations 4.9 : 1-8 -44)-s1 RR-9~]2 10 1 4 13 11 os|7 R>R-2R |) ~8 ~44/-51 Rokk |? 26 89 | 115 9 49 | 58 1-8 -44|-sr R,>-(R,-3R))~]0 1 58] 59 0 9 49] 58 i 1 ROR sR, 0 420] 421 Ror, 7|2 1 8] 9 ae 0 0 -473| -473 RR, b>-FeR flo 0/1 R,-> R,-420R,~]0 1 0 |1 R>R-58R, [0 0 141 The system AX = B reduces to the form x T yl=|1 z} ie, x=y=z=1 Example 4.6 Solve the equations 10x, +x, +x, = 12, x, + 10x,—x, = 10 and x, —2x, + 10x, =9 by Gauss—Jordan method. (M.U. 1997) Solution The matrix form of the given systems is 10 1 1] fx 12 1 10 ~1} x] _ ]10 1-2 10] [x5 9 A xX = B Scanned with CamScanner4.10 Numerical Methods 10 1 1 [iz : [1 10 -1)10 : WAl=) 2 wl 9 oc 1-89 10 -78 ROR-9R~{1 10 -1 10 1-2 10 9 1-89 10|-78 RBOR-R _|y 99 -11| 88 BORK ly g7 0 | 87 Ro% 1-89 10|-78 9~10 9 -1| 8 Roe lo 1 of 4 eae, 1-89 ‘10|-78 R,>R,-8R,~|0 1 -1} 0 0 1 0 1 10 -79|- RIRBR [yy a Re BOR oo 144 R>R+TOR, i 7 R, +R; BoOmt® clove 1 (1 :. The system AX= B reduces to 1 J, eralal | 001 1 Scanned with CamScannerSimultaneous Linear Algebraic Equations 4.11. * Example 4.7 Solve the following equations by Gauss—Jordan method. xt 2ytz-w=-2; Det 3y-242w=7 xty+32-2w=-6; xtytetw=2 (MU, BE, 1986) Solution The given system in matrix form is 12 1 -1) [x ~2 23-1 2] Ty 7 11 3 -2/ Jz} = |-6 i111} lw 2 A xX =B The argumented matrix is iar) -2 23, 7 [4iz}=}1 1 -6 Nee eet | al 12 1 =1}-2 Ro > (R-2R) lo 1 3-4] a1 Ro BOR lo =i 2, =1\-4 Ro > RR 0-10 2/4 : 10-5 7] 20 a+ nee 01 ~4|-1h Ro > RtR)~lq 90 1 -1]-3 Ro > RR 00 3 -2|-7 100 2/5 Ro > RR [9 1 0 -1|-2 r R > R-3R~lo 9 1 -1/-3 Ro > R-3R lo o-o- 1] 2 100 0/1 Ro > R-2R 19 1 0 of 0 Ro RtR~lo 0 1 ol-1 R > Bt |g 0 0 1] 2 Scanned with CamScanner* 4.12 Numerical Methods ©. The system AX'= B reduces to the form 00 oom coro ZN 00 10 0 ot ie. x= 1,y=0,2=-1 and w=2. 4.4 INVERSE OF A MATRIX USING G: ELIMINATION METHOD iAUSS Let A be a square matrix of order 3, [4] # 0 and X be its inverse. Then we: know that AX = 1, where /is a unit matrix of order 3. a 42 3 xu S1fA=|a ap ayy| and X= |%n As, G3 O33, 31 then ay A. Ay 1% As 1 ay Ay Ay %y Xn Ay] = 0 Gy, 432 33 Xs X32 %33 ‘This equation is equivalent to the three equations given below MM 43] |X 1 Gy “Gy x) || _ {0 Gy Ay 3 | | 3, 4% A M3] | Xr 0 4 4 %3|\%n| - |! 4 Ax. 33 | | %32. 9 4 A M3 | | Ms 0 Gy Ay Ay | |X| _ 10 Gy G32 33 | L%33, 1 Scanned with CamScanner 2 3 % %s Xy X33. 00 1 0 (4.5) ae de | (4.6) a? (4.8)‘Simultaneous Linear Algebraic Equations 4.43 Sixth approximation 1 To [7.74 -2.5195473 + 2(2.7646912)] = 1.0749835 1 =D [39.66 — 1.0781704 — 3(2.7646912)] = 2.5239797 1 3, zg [54.8 ~ 3(1.0781704) + 4(2,5195473)] = 2.76582 Seventh approximation 1 = = 10 [7.74 —2,5239797 + 2(2.76582)] = 1.074766 1 nF [39.66 — 1.0749835 — 3(2.76582)] = 2.523963 1 is [54.8 — 3(1.0749835) + 4(2.5239797)] = 2.7652754 :. From the sixth and seventh approximations x= 1.075, y= 2.524 and z= 2.765 correct to three decimals. 4.10 GAUSS-SEIDEL ITERATION METHOD ‘This is a modification of Gauss—Jacobi method. As before, the system of the linear equations . ajxtbytoz=d, a,x+b,y+¢,2= 4, axtbytoz=d, is written as 1 = 7 @-by-c7) (421a) 1 y= 5 Gn ax-e2) (4.21b) 1 27 5 (ax by) (4.210) Scanned with CamScanner4.44 Numerical Methods and we start with the initial approximation x, Yor Zor Substituting y, and z, in Eqn (4.21a), we get in Eqn (4.216), we get Now substituting x=, 7= 2, 1 5, G- am F) Substituting x =.x,, y= ),, in Eqn (4.21c), we get 1 He Gan ~by) This process is continued till the values of x, yz are obtained to the desired degree of accuracy. The general algorithm is as follows: Ifx, yp z, are the Ath iterates, then 1 Fas GU by- C8) G,-a%,4- 62) 1 a Fann = G5 a Ahan — PY) Since the current values of the unknowns at each stage of iteration are used in proceeding to the next stage of iteration, this method is more rapid in convergence than Gauss-Jacobi method. . : The rate of convergence of Gauss-Seidel method is roughly twice that of Gauss—Jacobi and the condition of convergence is same as we saw earlier in Section 4.8. Note: Gauss-Seidel iteration method converges only for special systems of equations. In general, the round of errors will be small in iteration methods. Moreover, these are self-correcting methods; that is, any error made in computation will be corrected in the subsequent iteration. Example 4.18 Solve the equations given in Example 4.9 by Gauss-Seidel iteration method. (B.U, B.E., 1994) Scanned with CamScanner‘Simultaneous Linear Algebraic Equations 4.45 Sottion From the given equations, we have 1 4g 20 + 3y—22) @ 1 * Y= 77G3- 4x42) Gi) ze FO5-6r-3) Gi) Putting y = 0, z= 0 in RHS of (i), we get x= 2 =25 Putting x= 2.5, 2= 0 in RHS of (ii), we get 1 a1 [33 — 4(2.5)] = 2.0909091 Putting x = 2.5, y= 2.0909091 in RHS of (iii), we get 1 D [35 - 6(2.5) — 3(2.0909091)] = 1.1439394 For the second approximation, (20+3y,-22,] - x= [ 20 + 3(2.0909091) - 2(1.1439394)] = 2.9981061 iL. 8 at a8 1 Y= 77 B34 tal = ao3 —4(2.9981061) + 11439394] = 2.0137741 : 3 2= j B5- 6-39 = $ [35 — 6(2.9981061)— 3(2.0137741)] = 0.9141701 Third approximation: xo ; [20 + 3(2.0137741) — 2(0.9141701)] = 3.0266228 Scanned with CamScanner4.48 Numerical Methods Ys ia 4(3.0266228) + 0.9141701)] = 1.9825163 5 [35 — 6(3.0266228) — 3(1 .9825163)] = 0.9077262 Fourth approximation: x= : [20 + 3(1.9825163) — 2(0.9077262)] = 3.0165121 | = 4(3.0165121) + 0.9077262)] = 1.9856071 y= =D +135 — 6(3.0165121)— 3(1.9856071)] = 0.9120088 Fifth vine ae Bot [20 + 3(1.9856071) — 2(0.9120088)] = 3.0166005 ye [33 — 4(3.0166005) + 0.9120088] = 1.9859643 $ [35 - 6(3.0166005) - 3(1.9859643)] = 0.9118753 Sixth approximation: = + 20 +3(1.9859643) --2(0.9118753)] =3.0167678 cn 1 = 7 B3- 4(3.0167678) + 0.9118753] = 1.9858913 1 nD [35 — 6(3.0167678) — 3(1.9858913)] = 0.9118099 Seventh approximation: 1 4B [20 + 3(1.9858913) — 2(0.9118099)} = 3.0167568 1 WT [33 — 4(3.0167568) + 0.9118099] = 1.9858894 z= pOs- 6(3.0167568) — 3(1.9858894)] = 0.9118159 Scanned with CamScanner‘Simultaneous Linear Algebraic Equations 4.47 Since at the sixth and seventh approximations, the values of x, y, z are the same, correct to four decimal places, we can stop the iteration process. 2. ¥= 3.0167, y= 1.9858, z= 0.9118 We find that 12 iterations are necessary in Gauss—Jacobi method to get the same accuracy as achieved by 7 iterations in Gauss-Seidel method. Example 4.19 Solve by Gauss-Seidel method, the following system of equations 28x + 4y—2=32, x+3y+ 10z=24, and 2x + 17y + 4z= 35 - (B.U, 1997, M.U, 1991) Solution The coefficient matrix of the given system is not diagonally dominant. Hence, we rearrange the equations as follows, such that the elements in the coefficient matrix are diagonally dominant. 28x+4y—z =32 2x + Wy + 4z= 35 xt+3y+10z =24 Hence we can apply Gauss-Seidal iteration method. From the above equations x Fo2-a+4 @ = #035 —2x-4z] Gi 22 4-2-3] Gi) First approximation Putting y=z=0 in (i), we get 1 =~+62)-1. 1 ¥,= 5g0@2)~ 1.142857 Putting x = 1.1428571, z= 0 in (ii), we get x7 $ [35 —2(1.1428571)] = 1.9243697 Putting x= 1.1428571, y= 1.9243697 in (iii), we get z= + [24 —1.1428571 - 3(1.9243697)] = 1.7084034 Scanned with CamScanner- 4.48 Numerical Methods Second approximation 4 x [32 — 4(1.9243697) + 1.7084034] = 0.9289615 1 a AW TF [35 -2(0.9289615) — 4(1.7084034)] = 1.5475567 = [24 - 0.9289615 — 3(1.5475567)] = 1.8428368 Third approximation x= l2- 4(1.5475567) + 1.8428368] = 0.9875932 =o +135 — 2(0.9875932) — 4(1.8428368)] = 1.5090274 A=— i 24 0.9875932— 3(1.5090274)] = 1.8485325 Fourth Fie i x= #2- 4(1.5090274) + 1.8485325] = 0.933008 Ye = [35 -2(0.9933008)] = 4(1.8485325)] = 1.5070158 1 2,7 79 [24- 0.993308 — 3(1.5070158)] = 1.8485652 Fifth approximation 1 B [32 - 4(1.5070158) + 1 -8485652] = 0.9935893 1 7 [35 —2(0.9935893) — 4(1 -8485652)] = 1.5069741 z= apt 0.9935893 — 3(1.5069741)] = 1.848548 Sixth approximation 1 = pg (32-4(1.5069741) + 1.8485488] = 0,9935947 28 1 1 Ys= 77 135 -2(0.9935947) — 4(1.8485488)] = 1.5069774 Scanned with CamScanner‘Simultaneous Linear Algebraic Equations 4.49 1 = 19 [24 - 0.9935947 —3(1.: 5069774)] = 1.8485473 . the values of x, y, z in the fourth and fifth iteration ave same ‘upto four pate we stop the process here. Hence x = 0.9936, y= 1.5069, z= 1.8485 Example 4.20 Using Gauss-Seidel iteration method, solve the system of equations. 10x - 2y—2—w=3;-2e+ 10y-2-w= 15; —x-y + 10z—2w=27;-x-y-2z +10w=-9 (MU, BE., 1987) ‘Solution ead ce ere a Hence we can apply Gauss-Seidel iteration method. From the given equations, we can write x= Ep tates) @ i y= Bs +2e+ 240] Gi) eo hprexty+2u] Gi) pietety +2 (iv) First approximation: 3 Putting y= z= w= 0on RHS of (), we get x, = 75 = 0.3 Putting x= 0.3, z= w= 0 on RHS of (ii), 1 we get y, = 75 [15 +2(0.3)] = 1.56 Putting x= 0.3, y= 1.56, w= 0 on RHS of (iii), we get z, = x [27+ 0.3 + 1.56] = 2.886 Putting x= 0.3, y= 1.56, 2= 2.886 on RHS of (iv), we get w, = a [-9 + 0.3 + 1.56 + 2(2.886)] =-0.1368 Scanned with CamScanner4.50 Numerical Methods Second approximation: x, = ee +2(1,56) + 2.886 — 0.1368] = 0.88692 1 e Ya = Fg [15 +2(0.88692) + 2.886 — 0.1368] = 1.952304 z = [27 +0.88692 + 1.952304 + 2(-0.1368] = 2.9565624 w= + [-9 +0.88692 + 1.952304 + 2(2.9565624)] = ~0.0247651 Third approximation: x, = a [3 + 2(1.952304) + 2.9565624 — 0.0247651] = 0.9836405 y= a [15 +2(0.9836405) + 2,9565624 — 0.024765 1] = 1.989087 = x [27 +0.9836405 + 1.9899087 + 2(-0.0247651)] = 2.924019 wy, a [-9 +0.983405 + 19899087 + 2(2.9924019)] =-0.0041647 Fourth approximation: 1 X= Ig [3 + 2(1.9899087) + 2.9924019 — 0.0041647] = 0.9968054 1 a= FQ [15 +2(0.9968054) + 2,9924019 — 0,0041647] = 1.981848 1 419 [27 +0.9968054 + 1.9981848 + 2(-0.0041647)] = 2.986661 1 = 79 [-9 +0.9968054 + 1.9981848 + 2(2.9986661)] =-0.0007677 Fifth approximation: ' 1 = 19 [3 + 2(1.9981848) + 2.986661 — 0.0007677] = 0.9994268 1 w= 79 [15 +2(0.9994268) + 2.998666 — 0.0007677] = 1.996752 Scanned with CamScannerSimultaneous Linear Algebraic Equations 4.51 1 25> 19 [27 +0.9994268 + 1.996752 + 2(-0.0007677)] = 2.997567 1 Ws= 79 [-9 +0,9994268 + 1.9996752 + 2(2.9997567)] = -0.0001384 Sixth approximation: 1 %s= 19 [3 + 2(1.9996752) + 2.9997567 — 0.0001384] = 0.9998968 1 Y= 79 [15 +2(0,9998968) + 2.9997567 — 0.001384] = 1.9999412 1 25> 10 [27 +0.9998968 + 1.9999412 + 2(-0.0001384)] = 2.999561 1 W,= 7 E-9 +0.9998968 + 1.999412 + 2(2.9999561)] =-0.0002498 ” Seventh approximation: : 1 4= 79 [3 + 2(1.99994 12) + 2.9999561 — 0.0002498] = 0.9999588 Y= rf [15 +2(0.9999588) + 2.9999561 — 0.0002498] = 1.9999624 a o [27 +0.9999588 + 1.9999264 + 2(-0.0002498)] = 2.9999422 w= a [-9 +0.9999588 + 1.9999624 + 2(2.9999422)] =—0.0001945 ‘Now, from sixth and seventh approximations the values of x, y, z and w correct to four decimal places are x= 0.9999 y= 1.9999 z= 2.9999 w= 0.0002 4.11 RELAXATION METHOD Consider the equations ax+bytoz=d, ax+by+o,2=d, a,x+ byt cz=d, Scanned with CamScanner