Bisection Method

Bisection Method
Prianka Mandal
Lecturer
Daffodil International University
1
2
Iterative Method
• An iterative technique usually begins with an approximate value of
the root, known as the initial guess, which is then successively
corrected iteration by iteration under a certain mathematical basis
• The process of iteration stops when the desired level of accuracy is

obtained.
• Iterative methods, based on the position of the root relative to the

position of initial guess(es), can be categorized into two categories:
 Bracketing methods (Interpolation methods)

 Open end methods (Extrapolation methods)
3
Iterative Method (continued)

• Bracketing methods start with two initial guesses that ‘bracket’ the
root and then systematically reduce the width of the bracket until
the solution is reached
• Two popular methods under Bracketing category are:
 Bisection method
 False position method
• These methods are based on the assumption that the function

changes sign in the vicinity of a root.
4
Iterative Method (continued)

• Open end methods use a single starting value or two values that do
not necessarily bracket the root.
• The following iterative methods fall under this category:
 Newton-Raphson method
 Secant method
5
Bisection Method
• One of the first numerical methods developed to find the root of a
nonlinear equation f(x)=0 was the bisection method (also called
binary-search method / binary chopping / interval halving /
Bolzano’s method).
• The method is based on the following theorem.
 Theorem
 An equation f(x)=0, where f(x) is a real continuous function of
x, has at least one root between xl and xu and if f(xl)f(xu)<0
6
Bisection Method (continued)

• Since the method is based on finding the root between two points,
the method falls under the category of bracketing methods.
• Since the root is bracketed between two points, xl and xu one can
find the mid-point, xr between xl and xu. This gives us two new
intervals.
• xl & xr and xr & xu

7
Steps of Bisection Method

• Step #1:
 Choose lower xl and upper xu guesses for the root such that the function
changes sign over the interval. This can be checked by ensuring that
f(xl)f(xu)<0.
• Step #2:
 An estimate of the root xr is determined by
𝑥𝑙 + 𝑥𝑢
𝑥𝑟 =
2
8
Steps of Bisection Method (continued)

• Step #3:
 Make the following evaluations to determine in which subinterval the
root lies:
(a) If f(xl)f(xr)<0, the root lies in the lower subinterval. Therefore, set
xu= xr and return to step 2.
(b) If f(xl)f(xr)>0, the root lies in the upper subinterval. Therefore, set xl
= xr and return to step 2.
(c) If f(xl)f(xr)=0, the root equals xr; terminate the computation.

9
An Exercise
• Use the bisection approach to determine the drag
coefficient c needed for a parachutist of mass m=68.1 kg to
have a velocity of 40 m/s after free-falling for time t=10 s.
Note: The acceleration due to gravity is 9.8 m/s2
• Solution:
This problem can be solved by determining the root of Eq.
𝑔𝑚 −
𝑐
𝑡
𝑓 𝑐 = 1 −𝑒 𝑚 −𝑣
𝑐
using the parameters t=10, g=9.8, v=40, and m=68.1:
9.8(68.1) 𝑐
− 68.1 10
𝑓 𝑐 = 1 −𝑒 − 40
𝑐
667.38
or, 𝑓 𝑐 = 1 − 𝑒 −0.146843𝑐 − 40
𝑐
10
• The first step:

Guess two values of the unknown (in the present problem, c) that give
values for f(c) with different signs.
The function changes sign between values of 12 and 16.
Therefore, the initial estimate of the root xr lies at the midpoint of the
interval,
12 + 16
𝑥𝑟 = = 14
2
This estimate represents a true percent relative error of εt =5.3% (note

that the true value of the root is 14.7802).
𝑇𝑟𝑢𝑒 𝐸𝑟𝑟𝑜𝑟
Review Formula:Relative True Error (percent), εt=
𝑇𝑟𝑢𝑒 𝑉𝑎𝑙𝑢𝑒 × 100
11
• The second step:

We compute the product of the function value at the lower bound and
at the midpoint:
f(12) f(14) = 6.067(1.569) = 9.517
which is greater than zero.

Hence, no sign change occurs between the lower bound and the
midpoint.
Consequently, the root must be located between 14 and 16.
Therefore, we create a new interval by redefining the lower bound as
14 and determining a revised root estimate as
14 + 16
𝑥𝑟 = = 15
2
which represents a true percent error of εt= 1.5%.

