Exploring Methods for Finding Roots of Equations

Finding roots of Equations (Algebraic and Transcendental) 1

Transcendental functions Transcendental functions Trigonometric, Inverse Trigonometric, Logarithmic, Hyperbolic, Infinite series 2

UNIT I (Topics) Roots of Equations: f(x)=0 Bisections Method, False Position Method, Newton s Raphson Method, Rate of convergence of Newton s Raphson method 3

Roots of equations: 2 4 b b 2 ac + + = = 2 0 ax bx c x a + x + + + + = = 5 4 3 2 0 ? ax bx cx dx ex f x + = = sin 0 ? x x 4

we are given a function of x, say F(x), and we wish to find a value of x for which F(x)=0. The function F(x) may be algebraic or transcendental, and we generally assume that it is continuous. In practice, the functions we deal with in the applications have no simple closed formula for their roots, as the quadratic equation has. Instead, we turn to methods for approximation of the roots, and two steps are involved: 1. Finding an approximate root 2. Refining the approximation to wanted accuracy 5

Intermediate Value Theorem: (also known as root location theorem) If a function f(x) is continuous in an interval (a,b), such that f(a) and f(b) are of opposite nature or opposite signs, then there exists at least one or an odd number of roots (solutions of f(x)=0) between a and b. 6

7

Nonlinear Equation Solvers Bracketing Graphical Open Methods Bisection False Position (Regula-Falsi) Newton Raphson Secant 8

Method 1 (Find root of f(x)=0) Bisection method Steps (Rule) Step-1:Find points a and b such that a<b and f(a) f(b)<0. Step-2:Take the interval [a,b] and find next value x0=(a+b)/2 Step-3:If f(x0)=0 then x0 is an exact root, else if f(a) f(x0)<0 then b=x0, else if f(x0) f(b)<0 then a=x0. Step-4:Repeat steps 2 & 3 until f(xi) is very close to 0 or |f(xi)| Accuracy 9

Example-1 1. Find a root of an equation f(x)=x^3-x-1=0 using Bisection method. (Perform only 11 iterations). Solution: Here x^3-x-1=0 Let f(x)=x^3-x-1 Here X 0 1 2 f(x) -1 -1 5 1st iteration : Here f(1)=-1<0 and f(2)=5>0 Now, Root lies between 1 and 2 Hence a=1, b=2 x0=(1+2)/2=1.5 f(x0)=f(1.5)=0.875>0

2nd iteration : Here f(1)=-1<0 and f(1.5)=0.875>0 Now, Root lies between 1 and 1.5 x1=(1+1.5)/2=1.25 f(x1)=f(1.25)=-0.29688<0 Similarly .. C = f(a) f(b) f(c) n a b Update (a+b)/2 -1 1.5 0.875 b=c 1 1 2 5 -1 1.5 0.875 1.25 -0.29688 a=c 2 1 1.25 -0.29688 1.5 0.875 1.375 0.22461 b=c 3 1.25 -0.29688 1.375 0.22461 1.3125 -0.05151 a=c 4 1.3125 -0.05151 1.375 0.22461 1.34375 0.08261 b=c 5 http://numericalmethods.eng.usf.edu 11

1.3125 -0.05151 1.34375 0.08261 1.32812 0.01458 b=c 6 1.3125 -0.05151 1.32812 0.01458 1.32031 -0.01871 a=c 7 1.32031 -0.01871 1.32812 0.01458 1.32422 -0.00213 a=c 8 1.3125 1.3125 1.32031 1.32422 1.32422 1.32422 1.3125 1.3125 1.32031 1.32422 1.32422 1.32422 -0.05151 -0.05151 -0.01871 -0.00213 -0.00213 -0.00213 -0.05151 -0.05151 -0.01871 -0.00213 -0.00213 -0.00213 1.34375 1.32812 1.32812 1.32812 1.32617 1.3252 1.34375 1.32812 1.32812 1.32812 1.32617 1.3252 0.08261 0.01458 0.01458 0.01458 0.00621 0.00204 0.08261 0.01458 0.01458 0.01458 0.00621 0.00204 1.32812 1.32031 1.32422 1.32617 1.3252 1.32471 1.32812 1.32031 1.32422 1.32617 1.3252 1.32471 0.01458 -0.01871 -0.00213 0.00621 0.00204 -0.00005 0.01458 -0.01871 -0.00213 0.00621 0.00204 -0.00005 b=c a=c a=c b=c b=c a=c b=c a=c a=c b=c b=c a=c 6 6 9 1.32422 -0.00213 1.32812 0.01458 1.32617 0.00621 b=c 7 7 8 8 9 9 10 10 10 1.32422 -0.00213 1.32617 0.00621 1.3252 0.00204 b=c 11 11 1.32422 -0.00213 1.3252 0.00204 1.32471 -0.00005 a=c 11 approximate root of the equation x^3-x-1 = 0 using Bisection method is 1.32471

