Introduction to the Bisection Method

Return to List of Lectures

Previous Lecture

• Misc
  • REU information session
    • (REU = Research Experiences for Undergraduates)
    • Today (Nov. 12), 5:30 PM, South 328
  • 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
  • Handout
  • Video lecture summary/questions
    • Given f(x₁), f(x₂), if sign changes then f has a zero between
      • Sign changes if f(x₁)f(x₂) < 0
    • Find midpoint, x_m, as (x₁ + x₂)/2
    • Make sure sign changes
      • Compute f(x_m)
      • If f(x_m)f(x₁) < 0
        • Set x₂ = x_m
      • Otherwise if f(x_m)f(x₁) > 0
        • Set x₁ = x_m
    • Repeat until f(x_m) = 0 or estimated error < tolerance
  • Example
    • Function and x values
      • f(x) = x² - 4
      • (f(x) = 0 at x = ±2)
      • Initial x₁ = 1, x₂ = 4
      • Tolerance = 10%
    • Execute by hand
      • f(x) = x² - 4
      • x₁ = 1, x₂ = 4
      • Iteration 1: x_m = 2.5, f(1)f(2.5) < 0 so x₂ becomes 2.5
      • Iteration 2: x_m = 1.75, f(1)f(1.75) > 0, so x₁ becomes 1.75
        • ε = 43%
      • Iteration 3: x_m = 2.125, f(1.75)f(2.125) < 0, so x₂ becomes 2.125
        • ε = 17%
  • Pseudocode
    

    εa =                % estimated error
    εs =                % tolerance
    while εa > εs 
        find midpoint, xm, as (x1 + x2)/2
        make sure sign changes
            compute f(xm)
            if f(xm)f(x1) < 0
                set x2 = xm
            otherwise if f(xm)f(x1) > 0
                set x1 = xm

• Next
  • Finish refining the pseudocode for bisection
  • Try doing it on your own between now and Friday

Next Lecture