Finding roots of Equations
(Algebraic
and
Transcendental)
1
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:
b b 2 4ac
ax 2 bx c 0 x
2a
ax 5 bx 4 cx 3 dx 2 ex f 0 x ?
sin x x 0 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 Newton Raphson
False Position
(Regula-Falsi) 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=
n a f(a) b f(b) f(c) Update
(a+b)/2
1 1 -1 2 5 1.5 0.875 b=c
2 1 -1 1.5 0.875 1.25 -0.29688 a=c
3 1.25 -0.29688 1.5 0.875 1.375 0.22461 b=c
4 1.25 -0.29688 1.375 0.22461 1.3125 -0.05151 a=c
5 1.3125 -0.05151 1.375 0.22461 1.34375 0.08261 b=c
http://numericalmethods.eng.usf.edu 11
6 1.3125 -0.05151 1.34375 0.08261 1.32812 0.01458 b=c
7 1.3125 -0.05151 1.32812 0.01458 1.32031 -0.01871 a=c
8 1.32031 -0.01871 1.32812 0.01458 1.32422 -0.00213 a=c
6 1.3125 -0.05151 1.34375 0.08261 1.32812 0.01458 b=c
97 1.32422
1.3125 -0.00213
-0.05151 1.32812
1.32812 0.01458
0.01458 1.32617
1.32031 0.00621
-0.01871 b=c
a=c
8 1.32031 -0.01871 1.32812 0.01458 1.32422 -0.00213 a=c
9 1.32422 -0.00213 1.32812 0.01458 1.32617 0.00621 b=c
10 1.32422 -0.00213 1.32617 0.00621 1.3252 0.00204 b=c
10
11 1.32422
1.32422 -0.00213
-0.00213 1.32617
1.3252 0.00621
0.00204 1.3252
1.32471 0.00204
-0.00005 b=c
a=c
11 1.32422 -0.00213 1.3252 0.00204 1.32471 -0.00005 a=c
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
n a f(a) b f(b) C =(a+b)/2 f(c) Update
1 1 -5 2 7 1.5 -1.25 a=c
2 1.5 -1.25 2 7 1.75 2.21875 b=c
3 1.5 -1.25 1.75 2.21875 1.625 0.33203 b=c
4 1.5 -1.25 1.625 0.33203 1.5625 -0.49561 a=c
5 1.5625 -0.49561 1.625 0.33203 1.59375 -0.09113 a=c
6 1.59375 -0.09113 1.625 0.33203 1.60938 0.1181 b=c
7 1.59375 -0.09113 1.60938 0.1181 1.60156 0.0129 b=c
8 1.59375 -0.09113 1.60156 0.0129 1.59766 -0.03926 a=c
9 1.59766 -0.03926 1.60156 0.0129 1.59961 -0.01322 a=c
10 1.59961 -0.01322 1.60156 0.0129 1.60059 -0.00017 a=c
1. Find the root of cos(x) – x*exp(x) = 0,where exp(x) means e^x
using Bisection method.
Iteration a b c =( a + b)/2 f(a) * f(c)
No.
1 0 1 0.5 0.053 (+ve)
2 0.5 1 0.75 -0.046 (-ve)
3 0.5 0.75 0.625 -0.357 (-ve)
4 0.5 0.625 0.562 -7.52 * 10-3(-ve)
-2.168 * 10-3 (-
5 0.5 0.562 0.531 ve)
6 0.5 0.531 0.516 3.648 * 10-4
(+ve)
7 0.516 0.531 0.524 -9.371 * 10-5(-ve)
8 0.516 0.524 0.520 -3.649 * 10-5(-ve)
9 0.516 0.520 0.518 -3.941 * 10-6(-ve)
10 0.516 0.518 0.517 1.229 * 10-5(+ve)
So one of the roots of cos(x) - x * exp(x) = 0 is
approximately 0.517 15
2. Find the root of x4-x-10 = 0
Iteration
a b c f(a) * f(c)
No.
1 1.5 2 1.75 15.264 (+ve)
2 1.75 2 1.875 -1.149 (-ve)
3 1.75 1.875 1.812 2.419 (+ve)
4 1.812 1.875 1.844 0.303 (-ve)
5 1.844 1.875 1.86 -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
a b c f(a) * f(c)
No.
1 0 1 0.5 0.107 (+ve)
2 0.5 1 0.75 -0.03 (-ve)
3 0.5 0.75 0.625 -9.56*10-3 (-ve)
4 0.5 0.625 0.562 7.758 *10-4(+ve)
5 0.562 0.625 0.593 -3.317*10-4 (-ve)
6 0.562 0.593 0.577 -1.307*10-4 (-ve)
7 0.562 0.577 0.569 -2.978*10-5 (-ve)
8 0.562 0.569 0.565 2.078*10-5 (+ve)
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
a b c f(a) * f(c)
No.
1 0.5 1.5 1 0.555 (+ve)
-1.554*10-3 (-
2 1.00 1.5 1.25
ve)
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. Regula–Falsi 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 line0 -L.
f(b) - f(a) f(b)
=
(b-a) (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
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
a b c f(a) * f(c)
No.
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.
1. Find the root of x * cos[(x)/ (x-2)]=0
The graph of this equation is given in the figure.
Let a = 1 and b = 1.5
Iteration
a b c f(a) * f(c)
No.
1 1 1.5 1.133 0.159 (+ve)
2 1.133 1.5 1.194 0.032 (+ve)
3 1.194 1.5 1.214 3.192E-3 (+ve)
4 1.214 1.5 1.22 2.586E-4(+ve)
5 1.22 1.5 1.222 1.646E-5 (+ve)
6 1.222 1.5 1.222 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 a b c f(a) * f(c)
No.
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
a b c f(a) * f(c)
No.
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
a b c f(a) * f(c)
No.
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)
6 3.733 4 3.733 1.733*10-3 (+ve)
26
Iteration
a b c f(a) * f(c)
No.
1 0 0.5 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 i)
x f x f(x i )
i, i xi 1 = xi -
f (xi )
f ( x i-1 )
x i+ 2 x i+ 1 xi X
Figure 1 Geometrical illustration of the Newton-Raphson
29 method.
Derivation
f(x)
AB
f(xi) B tan(
AC
f ( xi )
f ' ( xi )
xi xi 1
C A X f ( xi )
xi+1 xi xi 1 xi
f ( xi )
Figure 2 Derivation of the Newton-Raphson method.
30
Algorithm for Newton-
Raphson Method
31
Step 1
Evaluat f (x) symbolically.
e
32
Step 2
xi
Use an initial guess of the root, , to estimate the
new value of thexi root,
1 , as
f xi
xi 1 = xi -
f xi
33
Step 3
a
Find the absolute relative approximate error as
xi 1- xi
a = 100
xi 1
34
Step 4
Compare the absolute relative approximate
error with the pre-specified relative errors
tolerance .
Go to Step 2 using
Yes
new estimate of the
Is a s ? root.
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
35 algorithm and notify the user.
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
n x0 f(x0) f′(x0) x1 Update
1 1.5 0.875 5.75 1.34783 x0=x1
2 1.34783 0.10068 4.44991 1.3252 x0=x1
3 1.3252 0.00206 4.26847 1.32472 x0=x1
4 1.32472 0 4.26463 1.32472 x0=x1
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 x0 be 2.0
f(x) = 3x+sin[x]-exp[x] f '(x) = 3+cos[x]-exp[x]
i 0 1 2 3 4
1.9001 1.8901 1.8900 1.8900
xi 2
6 3 3 3
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 x0 be 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 x0 be 2.0
i 0 1 2 3 4 5
0.5671
xi 2 0.35761 0.55871 0.56713 0.56714
4
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 x0 be 2.0
i 0 1 2 3 4 5
1.2468
xi 2 1.02418 1.22523 1.24663 1.24682
2
43
THE END
