CHAPTER 5 : ROOTS OF EQUATIONS
Bracketing Methods
LESSON PLAN
roots
Bracketing Methods
1. Bisection Method
2. False Position Method
- when a function is zero
- when a function crosses x-axis
Chap5/1
2 TYPES OF EQUATIONS
Algebraic Equations
- A function y = f(x) is algebraic if it can be expressed in
the form
f i y n f i 1 y n 1 ... f1 y f 0 0
- Example: Quadratic equation 2x2 x 1= 0
Transcendental Equations
- Non-algebraic equations
- Trigonometric, exponential, logarithmic are examples of
transcendental equations
- Example
Chap5/2
ln x 2 1 0
GRAPHICAL METHOD
Try this in MATLAB:
>> f=inline(x^2-3*x+2)
>> fplot(f,[0,3])
7
6
5
4
3
2
1
roots
4.0
3.6
3.2
2.8
2.4
2.0
1.6
1.2
0.8
0.4
0.0
-1
y = x2 3x +2
plot the data points & connect them in a smooth curve
locate the points at which the curve crosses the x-axis
it provides rough estimate of the roots
useful visualisation tool
Chap5/3
BRACKETING METHODS
2 types:
1. Bisection Method
2. False-Position Method
Exploit the fact that a
function typically changes
sign in the vicinity of the
root f(xL)f(xU) < 0
It is called bracketing
because two initial guesses
that bracket the root on
either side are required
Chap5/4
BISECTION METHOD
It is also known as Binary Chopping or Interval Halving
In general, if there are two points xL(lower bound) and
xU (upper bound) such that f(xL)f(xU) < 0, then there is at least
one root between xL and xU
Next, the interval is
successively bisected into
half
After each bisection, the
upper and lower bounds
Interval is bisected into
are updated.
half
Chap5/5
BISECTION METHOD: 3-Step
ALGORITHM
STEP 1: Choose upper xU and lower xL guesses such that
f(xL) f(xU) < 0
STEP 2 : Estimate the root, xr by dividing the interval [xL xU]
into half
xL xU
Midpoint: xr
2
STEP 3 : Evaluate the next sub-interval
If f(xL) f(xr) < 0, root lies in the lower interval, set xU=xr, return to step 2
If f(xL) f(xr) > 0, root lies in the upper interval, set xL=xr, return to step 2
If f(xL) f(xr) = 0, root equals to xr, terminate computation
Chap5/6
BISECTION METHOD
STOPPING CRITERION
When to stop the iteration if it is hard to get f(xL) f(xr) = 0 ?
Apply the convergence (stopping) criterion as follows:
If error |a| < stopping error |s| , then root= xrnew
xrnew xrold
a
100 s
new
xr
xU xL
or a
100 s
xU xL
only valid for
Bisection method (p121)
where xrnew is the root for the current iteration,
xrnew
xL xU
2
Chap5/7
CLASS ACTIVITY
Use analytical method to determine the radius, r of a
cylindrical can so that it holds 400 ml of liquid. Given
r = h/3.
Now, use 3 iterations of the bisection method to determine
the radius of the can. Use initial guesses of rL=3 cm and
rU=4 cm. Also, calculate the estimated error, a and the true
percent relative error, t after each iteration.
Chap5/8
BISECTION METHOD
PROS AND CONS
Cons
Pros
Easy and simple
Slow to converge
Can always find a
Must know xL and xU that bound
single root
Convergence is
guaranteed
the root
Cannot detect multiple roots
No
account is taken of the
magnitudes of f(xL) and f(xU). If
f(xL) is closer to zero, it is likely
that the root is closer to xL than to
xU use False-Position Method
Chap5/9
FALSE-POSITION METHOD
If f(xL) is closer to zero, it is likely
that the root xr is closer to xL
The curve is replaced by a straight
line that crosses the x-axis & gives
false position at xr
Based on similar triangle principle,
we can approximate the solution by
using linear interpolation between
the lower & upper bounds to find
the root, xr
Gives
better estimate
Bisection method
than
Upper bound
Lower bound
xu xL
x xr
u
f ( xu ) f ( xL ) f ( xu ) 0
rearrange for xr :
xr xu
f ( xu )( xL xu )
f ( xL ) f ( xu )
Chap5/10
FALSE-POSITION METHOD
ALGORITHM
STEP 1: Choose upper xU and lower xL guesses such that
f(xL) f(xU) < 0
STEP 2 : Use similar triangle to interpolate the new estimate
of the root
Refer to Box 5.1
f xu xL xu
xr xu
(p125)
f xL f xu
STEP 3 : Evaluate the next sub-interval
If f(xL) f(xr) < 0, root lies in the lower interval, set xU=xr, return to step 2
If f(xL) f(xr) > 0, root lies in the upper interval, set xL=xr, return to step 2
If f(xL) f(xr) = 0, root equals to xr, terminate computation
Chap5/11
FALSE-POSITION METHOD
STOPPING CRITERION
Stopping criterion : Check for convergence criterion
whereby error, a < s . If not, go back to STEP 2.
xrnew xrold
a
100% s
new
xr
Why this method ?
converge faster than Bisection method
always converges to a single root
Chap5/12
CLASS ACTIVITY
Use 3 iterations of false-position method to find a root of
equation x3 + 4x2 10 =0.
Employ initial guesses of
xL=1 and xU=2. Calculate the approximate error, a and the
true error, t after each iteration. True value = 1.36523.
xr xu
f xu xL xu
f xL f xu
Chap5/13
SUMMARY: BRACKETING METHODS
Bisection
Easy and simple
Always converge to a
single root
Step 1: f(xL)f(xu) < 0
False-position
Faster than Bisection method
Always converge to a single
root
Step 1: f(xL)f(xu) < 0
Step 2:
Step 2:
xL xU
xr
2
Step 3:
If f xL f xr 0,
set xU xr
If f xL f xr 0, set xL xr
xr xu
f xu xL xu
f xL f xu
Step 3:
If f xL f xr 0,
set xU xr
If f xL f xr 0, set xL xr Chap5/14