Example-2 2. Find a root of an equation f(x)=2x^3-2x- 5=0 using Bisection method by performing 10 iterations. 13

Approximate root of the equation 2x^3-2x-5=0 using Bisection mehtod is 1.60059 C f(a) f(b) f(c) n a b Update =(a+b)/2 1.5 -5 -1.25 a=c 1 1 2 7 1.5 -1.25 1.75 2.21875 b=c 2 2 7 1.5 -1.25 1.75 2.21875 1.625 0.33203 b=c 3 1.5 -1.25 1.625 0.33203 1.5625 -0.49561 a=c 4 1.5625 -0.49561 1.625 0.33203 1.59375 -0.09113 a=c 5 1.59375 -0.09113 1.625 0.33203 1.60938 0.1181 b=c 6 1.59375 -0.09113 1.60938 0.1181 1.60156 0.0129 b=c 7 1.59375 -0.09113 1.60156 0.0129 1.59766 -0.03926 a=c 8 1.59766 -0.03926 1.60156 0.0129 1.59961 -0.01322 a=c 9 1.59961 -0.01322 1.60156 0.0129 1.60059 -0.00017 a=c 10

1. Find the root of cos(x) x*exp(x) = 0,where exp(x) means e^x using Bisection method. Iteration No. 1 0 1 a b c =( a + b)/2 f(a) * f(c) 0.5 0.053 (+ve) 2 0.5 1 0.75 -0.046 (-ve) 3 0.5 0.75 0.625 -0.357 (-ve) -7.52 * 10-3(-ve) 4 0.5 0.625 0.562 -2.168 * 10-3 (- ve) 3.648 * 10-4 (+ve) -9.371 * 10-5(- ve) -3.649 * 10-5(- ve) -3.941 * 10-6(- ve) 5 0.5 0.562 0.531 6 0.5 0.531 0.516 7 0.516 0.531 0.524 8 0.516 0.524 0.520 9 0.516 0.520 0.518 1.229 * 10-5(+ve) 10 So one of the roots of cos(x) - x * exp(x) = 0 is approximately 0.517 0.516 0.518 0.517 15

2. Find the root of x4-x-10 = 0 Iteration No. 1 2 3 4 5 a b c f(a) * f(c) 1.5 1.75 1.75 1.812 1.844 2 2 1.875 1.875 1.875 1.75 1.875 1.812 1.844 1.86 15.264 (+ve) -1.149 (-ve) 2.419 (+ve) 0.303 (-ve) -0.027 (-ve) So one of the roots of x4-x-10 = 0 is approximately 1.86. 16

3. Find the root of x - exp(-x) = 0 Iteration No. 1 a b c f(a) * f(c) 0 1 0.5 0.107 (+ve) 2 0.5 1 0.75 -0.03 (-ve) -9.56*10-3 (-ve) 3 0.5 0.75 0.625 7.758 *10-4(+ve) 4 0.5 0.625 0.562 -3.317*10-4 (-ve) 5 0.562 0.625 0.593 -1.307*10-4 (-ve) 6 0.562 0.593 0.577 -2.978*10-5 (-ve) 7 0.562 0.577 0.569 2.078*10-5 (+ve) 8 0.562 0.569 0.565 So one of the roots of x - exp(-x) = 0 is approximately 0.565. 17

4. Find the root of exp(-x)=3log(x) Iteration No. a b c f(a) * f(c) 1 0.5 1.5 1 0.555 (+ve) -1.554*10-3 (- ve) 2 1.00 1.5 1.25 3 1.00 1.25 1.125 0.063 (+ve) 4 1.125 1.25 1.187 0.014 (+ve) So one of the roots of exp(-x)=3log(x) is approximately 1.187. 18

Method 2. RegulaFalsi Method A better approximation to c can be obtained by taking the straight line L joining the points (a,f(a)) and (b,f(b)) intersecting the x- axis. To obtain the value of c we can equate the two expressions of the slope m of the line L. f(b) - f(a)= (b-a) 0 - f(b) (c-b) 19

