The Bisection Algorithm

Return to List of Lectures

Previous Lecture

• Misc
  • Another colloquium
    • Wednesday, Nov. 19, 2:30, Newton 202
    • “Concise History of Calculus”
    • Profs Towsley and Johannes
    • Extra credit for attending and writing summary/reaction
  • Exam 2
    • Wednesday, Nov. 19
    • Material since 1st hour exam (e.g., for loops, vectorization, while loops, if statements, algorithms - Riemann sums, trapezoid rule, Newton, bisection)
    • Rules and format similar to 1st hour exam, especially open book, notes, computer references
• Questions?
• The Bisection Method
  • Pseudocode
    

    function bisection( f, x1, x2 )
        εa = ...        % estimated error
        εs = ...        % tolerance
        xm = x1
        while εa > εs 
            xlast = xm
            xm = (x1 + x2)/2
            εa = | xlast - xm | / xm
            if f(xm)f(x1) < 0
                x2 = xm
            elseif f(xm)f(x1) > 0
                x1 = xm
            else
                εa = 0
            end
        end
        return xm 

  • Bisection vs Newton?
    • Usability: bisection needs to know roughly where a zero is
    • Convergence: Newton usually does well, but no guarantee
      • Bisection: after n iterations with initial interval length (x₂-x₁), interval length is (x₂-x₁)/2ⁿ
  • Start writing the code...
• Next
  • Finish bisection

Next Lecture