Department of Mathematics
Amer Rasheed
Lecture 3
Numerical Analysis
Math344, Math541
Amer Rasheed (MATH344) Department of Mathematics 1 / 21
Zero of a function
Zero of a function
Definition (Root/Zero of a function)
Assume that f (x) is a continuous function. Any number r for which
f (r) = 0 is called a root of the equation f (x) = 0 or zero of the function
f (x).
Definition (Order of a Root)
Assume that f (x) and its derivatives f 0 (x), f 00 (x),. . . , f M (x) are defined
and continuous on an interval about x = P . We say that f (x) = 0 has a
root of order M at x = P , if and only if,
f (P ) = 0, f 0 (P ) = 0, f 00 (P ) = 0, . . . , f (M 1) (P ) = 0, and f (M ) (P ) 6= 0.
Amer Rasheed (MATH344) Department of Mathematics 2 / 21
Bisection Method Bisection Method
Bisection Method
Graphical Interpretation
a = a1 a2 a3 an b1 = b
b1 b2 b3 bn a1
[a1 , b1 ] [a2 , b2 ] [an , bn ]
Amer Rasheed (MATH344) Department of Mathematics 3 / 21
Bisection Method
Bisection Method
Step - I : Find/choose two point xl , xr R such that f (xl )f (xr ) < 0
xl + xr
Step - II : Find the mid point xm =
2
Step - III :
If f (xl ) f (xm ) < 0, then root lies between xl and xm , then update
as xl = xl , & xr = xm
If f (xm ) f (xr ) < 0, then root lies between xm and xr , then update
as xl = xm , & xr = xr
If f (xm ) = 0, then root is xm . Stop algorithm.
xl + xr
Find the new mid point xm = and find the absolute relative
2
|xnew
m xm |
old
error Rm = new
|xm |
If |Rm | < T OL and |f (xm )| < T OL. Stop algorithm.
Amer Rasheed (MATH344) Department of Mathematics 4 / 21
Bisection Method
Bisection Method
Example : Find the root of the equation
2 + x ex = 0
Step - I : Find/choose two points such that
f (xl ) f (xr ) < 0
We choose
xl = 0, xr = 3
Find
xl + xr 0+3
xm = = = 1.5
2 2
and f (xm ) = f (1.5) = 0.981689
Amer Rasheed (MATH344) Department of Mathematics 5 / 21
Bisection Method Bisection Method
Bisection Method
Amer Rasheed (MATH344) Department of Mathematics 6 / 21
Bisection Method Bisection Method
Bisection Method
Amer Rasheed (MATH344) Department of Mathematics 7 / 21
Bisection Method Bisection Method
Bisection Method
Amer Rasheed (MATH344) Department of Mathematics 8 / 21
Bisection Method
Bisection Theorem
Convergence of Bisection Method
Assume that f C[a, b] and there exists a number r [a, b] such that
f (r) = 0, If f (a) and f (b) have opposite signs and {cn }
n=1 represents
the sequence of midpoints generated by bisection process, then
ba
r cn < , n = 1, 2, 3, . . . .
2n+1
and therefore the sequence {cn }
n=1 converges to x = r (zero of
function), i.e.,
lim cn = r.
n
Amer Rasheed (MATH344) Department of Mathematics 9 / 21
Bisection Method
Bisection Theorem
Convergence of Bisection Method
Proof : As both r and the sequence {cn } n=1 lie in the same interval
[an , bn ], the distance between r and cn cannot be greater than half the
width of this interval, i.e.,
bn an
r cn < n = 1, 2, 3, . . . . (1)
2
Also observe that the successive interval widths form the pattern
b1 a1
b2 a2 =
21
b2 a2 b1 a1
b3 a3 = =
21 22
In general, using mathematical induction, we can show that
b1 a1
bn an = n1 , n (2)
2
Amer Rasheed (MATH344) Department of Mathematics 10 / 21
Bisection Method
Bisection Theorem
Convergence of Bisection Method
Combining Eqns (1) and (2), we obtain
ba
r cn < , n = 1, 2, 3, . . . .
2n
Taking limit on both sides, we arrive at
lim cn = r.
n
Note : We observe that the sequence {cn}n=1 generated by bisection
1
process converges to r is of order O , i.e.,
2n
1
cn = r + O
2n
Amer Rasheed (MATH344) Department of Mathematics 11 / 21
Bisection Method
Bisection Theorem
Convergence of Bisection Method
Note : We can find number of iterations required to obtain desired
accuracy by Bisection method using
ln(b a) ln
N int
ln2
In previous example
ln(3 0) ln(105 )
N int = 18
ln2
Amer Rasheed (MATH344) Department of Mathematics 12 / 21
Bisection Method
Bisection Theorem
Speed of Convergence : The sequence {cn } n=1 generated by
bisection process converges to r linearly.
As
an+1 + bn+1 1 an + bn
|en+1 | = |r cn+1 | =
2 2 2
and also
an + bn
|en | = |r cn |
2
For sufficiently large n, i.e.,
|en+1 | 1
lim 1
n |en | 2
Amer Rasheed (MATH344) Department of Mathematics 13 / 21
Bisection Method
Bisection Method
Advantages/Drawbacks
Advantages
Always convergent.
The root bracket gets halved with each iteration.
Disadvantages
Slow convergence
If one of initial guess is close to the root, the convergence is even
slower.
Amer Rasheed (MATH344) Department of Mathematics 14 / 21
Bisection Method
Bisection Method
Advantages/Drawbacks
If a function f (x) is such that it just touches the x axis, we would be
unable to find the lower and upper guesses.
Amer Rasheed (MATH344) Department of Mathematics 15 / 21
Bisection Method
Bisection Method
Advantages/Drawbacks
Function changes sign but root does not exist.
Amer Rasheed (MATH344) Department of Mathematics 16 / 21
Method of False Position
Method of False Position
Also known as Regular Falsi Method. All other conditions/assumptions
are same as Bisection Method.
f (b) f (a) 0 f (b)
=
ba cb
Amer Rasheed (MATH344) Department of Mathematics 17 / 21
Method of False Position
Method of False Position
f (b) f (a) 0 f (b)
=
ba cb
af (b) bf (a)
c=
f (b) f (a)
If f (c) = 0, then c is the required root, otherwise replace
b = c, if f (a) f (c) < 0
a = c, if f (c) f (b) < 0
For n = 0, 1, 2, 3, . . . with [a, b] = [a0 , b0 ], we can write
an f (bn ) bn f (an )
cn =
f (bn ) f (an )
Amer Rasheed (MATH344) Department of Mathematics 18 / 21
Method of False Position
Method of False Position
Example : Find the root of the nonlinear equation
x2 2x 5 = 0
Using Method of False Position.
Starting interval : [a0 , b0 ] = [2, 5].
f (2) = 5, f (5) = 10
a0 f (b0 ) b0 f (a0 )
c0 = =3
f (b0 ) f (a0 )
As f (3) = 2, thus [a1 , b1 ] = [3, 5]
Amer Rasheed (MATH344) Department of Mathematics 19 / 21
Method of False Position
Method of False Position
Amer Rasheed (MATH344) Department of Mathematics 20 / 21
Method of False Position
Method of False Position
Comparison with bisection method
Amer Rasheed (MATH344) Department of Mathematics 21 / 21