Algorithm - False Position Scheme Given a function f (x) continuos on an interval [a,b] such that f (a) * f (b) < 0 Do a*f(b)-b*f(a) C = f(b) - f(a) Now the next smaller interval which brackets the root can be obtained by checking f(a) * f(c) < 0 then b = c > 0 then a = c = 0 then c is the root. c by the above expression is called Regula-Falsi method or False 20

Question1 Find a root of 3x + sin(x) - exp(x) = 0 using Regula Falsi method. The graph of this equation is given in the figure. You can use DESMOS app. From this it's clear that there is a root between 0 and 0.5 and also another root between 1.5 and 2.0. Now let us consider the function f (x) in the interval [0, 0.5] where f (0) * f (0.5) is less than zero and use the regula-falsi scheme to obtain the zero of f (x) = 0. 21

Iteration No. a b c f(a) * f(c) 1 0 0.5 0.376 1.38 (+ve) 2 0.376 0.5 0.36 -0.102 (-ve) 3 0.376 0.36 0.36 -0.085 (-ve) So one of the roots of 3x + sin(x) - exp(x) = 0 is approximately 0.36.

Find the root of x * cos[(x)/ (x-2)]=0 1. The graph of this equation is given in the figure. Let a = 1 and b = 1.5 Iteration No. 1 2 3 4 5 6 a b c f(a) * f(c) 1 1.133 1.194 1.214 1.22 1.222 1.5 1.5 1.5 1.5 1.5 1.5 1.133 1.194 1.214 1.22 1.222 1.222 0.159 (+ve) 0.032 (+ve) 3.192E-3 (+ve) 2.586E-4(+ve) 1.646E-5 (+ve) 3.811E-9(+ve) So one of the roots of x * cos[(x)/ (x-2)]=0 is approximately 1.222. 23

2. Find the root of x2 = (exp(-2x) - 1) / x The graph of this equation is given in the figure. Let a = -0.5 and b = 0.5 Iteration No. a b c f(a) * f(c) 1 -0.5 0.5 0.209 -0.646 (-ve) 2 -0.5 0.208 0.0952 -0.3211 (-ve) 3 -0.5 0.0952 0.0438 -0.1547 (-ve) 4 -0.5 0.0438 0.0201 -0.0727 (-ve) 5 -0.5 0.0201 9.212E-3 -0.0336 (-ve) 6 -0.5 9.212E-3 4.218E-3 -0.015 (-ve) 7 -0.5 4.218E-3 1.931E-3 -7.1E-3 (-ve) 8 -0.5 1.931E-3 8.83E-4 -3.2E-3 (-ve) So one of the roots of x2 = (exp(-2x) - 1) / x is approximately 8.83E-4. 24

3. Find the root of exp(x2-1)+10sin(2x)-5 = 0 The graph of this equation is given in the figure. Let a = 0 and b = 0.5 Iteration No. a b c f(a) * f(c) 1 0 0.5 0.272 -2.637 (-ve) 2 0 0.272 0.242 -0.210 (-ve) 3 0 0.242 0.24 -0.014 (-ve) 4 0 0.24 0.24 -2.51E-3(-ve) So one of the roots of exp[x2-1]+10sin(2x)-5 = 0 is approximately 0.24. 25

Find the root of exp(x)-3x2=0 Iteration No. a b c f(a) * f(c) 1 3 4 3.512 24.137 (+ve) 2 3.512 4 3.681 3.375 (+ve) 3 3.681 4 3.722 0.211 (+ve) 4 3.722 4 3.731 9.8E-3 (+ve) 5 3.731 4 3.733 3.49E-4 (+ve) 1.733*10-3 (+ve) 6 3.733 4 3.733 26

6. Find the root of sin(2x)-exp(x-1) =0 The graph of this equation is given in the figure. Let a = 0 and b = 0.5 Iteration No. 1 0 0.5 a b c f(a) * f(c) 0.305 -0.027 (-ve) 2 0 0.305 0.254 -4.497E-3(-ve) 3 0 0.254 0.246 -6.384E-4 (-ve) 4 0 0.246 0.245 -9.782E-5 (-ve) 5 0 0.245 0.245 -3.144E-5 (-ve) http://numericalmethods.eng.usf.edu 27

