The Bisection Method

Return to List of Lectures

Previous Lecture

• Misc
  • Colloquium
    • “History of Calculus”
    • Profs. Jeff Johannes and Gary Towsley
    • Wednesday, November 18, 2:30 - 3:45
    • Newton 204
    • Likely to be crowded, get there early if you can
    • Usual extra credit offer
  • Hour exam 2
    • Next Monday, November 23
    • Material since 1st exam, e.g., while, for, if, comparisons, logical operations, etc.
    • Rules and format similar to 1st exam (notably open book, notes, computer for reference)
    • Sample test now posted online
• Questions?
• Bisection
  • Video summary
    • Works on continuous functions
    • Need 2 points with opposite signs
      • So there’s a root between them
    • Shorten interval by picking midpoint x_m = (x_l + x_u) / 2
    • f(x_m) f(x_l) either + or -
      • If f( x_m) f(x_l) < 0
        • Make x_u = x_m
      • If f(x_m ) f(x_l ) > 0
        • Make x_l = x_m
      • If f(x_m ) f(x_l ) = 0
        • x_m is root
    • Continue as interval gets smaller
    • Bisection has easily calculated bound on how far x_m can be from true root, which can be used to stop the loop
      
  • Example
    • Find x such that x³ - 8 = 0 between x = 1 and x = 8 to within ±2 units
      
  • Initial pseudocode ideas
    

    bisect( f, xl, xu )
        while ...
            xm = (xl + xu) / 2
            if ...

  • Lab handout
• Next
  • Refine pseudocode
  • if statements
    • Read sections 13.1 and 13.2

Next Lecture