Root Finding: Bisection Method

Report
Dr. Marco A. Arocha
Aug, 2014
1
 “Roots” problems occur when some function f can be written in terms of one or
more dependent variables x, where the solutions to f(x)=0 yields the solution to the
problem.
 Examples:
 These problems often occur when a design problem presents an implicit equation
(as oppose to an explicit equation) for a required parameter.
2
 Finding the roots of these equations is equivalent to finding the values of x for
which f(x) and g(x) are “zero”
 For this reason the procedure of solving equations (3) and (4) is frequently referred
to as finding the “zeros” of the equations.
3
 Methods that exploit the fact that a function typically changes sign in the vicinity of
a root are called bracketing methods.
 Two initial guesses for the root are required.
 Guesses must “bracket” or be on either side of the root.
 The particular methods employ different strategies to systematically reduce the
width of the bracket and, hence, home in on the correct answer.
4

A simple method for obtaining the
estimate of the root of the equation
f(x)=0 is to make a plot of the function
as f(x) vs x and observe where it
crosses the x-axis.

Graphing the function can also indicate
where roots may be and where some
root-finding methods may fail:
a)
b)
c)
d)
who
is
doing
this
one?
Same sign, no roots
Different sign, one root
Same sign, two roots
Different sign, three roots
5
Some difficult cases:
 Multiple roots that occurs when the function is tangential
to the x axis. For this case, although the end points are of
opposite signs, there are an even number of axis
intersections for the interval.
 Discontinuous function where end points of opposite sign
bracket an even number of roots.
 Special strategies are required for determining the roots
for these cases.
6
 Graphical techniques alone are of limited practical value because they are not
precise.
 However, graphical methods can be utilized to obtain rough estimates of roots.
 These estimates can be employed as starting guesses for numerical methods.
 Graphical interpretations are important tools for understanding the properties of
the functions and anticipating the pitfalls of the numerical methods.
7
 The bisection method is a
search method in which the
interval is progresively
divided in half.
 If a function changes sign
over an interval, the function
value at the midpoint is
evaluated.
 The location of the root is
then determined as lying
within the subinterval where
the sign change occurs.
 The absolute error is
reduced by a factor of 2 for
each iteration.
8
9
 A simple termination criteria can be used:
 (1) An approximate error εa can be calculated:
  =
 − 
 where  is the root lower bound and  is the root upper bound from the present
iteration.
 The absolute value is used because we are usually concerned with the magnitude
of εa rather than with its sign.
10
 Another forms of termination criteria can be used:
 (2) An approximate percent relative error εa can be calculated:
  =
 −

100%
 where  is the root for the present iteration and  is the root from the previous
iteration.
 The absolute value is used because we are usually concerned with the magnitude
of εa rather than with its sign.
11
INPUT xl, xu, es, imax
xr = (xl + xu) / 2
iter = 0
DO
xrold = xr
xr = (xl + xu) / 2
iter = iter + 1
IF xr ≠ 0 THEN
% to avoid division by zero
ea = ABS((xr - xrold) / xr) * 100
END IF
test = f(xl) * f(xr)
IF test < 0 THEN
xu = xr
ELSE IF test > 0 THEN
xl = xr
ELSE
ea = 0
END IF
IF ea < es OR iter ≥ imax EXIT
END DO
BisectResult = xr
END PROGRAM
12
 An alternative method to bisection,
sometimes faster.
 Exploits a graphical perception, join f(xl) and
f(xu) by a straight line. The intersection of this
line with the x axis represents an improved
estimate of the root.
 The fact that the replacement of the curve by
a straight line gives a “false position” of the
root is the origin of the name, method of false
position, or in Latin, regula falsi.
 It is also called the linear interpolation
method.
13
 Can derive the method’s formula by using
similar triangles. The intersection of the
straight line with the x axis can be estimated
as
 which can be solved for xr
14
 The value of xr so computed then replaces whichever
of the two initial guesses, xl or xu, yields a function
value with the same sign as f(xr).
 By this way, the values of xl and xu always bracket the
true root. The process is repeated until the root is
estimated.

The algorithm is identical to the one for bisection
with the exception that the above eq. is used for step 2
(slide 9).
 The same stopping criteria are used to terminate the
computation (slides 10 and 11).
15
for some cases
false-position
method may
show slow
convergence
16

similar documents