Introduction to the Bisection Method

Return to List of Lectures

Previous Lecture

• Misc
  • Solutions to hour exam questions available through “Exercises” web page
  • Colloquium
    • Monday March 30, 4:00-5:00 pm
    • Newton 201
    • Julie Croteau ’97
    • Department of Mathematics
    • Corning Community College
    • “Bodybuilding! ... for Mathematicians”
• Questions?
  • From bisection video...
    • ε_a = “relative absolute(?) error”
      • = Estimate of difference between what algorithm thinks is the zero of f and what really is, measured by fractional change in estimate
    • ε_s = “pre-specified relative error”
      • = Target for relative absolute error
    • How to stop?
      • “while” loop = repeat while some condition is true
      • Decision-making = “if” statement
• Bisection
  • Basic algorithm:
    • Choose x_l and x_u such that f(x_l)f(x_u) < 0
    • Find midpoint: x_m = ( x_l + x_u ) / 2
      • (In order to find a smaller interval where sign changes)
    • 3: Find f(x_l )f(x_m)
    • If < 0
      • x_l stays same, x_u = x_m
    • if > 0
      • x_l = x_m, x_u stays same
    • If = 0
      • Root = x_m, stop
    • Find new midpoint: x_m = ( x_l + x_u ) / 2
    • Find ε_a = ( | new x_m - old x_m | / new x_m ) * 100
    • If < ε_s go back to step 3
  • Relation to Newton’s method?
    • Newton uses derivative to find a linear approximation to function
    • Bisection uses a more methodical process of halving the interval that contains the root
    • Newton often converges faster than bisection
    • But bisection is guaranteed to converge whereas Newton won’t for certain starting values
      
  • Example
    • f(x) = x³ ( f(0) = 0 )
    • x_l = -2
    • x_u = 4
      • Inputs = f, x_l , x_u, ε_s
    • Output should be x=0, i.e., x at which f(x)=0
    • Carry out a few steps by hand
      • f(-2)f(4) = -512 < 0
      • x_m = ( -2 + 4 ) / 2 = 1
      • f(-2)f(1) = -8 < 0
      • Keep x_l same, x_u = 1
      • New x_m = -1/2
      • ε_a = 300%
• Next
  • What needs to be refined?
  • “While”
    • Read section 5.3

Next Lecture