Math 441

Bisection Method

Bisection Method Error Estimate

Let \(p_n\), \(n = 1, 2, \ldots\) be the sequence of approximations generated by the bisection method on interval \((a,b)\), and let \(p\) be the solution to which the sequence converges. Then \[\left\lvert p_n - p\right\rvert \le \frac{b - a}{2^n} \text{ for } n \ge 1\]

---

Question: How many steps are required to guarantee that the approximation error will be at most \(\varepsilon\)?

Code in the book

function bisection(f::Function,a,b,eps,N)
    n=1
    p=0. # to ensure the value of p carries out of the while loop
    while n<=N
        p = a+(b-a)/2
        if f(p)==0 || abs(a-b)<eps
            return println("p is $p and the iteration number
                           is $n")
        end
        if f(a)f(p)<0
            b=p
        else
            a=p
        end
        n=n+1
    end
    y=f(p)
    println("Method did not converge. The last iteration gives
            $p with function value $y")
end

Summary

Bisection method:

• Requires \(f \in \mathcal{C}([a,b])\).

• Requires \(f(a)f(b) < 0\)!

• “Guaranteed” convergence

  (except floating point issues)

• One function evaluation per iteration

• Requires at least \[\log_2 \left(\frac{b-a}{\varepsilon}\right)\] iterations to reach \(\varepsilon\) precision.