2.2 BISECTION METHOD This method is based on Theorem 1.1 which states that if a function f(x) is, continuous between a and 5, and f(a) and (6) are of opposite signs, then there exists at least one root between a and 6, For definiteness, let f(a) be negative and f(b) be positive. Then the root lies between a and b and Iet its approximate value be given by xo = (a+ 6/2. If f(x) = 0, we conclude that xo is a root of the equation f(x) = 0, Otherwise, the root lies either between xp and 6, or between x and a depending on whether f(x) is negative or positive. We designate this new interval as [4, 61] whose length is jh — al/2. As before, this, is bisected at x and the new interval will be exactly half the length of the previous one, We repeat this process until the latest interval (Which contains the root) is as small as desired, say €. It is clear that the interval width is reduced by a factor of one-half at each step and at the end of the nth step, the new interval will be [a,. b,] of length [b— a2”, We then have |b- tee, a which gives on simplification log, ((b-ai/e) te 82 (23) Equation (2.3) gives the number of iterations required to achieve an accuracy ©. For example, if |b ~ a| = 1 and € = 0.001, then it can be seen that n>10 (2.4)‘The method is shown graphically in Fig, 2.1. [0.6] fa flay) Figure 2.1 Graphical representation of the bisection method. It should be noted that this method always succeeds. If there are more roots than one in the interval, bisection method finds one of the roots. It can be easily programmed using the following computational steps: 1. Choose two real numbers a and b such that f(a) f(b) < 0. Sel x, = (a + BY2. 3. (a) If fa) flr) < 0, the root lies in the interval (a, x). Then, set x, and go to step 2 above. (b) IF f(a) flx,) > 0, the root lies in the interval (x,, 4). Then, set a= x, and goto step 2. (©) IF f(a) flx,) = 0, it means that x, is a root of the equation Pee) = 0 and the computation may be terminated. In practical problems. the roots may not be exact so that condition (c) above is never satisfied. In such a case, we need to adopt a criterion for deciding when to terminate the computations. ‘A convenient criterion is to compute the percentag, error é, defined by 100%. @5) where x, is the new value of x,. The computations can be terminated when é, becomes less than a prescribed tolerance, say f. In addition, the maximum number of iterations may also be specified in advance. Example 2.1 Find a real root of the equation f(x) = 8 -x-1= 0. Since /(1) is negative and f(2) positive, a root lies between 1 and 2 and, therefore, we take xp = 3/2, Then Which is positive,Secniow ection Method 25 Hence the root lies between | and 1.5 and we obtain 141s a= 1.25 2 We find f(xy) = -19/64, which is negative. We, therefore, conclude that the root lies between 1.25 and 1.5. If follows that _ 125418 “2 ‘The procedure is repeated and the successive approximations are 34375, xy = 1.328125, ete. 0. 375 wy xy = 13125, y= Example 2.2 Find a real root of the equation x? — 2x — Let f(x) = 8 — 2x — 5. Then FQ)=-1 and (3) = 16. Hence a root lies between 2 and 3 and we take Since (x1) = f(2.5) = 5.62: Hence 2.25 Now, f(x2) = 1.890625, the root lies between 2 and 2.25. Therefore, 242.25 == =2005 Since f(x3) = 0.3457, the root lies between 2 and 2.125. ‘Therefore, 2242125 99635 xs Proceeding in this way, we obtain the successive approximations: Xs = 2.09375, xy = 2.10938, x7 = 2.10156, 19766, xy = 2.09570, xy = 2.09473, 9424, 0.0005, x= x0 09 = 2.0005 2.09424 x 100= 0.02% Hence a root, correct to three decimal places, is 2.094.Example 2.3 Find a real root of f(x) = x8 + 2 + x +7 = 0 correct to three decimal places. ‘The given equation is a cubic and the last term is positive. Hence, 0 will have a negative real root. We find that SN) = 6 f(-2)= 1 and f(-3) ‘Therefore, a real root lies between —3 and We take Se Now f(t) = -1.5781, and, therefore, the root lies between —2 and It follows that Successive approximations are given by xy = 2.0625, x5 = -2.0938, xy = 2.1016, 1055, xy = 21085, x = -2.1050, The difference between xyo and x}, is 0.0005, Hence, we conclude that the root is given by x = -2.105, correct to three decimal places. Exanpte 2.4 Find the positive root, between O and 1, of the equation x= e" toa tolerance of 0.05%. Let Ux) = xe" 1, which is positive. Hence, a root exists We have, f(0) = -1 and f(1) between 0 and 1, and ost 2 Because, f(x1) = ~ 0.1756, the root lies between 0.5 and 1.0. ThenNow, the tolerance ¢; is given by peel x100 % = 253 x 100= 33.33% ors «1 13.33% ).5878, the root lies between 0.5 and 0.75. ae y= 254275 _ p60 also, Proceeding in this way, successive approximations and tolerances are obtained: xy = 0.5625, &) = H111%; xs = 0.5938, S781, & = 2.71%; xy = 0.5703, 0.5664, &, = 0.69% Xo = 0.5684, 5674, & = 0.18%; 05671, &) = 0.035% Since &, = 0.035% < 0.05%, the required root is 0.567, correct to three decimal places. 0.5669, Example 2.5 Find a root, correct to three decimal places and lying between 0 and 0.5, of the equation 4e™ sin x — Let fe) = 4e* sin x = 1 We have f(0) = -1 and f(0.5) ).163145 Therefore, x = 0.25 Since (0.25) = — 0.22929, it follows that the root lies between 0.25 and 0.5. Therefore, 0.75 wget a0375 ‘The successive approximations are given by 4) = 03125, x4 = 0.3438, xs = 0.3504, Xe = 0.3672, x7 = 0.3711, xy = 0.3602, Xy = 0.3702, yy = 0.3706, xy, = 0.3704 0.3705, Hence the required root is 0.371, correct to three decimal places. w24 ITERATION METHOD We have so far discussed root-finding methods which require an interval in which the root lies. We naw describe methods which require one or more approximate values to start the solution and these values need not necessarily bracket the root. The first is the #feration method which requires one starting value of x. ‘To describe this method for finding a root af the equation I(x) = 0, 1) wwe rewrite this equation in the form x= (x) There sre many ways of doing this. For example, the equation +e 280 8) can be expressed in different forms ref after, 120-2)! ,ere l+x Now, let xy be an approximate root of Eq, (2.8). Then, substituting in Eq. (2.8), we get the first approximation as ae Successive substitutions give the approximations =O OGY tn = OC).32___ Charmer 2: Solution of Algebr and Transcendental Equations The preceding sequence may not converge to a definite number. But if the ‘sequence converges to a definite number é, then will be a root of the equation x = 9(x). To show this, let Smt = O68) 29) be the relation between the nth and (n + 1)th approximations. As increases, qui = § and if 6 (x) is a continuous function, then 9 (x,) —> 6(é). Hence, in the limit, we obtain §= 0@, (2.10) which shows that & is a root of the equation x = 6 (x). To establish the condition of convergence of Eq. (2.8), we proceed in the following way: From Eq, (2.9), we have x= 900) any From Eqs. (2.10) and (2.11), we get Em = 96) $4) =E-m)9'G) w [eae Spa pla seal og "hx 291 we = which shows that the convergence would be faster for smaller values of k. Now, let € be the specified accuracy so that |E-mlse Then, Eq. (2.20) gives x which can be used to find the difference between two successive approxima- tions (or iterations) to achieve a prescribed accuracy. Example 2.10 Find a real root of the equation x° = with an accuracy of 10°, We rewrite the equation as =? on the interval [0, 1] i) Here Therefore, Also,34 Carter 2: Solution of Algebraic and Transcendental Equat Therefore, Eq. (2.21) gives Taking xq = 0.75, we find 1 =e = 0.7558: SO im spon 275593 a a 3° YV75865 Now, |x5 — xz] = 0.00028 < 0.0004, Hence, the required root is 0.7549, correct to four decimal places. = 0.75465, = 0.75493, Example 2.11 Find a teal root, correct to three decimal places, of the equation 2x -3 = cos x ik ‘ 38 ya teat [3.5] We rewrite the given equation as Flot) Here vege di an leah alet.in[ 3.3} Choosing x = 1.5, we obtain successively: = $l60s15+3)=1.5354 n = F(oos 1,5384+3)=1.5177, a = Fleos 15177 +3)=1.5265, 521, ty = Hoos 1526543) seoHeotaaiy aise,= F(cos1 5243.43) =1.5252, 1 3 =5(608 1.52324 3) = 1.5238. 2 Now, [x7—16| = 0.0006 < 0.001. Hence, the root, correct to three decimal places is 1.524. ration to find a positive root of the ss between 0 and 1 Example 2.12 Use the method o ‘equation xe* = 1, given that a root Writing the equation in the form ‘we find that o@ ‘Therefore, [v@1<1 Choosing xo = 0.5, we find ay = & = 0.60653, x = 054524, 45 = 0.57970, x4 = 0.56007, xs = O.S7117, 0.56486, x7 = 0.56844, 0.S6641, Xp = 0.56756, Xp = 0.56691, xy = 0.56728, 0.56706, xis = 0.56719, 0.56712, xis = 0.56716, 0.56713, xi = 0.56715, 0.56714, ip = 0.56714, It follows that the root, correct to four decimal places, is 0.5671 Example 2.13 Use the iterative method to find a real root of the equation sin. x = 10(¢ — 1). Give your answer correct to three decimal places. Let FG) = sin x — 10 + 10 We find, ftom praph, that a root lies between 1 and x (The student is, advised to draw the graphs). Rewriting the equation as we have and36___Citarte 2: Solution of Algebraic and Transcendental Equations Taking xp = 1, we obtain the successive iterates as: Hence the required root is 1.089.4.1.4 Newton-Raphson Method ‘This method is also called Newton's method. This method is also a chord method in which we approximate the curve near a root, by a straight line. Let xo be an initial approximation to the root 0. Then, Pixy. fo), where f, = fx), is a point on the curve. Draw the tangent to the curve at P, (Fig. 1.8). We approximate the curve in the neighborhood of the root by the tangent to the curve at the point P. The point of intersection of the tangent with the x-axis is taken as the next approximation to the root. The process is repeated until the required accuracy is ro obtained.)'The equation of the-tangent to,the curve "#62 :Nenton-flephaon method y= fx) at the point P(x,, fa) is given by = tg) = x5) fe) where (x9) is the slope of the tangent to the curve at P. Setting y = 0 and solving for x, we get L0) pay eo 7G) ‘The next approximation to the root is given by lx) py B= fay Fix) #0. We repeat the procedure. The iteration method is defined as Flay) py Xp = hen Peay’ Fe) 40. (a.14) ‘This method is called the Newton-Raphson method or simply the Newton's method. ‘The method is also called the tangent method. Alternate derivation of the method Let x, be an approximation to the root of the equation fix) = 0. Let Ax be an increment in x such that x, + Ar is the exact root, that is flxy + Ax)12 NUMERICAL METHODS. Expanding in Taylor's series about the point x,, we get (ax)? flay) + Bx fle) + Gp Fe) + 0. (1.15) Neglecting the second and higher powers of Ax, we obtain fig) + Ae f';) «0, or ar=— A) fap Hence, we obtain the iteration method f(xy) " Sar te tema, — Fes PE )40, b= 0,1, which is same as the method derived earlier. Remark 7 Convergence of the Newton's method depends on the initial approximation to the root. If the approximation is far away from the exact root, the method diverges (see Example 1.6). However, ifa root lies in a small interval (a, 6) and x9¢ (a, b), then the method converges. Remark 8 From Eq.(1.14), we observe that the method may fail when f’(x) is close to zero in the neighborhood of the root. Later, in this section, we shall give the condition for convergence of the method. ‘Remark 9 The computational cost of the method is one evaluation of the funetion fix) and one evaluation af the derivative f"(e), for each iteration. Example 1.6 Derive the Newton's method for finding 1/N, where N > 0. Hence, find W117, using the initial approximation as (i) 0.05, (ii) 0.15. Do the iterations converge ? Solution Letx= +, or 2 =N. Define Ax)= 2 —N. Then, fra)=— + N x x x* ‘Newton's method gives (xy) (/y)-N) Sea 2%e— fay mage aa =x, + bx, — Naz] = 2c, — Nx? @ With N= 17, and x, = 0.05, we obtain the sequence of approximations 1 = Qty — Nxj = 2(0.05) — 170.05) = 0.0575. 2, = 2x, — Nx? = 2(0.0575) — 17(0.0575)? = 0.058794. 4 = 2x, — Nx} = 2(0.058794) — 17(0.058794)? = 0.058823. x, = 2ty— Nx} = 2(0.058823) — 17(0.058823)? = 0.058823. Since, | x,—.x, | = 0, the iterations converge to the root. The required root is 0.058823. (éi) With N= 17, and xy = 0.15, we obtain the sequence of approximations 2xq— NxZ = 20.15) - 17(0.15)? = - 0.0825. xSOLUTION OF EQUATIONS AND EIGEN VALUE PROBLEMS 13 -— Nx} = 2(— 0.0825) — 17(— 0.8025) = — 0.280706. x)= Qty — Naz xy 2(— 0.280706) — 17(— 0.280706)? = — 1.900942. “4 = 2ty— Nex} = 2(— 1.900942) ~ 17(— 1.900942)? = - 65.23275. We find that x, — — © as k increases. Therefore, the iterations diverge very fast. Thi shows the importance of choosing a proper initial approximation. Example 1.7 Derive the Newton's method for finding the qth root of a positive number N, N™, where N > 0, q > 0. Hence, compute 17 correct to four decimal places, assuming the initial approximation as x, Solution Let x=N%, or x7 =N. Define flx) = x7 N. Then, f') = qx? ‘Newton's method gives the iteration N_qtf-2{4+N _G@-Dxf+N ap aft at For computing 1738, we have q = 3 and N = 17. Hence, the method becomes ae =e 3 Syn a b=0,1,2, With x, = 2, we obtain the following results. 2xh +17 _ 28)417 3x3 4) = 2.75, Det +17 _ 202.75) +17 m= She Tea7ay? — * 2582645, 2x} +17 _ 2(2.582645)* +17 = ger geo pened)? = 2971852, 2x3 +17 _ 212.571992) +17 y= 2a So erggnt = 2571282. ax} Now, [xq —x5 | = | 2.671282 — 2.571882 | = 0.00005. ‘We may take x = 2.571282 as the required root correct to four decimal places. Example L8 Perform four iterations of the Newton's method to find the smallest positive root of the equation fix) = x5 - 5x +1=0. Solution We have f(0) = 1, f(1) =—8. Since, (0) f(1) < 0, the smallest positive root lies in the interval (0, 1). Applying the Newton's method, we obtain xp-5x,+1_ 2xf-1 Sxf-5 = af -5 + k=0,1,2,.. Xu =%14 NUMERICAL METHODS Let xy = 0.5. We have the following results. Qxp-1_ 2(0.5)9-1 3x -5 300.5)" -5 176471, 2x} -1_ 2(0.176471)° -1 = .201568, Bxp-5 3(0.17647D" -5 2(0.201568)* ‘Therefore, the root correct to six decimal places is x ~ 0.201640. Example 1.9 Using Newton-Raphson method solve x logy x = 12.34 with x, = 10. (A.U. Apr/ May 2004) Solution Define flx) = x logy x ~ 12.34 , 1 ‘Then 1G) = logy + 7575 = lobo x + 0.494204. Using the Newton-Raphson method, we obtain xp logig x, 1234 Togo x, + 0484294" Raa 1, 2, With x, (0, we obtain the following results. ay log yg xp - 12.34 10 logo 10 - 12.34 — ee a = 1.631465. Togo x9 + 0.484294 Toga 10+ 0.434294 2; log yp *1 ~ 12.34 Togo 2 + 0.484294 = 11,631465 — 11-931465 logo 11.631465~12.34 _ 1) so4a79, Togo 11.631465 + 0.434294 Xp log yo Xp - 12.34 Tog yy %2 + 0.434294 11.59487 log yo 11.59487- 12.34 _ 1) soagsy Togo 1.59487 + 0.434294 We have | x, ~ x, | =| 11.594854 ~ 11.594870 | = 0.000016. ‘We may take x = 11.594854 as the root correct to four decimal places.1.1.3 Méthod of False Position od is also called linear interpolation method or chord method or regula-falsi method. At the start of all iterations of the method, we require the interval in which the root lies. Let the root of the equation /(x) = 0, lie in the interval (x,_,, x,), that is, f,_, f, < 0, where Roxy.) = fer» and fly) = fy. Then, Plays, fy-s)s Oxy, fy) are points on the curve fix) = 0. Draw a straight line joining the points P and Q (Figs. 1.2a, b). The line PQ is taken as an approxima- tion of the curve in the interval [x,_,, x,]. The equation of the line PQ is given by = OE fant Teams ‘The point of intersection of this line PQ with the x-axis is taken as the next approxima- tion to the root. Setting y = 0, and solving for x, we get Reanme) py (termes) y aye * (ae) ‘The next approximation to the root is taken as Fae = p> (foe ss a 10) Simplifying, we can also write the approximation as h=1,%.. (LID ‘Therefore, starting with the initial interval (xg, x,), in which the root lies, we compute toh = nfo f-f Now, if flx,) lt.) < 0, then the root lies in the interval (x, x,). Otherwise, the root lies in the interval (x,, x,). The iteration is continued using the interval in which the root lies, until the required accuracy criterion given in Eq.(1.8) or Eq.(1.9) is satisfied. Alternate derivation of the method Let the root of the equation flx) = 0, lie in the interval (x,y, x,)- Then, Plxy yy fy. Qty fy) are points on the curve ix) = 0. Draw the chord joining the points P and @ (Figs. 1.2a, b). WeSOLUTION OF EQUATIONS AND EIGEN VALUE PROBLEMS 7 approximate the curve in this interval by the chord, thatis, flx) ~ ax +b. The next approximation to the root is given by x = — b/a. Since the chord passes through the points P and Q, we get fox 2% 440, and f,zax, +d. Subtracting the two equations, we get fa-fir fa —fix=aly—x_y) oF a= : h — fi eae iam ‘The second equation gives b = f, - ax,. Hence, the next approximation is given by Fig. 1.2a ‘Method of false position’ —_—_—Fig, 1.2b ‘Method of false position’ Romark 3 At the start of each iteration, the required root lies in an interval, whose length is decreasing. Hence, the method always converges. Remark 4 The method of false position has a disadvantage. If the root lies initially in the interval (xq, x,), then one of the end points is fixed for all iterations. For example, in Fig.1.2a, the left end point x, is fixed and the right end point moves towards the required root. There- fore, in actual computations, the method behaves like 2 tha fey ir oor a In Fig.1.2b, the right end point x, is fixed and the left end point moves towards the required root. Therefore, in this case, in actual computations, the method behaves like 21,2,... (1.12) Shins p19 A-fe Remark 5 The computational cost of the method is one evaluation of the function lx), for each iteration. Remark 6 We would like to know why the method is also called a linear interpolation method. Graphically, a linear interpolation polynomial describes a straight line or a chord. The linear interpolation polynomial that fits the data (x,_,, fs) (tp fy) is given by (1.13) Xho8 NUMERICAL METHODS = 0, we get or hy hd = Sah *he1 fa fea Fa ih or eh This gives the next approximation as given in an (ay. Example 1.4 Locate the intervals which contain the positive real roots of the equation x°— 8x +10. Obtain these roots correct to three decimal places, using the method of false position. Solution We form the following table of values for the function f(x). z 0 1 2 = re 1 -1 8 19 ‘There is one positive real root in the interval (0, 1) and another in the interval (1, 2). ‘There is no real root for x > 2 as fx) > 0, for all x > 2. First, we find the root in (0, 1). We have X9=0,3,= 1, fy= fe) = ofi=*ifo _ 0-1 a ayn Oe Dy 705s fey) = 05) Since, /(0) (0.5) < 0, the root lies in the interval (0, 0.5). 0) = 1, f= Ay = AD = 0.375. _ Sofa = *fo _ 0-05) "3° fa fy = 0875-1 Since, f(0) /(0.36364) < 0, the root lies in the interval (0, 0.36364). Xofs—*afy _ 0- 036364(1) fy-fy ~004283-1 Since, /(0) /10.3487) < 0, the root lies in the interval (0, 0.34870). of ~Xafy _ 0- 0348711) =f) ~ 000370 Since, /(0) /10.34741) < 0, the root lies in the interval (0, 0.34741). 0- 0347411) 0.00031 0.36364, flx,) = 0.36364) = - 0.04283. = 0.34870, fix,) = (0.34870) 0.34741, fx,) = 0.34741) = — 0.00030. = 0.347306.SOLUTION OF EQUATIONS AND EIGEN VALUE PROBLEMS 9 Now, |x, —25 |= | 0.347806 — 0.34741 | = 0.0001 < 0.0005. ‘The root has been computed correct to three decimal places. The required root can be taken as x = x, = 0.347306. We may also give the result as 0.347, even though x, is more accurate. Note that the left end point x = 0 is fixed for alll iterations. Now, we compute the root in (1, 2). We have Xo = 1,5, = 2, f= Ary) =AD=-LA oh -xfo _3- 2-1) ~fo 3-(-D Since, (1.25) 2) < 0, the root lies in the interval (1.25, 2). We use the formula given in Eq.(1.13). ix) = A2)=3. X= = 1.25, flx,) = (1.25) = - 0.796875. = ah Xify _ 1.25(3) - 2(- 0.796875) ~ha 3- (0.796875) fx.) = 407407) 0.434437. Since, /t1.407407) /l2) < 0, the root lies in the interval (1.407407, 2). 407407, Xy fy _ 14074078) aye = = 1.482367, “Anh flx,) = (1.482367) = - 0.189730. Since f(1.482367) f(2) < 0, the root lies in the interval (1.482367, 2). af —xifa _ 1.482367(8) - 2(- 0.18973) _ “fy 3-(- 0.18973) =a bIs166, fix.) = (1.518156) = - 0.074884. Since, f(1.513156) f(2) < 0, the root lies in the interval (1.513156, 2). eh ~ ifs _ 1.513156(3) = = 1.525012, f-ts 3 fix.) = 1.525012) = - 0.028374. Since, f(1.525012) f2) < 0, the root lies in the interval (1.525012, 2). - of = fo _ 162501208) 2(~ 0.028374) _ 1 soo4go, -fe 3-(— 0.028374) flx,) = 1.529462) = — 0.010586. Since, f(1.529462) f(2) < 0, the root lies in the interval (1.529462, 2). = ahi ~X1hr _ 1.529463) ~ 2- 0.010586) _y ssirig, —f —~C«S = (0.010586) fix) = (1.531116) = — 0.003928. Since, (1.531116) 2) < 0, the root lies in the interval (1.531116, 2).10 NUMERICAL METHODS 531116(3) 1.003928) fi-h 3= (0.003928) fxg) = 1.531729) = - 0.001454. Since, (1.631729) (2) < 0, the root lies in the interval (1.531729, 2). x, = Z0hiz%ifo _ 1.531729(3) ~ 2(— 0.001454) 10° inf 3-(- 0.001454) Now, [jo — xy | =| 1.581956 — 1.58179 | « 0.000227 < 0.0005. ‘The root has been computed correct to three decimal places. The required root can be taken as x =x) = 1.531956. Note that the right end point x = 2 is fixed for all iterations. Example 15 Find the root correct to two decimal places of the equation xe* = cos x, using the method of false position. Solution Define /lx) = cos x —xe* = 0. There is no negative root for the equation. We have fO)=1, fil) = cos 1 —e = — 2.17798. A root of the equation lies in the interval (0, 1). Let x9 = 0, x, false position, we obtain the following results. ofi=*ifo 0-10) fi-fy —2.17798-1 Since, (0.31467) f(1) < 0, the root lies in the interval (0.31467, 1). We use the formula given in Eq.(1.13). = 1.531729, 581956. 1. Using the method of = 0.31467) = 0.51986. 81467, flrs) efi —Xafz _ 0.31467(~ 2.17798) - (0.51986) fi-h 2.17798 — 0.51986 x5 0.44673, flx,) = 0.44673) = 0.20354. Since, f(0.44673) f(1) < 0, the root lies in the interval (0.44673, 1). Safi af _ OAAGTOLR 2.17708) ~ 10.2058) Ah = 2.1798 - 0.20354 flx4) = fl0.49402) = 0.07079. Since, /(0.49402) (1) < 0, the root lies in the interval (0.49402, 1). = Saha if _ 0.494021 2.1798) — 100.07079) oO Awhe 2.17798 - 0.07079 Aix,) = (0.50995) = 0.02360. Since, f(0.50995) f\1) < 0, the root lies in the interval (0.50995, 1). 0.50995(— 2.17798) - 1(0.0236) — 2.17798 — 0.0236 flxq) = (0.51520) = 0.0076. = 0.49402, = 0.50995, = 0.51520,‘SOLUTION OF EQUATIONS AND EIGEN VALUE PROBLEMS " Since, (0.51520) fl) < 0, the root lies in the interval (0.51520, 1). (0.00776) _ 9.51692. 17798 — 0.00776 Now, |x; ~x¢| =| 0.51692 — 0.51520 | = 0.00172 < 0.005. The root has been computed correct to two decimal places. The required root can be taken as x = x, = 0.51692 Note that the right end point x = 2 is fixed for all iterations.1.2 LINEAR SYSTEM OF ALGEBRAIC EQUATIONS 1.2.1. Introduction Consider a system of n linear algebraic equations in n unknowns yh Fahy tH, ayy + gat +n + agg = 2 Oy F Ogghy tm + Aggy = Dy wherea,, i= 1, 2,....,j = 1,2, ...,n, are the known coefficients, b,, i= 1, 2, ...., are the known right hand side values and x,, i = 1, 2, ..., n are the unknowns to be determined. In matrix notation we write the system as Ax=b (1.83) ay ay an @, where Py i nd ‘The matrix [A | bl, obtained by appending the column b to the matrix A is called the ‘augmented matrix. That is26 NUMERICAL METHODS. a TA] b] = [22 722 + an | By Bn On ‘We define the following. (® The system of equations (1.33) is consistent (has at least one solution), if rank (A) = rank [A | bl =r. Ifr =n, then the system has unique solution. Ifr [1 | XI In this case, after the eliminations are completed, we obtain the augmented matrix for a3 x3 system as 10 0} d 0 1 Old (1.42) 00 1;a& and the solution is -x,=d,,i=1,2,8.34 NUMERICAL METHODS Elimination procedure The first step is same as in Gauss elimination method, that is, we make the elements below the first pivot as zeros, using the elementary row transformations. From the second step onwards, we make the elements below and above the pivots as zeros using the elementary row transformations. Lastly, we divide each row by its pivot so that the final augmented matrix is of the form (1.42). Partial pivoting ean also be used in the solution. We may also make the pivots as 1 before performing the elimination. Let us illustrate the method. Example 1.17 Solve the following system of equations Xytay tage 4x, + 8x, -2, = 6 Bx, + Sr, + Oxy 4 using the Gauss-Jordan method (i) without partial pivoting, (ii) with partial pivoting. Solution We have the augmented matrix as 11 aft 43 -1|6 4 aS 8: @ We perform the following elementary row transformations and do the climinations. r a 1 a 1 1 R,-4R,,Ry-3R,:|0 -1 -5 o 2 0 1 0 -4/3 Ry + Roy Ry+2Ryi]0 -1 -5 | 2): © 0 -1015, 1 0 oO} 1 R,-(/ORg, Rp- (6/0) R, :}0 -1 0 | -12]. 0 o -10] 5 Now, making the pivots as 1, ((- R,), (Ry(- 10))) we get 10 0] 1 0 1 0} wi]. 0 0 1)-172 ‘Therefore, the solution of the system is x, = 1, x,= 1/2, x, Gi) We perform the following elementary row transformations and do the elimination. 6 1 94 -14/32 a Ryv4cfa 1 oa fa]. 4 12. 4 3 -1 ROR,:]1 1 0 1 35 38\4 35 38SOLUTION OF EQUATIONS AND EIGEN VALUE PROBLEMS 35 1 34 -¥4) a2 Ry-RyRy-3R,:|0 V4 54 | - v2]. 0 1v4 asi | - 1 94 -v4] a2 1 84 UA] a2 R,R,:}0 14 194 |-v2}. Ryav4:|o0 1 151 | 23]. o m4 54 |-2 o v4 4 | -12 10 -14n1) 1st R,-(/A) Ry Ry— (VAR: |0 1 18/11]-2/11]. 00 1011|-511 10-1411] 18/11 Rydon: |0 1 agai | -21). oo 1 |-w 10 0/1 R,+ (14/11) Ry R,- (6K, :}0 1 0] v2 |. 00 1/-12 ‘Therefore, the solution of the system is x, = 1, x, = 1/2,x,=— 1/2. Remark 18 The Gauss-Jordan method looks very elegant as the solution is obtained directly. However, it is computationally more expensive than Gauss elimination. For large 7, the total number of divisions and multiplications for Gauss-Jordan method is almost 1.5 times the total number of divisions and multiplications required for Gauss elimination. Hence, we do not normally use this method for the solution of the system of equations. The most important application of this method is to find the inverse of a non-singular matrix. We present this method in the following section. 1.2.2.8 Inverse of a Matrix by Gauss-Jordan Method As given in Remark 18, the important application of the Gauss-Jordan method is to find the inverse of a non-singular matrix A. We start with the augmented matrix of A with the identity matrix I of the same order. When the Gauss-Jordan procedure is completed, we ob- tain since, AA = I. Remark 19 Partial pivoting can also be done using the augmented matrix [A|I]. However, ‘we cannot first interchange the rows of A and then find the inverse. Then, we would be finding the inverse of a different matrix. Example 1.18 Find the inverse of the matrix i) 43-1 a5 336 NUMERICAL METHODS using the Gauss-Jordan method (i) without partial pivoting, and (ii) with partial pivoting. Solution Consider the augmented matrix 11 1/100 4 8 -1/0 1 Oj. 3) Sp 13) oo1 (@) We perform the following elementary row transformations and do the eliminations. 111 100 Ry-4Ry, Ry-3R,; |0 -1 -5]-4 1 0 0 2 ol-3 01, 10 -4/-3 10 R,-RyRy-2R,:}0 1 5] 4 -10 00 -10|/-11 21 10 -4| -3 1 0 RjA-10):}0 1 5 4 -1 0 oo 1/1vio -210 -V10 10 0} Mo 20 40 R,+4R,,R,-4R,:]0 1 0/-1810 0 — s/10), oo 1] 1m0 -20 -w0 Therefore, the inverse of the given matrix is given by 1s WS -25 -32 0 12] 10 -15 -V0, (éé) We perform the following elementary row transformations and do the eliminations. 4 3-1/0 1 0 1 34 -V4)0 v4 0 RyoR,:/1 1 1/1 0 Of ryva:]2 1 1 |1 0 of, 35 sloo01 35 3 ]0 01 1 84 -V4J0 V4 OF Ry-RyRy-3R,:}0 V4 G4 |1 v4 oO}. o 14 1940-324 1 1 4 -w)o um oO R,ORy:|0 1v4 164 ]0 -94 1]. ov wa 1 -14 0194 -v4 |0 wm 0 RAAv):|0 1 1811 }O -3n1 41 ow 94 |1 -”%4 0 10-1411 el -air R,-(@G/4)R,,R,- (WAR, }0 1 a1}o -a11 41 0 0 toi}. -21 -m1 10-141) 0 m1 -mT Ryaont):|0 1 111} 0 -a11 ani}. 00 1 |imo -w% -10 10 0| % W -2 R, + (14/11) Ry Ry-(15/1)R,:]0 1 0] -92 o Ww 0 0 1] imo -1%6 -mo ‘Therefore, the inverse of the matrix is given by 1 WS 28 -92 oO WW 10 -% -10 Example 1.19 Using the Gauss-Jordan method, find the inverse of 223 211). (AU. Apr./May 2004) 135 Solution We have the following augmented matrix. 22 3/100 21 1/0 1 o} 13 5001 We perform the following elementary row transformations and do the eliminations. 1132/12 00 11 92 w00 Rs2:}2 1 110 1 O|. Ry-2R,Ry-Ry:/0 -1 -2 |-1 10 13 5/0 0 1 o 2 Ww |-12 0 1 1 1 92 v0 0 RyRy Then,R/2:/0 1 4] -14 0 19]. Oo -1 -2 “a 10 10 -V4 34 0 -2 R,-RyR,+R,:}0 1 W4|-v4 0 1B 00 -m|-s4 1 12NUMERICAL METHODS 38 10 -14| 94 0 -12 Ryf-va): ]O 1 vw 0 Ww 00 5 -4 -2 10 0] 2 -1 - R,+ (WAR, Ry-(WARy:|0 1 0/-9 7 4 oo1| 5 -4 - Therefore, the inverse of the given matrix is given by Hay 5-4-2,4.4.6 Convergence of the Iteration Methods ‘We now study the rate at which the iteration methods converge to the exact root, if the initial approximation is sufficiently close to the desired root. Define the error of approximation at the hth iterate as &, =x,- 0, = 0,1, Definition An iterative method is said to be of order p or has the rate of convergence p, if p is the largest positive real number for which there exists a finite constant C #0, such that Tey lS Cle P (1.28) ‘The constant C, which is independent of h, is called the asymptotic error constant and it depends on the derivatives of flx) at x = a. Let us now obtain the orders of the methods that were derived earlier. Method of false position We have noted earlier (see Remark 4) that if the root lies initially in the interval (x,, x,), then one of the end points is fixed for all iterations. If the left end point xq is fixed and the right end point moves towards the required root, the method behaves like (see Fig.1.2a) sof fe, hbo Substituting x, = € +, X44 = 441 + 04 %9 = €) + Of We expand each term in Taylor's series and simplify using the fact that fla) = 0. We obtain the error equation as fay 2f%o)” Fa = 44, = Céyty where C=Since ¢, is finite and fixed, the error equation becomes learl=1C* leq where C* = Ceo. (1.29) Henee, the method of false position has order 1 or has linear rate of convergence. Method of successive approximations or fixed point iteration method We have yy = O04), and a= O(c) Subtracting, we get 24.4 &= OCR, — Ka) = Oa + 3, — @) — G10) = (40) +, - @) O(@) + 1 - 9) or Egy, = &yO() + Ol€Z). Therefore, lel=Clal 4 +O), 2r@ Fo © +L (a) a fo) *op@ tte dpe Fa **™ | - LO) 2, Jaf 2 £1 apa) * "| apa Neglecting the terms containing ej and higher powers of ¢,, we get 7) =Ce?, where c= LE , me Sian SESE arSOLUTION OF EQUATIONS AND EIGEN VALUE PROBLEMS. 21 La lee l= 1C11& P asp ‘Therefore, Newton's method is of order 2 or has quadratic rate of convergence. Remark 12 What is the importance of defining the order or rate of convergence of a method? Suppose that we are using Newton’s method for computing a root of fix) = 0. Let us assume that at a particular stage of iteration, the error in magnitude in computing the root is 10"? 0.1. We observe from (1.81), that in the next iteration, the error behaves like G(0.1)? = (107). ‘That is, we may possibly get an accuracy of two decimal places. Because of the quadratic convergence of the method, we may possibly get an accuracy of four decimal places in the next iteration. However, it also depends on the value of C. From this discussion, we conclude that hoth fixed point iteration and regula-falsi methods converge slowly as they have only linear rate of convergence. Further, Newton's method converges at least twice as fast as the fixed point iteration and regula-falsi methods. Remark 13 When does the Newton-Raphson method fail? (@ The method may fail when the initial approximation x, is far away from the exact root (see Example 1.6). However, if the root lies in a small interval (a, 6) and x9 € (a, 6), then the method converges. (ii) From Eq.(1.31), we note that if f(a) = 0, and f“(x) is finite then C + « and the method may fail. That is, in this case, the graph of y = f(x) is almost parallel to x-axis at the root Remark 14 Let us have a re-look at the error equation. We have defined the error of approxi- mation at the hth iterate as ¢, =x, — 0, k = 0, 1, 2,.. From2,,, = 0(x,), k= 0, 1,2... and = 6(0), we obtain (see Eq.(1.24)) Xp — 0 = Oxy) = Had = Ola + )— Gad = [sie +o(ae + i "ode? +...| — e409 or Sg ye, $aG2 ow (1.32) where 4a, = (6), a, = (1/2)6"(o), ete. ‘The exact root satisfies the equation « = 6(«). Ifa, #0 that is, 6a) #0, then the method is of order 1 or has linear convergence. For the general iteration method, which is of first order, we have derived that the condition of conver- gence is | 6x) |< 1 for allx in the interval (a, 6) in which the root lies. Note that in this method, 1¢’@) | #0 for all x in the neighborhood of the root «. Ifa, = (a) = 0, and a, = (1/2)6"(q # 0, then from Eq, (1.32), the method is of order 2 or has quadratic convergence. Let us verify this result for the Newton-Raphson method. For the Newton-Raphson method F(x) fix) hi =x- Fons Wehave Ole) =2— FN? = Fo FG) _ FF") ror rar a= ‘Then, oe)22 NUMERICAL METHODS ya) = La) and 0) = Rar since f(a) = 0 and f"(a) # 0 (ais a simple root). When, x, — a, flx,) > 0, we have | o%,) |< 1, Now, Ox) = er LF) (FC) FG) + A) f= 2 fl) (FGI and a= ce #0. ‘Therefore, a, # 0 and the second order convergence of the Newton's method is verified.Define a (i) root, (ii) simple root and (iii) multiple root of an algebraic equation f(x) = 0. Solution (@ Anumber a, such that a) = 0 is called a root of fix) = 0. (i) Let a be a root of fix) = 0. If fla) = 0 and f(q) 4 0, then a is said to be a simple root. ‘Then, we can write flr) as f(x) = (x - a) gtx), gla) # 0. (ii) Let a be a root of lx) = 0. If Ala) = 0, f(0) = Ons f°" (@) = 0, and f'™ (a) #0, then, ois said to be a multiple root of multiplicity m. Then, we ean write f(x) as fix) = @ — 0)” glx), g(a) #0. 2. State the intermediate value theorem. Solution If f(x) is continuous on some interval [a, b] and f(a)f(6) < 0, then the equation fcc) = 0 has at least one real root or an odd number of real roots in the interval (a, b). 3. How can we find an initial approximation to the root of f (x) = 0? Solution Using intermediate value theorem, we find an interval (a, b) which contains the root of the equation f(x) = 0. This implies that f (a)b) < 0. Any point in this interval (including the end points) can be taken as an initial approximation to the root of fix) = 0. 4. What is the Descartes’ rule of signs? Solution Let f(x) = 0 be a polynomial equation P,(x) = 0. We count the number of changes of signs in the coefficients of f (x) = P,(x) = 0. The number of positive roots cannot exceed the number of changes of signs in the coefficients of P,(x). Now, we write the equation f(—x) = P,(—x) = 0, and count the number of changes of signs in the coefli- cients of P,(— x). The number of negative roots cannot exceed the number of changes of signs in the coeflicients of this equation. Define convergence of an iterative method. Solution Using any iteration method, we obtain a sequence of iterates (approxima- tions to the root of flx) = 0), x, Xp Spe TEae Jim a0" J ‘where isthe exact oot, then the method is said to be convergent ©. What are the criteria used to terminate an iterative procedure? Solution Lete be the prescribed error tolerance. We terminate the iterations when cither of the following erteriais satisfied fap ise 1x45 156 Sometimes, we may use bath the entra, 1% Define the fixed point iteration methed to cbtain a ret offs) =O. When does the method converge? Solution Let a root offx) =O lie in the interval, 8). Letxy be an initial approximation tothe root We write) =0 in an equivalent form as = (x), and define the fixed point iteration method as, ,= os,),k=0, 1,2, Starting with x, we abtain a sequence af ‘approsimations zy xf", s.r such that in the limit as & ~¥-—, 5, >a. The method canverges when |G) |'< 1, for all x inthe interval (, 6). We normally eheck this canditon at x5 1. Write the method of filse position to obtain a root ots) = 0. What isthe computatio cist ofthe method? ‘Solution Let a root of fi) = ie in the interval (a, 8). Lets be two nitial approxi- ‘mations to the rot in this interval. The method of false postion is defined by ge teins = ‘The computational cot ofthe method is one evaluation offs) per iteration 8, What isthe disadvantage of the method of false postion? ‘Solution IF the root lies initially in the interval (ex), then one of the end points is fixed for all iterations. For example, in Fig. 12a, the Ie end point zis fixed and the right end print moves towards the required root. Therefore, in actual computations the ‘method behaves like ew ths y= Shia 8eh Rho Jn Fig.2b, the right ond point; is fie and the left end point moves towards the required ost. Therefore, in this case, nactal computations, the method behaves like 10, Write the Newton-Raphson method to abiain a root of fle) = 0. What ‘onal sost of the method? Solution Let a root offx) =O lie in the intarval(a,b). Lets, bean initial approximation ta the root in this interval The Newton-Raphon method 0 find this rot is defined by is the computa. Downloaded From : www Easy Faginerag net Dowalaaded From wort EasyEagiecering net 24 NUMERICAL METHODS 21,00, payee, be snes FEL, 159 #0, #2 01,200 ‘The computational cost of the method is one evaluation of lx) and one evaluation of the derivative ') per iteration 11, Deine the order (rate) of convergence ofan iterative method for finding the root of an ‘equation fx) = 0 ‘Solution Let be the exact root offs) = 0. Define the error of approximation atthe th itorate asc, =x,~c, #= 0, 1,2, Amiterative method is sid tobe of order p or has the rate of convergence p, ip is the largest psitive real number for which there exists a Finite constant C 0, such that Ina Sele ir. ‘The constant C, which s independent of iealed the asymptotic error constant anit depends on the derivatives of fis) ats = 12, What isthe rate of convergence ofthe following methods: (i) Method of flee position, (i) Newton Raphsen method, (i) Fixed point iteration method? Solution (One. (i) Two. (it) One.n Method. In Section 7.3, we described a scheme for computing the matrices £ and U such that 7.5.6 LU Decomposi 4a=LU (738) where L is unit lower triangular and U an upper triangular matrix, and these are given in Eq, (7.2). Let the system of equations be given by ays + ayaty + ayaxy = by ane + anes + assy = (7.36) ay xy + ages + ayy = by which can be written in the matrix form AX=B (737) LUX = B (7:38) If we set Ux = ¥, (739) then Eq. (7.38) becomes Ly = 8 (7.40) which is equivalent to the system fa +2 aay fu + Gove + ys where Ov J ys" = Vand (by, by, by) = Be ‘The system (7.41) can be solved for yi, y and yy by forward substitution. When Y is known, the system (7.39) becomes yxy + take + sts at ut = ys (742) ayes which can be solved for x1, x2, 5 by backsubstitution process. As noted earlier, this method has the advantage of being applicable to solve systems with the same coefficient matrix but different right-hand side vectors. vs272 Cuarren 7: Numerical Linear Algebra 7.5.7 Computational Procedure for LU Decomposition Method Given any nonsingular square matrix A, the LU decomposition, where L is unit lower triangular and U an upper triangular matrix, can be achieved by the following computational steps: Do i = 1(1jy - 1 Do j= i+ 1tN ACH, 4) = ACG, AV/ALA, 4) DoM= i+ 10) ™ AUj, = ALG, MY - ALG, MA C5 4D Next Next j Next i End To save storage space, the elements of Z and U are stored in the space occupied by A, the elements J being omitted. Thus, after the factorization is effected, the layout of the store for a (4% 4) matrix is given by My zs the fy tay tag ag Be bz sy ss fleas a, If the right-hand side vector is B = (b,, by, by), then the forward substitution can be accomplished by the statements: Do j= 1(yw = 1 Do i= fj +10) bli) = Bla) - 2a, f1*bCD) Next 4 Next j End. Similarly, the backsubstitution can be effected by the steps: Do j = MI-2)1 BER = dIG/UH. 5 Do i =1(1) 9-1 bla) = DEA) ~ ula, FV BC 9) Next 4 Next 7 EndSccrion 7.5: Solution of Linear Systems—Direct Methods 273 Example 7.8 Solve the equations det 3yt2=9 x+2y+32=6 Bet yt22 by the method of LU decomposition. We have 23 0 9 A=|1 3| and B=| 6 312 8 In Example 7.2, we obtained the LU decomposition of 4. This is 1 0 0 23 4 L=|05 1 0| and U=|0 05 25 is 7 1 oo WB Dis gos yall then the equation LY = B gives the solution: Ni =% a> and y= 5. Finally, the matrix equation uv gives the required solution