12
• The third step:

The process can be repeated to obtain refined estimates.
For example,
f(14) f(15) = 1.569(−0.425) = −0.666
Therefore, the root is between 14 and 15.

The upper bound is redefined as 15, and the root estimate for the third
iteration is calculated as
14 + 15
𝑥𝑟 = = 14.5
2
which represents a percent relative error of εt= 1.9%.

13
• The fourth step:
And it continues…………..
The method can be repeated until the result is accurate enough to

satisfy your needs.
14
Understand Visually
A graphical depiction of the bisection method. This plot conforms to the first three iterations
15
Another Example
• Continue the previous example until the approximate
error falls below a stopping criterion of εs = 0.5%. Use the
same equation to compute the errors.
• Solution:
Iter. xl xu xr εa (%) εt (%)
1 12 16 14 - 5.279
2 14 16 15 6.667 1.487
3 14 15 14.5 3.448 1.896
4 14.5 15 14.75 1.695 0.204
5 14.75 15 14.875 0.840 0.641
6 14.75 14.875 14.8125 0.422 0.219
• Thus, after six iterations εa finally falls below εs = 0.5%, and the
computation can be terminated.
16
Exercise
• Determine the real roots of f (x) = −0.6x2 + 2.4x + 5.5 using
bisection method for three iterations. Employ initial guesses of xl =
5 and xu = 10. Compute the estimated error εa after each iteration.
• Determine the real root of f (x) = 4x3 − 6x2 + 7x − 2.3 using bisection
to locate the root. Employ initial guesses of xl = 0 and xu = 1 and
iterate until the estimated error εa falls below a level of εs = 10%.
17
𝑇𝑟𝑢𝑒 𝐸𝑟𝑟𝑜𝑟
• Review Formula:Relative True Error (percent), εt=
𝑇𝑟𝑢𝑒 𝑉𝑎𝑙𝑢𝑒 × 100
• Review Formula:Relative Approximate Error (percent),

𝑥𝑟𝑛𝑒𝑤 −𝑥𝑟𝑜𝑙𝑑
εa = × 100
𝑥𝑟𝑛𝑒𝑤
18
Pseudocode for function to implement bisection

19
Advantages of Bisection Method
• Since the method brackets the root, the method is guaranteed to

converge.
• As iterations are conducted, the interval gets halved. So one can

guarantee the error in the solution of the equation.
20
Drawbacks of bisection method
• The convergence of the bisection method is slow as it is simply

based on halving the interval.
• If one of the initial guesses is closer to the root, it will take larger
number of iterations to reach the root.
21
Thank you!!!

Bisection Method

Uploaded by

Copyright:

Available Formats

Bisection Method

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Bisection Method

Uploaded by

Copyright:

Available Formats

What are the two main categories of iterative methods?

What are the two main categories of iterative methods?

What are the main steps of the bisection method?

What are the main steps of the bisection method?

Bisection Method

• The process of iteration stops when the desired level of accuracy is

• Iterative methods, based on the position of the root relative to the

 Bracketing methods (Interpolation methods)

Iterative Method (continued)

• Two popular methods under Bracketing category are:

• These methods are based on the assumption that the function

Iterative Method (continued)

• The following iterative methods fall under this category:

• The method is based on the following theorem.

Bisection Method (continued)

• xl & xr and xr & xu

Steps of Bisection Method

Steps of Bisection Method (continued)

(c) If f(xl)f(xr)=0, the root equals xr; terminate the computation.

• The first step:

The function changes sign between values of 12 and 16.

This estimate represents a true percent relative error of εt =5.3% (note

• The second step:

which is greater than zero.

which represents a true percent error of εt= 1.5%.

• The third step:

f(14) f(15) = 1.569(−0.425) = −0.666

Therefore, the root is between 14 and 15.

which represents a percent relative error of εt= 1.9%.

• The fourth step:

The method can be repeated until the result is accurate enough to

• Review Formula:Relative Approximate Error (percent),

Pseudocode for function to implement bisection

Advantages of Bisection Method

• Since the method brackets the root, the method is guaranteed to

• As iterations are conducted, the interval gets halved. So one can

Drawbacks of bisection method

• The convergence of the bisection method is slow as it is simply

You might also like