Section 2.1 of Burden and Faires: Bisection


Jump to: navigation, search

Convergence of Bisection

Theorem 2.1 Suppose that f \in C[a,b] and \left.f(a)*f(b)<0\right.. The bisection method generates a sequence \{r_n\}_{n=1}^\infty approximating a root \left.r\right. of \left.f\right. with

|r_n-r| \le \frac{b-a}{2^n},

when n\ge 1.

So, using the terminology of section 1.3, we'd say that the sequence \{r_n\}_{n=1}^\infty converges to \left.r\right. as O\left(\frac{1}{2^n}\right) with constant \left.\kappa=b-a\right..

In the big picture, this means that we get one additional digit of binary accuracy with each iteration of bisection.

Personal tools