Iterative methods: Starting with an initial guess, say x0 and generating a sequence x1, x2, x3, . . . recursively from any relation is called an Iterative method. Convergence : Any iterative process defined by xi+1= g(xi), i = 0, 1, 2, . . . is said to be convergent for the initial guess x0 if the corresponding sequence x1, x2, x3, . . . converges.

Method 3 Newton-Raphson Method f(x) f(x ) ( ) x f(xi) x, f i x = x - i i +1 (x i i f ) i f(xi-1) X xi+2 xi+1 xi Figure 1 Geometrical illustration of the Newton-Raphson method. 29

Derivation f(x) AB ) = tan( f(xi) B AC ( ) f x = ( ' ) i f x i x x + 1 i i ( ) f x C A X = i x x xi+1 xi + 1 i i ( ) f x i Figure 2 Derivation of the Newton-Raphson method. 30

Algorithm for Newton- Raphson Method 31

Step 1 f (x ) Evaluate symbolically. 32

Step 2 ix Use an initial guess of the root, , to estimate the new value of the root, , as 1 + ix ( ) ( ) x f x i x = x - +1 i i f i 33

Step 3 Find the absolute relative approximate error as a x - x + 10 0 1 = i i a x + 1 i 34

Step 4 Compare the absolute relative approximate error with the pre-specified relative error tolerance . s Go to Step 2 using new estimate of the root. Yes Is ? a s No Stop the algorithm Also, check if the number of iterations has exceeded the maximum number of iterations allowed. If so, one needs to terminate the algorithm and notify the user. 35

Example-1 Find a root of an equation f(x)=x^3- x-1 using Newton Raphson method Solution: Here x^3-x-1=0 Let f(x)=x^3-x-1 f (x)=3x2-1 Here x 0 1 2 f(x) -1 -1 5 Here f(1)=-1<0 and f (2)=5>0 Root lies between 1 and 2 x0=1+22=1.5

Algorithm to guess initial approximation: Step 1. Find a suitable guess (a,b) by root location theorem. (you can take help of bisection method) Step 2. if f(a) is much closer to 0 than f(b) then initial guess x0= a. Otherwise x0 = b Example: Suppose f(1)=-1<0 and f (2)=5>0 where f(x)=x^3-x-1 Root lies between 1 and 2 c = (1+2)/2=1.5, now f(c)=f(1.5)=0.875 So new a=1 and b=1.5 f(1.5) is much closer to 0 than f(1) so initial guess is x0= 1.5 Remark: You can use bisection method initially to make interval (a,b) as smaller as much you wish so that less iteration are required.

: 1-iteration f(x0)=f(1.5)=0.875 f (x0)=f (1.5)=5.75 x1=x0-f(x0)/f (x0) x1=1.5-0.8755.75 x1=1.34783 2-iteration : f(x1)=f(1.34783)=0.10068 f (x1)=f (1.34783)=4.44991 x2=x1-f(x1)/f (x1) x2=1.34783-0.100684.44991 x2=1.3252

f(x0) f (x0) n x0 x1 Update 1.5 0.875 5.75 1.34783 x0=x1 1 1.34783 0.10068 4.44991 1.3252 x0=x1 2 1.3252 0.00206 4.26847 1.32472 x0=x1 3 1.32472 4.26463 1.32472 x0=x1 4 0

Find a root of 3x+sin[x]-exp[x]=0 using Newton Raphson Method where initial guess is 2. (Perform 4 iterations) Let the initial guess x0be 2.0 f(x) = 3x+sin[x]-exp[x] f '(x) = 3+cos[x]-exp[x] i xi 0 2 1 1.90016 1.89013 1.89003 1.89003 2 3 4 So the iterative process converges to 1.89003 in four iterations.

Find the root of x4-x-10 = 0 The graph of this equation is given in the figure. Let the initial guess x0be 2.0 i 0 1 2 3 4 xi 2 1.87097 1.85578 1.85558 1.85558 41

3. Find the root of x-exp[-x] = 0 The graph of this equation is given in the figure.l Let the initial guess x0be 2.0 i xi 0 2 1 0.35761 2 0.55871 3 0.56713 4 0.56714 5 0.56714 42 http://numericalmethods.eng.usf.edu

6. Find the root of exp[x]=3log[x] by Newton Raphson Method correct upto 4 decimal places. let the initial guess x0be 2.0 i xi 0 2 1 1.02418 2 1.22523 3 1.24663 4 1.24682 5 1.24682 43

THE END