Module - 5 Chapter 7 Numerical Methods - I In this chapter we present some numerical methods of solving algebraic and transcendental equations. 7.1 Algebraic and Transcendental Equations For our discussions in this chapter, we consider equations of the form f(x) = 0, where f(x) is a polynomial or a transcendental function of a real variable x. These equations are together referred to as non-linear equations. ‘The reader may recall that a function f(x) is said to be a polynomial function (or just a polynomial) of degree nif it is of the form S(%) = agx" + ay) +o + Op x + Any where the coefficients ao,a,-+-a, are constants with ay # 0. A function which is a sum, difference or product of two polynomials is called an algebraic function. ‘A function which is not an algebraic function is called a transcendental function. For example, e*, log x, cos x are transcendental functions. If (2) is an algebraic function, then the equation f(x) = 0 is called an algebraic or poly- nomial equation. Likewise, if f(x) is a transcendental function, then the equation f(x) = 0 is called a transcendental equation. Root of an equation ‘A real or complex number m is called a root or a solution of an equation f(x) = 0 if ‘f(m) = 0. Then we say that m satisfies the equation f(x) = 0 or that m is a zero of the function f@). For example, 1/2 is a root of the equation cos x = 0 (because cos x/2 = 0). Equivalently, 1/2 is a zero of the function f(x) = cos x. ‘The process of finding roots of an equation f(x) = 0 is known as solving the equation f(x) = 0. Approximate root (solution) of an equation Given a non-linear equation f(x) = 0, it is generally not possible to find the exact value of a root m of the equation. In such a situation, we try to find an approximate value of m; such an approximate value satisfies the equation f(x) = 0 only approximately, This means that if m. 249250 7. Numerical Methods-I is an approximate value of m to a degree of approximation k, then f(g) = &, where & is a small number which tends to 0 as mg tends to m. The approximate value mi of m is called an approximate root ot an approximate solution of the equation f(x) = 0 and ¢, is called the error in this root (solution) in the kth-order approximation. The methods of finding approximate roots of f(x) = O are referred to as Numerical Methods of solving f(x) = 0. Intermediate-value property In our further discussions we deal with equations f(x) = 0, where f(x) is a non-linear, real-valued continuous function of a real variable x. An important property (called location of roots property, ot intermediate-value property) of such a function is that if f(x) has opposite signs for two values x = a and x= b, then the equation f(x) = 0 has at least one root between a and b, Geometrically, this means that if f(a) and f(b) are of opposite signs, then the curve y = f(2) cuts (crosses) the x-axis at least at one point m that lies between a and b. This point mis a real root of the equation f(x) = 0. Figure 7.1 The intermediate-value property of a continuous function f(x) may be employed to find the location of a real root of f(x) = 0. By some considerations, if we find that f(a) and f(b) are of opposite signs for some real values a and b of x which are near to one another, then f(x) = 0 will certainly have a root between a and b, and we take a or b, or some number between a and as an initial approximation of this root. In the following Sections, we consider two standard Numerical methods of solving alge- braic and transcendental equations f(x) = 0. 7.2, Regula-falsi Method Suppose an equation f(x) = 0 is known to have only one real root m between a and b. This happens when f(a) and f(b) are of opposite signs and the curve y = /(x) crosses the x-axis only once at the point x = m lying between the points x = a and x = b. See Figure 7.2.7.2, Regula-falsi Method 251 Figure 7.2 Consider the points A(a, f(a)) and B(b, f(b)) on the curve y = f(x). Then the equation of the chord AB is y= f@ _ fo)-f@ a x-a boa ‘At the point C where the chord AB crosses the x-axis, we have y = 0 and equation (1) yields b ea Fy Fay ie This gives the x-coordinate of the point C. If the interval [a, b] is sufficiently small, the x-coordinate of the point C is sufficiently close to the point x = m (where the curve y = f(x) crosses the x-axis). In other words, x given by (2) serves as an approximate value of m when b - ais sufficiently small. The method of finding an approximate value of m on the basis of this observation is known as the Method of False Position or the Regula-falsi method. The Working Rule for this method is as indicated below. Working Rule Step 1. Given an equation f(x) = 0, choose an interval [a,b] such that the equation f(x) = 0 has exactly one root m between a and b. (Then f(a) and f(b) will have to have opposite signs). Step 2, Employ the formula (2) with x replaced by x1. Thus, (a=70) "0 2 This x; serves as the first-order approximation of the root m. x1 = x0 - Step 3. Find f(x). Then either (a) and f(x1) are of opposite signs or f(x1) and f() are of opposite signs. Suppose f(a) and /(x;) are of opposite signs. Then employ the formula (2) with b replaced by x to find the value x2 of x. Thus ee ee Ta)" ey7. Numerical Methods -I On the other hand, if (x1) and f(b) are of opposite signs, employ the formula (2) with a replaced by x; to find the value x of x. Thus, in this case, = .—2 C men- Gate ats) 0 (40) The x2 given by (4a) or (4b) serves as the second-order approximation of m. Step 4. Repeat the process to determine the third-order, fourth-order,. .. approximations of m. In this process, xz serves as the k'"-order appriximation of the root (being determined). Stop the process when the desired degree of approximation is reached. = O that lies between 1.8 and 2. Carry out three approximations. > Letus take f(x) = x4 —x—10, anda = 1.8, b = 2. Then, we find F(a) = f(1.8) = (1.8)* — (1.8) — 10 = -1.3024 ¥ -1.3<0 and FO) = f2Q)=24-2-10=4>0. We note that f(a) and f(b) are of opposite signs. Therefore, the given equation f(x) = does have a root m between a = 1.8 and b = 2. The first-order approximation of this root is b- 2-18 xy =a- (ats oa) fan 18 ~ Fag * O15) = 1.849. ‘We find that f(x) = f(1.849) = (1.849)4 — (1.849) - 10 = -0.161 <0. ‘We observe that f(x1) and f(b) are of opposite signs. Hence, the root m lies between x1 = 1.849 and b = 2, and the second-order approximation of this root is bx _ _2= 1.849 _ aa (aya pa 0 = 80 Fer COND = 18548 We find that (x2) = (1.8548) = -0.019 < 0. We observe that (xz) and f(b) are of opposite signs. Hence the root m lies between x2 = 1.8548 and b = 2, and the third-order approximation of this root is = 1.8548 x3 =X) — (oe) = 1.8548 — aus X (-0.019) = 1.8555 ‘This is the required root in the third-order approximation. .7.2. Regula-falsi Method 253 Using the method of false position, find a real root (correct to three decimal places) of the equation x3 —2x-5 =0 that lies between 2 and 2.5. » Letus take f(x) = x? —2x-5 anda = 2, b = 2.5. Then we find f(a) = f(2) = 2 -2x2-5=-1<0. f(b) = f(2.5) = (2.5) — 2 x (2.5) — 5 = 5.625 > 0. Since f(a) and f(b) are of opposite signs, the given equation f(x) = 0 does have a real root m between a and b. The first-order approximation of this root is __(_b-a 5 25-2) xa=a ( ) Aa) =2 Goss *' 1) = 2.07547 £6) - f@) ‘We find that (x1) = (2.07547) = (2.07547) — 2 x (2.07547) — 5 = -0.210696 < 0. We note that f(x;) and f(b) are of opposite signs. Therefore, the root m lies between x, = 2.07547 and b = 2.5. The second-order approximation of this root is (2.5 — 2.07547) b- xm _ _ _@5 = 2.07547), _ 2 = (ets) Sf (21) = 2.07547 G.625 + 0.210696) x (—0.210696) = 2.0908. We find that ‘fl%2) = f(2.0908) = -0.04178 <0. We note that f(x2) and f(b) are of opposite signs. Therefore, the root m lies between x2 = 2.0908 and b = 2.5. The third-order approximation of this root is (2.5 — 2.0908) b-xm G.625 + 0.04178) meee (ws = Fa) We find that ) f(x2) = 2.0908 — (-0.04178) = 2.0938. —0.00838 < 0. F (x3) = F(2.0938) ‘We note that f(x3) and f(b) are opposite signs. Therefore, the root m lies between x3 = 2.0938 and b ‘The fourth-order approximation of this root is (2.5 — 2.0938) (5.625 + 0.00838) bx ) =x, -[|—2- 3 —} fas) = 2.0938 - x (—0.00838) = 2.0944. ies (as = fea) ‘We note that x4 and x3 are equal up to three places of decimals. Therefore, we take m = 2,094 as the required root, correct to three decimal places. .254 7. Numerical Methods - I PEELED 8) using the Regula-falsi method, find the root, correct to 2 decimal places, of the equation xlogyyx = 1.2 that lies between 2 and 3. » The given equation is f(x) = 0, where la) = xlogig x — 1.2. Let a = 2, b = 3. Then we find Fla) = f(2) = 2logg 2 — 1.2 = 2x (0.30103) - (1.2) = -0.59794 <0, and f(b) = (3) = 3logyg 3 — 1.2 = 3 x (0.47712) - (1.2) = 0.23136 > 0. Since f(a) and f(b) are of opposite signs, the given equation f(x) = 0 does have a root m between a = 2 and b = 3. The first approximation of this root is b-a 3-2 xp =a- (acto 0. Since f(a) and f(b) are of opposite signs, the equation f(x) = 0 does have a real root m between a = 0 and b = 1. The first approximation of this root is asa b- (1-0) _ ( OE Fara) io=9 ~ Wres = 073595. We find that f(x1) = f (0.73575) = (0.73575)e°7957 — 2 = -0.46445 <0 We note that f(x1) and f(b) are of opposite signs. Therefore, the root m lies between = 0.73575 and b = 1. The second approximation of m is (1 — 0.73575) 0-783 + 0.46445 ~ 046445) = 0.8395 part BY A Peres = 0.73575 — mea oes) eo o7s7s We find that F(2x2) = (0.8395) = (0.839585 — 2 = -0.05638 < 0 We note that f(x2) and f(b) are of opposite signs. Therefore the root m lies between 2 = 0,8395 and b = 1. The third approximation of m is 1— 0.8395 F(G22) = 0.8395 ~ T7855 0.05638 33 = x2 — (—0.05638) = 0.8512 (e765) f(b) ~ f(x2) We find that f(x) = f0.8512) = (0.85120!) — 2 = -0.0061 < 0 We note that f(x3) and f(b) are of opposite signs. Therefore, the root m lies between x3 = 0.8512 and b = 1, The fourth approximation of m is x _ _ (= 0.8512) _ x4 = 3 — (Sa) = 0.8512 ~ Taras 5p opgT (0.0061) = 0.8545 We find that ‘flx4) = f(0.85245) = (0.85245) e845) — 2 = 0,00068 < 0256 7. Numerical Methods -I ‘We note that f(x4) and f(b) are of opposite signs. Therefore, the root m lies between x4 = 0.85245 and b = 1. The fifth approximation of m is ) oxo = = 0.85245 — (—0.00068) = 0.8526 se (et Fa) 7183 + OEE We note that x4 = x5 = 0.853 correct to three decimal places. We therefore take this as the required root correct to three decimal places. . Using the Regula-falsi method, find a real root (correct to three decimal places) of the equation cosx=3x-1 that lies between 0.5 and 1. (Here, x is in radians). > Let us take f(x) = cosx 3x41, so that the given equation is f(x) = 0. Also, let a = 0.5 and b = 1. Then we find f(a) = f(0.5) = cos (0.5) ~ 3 x (0.5) + 1 = (0.8776) ~ 0.5 = 0.37756 > 0 f(b) = f(1) = (Cos 1) — 3 + 1 = 0.54030 — 2 = -1.4597 <0 Since f(a) and f(b) are of opposite signs, the given equation f(x) = 0 does have a real root m between a = 0.5 and b = 1. The first approximation of this root is _ b-a os (1-0.5) _ xy=a- (eos Fa 5) iano TaS7 = 03 7TSH * 037756 = 0.60275. ‘We find that Ff (x1) = (0.60725) = cos (0.60275) — 3 x (0.60275) + 1 = 0.0155 > 0. We note that f(x1) and f(b) are of opposite signs. Therefore, the required root m lies between x; = 0.60275 and b = 1. The second approximation of this root is b-x (1 — 0.60275) =x, -|————— = 0.60275 — ——___———__ = men (ras = a cy [1.45976 — 0.0155) * 9.0155 = 0.60692. We find that S22) = F (0.60692) = 0.0006 > 0. We note that f(xz) and f(b) are of opposite signs. Therefore, the required root m lies between x2 = 0.60692 and b = 1. The third approximation of this root is __(1= 0.60690) (-1.45976 — 0.0006) b-x 73 \ Fb) = F020), We observe that x2 and x3 are identical up to three decimal places, Hence we take m = 0.607 as the required root correct to three decimal places. . ) om = 0.60692 — x 0.0006 = 0.6071.7.2, Regula-falsi Method 257 Using the Regula-Falsi method, find the root, correct to four decimal places, of xe* = cosx that lies between 0.4 and 0.6, (Here, x is in radians). > Let f(x) = xe* — cos x, and a = 0.4 and b = 0.6. We find that F(a) = f(0.4) = (0.4) x e* — cos (0.4) = -0.32432 < 0, Fb) = f(0.6) = (0.6) x e — cos (0.6) = 0.268 > 1. Since f(a) and f(b) are of opposite signs, the given equation f(x) = 0 does have a real root m between a = 0.4 and b = 0.6. The first approximation of this root is oe x (0.32432) = 0.50951. b-a “een (a = <5) 40 = 04~ (568 +0.3243) We find that fx1) = f(0.50951) = -0.0249 < 0. We note that f(21) and f(b) are of opposite signs. Therefore, the required root m lies between x1 = 0.50951 and b = 0.6. The second approximation of this root is (0.6— 0.5095D) 0.0249) = 0.5172. = ba eI othteieeeedh ae ( F®)-fea J. (an) = 0.50951 ~ 5655 0,0249) We find that f(x) = f(0.5172) = -0.00168 < 0. We note that f(x2) and f(b) are of opposite signs. As such, the required root m lies between . The third approximation of this root is X2 = 0.5172 and b = =y-(—-2— = ~ 06= 05172), = n-n-(ay 22) fon) =0.5172 D2e + ODDIE * 0.00168) = 0.517716 We find that (x3) = £(.517716) = -0.000107 < 0. We note that f(x3) and f(b) are of opposite signs. As such, the required root m lies between x3 = 0.517716 and b = 0.6, The fourth approximation of this root is b- x3 _ _ 0.6 = 0.517716) _ X4 = 3 — (Ste) = 0.517716 0.268 + 0.000107) x (0.000107) = 0.51774. We observe that x3 and x4 are equal up to four places of decimals. Therefore, we . take m = 0.5177 as the required root correct to four decimal places.258 7. Numerical Methods -I Exercises 1. By using the method of false position (Regula-Falsi method) find the roots, correct to 3 decimal places, of the following equations in the indicated intervals. () 8 -4x-9=0in(2.5,3.0). (2) x -9x+ 1 = Oin (2,3). @) »-3x+4=0in(-25,-2). (4) 244-722-245 =0in(2,2.5). () e* =3xin (0.5, 1.0). © x=e*in(@5,1.0). (xe =3in (1, 1.1). (8) 2x-logx=6 in (3,3.5).” (9) 2 -logx = 12in@,4). (10) 2x-logyg x = 7 in (3.5, 4). 2. By using the method of false position, find the roots, correct to 4 decimal places, of the following equations in the indicated intervals: (Q) +2 +x+7=0in(-25,-2.0) (2) 2-422 +x-10=0in (4,5) @) x42%-16x+5=0in@,1) (4) 8-4-1 =0in(1.4,15) (5) e*sinx = 1 in (2,3) in radians (6) logx—cos.x = 0 in (1,2) in radians Answers 1 (2.706 2) 2.942 (@) -2.196 2.060 ©) 0619 © 0567 1.050 (8) 3.257 ©) 3.646 (10) 3.789 2. (1) -2.1049 (2) 4,3069 (3) 0.3265 (4) 1.4036 (5) 2.962 6) 1.3029 7.3. Newton-Raphson Method Let m be a real root of an equation f(x) = 0. Then, we have f(m) =0. a If m lies near a point a, we have, by Taylor’s expansion, (m-ay ., OP ato fm) = fa + (m- a) f(a) + Throughout, log x stands for log, x. This notation is used throughout.7.3. Newton-Raphson Method __ 259 Ignoring the second and higher degree terms in (m — a), this expression becomes fon) = f(a) + (m—a)f"(a) (2) This expression serves as the first-order approximate value of f(m) near the point a, the exact value being zero as in (1). From (1) and (2), we obtain 0=f@+(m-a)f"@, sothat_ m—a=~ e. -__1@ or =a 5G @) Since expression (2) gives the first-order approximate value of f(m), expression (3) gives the first-order approximate value of m (in terms of a). Taking a = xo and m = x; in expression (3), we get fGo) £0) x, = Xo — 4 This gives an approximate value x; of m in terms of a = xo. Here xp is called the initial approximation of m, and x; is the first-order approximation. Replacing xy by x; and x; by x2 in expression (4) we get the following expression for x2, which is the second-order approximation of m: _ fe) fay a2 = x1 () Proceeding like this, we obtain successive approximations x3, x4,... of m. ‘The following is the formula for the (k + 1)" -order approximation of m in terms of the k”" -order approximation: _ FG”), few ‘This formula is known as the Newton-Raphson formula or the Newton’s iterative formula. ‘The process of computing an approximate root of an equation f(x) = 0 by using this formula is known as the Newton-Raphson method, or just the Newton's method. ©) Nee = Xk Geometrical Meaning “The Newton-Raphson formula (6) is derived on the basis of expression (3). We now obtain ‘4 geometrical meaning of this expression. Since m is a root of the equation f(x) = 0 near the value x = a, the curve y = f(x) crosses the x-axis at the point x = m which lies near the point x = a (on the x-axis), See Figure 7.3.260 7. Numerical Methods -I Figure 7.3 Consider the point A(a, f(a)) on the curve y = f(x). Then the equation of the tangent to the curve at the point A is Y-f@ _ sg LO o At the point C where this tangent meets the x-axis, we have y = 0 and equation (7) yields _ fo, f@ x=a (8) This gives the x-coordinate c of the point C. Comparing expressions (3) and (8), we find that m determined by expression (3) is the x- coordinate of the point where the tangent to the curve y = f(x) at the point (a, f(a))) meets the x-axis. Similarly, comparing expressions (6) and (8), we note that xg+1 is the x-coordinate of the point where the tangent to the curve y = f(x) at the point (xz, f(xz)) meets the x-axis. This is the geometrical meaning of the formula (6). Figure 7.4 Using the Newton-Raphson method, find a real root, correct to four decimal places, of the equation x4 +2x*- 16x+5=0, which lies near x = 0.7.3. Newton-Raphson Method 261 > Here, the equation to be solved is f(x) = 0, where f(x) = x8 +20? - 16x +5, so that S10) = 40 + 4x— 16 = 400 + 2-4), We have to find a root of f(x) = 0 which is near x) = 0. By using the Newton-Raphson formula (6), we obtain the following successive approximations of the root: _ feo) fO) _9_-_5_ ~ 93125 xy = x9 F'@0) FO) (16) FO) £(0.3125) y=x- = 0.3125 - 2 *2 = 1 Fiery 3125 ~ 503125) = 0.3125 — 23125)" +2 x (0.3125)? ~ 16x (0.3125) +5 ~ 4 x (0.3125) + 0.3125 = 4} 0.2048491 = 03125 ~ Tip eragay = 05265 f(a) £(0.3265) =e = 0.3265 - So B= 72 FG) 9576 (0.3265) _ (0.3265)* +2 x (0.3265)? — 16 x (0.3265) +5 meme 4 x (0.3265) + (0.3265) — 4} = 0.3265 ~ 2.005885 _ 9.3965, (14554777) We note that x3 is indentical with x2. Hence, we take m = 0.3265 as the required root correct to four decimal places. 2 Apply Newton-Raphson method to find an approximate root of the equation x = 3x5 =0, which lies near x = 2. » Here, the equation to be solved is f(x) = 0, where f(x) =P -3x-5, so that S10) = 30? ‘Therefore, the Newton-Raphson formula yields, in this case, )). SOW) _ Fa) 7 for k=0,1,2, @ Xk = Xk ~262 7. Numerical Methods - I To find the root near x = 2, we take xo = 2. Then (i) gives 2g+5 1645 _ 21 = StS _ 1645 21 3333, “302-1 34-9 2xp+5 _ 2x (2.3333)3+5 _ 30.406318 302-1) 32.3333 — 1) 13.332866 meas 2x3 +5 _ 2x (2.28055)? +5 _ 28.721862 i 303-1) 3{(2.28055)?- 1} ~ 12.602724 ~ ceed 2345 = +S _ 2x (2.279029 +5 _ 2867415 _ 5 saggy 3@3-1) 3{(2.27902)? = 1} ~ 12.581796 Since x3 and xq are identical, we take m = 2.27902 as the required root (correct to five places of the decimal). . Using the Newton-Raphson method, find an approximate root of the equation — 3x = 0 that lies between 0 and 1. » Here, the given equation is f(x) = 0, where f(x) = e*—3x, so that f’(x) = the Newton-Raphson formula yields 3. Therefore, F(x) =y- et — 3x, _ OK- Gx = De* fen“ Heed = Xe a3 ern” for k=0,1,2,-+- @ Since the required root is supposed to lie between 0 and 1, we take x9 to be the average of O and 1; that is xo = 0.5. Then formula (i) yields (Xo — De® _ O.5-1)e*5 _ (-0.5) x (1.64872) _ -0.82436 aoe = SPER ay = —pastag = 0.61006, a : eee = 0.618996, ue Gade” _ 0.61906 ~ 1061906 _ (0.38094) x (1.85718) = 0.61906. (28-3) 0.619061 3, ~ (1.85718 — 3) We observe that x3 and x4 are identical. We therefore take m = 0.61906 as an approximate root of the given equation.7.3. Newton-Raphson Method 263 BEE] 2» Newton-Raphson method, find the real root of the equation xe* = 2 correct to three decimal places. » Here, the given equation is f(x) = 0, where f(x) = xe* — 2, so that f"(x) = (x+ Det. We note that fO)=-2 and f(1) = e-2 = 2.71828 — 2 = 0.71828. Since f(0) and f(1) have opposite signs, f(x) = 0 has a root between 0 and 1. Since f(1) is numerically less than f(0), this root is nearer to 1 than to 0, and we take x = 1 as the initial approximation of the root’. Now, the Newton-Raphson formula yields _ SG) fQ) @22ee e 0.11828 M=%- Fay Fay 71 Se = Fagg = 986788, nen al = 0.86788 - i ae e = 0.86788 — 086788) x 2.38186) —2 Re oa ai 2 < 0.96788 - an = 0.85278, x3 =) - 4 ee = 0.85278 — Oa 85278 — ws = 0.85261. We observe that x7 and x3 are equal up to three decimal places. We therefore take m = 0.853 as an approximate root of the given equation, correct to three decimal places. . By using the Newton-Raphson method, find an approximate root of the equation xlogyg.x = 1.2 that lies near 2.5. » Here, the given equation is f(x) = 0, where F(X) = xlogyy x 1.2. We note that" f1Q) = a(t Loewe) + logyo x = 0.43429 + logy x. The initial approximation of the root is given as x9 = 2.5. Now, the Newton-Raphson formula gives Sx) (2.5) logio2.5= 1.2 _ 4 5 _ (2.5) x (0.39794) ~ 1.2 eee het Ga) 3 043429 + ogig2.5 (0.43429 + 0.39794) “One can also work with the average of | and 0, namely 0.5, as the initial approximation xp. e (log, x) = : log,¢; login e = 0.43429.264 7. Numerical Methods -I 0.20515 =2: = 2.7465, 5+ g3n03 =? (2.7465) log 2.7465 — 1.2 0.005109 7465 — <> E10 = 2.7465 - ——— = 2.7406, 2.7465 ~ 7734009 + logya 2.7465 0.87307 (2.7406) log 2.7406 — 1.2 0.00004 2.7406 - <8 10 T= 2.7406 + = 2.7406. 06 OABA29 + log g 2.7406 * o7214 Since x3 is identical with x2, we take m = 2.7406 as the required root, correct to 4 decimal places. . ea Using the Newton-Raphson method, find the real root, correct to three decimal places, of the equation cosx~xe*=0, which lies near x = 0.5. (Here, x is in radians). > The given equation is f(x) = 0, where f(x) = cos x — xe* so that ’(x) = —sinx-(x+ De*. We have to find a root near x9 = 0.5. By using the Newton-Raphson formula, we obtain the following successive approximations to the root: £20) _ 9,5 , €08(0.5) ~ (0.5) x 5 *1=20~ FG) * Sin @.5) + (0.5 + 1) xeO3 7758 ~ (0.5) x 1.64872 _ 5 ¢ | 0.05322 943 + (15) x 1.64872 °° * 2.9595 cos (0.51803) ~ (0.51803) x e0-51803 ‘sin (0.51803) + (1.51803) x €051805 = 0.51803 ~ 57555 = 0.51776. We note that x2 and x are identical up to three places of decimals. We therefore take ‘m = 0.518 as the required root correct to three decimals places. . TELE Find an approximate positive root of the equation e* sin x = 1 using the Newton- Raphson method, (Here, x is in radians). » The given equation is f(x) = 0, where f(x) = e* sinx - 1 ‘We note that f)=-1 and f(l) =e (sinl)-1 (2.71828 x 0.84147) — 1 = 1.28735.7.3. Newton-Raphson Method 265 Since (0) and f(1) are of opposite signs, the equation f(x) = 0 does have a root m between y= Qand x = 1. Let us take the first approximation x» of mas the average of 0 and J, namely 05. We note that ['() = eX(sin x + c05 x) Now, the Newton-Raphson formula gives _ _ £0) 8 sin xo — | x1 = Xo — = xy — (x0) e%0(sin x9 + COS Xo) _ in (0.5) — 1) (1.64872) = 05 - so SRO) ig 5 - 2 e5{sin (0.5) + cos (0.5)} (1.64872)(0.47943 + 0.87758) 0.20955 = 05 + x 5aa55 = 0.59367, fa) {e959367 sin (0.59367) — 1) 2 =x = 0.59367 — a ee FC) €959967{sin (0.59367) + cos (0.59367)} (1.81062)(0.55941) ~ 1 0.01288 < = 0.59367 — = 0.59367 - = 0.58855, (1-81062)(0.55941 + 0.82889) T= 551368 ~ 788° _ fO) _ {€258855 sin (0.58855) — 1) %3 = 22 Fray = 058899 ~ Zasats5| sin (58855) + cos (0.58855) {(1.80137)(0.55516) = 1} 0.00005 . =0: — 10.8015 (0.999 19) — Th __ = 9.58855 - ——_— = 0.58853, 9.58855 ~ Ta9137\0.55516 + 0.83175) 2.49834 _ Se) _ {058855 sin (0.58853) — U) 88 Fs) 0.58853 €958853 {sin (0.58853) + cos (0.58853)} 55514) — ~ 0.58853 — —_(1-8013400.55514) =) _ (1.80134)(0.55514 + 0.83176) We note that x4 = x3 correct to five places of decimals. Using the Newton-Raphson method, find the root that lies near x = 45, of the equation tan x = x, correct to four decimal places. (Here, x is in radians). > The given equation is f(x) = 0, where f(x) = tan x x, so that f(a) = sec?.x — 1. Then the Newton-Raphson formula becomes sou) Maman) = si a ee mt266 7. Numerical Methods -I _ Xk = (lan xy)(cos? xy) _ Xe = 1 = cos? xp sin? xp Since it is required to find the root that lies near x = 4.5, we take x = 4.5. Then (i) yields @ 1 rom }sinday _ 45 (041212) 4.29304 - ZOAIED) _ 4.29994 _ 4.49366, “ ‘977532 ~ 0.955556 ~ “4 449366 - 0.21182 - oe ee a % sin? (4.49366) 0.95292 4.49339 — 1 sin (8.98678) 4.49339 — 0.21206 xy = = OTS = 4.49342. ° sin? (4.49339) 0.9528 Since x3 and xp are equal up to four places of decimals, we take m = 4.4934 as the required root, correct to 4 decimal places. . Using the Newton-Raphson method, find the real root of the equation xsin x +cos.x = O near x = x, up to four decimal places. > The given equation is f(x) = 0, where f(x) = xsinx + cos x, so that f"(x) = xcosx. The Newton-Raphson formula yields (x) Xx SIN Xp + COS 1 Xe = Xe @ fia ™* Xp COS Xf. The initial approximation of the root is given as x) = m ~ 3.14159 (in radians). Now, formula (i) yields X= Xo- (¢ + tan) =_- + = 3.14159 — 0.31831 = 2.82328, 22 = xX - (= + tan») = 2.82328 — x co + tan 2. e228) = 2.82328 — (0.35419 — 0.32952) = 2.7986, x3 2 (2 +tan ») = 2.7986 - x ; cm * tan 2.7986) = 2.7986 — (0.35732 — 0.35711) = 2.79839, 1 2.79839 = 2.79839 — (0.35735 — 0.35734) = 2.79838, We observe that x4 = 13 = 2.7984, up to four decimal places. Therefore, an approximate root of the given equation, correct to 4 decimal places is, m = 2.7984. . 1 x4 = x3 - (: +tan ») = 2.79839 — ( + tan 2.79839) _d7.3.1. Some Deductions from the Newton-Raphson formula 267 Exercises 1, By using Newton-Raphson method, find the real roots of the following equations, correct to 3 decimal places. (In cases involving trigonometric functions, x is in radians) (ly) x8 -8x-4=0 near3, QQ) x8-2x-5=0 near2. (3) x +5x-11=0 near (4) 4224+3x4+4=0, near-l. (5) x -S5x°4+4x-3 neard, (6) xt-x-9=0 near2. (7) 3sinx-2x+5=0 near 3. (8) cosx=x? near 1 (9) e'cosx=1.2 near 0. (10) logx—cosx=0 near 1 2. By Newton-Raphson method, find the real roots of the following equations, correct to 4 decimal places. (In cases involving trigonometric functions, x is in radians), a x« 0 near 13 Q) 8-6x+4=0 near0.75. @) x 13=0 near2. (4) xsinx=1 near 1. (5) 2 +x=cosx near0.5 (©) xtanx+1=0 near 2.5 (2) ef =5x near 0.3. (8) x+logigx=2 near LS Answers 1) 3.051 (2) 2095 (3) 1511 @) -1223 (3) 427 (©) 1.813 (7) 2.883 (8) 0.824 (9) 0.203 (10) 1.303 2 1) 1.3258 (2) 0.7321 3) 1967 (4) 1.1142 (5) 0.5500 (6) 2.798 (7) (0.2592 (8) 1.7556 7.3.1 Some Deductions from the Newton-Raphson formula Below we deduce some useful formulas from the Newton-Raphson formula (6) of Section 7.3. Reciprocal of a number Suppose we wish to find the reciprocal of a non-zero real number N. That is, suppose we 1 wish to find x such that =, ot N x N. Then, xis real root of the equation268 7. Numerical Methods - I 1 Here, f(x) =~, and the Newton-Raphson formula yields F(x) (xx) -N Ma = Ke - 4 = xp — EES = xy + Oe - Na) = (2 — Nw) () HL =k Gy = Hk ~() ik + Oe 2 If we take k = 0,1,2,+++ successively in this formula, starting with some xo, we obtain successive approximations to 1/N. In other words, (1) is the formula for successive approxi- mations for the reciprocal of the number N. Square root of a number Suppose we wish to find the sqaure root of a positive number N. That is, we wish to find x such that x= VN, or x? = N. Then, x is a positive real root of the equation f@=2-N=0. Here, f"(x) = 2x, and the Newton-Raphson formula yields u-N 1 1 N awn =“ = 5 fh - CE -M)} 3(=+2) 2) If we take k = 0,1,2,--+ successively in this formula, starting with some xo, we obtain successive approximations to VN. In other words, (2) is the formula for successive approxi- mations for the square root of the number N. Reciprocal of the square root Suppose we wish to find the reciprocal of the square root of a positive number N. That is, suppose we wish to find x such that x = 1/ VN. Then xis a positive real root of the equation f@=sN- Here, f’(x) = 2/23, and the Newton-Raphson formula yields dix) _ NR Qi) Xk = Xe GB) — 1 This is the formula for successive approximations to — p"" root of a number Suppose we wish to find the p"* root of a positive number N. That is, we wish to find x such that x = N'/. Then, x is a real root of the equation fx) =x? -N=0.| | | | 7.3.1. Some Deductions from the Newton-Raphson formula 269 Here, f’(x) = px?! and the Newton-Raphson formula yields 2 -N (p-txP4Ny N eee eee ee ee @ ml =) Px px P i This is the formula for successive approximations to the p” root of the number N. For p= 2, this formula reduces to formula (2). Reciprocal of the p" root Suppose we wish to find the reciprocal of the p" root of a positive number N. That is, we wish to find x such that x = 1/(N'/P). Then x is a real root of the equation fx) =N- x? =0. Then f’(x) = px~*), and the Newton-Raphson formula yields Nae) — x, SFP tne] (6) kel = Xe This is the formula for successive approximations to the reciprocal of the p” root of the number NV. For p = 2, this formula reduces to formula (3). By using the Newton-Raphson method, evaluate the following, correct to five places of decimals: @ 1/31 Gi) 1/18 ii) Lev) VIO) 1 VID > () For N = 31, formula (1) for the reciprocal of N yields Kee = xe(2 — 31x) @ We note that 1/31 ~ 0.03 correct to two decimal places. Hence we use xp = 0.03 as an initial approximation for 1/31. Then, formula (i) yields x1 = x9(2 — 31x) = (0.03)(2 — 31 x 0.03) = 0.0321, xq = xj(2—31x1) = (0.0321)(2 — 31 x 0.0321) = 0.032257 x3 = x9(2.— 31x) = (0.032257)(2 ~ 31 x 0.032257) = 0.03226. Since x2 and x3 are identical up to 5 decimal places, we take 1/31 ~ 0.03226. (ii) For N = 18, formula (1) yields Xpe1 = xe(2 — 18x4) ii)270 7. Numerical Methods -I ‘We note that 1/18 ~ 0.06 correct two places of decimals. Hence we use xo = 0.06 as an initial approximation for 1/18. Then, formula (ii) yields = xo(2 — 18xo) = (0.06)(2 — 18 x 0.06) = 0.0552 X2 = x1(2 — 18x1) = (0.0552)(2 — 18 x 0.0552) = 0.05555 X3 = X2(2 — 18x2) = (0.05555)(2 — 18 x 0.05555) = 0.05555. The above approximations indicate that 1/18 = 0.05555, correct to five decimal places. (ili) For N = e, formula (1) yields en = xe(2~ ex) ii) Let us recall that e ~ 2.71828 which is near to 3. Hence (1/e) is near to 4, and we use Xo = 1/3 as an initial approximation for 1/e. Thus, formula (iii) yields 2.71828 1 = X9 [2 — (2.71828)xo] = ; p- | = 0.36464, X2 = x [2 — (2.71828)x1] = (0.36464) x [2 — (2.71828) x 0.36464] = 0.36785, 3 = x2 [2 — (2.71828)x2] = 0.36785 x [2 — (2.71828) x 0.36785] = 0.36788, xq = 0.36788 x [2 — (2.71828) x 0.36788] = 0.36788. Since xq and x3 are identical up to five places of decimals, we take x4 = 0.36788 as the approximate value of 1/e, correct to 5 decimal places. (iv) For N = 10, formula (2) for the square root of N becomes eet ee iv) ent = 2 [te + Gy) ‘We note that the number nearest to 10 which is a perfect square is 9 with 9 = 3. We take xo = 3 as an initial approximation to V10. Then formula (iv) gives 1 10 ea =3(w+¥)- a 3.166667, 10' = (0 + 2)- 53 166667 + ——— 162280, 1 10 x= 5 (> 16228 + 5- sam) We note that x3 and x2 are identical up to five places of decimals. Hence x3 = 3.16228 is taken as the square root of 10, correct to five places of decimals.7.3.1. Some Deductions from the Newton-Raphson formula 271 (¥) To find 1/-V12, we employ the formula (3) with N = 12. Thus, the formula that gives successive approximations to 1/ VT2 is nen = [3 - 1239] ) We note that the positive number nearest to 12 which is a perfect square is 9 and 1/ V9 = 1/3. Hence we take xp = 1/3 as an initial approximation to 1/-V12. Then, formula (v) yields x 12 3| = 0.277778, " * = [3 — 12x47] = 0.138889 x [3 — 12 x (0.277778)"] = 0.288066, x5 = 0.144032 x [3 - 12 x (0.288066)"] = 0.28867 x4 = 0.14433 x [3 - 12 x (0.28867)"| = 0.28867. Since x4 and x3 are identical, we take x4 = 0.28867 as an approximate value of 1/ ai correct to five decimal places. By using the Newton-Raphson method, evaluate the following, correct to four decimal places: @ (108 Gi) GBD? Gil) _22)"* Gv) 24 ()_ BOYNE » (i) For N = 10 and p = 3, formula (4) yields 2x t z @ ae Mee = 3 2 + to 10 which is a perfect cube is 8, and 81/3 = al approximation to (10)"/3, Then formula (i) | We note that the positive number ne: 2. We therefore take x9 = 2 as an above yields am +12 10 += oar 2.166667, 10 asa ee 10 (2.1545? ao 3 if X 2.166667 + 2x 2.1545 + aia | 2548 2.15443, ae oe sath x 2.15443 + a272 7. Numerical Methods -I Since x4 and x3 are identical, we take x4 = 2.1544 as the value of 10'/3, correct to four places of decimals. (i) For N = 37 and p = 3, the formula (4) becomes 1 31 -. Xk = ies + 3 (ii) ‘We note that the positive number nearest to 37 which is a perfect cube is 27, and 273 = 3, Therefore, we take x = 3 as an initial approximation to (37)'3. Then formula (ii) above yields poe =4 6+2 = 3.3704 fox + 2 ile x 3.3704) + asm = 3.3327 x= ; px + 2 = ie x 3.3327) + am = 3.3322 x= 5px + 2 = ; [e x 3.3322) + am = 3.3322, Since x is identical with x3, we take x4 = 3.3222 as the cube root of 37, correct to four places of decimals. (iii) For N = 22 and p = 4, formula (4) yields _ 1 aa + 22 7 Meet = 7 [3a 3 Gi) We note that the positive number nearest to 22 whose fourth root is a positive nteger is 16, and 16 = 2. Hence, we take xp = 2 as an initial approximation to V22. Then formula (iii) above yields x= 22] 1 22 ip» jfo+2]=218%5 8 1 22) 1 22 =e =l=-|ax2, 2 ifn+3| 5K x 2.1875) + am = 2.1661 1 22 n= qBetS i{e * 2.1661) + a] 4 22) 9.1657 (2.16613 | ~~7.3.1. Some Deductions from the Newton-Raphson formula 273 22 1 meq [> +S = 2.1657. % 1 22 5 \3 x 2.16! Ss 4 [ - he (2.1657)3 Since xq = x3, we take x4 = 2.1657 as the approximate value of V22, correct to 4 decimal places. (iv) For N = 24 and p = 3, formula (5) becomes sir = (4-243) (iv) We note that the number nearest to 24 which is a perfect cube is 27 with (27)-1/3 = i Hence, we take x9 = 1/3 as an initial approximation to (24)-!/3. Then formula (iv) above yields Fd " (4-243) AG - 3) = 034568 (4-243) = oe ce {4-24(0.34568)°} = 0.34668 _ 0.34668 “3 3 = Ro \ ws w]e o/s (4-24x3) {4- 24(0.34668)*} = 0.34668. We note that x3 and xp are identical. Therefore, we take x3 = 0.3467 as an approximate value of (24)-1/3 correct to four decimal places. (¥) For N = 30 and p = 5, formula (5) becomes Xk set = [6- 30%] ww) We note that 32-5 = 1/2 and 32 is near to 30. Hence we take xo = 1/2 as an initial approximation to (30)~"/5. Then formula (v) above gives 20 =1[5_2]- x 8 [o-s0xa4]=Hlo- 5 = 0.50625, 0.506265 5 [o-30x@ 506495)°] = 0.506496. x= }[6-30xx1] = 0.506495 5 [6 - 30x (0.50625)*] = 0.506495, ne Since x3 and xp are identical up to 5 places of decimals, we take x3 = 0.5065 as the value of (30)~"/5, correct to four decimal places. fn274 7. Numerical Methods -I Exercit Find the approximate values of the following by using the Newton-Raphson method: @ 117 @) VIZ @) VB @) 4D 5) Gayl4 (©) GOS (7) I/¥i4 () 1/VI5 (9) 7-8) (10) (28) Answers (1) 0.05882 (2) 3.4641 (3) 5.2915 (4) 3.4482 (5) 2.3784 () 19743 (7) 0.2673 (8) 0.258 (9) 0.3001 (10) 0.4347Chapter 8 Numerical Methods - IT This chapter is a continuation of Chapter 7. Here, we consider the topic of Finite Differences with applications to Interpolation and Integration. 8.1 Finite Differences In this section, we introduce what are called the forward differences and backward differences of a function y = f(x). These differences are two standard examples of finite differences which play a fundamental role in the study of Numerical Applied Mathematics. Forward Differences Consider a function y = f(x) of an independent variable x. Let yo.)1.20°°-Yr7** Jn be the values of y corresponding to the values x9, X14.X2,°+-%7,"++ +4, of x, respectively, as displayed below: x: [x [a |e] | y: || yo | | yz | | Let us write Ayo=y1-Yo, Ay =y2— Yt, AY2 = ¥3—Yo0-7 and so on. Then, Ayo, Ayi, Ay2, «++ are called the first forward differences of y. Thus, the first forward differences of y are defined by Ayr = Yrut ~ Yrs for r= 0,1,2,---2-1 a) Here, the symbol A is called the first forward difference operator. ‘The first forward differences of the first forward differences are called the second forward differences and are denoted by A?yo, A?y1,-++; that is, typ = A(Ayo) = Ay — Ayo, A’yy = A(Ayi) = Aya ~ Ayt,--> and so on, Thus, the second forward differences of y are defined by A?y, = Ayre ~ Ayr, for rr =0,1,2,---0-2 (2) The higher-order forward differences of y are defined similarly. 275276 8. Numerical Methods - IT Thus, for 1 < k | differences | differences | differences 01 | 2.68 0.36 0.2 | 3.04 - 0.02 0.34 - 0.02 03 | 3.38 0.04 0.30 04 | 3.68 From the above Table, we find that, with x9 = yo = 2.68, Ayo =0.36, A*yo = 0.02, Ayo = — 0.02. oy We are required to find y when x = 0.15. The corresponding p is given by ii) =8.2.1. Newton's forward Interpolation formula 283 Using expressions (i) and (ii) in the forward difference formula, we get the value of y at 0.15, namely (0.15), as FOS) = y0-+ PCA) + APD (42s) + P= DO 74259) (0.5)(0.5 — 1) 5 — 1)(0.5 — = 2.68 + (0.5)(0.36) + ae 0.02) + + 05105 DO5~? 9.02) = 2.68 + 0.18 + 0.0025 - 0.00125 = 2.86125 (approx) . A function y = f(x) is given by the following table: x 1.0 12 | 14 1.6 18 [| 20 y=f@) 0.00 0.128 0.544 1.296 2.432 4.00 Find an approximate value of f(1.1). > Here, the step-length is h = 0.2. We form the following Difference Table. z — ro —J Tet re Ive a differences _| differences | differences | differences 1.0 | 0.00 0.128 12 0.128 0.288 0.416 0.048 14 0.544 0.336 0.00 0.752 0.048 16 1.296 0.384 0.00 1.136 | 0.048 1.8 2.432 0.432 1,568 2.0 4.00 From the Table we find that, with xy = 1.0, yo = 0.00, Ayo = 0.128, Ayo = 0.288, A*y = 0.048, A’yy = 0.00 @ We have to find y = f(x) atx = 1.1, The corresponding p is given by x-4a _ L1-10 ho OL . ‘The forward difference formula now gives, on using expressions (i) and (ii), (0.5)(0.5 — 1 F(A) = 0.00 + (0.5) x (0.128) + eons =) X (0.288) (Gi)284 8, Numerical Methods - It SS — a pes =4) , (0.048) + x (0.00) = 0.00 + 0.064 — 0.036 + 0,003 = 0.031. Lt a PEMSLEY Given that sin45° = 0.7071, sin 50° = 0.7660, sin55° = 0.8192, sin 60° = 0.8660, find sin 48°. » The given data may be put in the following tabular form. x (in degrees) 45 50 55 60 FQ) = sinx 0.7071 0.7660 0.8192 0.8660 We note that the step-length is h = 5. We first form the following Difference Table: r ro ure * | J | differences | differences | differences 45 | 0.7071 | 0.0589 50 | 0.7660 — 0.0057 0.0532, = 0.0007 55 0.8192 — 0.0064 0.0468 | |_60 | 0.8660 From the table, we find that, with x9 = 45, Yo = 0.7071, Ayo = 0.0589, A*yp = -0.0057, A¥yp = 0.0007. @ We have to find f(x) = sin x at x = 48. The corresponding p is given by = = 8-4 _ 06, (i) Substituting expressions (i) and (ii) in the forward difference formula, we obtain 20.0057) 10.6 — es 20.0007) = 0.7071 + 0.03534 + 0.000684 — 0.0000392 = 0.7430848 (approx). f(48) = 0.7071 + (0.6)(0.0589) + (0.6)(0.6 ~ 1 2! + (0.6)(0.6 Thus, sin 48° ~ 0.7431 (approx). 58.2.1. Newton's forward Interpolation formula aes From the data given in the following Table‘, find the number of students who obtained (i) less than 45 marks, and (ii) between 40 and 45 marks. Marks 30-40 0 | 50-60 | 60-70 | 70-80 No. of students 31 42 51 35 31 » Let y = f(x) denote the number of students getting less than x marks. Then, y = 31 for x= 40, y = 31 +42 = 73 for x = 50, y = 73 + 51 = 124 for x = 60, y = 124 + 35 = 159 for x= 70, and y = 159 +31 = 190 for x = 80. Accordingly, the given data may be expressed as shown in the following Table: E x 40 30 60 70 80 y [| 31 | 73 | 124 [159 | 190 Here, the step length is h = 10. The corresponding Difference Table is shown below. xl y P| pe mr Wve differences differences differences differences 4} af a 7 42 so | 73 | 9 51 =25 60 124 -16 37 35 | 12 70 | 159 -4 31 80 | 190 From the Table, we find, with xy = 40, yo =31, Ayo =42, A*yo=9, AXyp =-25, Atyo = 37. = hi For x = 45, we have eee Pa 0 ‘The forward interpolation formula now gives 5 — (0.5)(0.5 — 1)(0.5 — 2 5105 VD og 4 050.5 LS ) Tin the given Table. the range of marks 30-40 means: “marks greater than or equal to 30 but less than 40”, The other ranges have similar meanings. Also, marks “between 40 and 45” means: marks greater than or equal to 40 but less than 45. 0.5. ‘{(45) = 31 + (0.5) x42 + x (-25)286 8. Numerical Methods - IT + @ 5)(0.5 = 1)(0.5 — 2)(0.5 — 3)» 4! = 31 +21 — 1.125 - 1.5625 - 1.445 = 47.8675 ~ 48. This shows that the number of students who obtained less than 45 marks is about 48. Since the number of students who obtained less than 40 marks is 31 (by data), it follows that the number of students who obtained between 40 and 45 marks is 48-31=17 (approx.) m= Find the interpolating polynomial for the function y = f(x) given by f(0) = 1, Fa , f(2) = 1, FB) = 10. Hence evaluate f(0.75) and f(-0.5). » Here, the step-length is = 1. The corresponding Difference Table is shown below: x | f@ ae me mr differences _| differences differences o; 1 1 wey. 2 -2 -1 12 2} 1 10 9 From the table, we find, with x9 = 0, yo=l, Ay=1, A*y= AByq = 12. Also, for any x near xo, ee F dons 7 aid Using these in the forward difference formula we obtain oo y= 90+ Reds) + P2504 A VE—P 359) 1 =14x(1)+ a + o-De-Day = 20-7 +6x+1 Thus, 2x3 — 7x2 + 6x + 1 is the interpolating polynomial for the given f(x). From this polynomial, we find that (0.75) = 2 x (0.75)° - 7 x (0.75)? + 6 x (0.75) + 1 = 2.406 and f(-0.5) = 2 x (-0.5)° = 7 x (0.5)? + 6 x (-0.5) +1 = 4.0 .8.2.1. Newton's forward Interpolation formula 287 From the following table of values of y = f(x), find the values of y for x= 1 and 4 J 6 7 8 9 y 48 8.4 14.5 23.6 36.2 52.8 73.9 > The Difference Table for the given data, for which h = I, is as given below: xl y m me mi rv" L differences | differences | differences | differences | 3] 438 a 3.6 4 8.4 2.5 6.1 0s 5 | 145 3.0 0.0 OL 0S 6 | 23.6 35 0.0 12.6 0.5 | 7 | 36.2 40 00 16.6 0s | 8 | 528 45 21d 9 73.9 From the Table, we find, with x9 = 3, yo = 4.8, Ayo = 3.6, A?yy =2.5, Ay = 0.5, Atyy = 0. Also, for any x near xo, eo ee Pen 1 . The forward difference formula yields the corresponding y =f 3ya-4 y 48-4 (e-3) x 3.6) + F=DEHD y 2.5) + Ge OD) x5) +0 = 4.8 + 3.6) x (x — 3) + (1.25) x Q? = 7x + 12) + (0.0833) x (x9 = 12x? + 47x = 60) = (0.0833)x? + (0.2504),? ~ (1,2349)x + 4,002 @288 8. Numerical Methods - IT ‘The right hand side of the above expression is the interpolating polynomial for the given F@). For x = 1 and x = 2, expression (i) gives y = 3.1008 and y = 3.2002 respectively.* . The first five terms of a sequence are 2, 7, 16, 35, 70. Using the Newton's forward interpolation formula, find the general term of the sequence. What is the tenth term? > Let us denote the given terms as yo,y1,.)2.3 and yg respectively and the (p + 1)" term as ‘yp: Also let us prepare the following Difference Table. r Ir “ore Iv" y differences | differences | differences | differences yo =2 S | ys7 4 | 9 6 y= 16 10 0 19 6 y3=35 16 35 |_y4=70 _ | From the Table, we find that yo=2, Aw=5, Ay =4, The forward interpolation formula now gives 4p(p—1) , 6p(p- 1p ~ 2) 7 31 pP+5p+2. y=245p+ This y is the general (p + 1)" term, namely yp, of the given sequence. The tenth term of the sequence is therefore 9 =P - 97 + (5x9) +2 = 695, a Tere, x = 1 and x = 2 do not fall within the range of the given Table. What we have done is actually extrapolation.8.2.1. Newton’s forward Interpolation formula 289 Exercises 1. Using the Newton's forward interpolation formula, find (4) from the following table: x 3 5 7 9 £@) 27 12.5 34.3 Rd 2. Given: x 1.0 14 18 22 fQ) 3.49 4.82 5.96 65 Compute f(1.3). 3. Find y(1.4) using the following data: 1 2 3 4 5 y 10 26 58 112, 194 4. Find y(1.05) from the following data: x 10 | il 12 | 13 14 ye) 0.841 0.891 | 0932 | 0.963 0.985 5. Estimate the value of tan (0.12) from the table given below: x 0.10 0.5 0.20 025 | 030 y= tanx 0.1003 0.1511 0.2027 0.2553 | 0.3093 6. Evaluate f(x) = e* for x = 0.02 from the following table of values: x 0 01 0.2 03 | 04 e 1.0000 1.1052 1.2214 13499 | 1.4918 7. Given log, 654 = 2.8156, logy 656 = 2.8169, logia 658 = 2.8182, logo 660 = 2.8195, logyo 662 = 2.821, find logy 655. 8. Given yao = 512, y20 = 439, yao = 346, Yso = 243, find yss. 9. In each of the following cases, find the interpolating polynomial for the function f(x): x 0 1 4 £@) 3 @290. 8. Numerical Methods - IT ‘ x 0 1 2 3 4 Gi) aa oa te a as - x 0 2 4 6 8 10 a £@) 0 4 56 204 496 980 ‘Answers: Lo 64 2. 4.489 3. 14.864 4. 0.867 5. 0.1205 6. 1.02023 7. 2.8162 8 394.375 9 @ 42x43 Gi) B-6x-5 Gill) B-2x 8.2.2 Newton’s backward Interpolation formula As indicated, the forward interpolation formula given in Section 8.2.1 is used for interpolation at a point near the initial value x9 of x in the Table for the function y = f(x). It can be proved (we omit the proof) that the corresponding formula that determines an approximate value of y = f(x) at a point near the ending value x, of x is given as follows: 1 1 2 Y= Int gyn) + LEED Gy) 4 LAF DE+D gry, vp PENG GF 9 VD egny,) w Here, xm ants @ ‘The expression (1) is known as the Newton’s or Newton-Gregory backward interpola- tion formula. Substituting for q from expression (2) in the right hand side of expression (1), we get @ polynomial of degree n in x. This polynomial is the Interpolating polynomial in the present case. This polynomial serves as an approximation to f(x) when x is near xy. If y is required to be determined at a particular value x, of x which is near x», we first find the corresponding q from expression (2). Then we substitute this q into the formula (1). The value of y so determined, say y4, is the value of y at x,. The value of yy can also be got by first determining the interpolating polynomial and then substituting xj for x in this polynomial.8.2.2. Newton’s backward Interpolation formula 291 For the data given in Example \ of Section 8.2.1, find f(2.9) by using the back- ward Interpolation formula. » For the given data, the step-length is h = | and the corresponding Difference Table is shown in Example | of Section 8.2.1. In this table, the final value of x is 3. Taking this as x, we note that Yn= 13, Vyn=6, V*yn=2, V5y_=0. @ We are required to find the value of y for x = 2.9. The corresponding value of g is given by X-%n h Using expressions (i) and (ii) in the Newton’s backward Interpolation formula (1), we get q= (ii) +1 Y= Yn + gn) + Mae Dyry,) +0 « 13+ (0.1) x6+ ODEOI*D x240 = 13 + (-0.6) + (0.09) = 12.31 Thus, the value of y = f(x) at x = 2.9 is 12.31. That is, f(2.9) = 12.31. . From the following Table of values of y = f(x) compute f(0.53), using the backward Interpolation formula. x 030 | 0.40 0.50 0.60 y=f@ 0.6179 | 0.6554 0.6915 0.7257 » Here, the step-length is h = 0.1. We prepare the Difference Table as shown below: pt re mm Z y= f@) differences differences | differences 0.30 0.6179 0.0375 0.40 0.6554 = 0.0014 0.0361 0.0005 | | 0.50 0.6915, — 0.0019 | 0.0342 0.60 0.7257 | | From the entries in the Table, we find that, with x, = 0.60, Yn = 0.7257, Vyn = 0.0342, V?yn = ~ 0.0019, V*yn = — 0.0005. @292 8. Numerical Methods - IT We are required to find y for x = 0,53. The corresponding q is given by = Xrtn _ 053-060 | _o7, (ii) h 0.10 Using expressions (i) and (ii) in the backward interpolation formula we get (-0.7)(-0.7 + 1) 2! f(0.53) = 0.7257 + (-0.7)(0.0342) + (0.0019) eo (-0.7(-0.7 +o7 + 2) 0.0005) = 0.7257 — 0.02394 + 0.0002 + 0.00002 = 0.70198. . The following Table gives the values of y = tanx for various values of x: x 0.10 015 | 0.20 0.25 0.30 y= tanx 0.1003 0.1511 0.2027 0.2553 _ 0.3093 Find an approximate value of tan(0.28). > Here, the step-length is h = 0.05. We prepare the Difference Table as shown below: l EF 1 7a ve * au differences | differences | differences | differences [0.10 | 0.1003 0.0508 0.15 0.1511 0.0008 0.0516 0.0002 0.20 | 0.2027 0.0010 | 0.0002 0.0526 0.0004 0.25 | 0.2553 0.0014 | 0.0540 0.30 | 0.3093 _ From the table we find that, with x» = 0.30, yn = 0.3093, Vyn = 0.0540, Vy, = 0.0014, Vy, = 0.004, V4y, = 0.0002 (i) We are required to find y for x = 0.28. The corresponding q is given by iy _ 0.28- 0.30 _ hn 005 >A w8.2.2. Newton’s backward Interpolation formula 293 Using expressions (i) and (ii) in the backward interpolation formula we get tan (0.28) = 0.3093 + (-0.4)(0.0540) + copcoss dD 4 COA 0+ {04 +2) 3 +1 (0.0014) (0.0004) +3) a (0.0002) = 0.3093 — 0.0216 — 0.000168 — 0.0000256 — 0.0000003 ~ 0.2875 . A+2 mial for the function given by the following table: x 10 i 12 13 f@) 2) 23 27 33 Hence find f(12.5) and f(13.1). > For the given data, the step length is h = 1 and the Difference Table is as shown below: = y 1 re differences differences differences 10 2 - 2 u 23 2 4 0 2 | 27 2 6 13. 33 From the entries in the Table, we find, with x, = 13, yn = 33, Wn=6, Vy =2, Vn =0- Also, for any x which is near Xp, 3 = = (x- 13). q hh T (x- 13). ‘The backward interpolation formula gives the corresponding value of y as y=33-4 (r= 13) x64 SPIE B*D 469 49 = 33 + 6(4~ 13) + (4 ~ 13)68~ 12) =x7-19x4 111.294 8, Numerical Methods - II Thus, x2 - 19x + 111 is the interpolating polynomial for the given function. From this polynomial we find that f(12.5) = (12.5)? = (19 x 12.5) + 111 = 29.75. and FIBA) = (13.1)? ~ (19 x 13.1) + LL = 33.71 . For the data given in Example 6, Section 8.2.1, find the interpolating polynomial using the backward interpolation formula. Hence evalutate (2.5) and f(4). » From the Difference Table in the given Example, we find, with x, = 3, Yn= 10, VWyn=9, Vy, =10, Viyq = 12. Also, the step-length is # = 1. Further, for any x near x, H=%n _ 4-3 eo a3 By the backward interpolation formula, the corresponding value of y is given by ye 10+ (x=3)x9+ FIGS 4) 3+) x04 Baa 3 DEW 3 +2) x12 = 10 + (9x ~ 27) + 5(x* - 5x46) + 200° — 6x7 + 11x-6) = 2-72 + 6x41 q= Thus, 2x3 — 7x? + 6x + 1 is the required interpolating polynomial. From this polynomial we find F(25) = 2x (2.5) 7 (2.57 +6 x (2.5) +1 =3.5 and F(4) = (2x4) - (7x 4) +(6x4)41=41 . BEd For the data given in Example 7 of Section 8.2.1, estimate the values of y for 10 and x = 11. » From the Difference Table of the given example, we find that, with x, = 9, Yn = 73.9, Vyn= 21.1, Vy = 4.5, Vy =0.5, V4yn =0. Also, the step-length is r= 1. Further, for any x near xy, i= er The backward difference formula therefore gives the corresponding value of y as. eae Sea =P 26-9, Y= BI + (e-9XQLD +8.2.2. Newton’s backward Interpolation formula 295 fp aKe= OG ET) me 9E-? co540 = 73.9 + (21.1) x (x — 9) + (2.25) x (a? ~ 17x +72) + (0.0833) x (x? — 24%? + 191x - 504) = (0.0833)x? + (0.2508)x? — (1.2397)x + 4.0168 From this, we find that: y(10) = (0.0833) x 10° + (0.2508) x 10? — (1.2397) x 10 + 4.0168 = 99.9998 LL) = (0.0833) x 113 + (0.2508) x 11? — (1.2397) x 11 + 4.0168 = 131.5992 Exercises 1. Find f(84) from the following table: x 40 50 60 70 80 90 f@) 184 204 226 250 276 304 2. Find f(7.5) from the following table: x 1 [2 [3 4 5 6 7 8 f@ |i | 8 [27 | 6 | 15 | 216 | 343 | 512 3. Given x] 19 20 21 22 23 | 24 25 y || 91.00 [ 100.25 [ 110.00 | 120.25 | 131.00 | 142.55 | 154.00 find y when x = 23.4 and x = 25.4. 4. From the following table of sines, compute sin 38°: & 0 10 20 30 40 sing? 0 0.17365 0.34202 0s 0.64279 5. Find an approximate value of ¢°75 by using the following Table: x 0 Ol 0.2 03 04 e 1,0000 1.1052 1.2214 1.3499 1.4918 6. Estimate the value of f(42) from the data available in the following Table: x 20 25 30 35 40 45 Fo) 354 332 291 260 231 204296 8. Numerical Methods - I 7. From the following table, find y when x = 2.4: x 17 18 19 2.0 21 2.2 23 y 5.474 | 6.050 | 6686 | 7.389 | 8166 | 9.025 9.974 8. Given /(40) = 184, f(50) = 204, ((60) = 226, f(70) = 250, (80) = 276, f(90) = 304, find (38) and f(85). 9. Using Newton's backward interpolation formula, find the interpolating polynomials for the functions given by the following tables : @ £O) 1 3 Gi —— i) 5 =10 9 4 35 10. From the following table, estimate the number of students who obtained marks between 76 and 80. Marks 36-45 | 46-55 | 56-65 | 66-75 | 76-85 No of student 18 40 64 50 28 Answers 1. 287 2, 4218 3, 135.44; 158.84 4, 0.61566 5. 14191 6. 219 7.11.02 8. 180.24; 289.75 9.@) P+x41 Gi) B-6r-5, 10. 16. 8.2.3 Newton’s Divided Difference Interpolation Formula In the preceding subsections, we considered interpolation formulas valid for the case where the values of x, for which the values of y = f(x) are specified, are equally spaced with a step-length h. In this and the next subsection we will consider interpolation formulas for the case where the values of x are not necessarily equally spaced, Let yo, yi, Y2s "Yn be the values of an unknown function y = f(x) corresponding to the ‘values xo,.X1, 23, +, of x, which are not necessarily equally spaced. Let us define the symbols Lis xjh Lei xj, 4s [xi xj. Xp] and 80 on, as follows: [x24] z = x w8.2.3. Newton’s Divided Difference Interpolation Formula 297 [na] - [zea] fr tion a @ [rij ap] brave -onsn : fe “ @ and so on. Here xj, xj, x2, Xp, ++ are any specified or unspecified values of x, and yi, yj. Yes Yp ++ are the corresponding values of y = f(x). The symbol [xj, xj] defined by (1) is called the first divided difference for xj, xj: the sym- bol [3i, xj,%4] defined by (2) is called the second divided difference for x;, xj, x,; the symbol [xi, Xj, X4, Xp] defined by (3) is called the third divided difference for xi, xj, Xt, Xp, and so on. These divided differences may be employed to derive the following interpolation formula for ‘f(&) C the derivation is omitted): Y= FO) = yo + (= x0) [x0, 41] + (= 20) = 1) Doo, 1, 22] + (% = Xo) (8 = x1) (= 2) [205 ¥1, 2,23] Fo + (8 = x0) (8 44) + = Xn-1) Dro, M15 Xn 4) This formula is known as the Newton’s general interpolation formula, ot Newton’s divided difference Interpolation formula. The polynomial present in the right hand side of this formula is the interpolating polynomial associated with the divided differences. Remarks (1) The formula (4) holds when x0, x1,x2.---%, are not necessarily equally spaced. If Xo, X1,%2,°*-%y are equally spaced with step-length fh, it can be proved that this formula reduces to the Newton’s forward interpolation formula. (2) When the formula (4) is to be employed for computing y for a required value of x, we have to first compute the divided differences [x9, x1], [0, X1, X2]} [x0..%1,.22, x3} and so on, For convenience, these divided differences are entered in a Divided Difference Table. The values are then substituted into formula (4) to obtain the required value of y. Given that f(O) = 8, f(1) = 68 and (5) = 123, construct a divided difference table, Using the table, determine the value of f(2). » The given data can be put in the following tabular form: == y= fo: Using formulas (1) and (2) we find that yy 68 — Yayo _ 8-8 _ oy x — Xo 1 [20.41] =298 8. Numerical Methods - I [xp xg) = 22228 = 123-68 _ 13.75 2 = x1 5-1 Lexa] = Ga, x2] = feo, a1) _ 13.75- 60 _ 9g 95 2 — x0 5 The corresponding Divided Difference Table is shown below: First divided ‘Second divided differences difference [xo, 1] = 60 al | 1 =68 [x0,.21,22] = — 9.25 (a, x2] = 13.75 n=5 | p=123 Using the entries in the above Table, the Newton’s interpolation formula (4) gives Y= fla) =8 + (x — 0)(60) + (x Ox - 1)(-9.25) For x = 2, this yields F(2) = 8 + (2 —0)60 + (2 - 0) (2 ~ 1) (-9.25) = 109.50 . Using Newton's divided difference formula find an interpolating polynomial for x oo | os | 10 | 20 f@ || 000 | 057 | 146 | sos Hence find f(0.3) and f(1.6). » Here, 4 =00, m=05, m=10, x3=20, yo = 0.00, yi =0.57, y2 = 1.46, y3 = 5.05. ‘We now compute the following divided differences: yi-yo _ 0.57-0.00 _ 0.57 x — x0 [x0 *1] = [xm] = 2 = : M1 2t xe «10-05 =y2 _ 5.05 - 1.46 [xp x3] = BO = ~S = AP _ 3.50, x3 x2 2.0-1.08.2.3. Newton’s Divided Difference Interpolation Formula 299 [x1 x2] = x0, m1] _ 1.78 = 1.14 [x0, «1, 2] = —=—"— = -—___ = 0.64, ae 2-30 To-00 = 0% = baad = Dea) _ 3.59- 1.78 [x1 42,43] = oh Foros = 2067 [x0 41, 2,3] = ‘We now prepare the following Divided Difference Table : x fia | Fitstdivided | Second divided ‘Third divided differences differences difference x90 =0 | yo = 0.00 oT Exo, x1] = 1.14 a1 = 0.5 | y) = 0.57 [xo. x1 42] = 0.64 [a,x] = 1.78 [x0, 21,22, x3] = 0.2834 x2 = 1.0 | y2 = 1.46 [a1, 22, x3] = 1.2067 [x2, x3] = 3.59 43 = 2.0 | ys = 5.05 | Using the entries in the table in the Newton’s divided differenc formula, we get y= f(x) = 0.00 + (x 0.0) x (1.14) + (x - 0.0)(x - 0.5) x (0.64) + (x= 0.0)(x = 0.5)(x = 1.0) x (0.2834) = L14x + 0.64x(x - 0.5) + 0.2834x(x - 0.5)(¢- 1) = 0.283427 + 0.214927 + 0.9617x ‘This is the required interpolating polynomial. From this interpolating polynomial, we find f(0.3) = 0.2834 x (0.3)? + 0.2149 x (0.3 + (0.9617 x 0.3) = 0.3155 £16) = 0.2834 x (1.6)? + 0.2149 x (0.6)? + (0.9617 x 1.6) = 3.2497 . Using Newton's divided difference formula, represent f(x) as a polynomial in x {for the following data: x -4 [-1[o[2][ 5 fe) || 1245 | 33 | 5 | 9 | 1335 Hence find f(-2) and {(3).300 8. Numerical Methods - I » For the given data, the Divided Difference Table is as shown below:5 x ly=say| Msividea 2"! divided 3% divided 4! divided differences differences differences differences yo = 1245 [x0, x1] = — 404) [xo, x1, 2] = 94 [x2] = -28 (20.21, 22,35] = — 14 42 =0 Jy =5 [21, x2, x3] = 10 [xo x1, x2, x3, x4) = 3 [x2 25) = 2 [at aa, 3, x4] = 13 |tsa.25,24] = 88 (25, x4] = 442 x4 =5 ys = 1335 Using the entries in the above table in the Newton’s divided difference formula, we get F(R) = 1245 + (+ 4) x (404) + (x + et 1) X94 4 (H+ 4(x+ D(x 0) x (14) + (4+ 4x + Ie - Ox - 2) x3 = 3x4 - 5x3 + 6x? - 14 +5 This is the representatiton of the given f(x) as a polynomial. From this, we get F(-2) = 3 x (-2)* — 5 x (-2) + 6 x (-2)? — 14 x (-2) +5 = 145 £@) = @x3*)- (5x39) + © x3?) ~ (14 x 3) +5 = 125 . Given the data: x 5 1 W 2B 7 f(x) || 150 | 392 | 1452 | 2366 | 5202 find (9) and f(18) using the Newton's divided difference formula. Phe computation of the required divided differences may be carried out as in Example 2. In this and the following examples computation of divided differences is let as an Exercise,8.2.3. Newton’s Divided Difference Interpolation Formula 301 » For the given data, the divided difference table is as shown below: x i 1 divided | 2™4 divided | 3" divided | 4" divided differences | differences | differences | difference x0 =5 | yo =150 ] 121 x=7 | yy = 392 4 265 1 x2 = 11 | y= 1452 32 0 457 1 x3 = 13 | y3 = 2366 42 709 x4=17 | ye = 5202 Using the entries in the Table, the Newton’s divided difference formula gives F(X) = 150 + 121(x — 5) + 24x — T(x — 5) + Ux Le - (x - 5) +0 This is the interpolating polynomial that approximates the given f(x). This gives f() = 150 + (121 x 4) + (24x 2x4) + (-2 2x4) = 810, f(18) = 150 + (121 x 13) + 24x 11 x 13) + (7 x LL x 13) = 6156. . Fit a polynomial for the following data, using Newton's divided difference for- ‘mula. Hence find f(8) and f(15). FQ) | 48 100 294 900 1210 | 2028302 8. Numerical Methods - IT » We first form the Divided Difference Table shown below: 1" divided | 2" divided | 3 divided | 4" divided | 5 divided lea Y | differences | differences | differences | differences | differences x0 =4 [yo = 48 52 yi = 100 15 ” 1 yn = 294 21 0 202 7 0 y3 = 900 27 0 310 1 y4 = 1210 33 409 x5 = 13 | x5 = 2028 Using the entries in the Table, the Newton’s divided difference formula gives F(X) = 48 + 52(x—4) + 15(x— 5)(x—4) + 1e— E- SX-4) +0 ‘This is the polynomial that fits the given data. From this, we get FS) = 48 + (52x 4) + (15 X3 x4) + (1x3 x 4) = 448 and ‘f(LS) = 48 + (62 x 11) + (15 x 10 x 11) + (8 x 10 x 11) = 3150. . Exercises 1. Use Newton’s divided difference formula to find f(4), given [ence o [ 2 3 6 FQ) -4 2 14 158 2. By using the Newton’s divided difference formula, find a polynomial f(x) which assumes the values 3, 12, 15, -21 when x has the values 3, 2, 1, -1, respectively. 3. Given logy 300 = 2.4771, logo 304 = 2.4829, log, 305 = 2.4843, and logy 307 = 2.4871, find by using divided difference formula the value of logy, 306. 4. Applying the method of divided differences for interpolation, find the value of y when x = 5, given x 4.50 455 4.70 4.90 5.15 y 1345 1470 2010 3815 109658.2.4, Lagrange’s Interpolation formula 303 5, By means of Newton’s divided difference formula, find the interpolating polynomial that approxi- mates the function given by the following table: x 0 1 2 4 5 6 f@) 1 14 15, 5 6 19 6. For the data given in the following table, find the polynomial approximation of f(x) using Newton’s divided difference formula: x 2 4 5 6 8 10 fe) 10 96 196 350 868 1746 Answers 1 400 2 9 41Tx+6 3. 2.4857 4 S745 S$. 8-9 H2Ix+1 6 29-37 45x-4 8.2.4 Lagrange’s Interpolation formula ‘As usual, let yo,y1,)25"++Jn be the values of an unknown function y = f(x) corresponding to the values x0, x1, x2,-++%n Of x, Where 29, .%1,.2,°++%_ are not necessarily equally spaced. It can be proved (~ we omit the proof) that the polynomial representation of y is given by the following formula: (x= Xo) = x2) = 3) ++ = Xn) ; (x1 = X0)(%1 = ¥2)@1 = 3) +++ G1 = An) (x= xo)(e = 41) = ¥3) ++ = An) p (22 — xo)(%2 — x1 )(2 = ¥3) +++ G2 = Xn) coe GED OE = 1) = Ant) Gin = 40) in = 21) +++ On = Xn” ‘This formula is known as the Lagrange’s interpolation formula, The polynomial on the right-hand side of this formula is called Lagrange's interpolating polynomial.304 8. Numerical Methods -II Using Lagrange’s interpolation formula, find the value of y when x = 2.from the {following data: x 1 3 4 6 y 4 | 4 85 259 > Here, xo=l, x =3, m=4, x3 =6, yo=4, y= 40, y2=85, ys = 259 Using these in the Lagrange’s interpolation formula, we get _ GE DE-ME-H) 4 @-DE-DE-O) 7-90-40 -6) GB-DB-4G-6) = DE= 3K 8) | gg, DE 3-4) G-D)G4-3)4-6) (= )6-3)6-4) For x = 2, this gives the value of y as @-3)2-4 2-6). @-N2~-4H2~-6) Cx C3)xCS) 2x (Dx 3) Q-)Q-3)2-6 Q-DE-32-4) + BRIRED TS et eaSRSRa 16 160 170 , 259 = 5 tara tas © 1087 + 53.33 — 56.67 + 17.27 = 15. s By using the Lagrange’s interpolation formula, find f(11) from the following «40 x 259 y(2) = x40 x 2 5 8 14 y= f@) 94.8 87.9 813 68.7 > Here %=2 m=5, m=8 a=14, yo=948, yi =87.9, y2=81.3, ys = 68.7. Using these values and setting x = 11 in the Lagrange’s interpolation formula, we get (11 — 5)(11 ~ 8)(11 = 14) (11 — 2)(11 — 8)(11 - 14) = Gao (04.8) + f= “Gr ye-H0-14 ©) +” Gr ays-Hs-1H 7 a (l= 2yc11 = 5)(11- 8) oT * Ga= aa syaa—a) = 23.7 — 87.9 + 121.95 + 17.175 = 74.925 .8.2.4, Lagrange’s Interpolation formula 305 Using Lagrange’s interpolation formula, find (5) from the following data: x 1 3 4 6 9 f£Q) 3 9 30 132 156 > Here xo = 1 1=3, m=4, x3 =6, x=9 yo=r-3, 1 =9% y2=30, ys = 132, ye = 156 Using these and taking x = 5 in the Lagrange’s interpolation formula, we get _ 6315-415 -015-9 4, G-DE-45- 65-9) f= Gay Ha =o =H) *— * G=DS=HB-9—9 ~ 5-9) 9, (SINS —3NS- 45-9) (4-9) 29+ G6 36— AG 9) * 6-D6-3)5-4)5-6) * @-DO-3)9- 40-6 =-0.1-4 +32 + 46.93 — 1.73 = 73.1 x 156 onte For the data given in Example 4, Section 8.2.3, find f(9) using Lagrange’s inter- polation formula. > Here, x=5, m=7 mall, 4=13, 4=17 yo = 150, y1 =392, yp = 1452, y3= 2366, y4 = 5202 Using these and taking x = 9 in the Lagrange’s interpolation formula, we get = 799 = 11)(9 - 13) = 177 = 59 - = = 10)= GRE NO=IBI <4 9=BO=IDE =O a + (9 — 5)(9 — 79 — 13)(9 — 17) (11 — 5)(11 = 711 = 1311 - 17) (9 — 59 -— 7)(9 — 119 — 17) “ (13 — 5)(13 — 7)(13 — 11)(13 — 17) (9 -5)9- 19 — 11)(9 - 13) + (17 -5)C7 = 7)(17 = L1)(17 = 13) _ 50 3136 , 3872 _ 2366 , 578 g10, . s-3ta +373 x 1452 x 2366 x 5202306 8, Numerical Methods - I SN Certain corresponding values of x and logy x are: (300, 2.4771), (304, 2.4829), (05, 2.4843) and (307, 2.4871). Find logy, 301 by using the Lagrange’s interpolation formula. > Here 30 =300, 1 = 304, x = 305, x3 = 307, yo= 24771, yi = 2.4829, y= 2.4843, y3 = 2.4871. Using these and taking x = 301 in the Lagrange’s interpolation formula, we get (301 - 304)(301 — 305)(301 ~ 307) (00 — 304)(300 — 305)(300 — 307) 305)(301 — 307) 05304 — 307) (24829) (301 — 300)(301 ~ 304)(301 - 307) (B05 — 300)(305 — 304)(305 — 307) (301 — 300)(301 - 304)(301 ~ 305) (307 — 300)(307 — 304)(307 — 305) logy 301 = (2.4771) (2.4843) (2.4871) = 1.2739 + 4.9658 — 4.4717 + 0.7106 = 2.4786. . Using the Largange’s formula, find the interpolating polynomial that approxi- ‘mates to the function described by the following table: x 0 1 2 3 4 FO) a 6 is 18 27 Hence find f(0.5) and (3.1). > Here xm=0 meal, m=2, x3 =3, x4 =4 8, yg = 27 yo=3, wW=6 yall w= Using these in the Lagrange’s interpolation formula, we get, for any x, == DE=DA= DEM , (8 OE=2e~ HL— 4) $= @=HO-HO- 30-4) * C= DA=3yd =a) + (x= O)(e- DO=DE=H iy, (&= Oe = Dr 2x — 4) = 0@-DE-32-4) G-HB-NB-HB—4) (x- Olx= r= 2) = 3) * @-04- NEG-DE=3) @) + © (18) (27)8.2.4, Lagrange’s Interpolation formula 307 0 gee I(x = 2)(% = 3a = 4) = x(a — 2(x = 3) = 4) + Bac = De = 3) 4) = 3x = IN 2-4) 27 + yal — 1) - 2)(x- 3) ie) 14 u 3 9 xa-De-De-ae-4) 8 x-1* 4a x-3* BH = 242043 © X= = 2(X— 3-4) or so that f= 42x43 This is the required interpolating polynomial. From this, we find (0.5) = 4.25 and f(3.1) = 18.81. . Exercises 1. Use Lagrange’s interpolation formula to find f(4), given ® 0 2 3 6 fo) 4 2 14 158 2. Given = 3 7 9 10 i) 168 120 2 6 find F(6).. 3. Using Lagrange’s interpolation formula, find y when x = 10 from the following data: x 5 6 9 ul y 12 13 4 16 4, Given logy, 654 = 2.8156, logy, 658 = 2.8182, logy, 659 = 2.8189, logy 661 = 2.8202, find Jog 656, by using the Lagrange’s interpolation formula,308 8. Numerical Methods - II 5, Given (0) = -18, f(1) = 0, (3) = 0, f(5) = 248, f(©) = 0, f(9) = 13104, find (2) using the Lagrange’s interpolation formula, 6. Find the Lagrange’s interpolation polynomial for the function f(2) given by the following table: £Q) 1 7. Using the Table x 0 2 3. | 6 #Q) 648, 704 m9 | 792 find the polynomial approximation of f(x). 8. Find the polynomial which fits the following data: x 4 3 5 i 9 i yi «6 24 58 108 174 Hence find the values of y corresponding to x = 8 and x = 5.5. ‘Answers 1 40 2 147 3. 14.66 4. 2.8168 5. 28 6 Le det Sst 1 648490x—37 8 27x49, 81, 31, 8.2.5 Inverse Interpolation In the preceding subsections we had been considering the process of finding the value of y corresponding to a given value of x, when a set of corresponding values of x and y for a function y = f(x) is known before hand. We now consider the process of finding a value of x that corresponds to a desired value of y. This process is known as Inverse Interpolation. ‘The Lagrange’s interpolation formula given in Section 8.2.4 can be employed for inverse interpolation as well. Because, this formula is just a relation between the corresponding values of two variables x and y, either of which can be treated as an independent variable. Thus, if we interchange x and y in this formula, we obtain the following formula: _O=WO=y2) OY), =I =Y2)-*"= Yn) (G0 = 00 — ya) O0- Yn)” Or = YOO —Y2)-- Or —w) = yo) = y1) ++ = Yn) n= Yon = Y1)== On = Yn This formula yields the value of x corresponding to a desired value of y. This is known as the Lagrange’s inverse interpolation formula. + +e am8.2.5. Inverse Interpolation 309 x 2 5 9 1 y 10 12 15 19 {find x corresponding to y = 16. > Here, 5, m=9, x=, 12, y=15, y= 19 Hence, the Lagrange’s inverse interpolation formula with y = 16 gives y= AS12116 = 15)U6 = 19) |, 16 = 10V(16 = 15)A6 = 19) (10 — 12)(10 — 15)(10 — 19) (12 = 10)(12 = 15)(12 = 19) (16 = 10)(16 ~ 12)(16- 19) | U6 10)(16 ~ 12)(16- 15) (15 — 10)(15 — 12)(15 — 19) (19 10)(19 = 12)(19 = 15) _24 90, 648, 264 = 57 tot 257 7997143. il Thus, for the given data, x = 9.97143 corresponds to y = 16. 1 Apply Lagrange’s method to find the value of x corresponding to f(x) = 15 from the following data: x 5 6 9 il f@) 12 13 14 16 > Here, m=5, m=6 m=9, w=ll, y=rl2, w=13, w=14 y3=16 Hence, the Lagrange’s inverse interpolation formula with y = f(x) = 15 gives _ 5 = 13)(15 = 14)(15 = 16) 5 (15 ~ 12)(05 ~ 14)(15 ~ 16) ** G2= 1302 — 1412 = 16) (3 = 12)(13 - 14)(13 - 16) (1S ~ 12)(15 = 13)(15 ~ 16), , (15 ~ 12)(15 ~ 13)(15 ~ 14) (Ga—12)(14 — 13)(14 — 16) *” * (16 = 1216 = 13)(16— 14) 1018 54, 66 _ qa stata ils Thus, f(x) = 15 when x = 11.5. . x16 xi310 8. Numerical Methods - II Ginen = 2 22 2.4 2.6 28 fe) 0.6 = 0.45 = 0.29 = 0.12 0.05 {find x for which f(x) = 0. > Here, M=2, 1=22, m=24, 13 =2) yo=-0.6, yi =-0.45, yp =-0.29, y3 = Now, Lagrange’s formula gives, for y = f(x) = 0, ae (0.45)(0.29)(0.12)(—0.05) x 2 ~ €0.6 + 0.45)(-0.6 + 0.29)-0.6 + 0.12)(—0.6 — 0.05) (0.6)(0.29)(0.12)(—0.05) x 2.2 * (0.45 + 0.6) + 0.29)(-0.45 + 0.12)(—0.45 — 0.05) (0.6)(0.45)(0.12)(—0.05) x 2.4 * (-0.29 + 0.6)(—0.29 + 0.45)(—0.29 + 0.12)(-0.29 — 0.05) o (0.6)(0.45)(0.29)(0.12) x 2.8 ©.05 + 0.6)(0.05 + 0.45)(0.05 + 0.29)(0.05 + 0.12) = -0.1079 + 0.58 — 1.3562 + 2.2236 + 1.4005 = 2.74. Thus, f(x) = 0 when x ~ 2.74. Apply Lagrange’s formula to find a root of the equation f(x) = 0, given that £30) = -30, f(34)=-13, fG8)=3, (42) = 18. > Here, xo = 30, yo = f(30)=-30, x; = 34, yi = f(4) = -13, 2 = 38, y2=fG8)=3, 4 = 42, ya = f(42) = 18. We have to find x corresponding to y = f(x) = 0. The Lagranges’s formula gives, fory = 0, - 13 x (—3) x (-8) = C3041) x 30-3) x 30-1 * 39 x8.2.5. Inverse Interpolation 30 x (3) x (=18) (-13 + 30) x (=13 = 3) x (-13 = 18) 30 x 13 x (-18) * @530) xG+13)xG-18 * 30 x 13 x (-3) * G84 30) x U8 + 13) x (18-3) = -0.78 + 6.53 + 33.68 — 2.2 = 37.23. x34 x38 x42 This is the root (approximate) of the equation f(x) = Exercises 1, Given nee | oaL 3 4 en iears 2 19 find x corresponding to y = 7. 2. For the data in the following table, find the value of x which corresponds to y = 10. x 20 40 y: 2 3. Given x 3 5 a 9 uL ye 6 24 58 108 174 find the value of x corresponding to y = 100. 4. The following table gives a set of value of x and y. x 12 21 2.8 41 49 62 y: 4.2 68 98 1B4 15.5 19.6 Find the value of x corresponding to y = 5, Solve the equation f(x) = 0, in each of the following cases: 9 m fo] ot 02 03 04 SQ): i 0.80484 0.61873 0.44082 0.27032 Gi) x 2.0 21 2.2, 23 24 Fay, [2.0000 | -1.0390 | 0.0480 | 1.2670 | 2.6240 311312 8. Numerical Methods - II Answers: 1 1.86 2 35.25 3 8656 4. 3.55 5. (i) 0.5671 Gi) 2.19586 8.3 Numerical Integration Consider a function y = f(x) and suppose yo,91,Y2,"*-Yn ate the specified values of y corre- sponding to the equidistant specified values x9, x1, x2,---%n of x. Let h be the step-length so that x) = x9 +h, x2 = xy +h = x9 + 2h, x3 = x +h = xy + Bh, +X, = An-1 th = xO +h. Suppose we wish to evaluate the integral xorh ie frou { vo aw by using the specified values yo, y1,y2,-*-Yn Of Y. For any x, let us set x = xo + ht, so that r = 0 corresponds to x = xp and 1 = n corresponds to x= x». Then dx = hdt and expression (1) becomes f(x + ht) dt 2) By employing the Newton's forward interpolation formula [see (1) of Section 8.2.1] to the integrand in (2), we obtain f porns Datyy ME Parse). | In te OG oat 1/4 " = ifes Seay (5 - FJoro+3(E-P+A)aso +] =nh n 1 (nr? 1 (3 po + (Ayo) + 55 (5 - 5) a) + a(S =? +narmre| @ This formula which gives the value of /, is known as the quadrature formula. By trun- cating the right hand side of this formula at appropriate stages, we obtain approximate values of J, to the desired degrees of accuracy. ‘The process of evaluating /, by using formula (3) is known as Numerical Integration. Below we consider some particular cases of the formula (3).8.3.1. Simpson’s One-third Rule 313 8.3.1 Simpson’s One-third Rule In the quadrature formula (3) of Section 8.3, let us take n = 2 and neglect terms containing Ayo, A*yo,*++. Then this formula becomes a 1 hs f fla)dx = 2h [wn + (Ayo) + 2(A%y0) a Bs Let us recalll that Ayo=yi-Yo, and A? yo = A(Ayo) = AG — yo) = (Ayi) — (Ayo) = 2 — 91) - 1 - Yo) = 2 - 2y1 + Y0- Using these in expression (1), we get Fp 1 J rendr=2nfso+01-v0+ F02-2 tw} = Fhoot4n +) — @ A Changing x, to x;42 and y, to y,42 (for r = 0,1,2,-+- ,n 2) successively in this, we obtain a f forde= Fiona +41 +90 ® (This is valid only when nis even). ‘Adding all the integrals computed above, we obtain f seode= Salons y) e401 ton bots 4200 3 This formula may be employed to evaluate the integral on the left hand side when n is an even number (that is when the specified values yo, Y1,)2,**+ »Yn Of y are such that n is even). This formula is known as the Simpson’s 1/3 Rule, or, simply, the Simpson’s Rule ‘, sees sates date saaelaaaes suaaeEOSInEneES Se simpson (1710-1761).314 8. Numerical Methods-II 5 By using the Simpson's 1/3 Rule, evaluate f f(x) dx, given i x 1 2 4 4 5 FQ): 13 50 | 70 80 100 » From the given Table, we note that, xo = 1,11 = 2,22 = 3,x3 = 4 and x4 = 5, and the corresponding values of y = f(x) are yo = 13,y1 = 50,y2 = 70,y3 = 80 and y4 = 100. Thus, here, n = 4 which is even. Also, the step-length is h = 1. Hence the Simpson’s 1/3 rule gives : 5 fte0ax= f rorae= Filo0 +39 +401 +9) +201 : z x 1 x [(13 + 100) + 4(50 + 80) + 2 x 70] = 257.6667. = 6 By using Simpson's 1/3 Rule, evaluate f a pr dividing the interval (0, 6] into a six equal parts. > Here, the interval (0, 6] is to be divided into six equal parts. Hence, we take h = 1 and compute the values of y = at the points x9 = 0,x; = 1,x2 = 2,---,x5 = 6. These values of y are shown in the following Table. 1 0.5 xo =0] x1 yo=rlly x4 =4 4 = 0.0588 ‘The Simpson's 1/3 rule now gives i dx 1 = f fond tiloo +70 +401 +95 +39)+262 +90] a - ok, = 5 x 1 x [(1 + 0.027) + 4(0.5 + 0.1 + 0.0385) + 2(0.2 + 0.0588)] = 1.3662 = x 1+ x? and hence deduce an approximate value of log.2. » Here, the interval (0, 1] is to be divided into six equal parts. Hence, we take h = 1/6 and compute the values of y = x/(1 + x*) at the points xo = 0, x1 = 1/6,.x2 = 2/3,-++x6 = 1. The values are shown in the following table. 1 LY Zvatuare f ax by using the Simpson’s 1/3 Rule taking six equal strips, 3 x: [fx =0[ m= 1/6 [x2 =1/3|x3= 1/2] x4 = 2/3 x5=5/6 | x= 2 lly =0 [1 = 0.16216 | y2 = 0.3 | ys = 0.4 [ya = 0.46154 [ys = 0.4918 | yg = 0.58.3.1. Simpson’s One-third Rule 31s The Simpson’s 1/3 rule now gives x 1 as = gh lo + y0) + 401 +93 +5) + 202 +94)] 2 Ex +05) +4x0. 16216 +0.4 + 0.4918) +2 x (0.3 + 0.46154)] 7810+ 5 + 4.21584 + 1.52308] = 0.34661 wi sli Cd on Next, by direct integration, we find foe 5 ral [loca + 2 = $1082 Gi) From (i) and (ii), we get log 2 = 2 x 0.34661 = 0.69322 . x2 EY Evaluate [ Vcos6 dé by dividing the interval into eight equal parts. a > Here, the interval is (0,/2) whose length is /2. ‘To divide this interval into eight equal parts, we take h = 1/16 and compute the values of the integrand y = f(@) = Veos0 for 6 = 0, = 1/16, 6 = 7/8, «++, 63 = 7/2; the values are shown in the following Table. 6: 0| 2/16 n/8 | 3n/16 | 2/4 | 5x/16 | 3n/8 | 7x/16 | 2/2 g = £@): || 1 | 0.9903 [0.9612 [0.9118 0.8409 | 0.7454 | 0.6186 | 0.4417 | 0. ‘The Simpson’s 1/3 rule now gives ald [eater [reas inrnranrnencicannn 2 x [C1 + 0) + 40.9903 + 0.9118 + 0.7454 + 0.4417) + 20.9612 + 0.8409 + 0.6186)] x [1 + (4 x 3,0892) + (2 x 2.4207)] = (0.37913) .— 316 8. Numerical Methods - II by using the Simpson’s 1/3 Rule with the aid of 11 ordinates. 5 Evaluate [ a Hence find log 5. > Here, we have to use 11 ordinates (that is: 11 values of y). This means that we have to divide the interval [0, 5] into ten equal sub-intervals. Accordingly, we take h = 1/2. Then xo = dx 4x+5 0,x1 = 0.5,.x2 = 1.0,+++x19 = 5. We compute the corresponding values of y = f(x) = and the values are shown in the following table. 4x+5 yo =0.2 yi = 0.14286 yo = 0.11111 ys = 0.09091 ya = 0.07692 ys = 0.06667 Ye = 0.05882 yr = 0.05263 ye = 0.04762 yo = 0.04348 Yio = 0.04 Using the entries in the Table, the Simpson’s 1/3 rule gives are Feng = 3! [Oo +0) +401 +¥3 +95 +7 +99) +202 +94 +96 +y8)] = x 3102 + 0.04) + 4(0.14286 + 0.09091 + 0.06667 + 0.05263 + 0.04348) ao + 2(0.11111 + 0.07692 + 0.05882 + 0.04762)] = z x (0.24 + 1.5862 + 0.58894] = 0.40252 @ On the other hand by direct integration, we find that 1 7 1 ie Toes = jllowt4e + 13 = jlloe 25 — log 5] = 5 logs Gi) From (i) and (ii), we get Jog 5 = 4 x (0.40252) = 1.6101. .8.3.1. Simpson’s One-third Rule 317 06 By using Simpson's 1/3 Rule, evaluate [ a > We have to divide the given interval 0, 0.6] into six equal parts. Therefore, the step-length is h = 0.1 and x9 = 0, x1 = 0.1, xp = 0.2,--+ , xs = 0.6. We first tabulate the corresponding values of y= f(x) = e~*. The computations are summarized in the Table shown below. * dx, taking seven ordinates. [: [= | x = 0.1 0.01 x = 0.2 0.04 yx = 0.96080 x3 = 03 0.09 ys = 0.91393 xg = 04 0.16 ya = 0.85214 x5 = 0.5 0.25 ys = 0.77880 0.36 6 = 0.69768 f dx = EnlQo+y6) +401 +93 +99) 4202490) ; x 0.1 x [(1 + 0.69768) + 4(0.99005 + 0.91393 + 0.77880) + 2(0.96080 + 0.85214)] 0 ot x [1.6977 + 10.7311 + 3.6258] = 0.5352 . PETIT By dividing the range into 6 equal parts, find an approximate value of { e**d6, using the Simpson's 1/3 Rule. > Here, the range (interval of integration) is (0,7) whose length is x. We have to divide this range into 6 equal parts. Therefore, we take h = 7/6 and set @ = 0, 0 = 1/6, 62 = 1/3,--+ ,05 = 5m/6,0 = *. We first determine the corresponding values of the integrand @ = f(0) = e%4, and the results are summarized in the following Table.318 8. Numerical Methods - IT a sing e= f@= en? 0 go=e=l 05 yi =e = 1.6487 V3/2 = 0.866 || gy = 98 = 2.3774 gy el =e = 2.7183 94 = 2865 = 2.3774 gs = 65 = 1.6487 yo=e=1 sin 1 °d8 = sh [G0 + 96) + 4(y1 + Ys + Ys) + yr + s)] 3 ; : z [2 +4 (1.6487 + 2.7183 + 1.6487) + 4 x 2.3774] = ae + 24,0628 + 9.5096) = (1.9762) . Exercises 2 1. Using the Simpson’s 1/3 Rule, evaluate f f(x)dx, given a 2H 0.0 05 1.0 15 20 Say: 0.399) 0.352 0.242 0.129 0.054 2. The following table gives the values of y = f(x): x 0 1 2 3) 4 5 6 y: || 0146 | 0.161 | 0.176 | 0.190 | 0.204 | 0.217 | 0.230 6 Evaluate f f(x) dx by using the Simpson's 1/3 Rule, a » 52 . Evaluate flog xdx by using the Simpson’s 1/3 Rule with the aid of the following data. 4 x 4.0 42 44 4.6 48 5.0 5.2 Togx: || 1.3863 | 1.4351 | 1.4816 | 15261 | 1.5688 | 1.6094 | 1.64848.3.2. Simpson’s Three-eighth Rule 319 4, Evaluate the following integrals by using the Simpson’s 1/3 Rule. A pdx L dx (i) = withh= i —, = @ Hig wit 1/4 Gi) lie with h = 1/8 aay px . pdx Git) { Taw with h=025 Gv) { Trg” With n = 6. Hence evaluate | w) { i 7 a di with n = 4, Hence evaluate log? " ap Wi) fPlogxdx, withn=4 — (vii) ff sinxdx, withn = 10 3 a 5 rp (vili) flogxdx, withn=10. (ix) f Veosddé, withn = 6 i a 8 5, Evaluate [ —“ by using the Simpson’s 1/3 Rule using seven ordinates. 3 l0B 9x 1 6. Using the Simpson’s 1/3 Rule with h = 0.1, show that fe" dx = 0.7468. a Answers 1. 0.693 2 1.13625 3. 1.827847 4. (i) 1.3662 Gi) 0.6932 iii) 0.7854 (iv) 0.785397; 3.141588 (v) 0.23108; 0.69324 (vi) 177.483 (vii) 0.9985 (viii) 4.0467 (ix) 1.1873 5. 9.7203 8.3.2 Simpson’s Three-eighth Rule In the quadrature formula (3) of Section 8.3, let us take n = 3 and neglect terms containing (A*y0), (A°yo),-++- Then this formula becomes ey 3 3 1 he f FC) dx = 3h) 0 + 5(Ayo) + 7(A°y0) + g(A*y0) @ Ea Now, let us recall that Ayo = ¥1 — Yor Ayo = A(Ayo) = AGQi ~ Yo) = Ayi — Ayo = G2 — 1) - O1 = Yo) = 2 - v1 +0. 8 yo = A(A?y0) = AQ2 ~ 2y1 + ¥0) = Aya ~ 2Ayi + Ayo, = (3 — y2) — 202 — y1) + O1 — Yo) = y3 — 3y2 + 3y1 — Yo.