Ch 6.1.1: Bisection Method

Bisection Method

  • The Bisection Method is a root-finding algorithm that repeatedly divides intervals in half, bracketing root each time.
  • The Intermediate Value Theorem (IVT) guarantees that root is in each successive interval; see figure below [1].

Humor



Knock knock.

Who's there?

Nanna.

Nanna who?

Nanna your business, that's who.

Behavior of Approximants

  • The midpoints of the successive intervals form a sequence \( p_n \) that approximate the root \( p \); see figure below left [2].
  • The errors \( |p - p_n| \) fluctuate up and down as \( p_n \rightarrow p \).

Midpoint Formulas

  • Intervals repeatedly halved, bracketing root each time.
  • Midpoints are computed:

\[ \begin{aligned} p_k & = \frac{a_k+b_k}{2} \\ p_k & = a_k + \frac{b_k-a_k}{2} \end{aligned} \]

  • As \( k \) increases,

\[ \begin{aligned} a_k & \rightarrow b_k \\ p_k & \rightarrow p \end{aligned} \]

Computing Midpoints

  • The midpoint \( p \) of \( [a,b] \) can be computed in one of two ways:

\[ \begin{aligned} p & = \frac{a+b}{2} \\ p & = a + \frac{b-a}{2} \end{aligned} \]

  • Algebraically equivalent but not computationally equivalent.
  • Numerically, problems arise in both when \( a \rightarrow b \):
    • The computed value \( fl\left(\frac{a+b}{2}\right) \) may not be in \( [a,b] \).
    • The computed value \( fl\left(\frac{b-a}{2}\right) \) has cancellation error but since it is a small update to \( p \), it won't change \( p \) that much.

Bisection Method Stopping Criteria

Common stopping criteria:

\[ \begin{aligned} |p_{n+1}-p_n| & < \epsilon \\ |f(p_{n+1})| & < \epsilon \end{aligned} \]

Numerical analysis caution:

  • The following are possible:
    • \( |x_{n+1}-x_n| \rightarrow 0 \) even though \( x_n \) diverges.
    • \( |r - x_n| \gg 0 \) even though \( f(x_n) \cong 0 \).

Stopping Criteria: Example 1

Stopping Criteria: Example 2

Bisection Method: Code Chunk 1

bisect <- function(f,a,b,tol = 10^(-3),m =100) {

#Initializations
iter <- 0
fa <- f(a)
fb <- f(b)
#d <- b-a  Can save flops in code below with d

#Bisection Loop
while(abs(b-a) > tol) {
  iter <- iter+1
  if(iter > m) { 
    warning("iteration max exceeded")
    break}
  xmid <- a + (b - a)/2
  ymid <- f(xmid)

Bisection Method: Code Chunk 2

xmid <- a + (b - a)/2
ymid <- f(xmid)

if(fa*ymid > 0){
  a <- xmid
  fa <- ymid  }
else {
  b <- xmid
  fb <- ymid}  }

## Return root estimate and iteration count
root <- a + (b - a)/2
return(c(root,iter)) }

Example 3

f<-function(x){x^2-1}
bisect(f,0.5,1.25,1e-3)

[1]  0.9998779 10.0000000

bisect(f,0.5,1.25,1e-6)

[1]  0.9999999 20.0000000

bisect(f,0.5,1.25,1e-9)

[1]  1 30

Example 4

f<-function(x){sin(x)}
bisect(f,2,4,1e-3)

[1]  3.141113 11.000000

bisect(f,2,4,1e-6)

[1]  3.141593 21.000000

bisect(f,2,4,1e-9)

[1]  3.141593 31.000000

Example 5

f<-function(x){x^3+4*x^2-10}

coeffs <- c(-10,0,4,1)
roots <- polyroot(coeffs)
r <- Re(roots[1])

print(paste(r));

[1] "1.3652300134141"

bisect(f,1,2,1e-13)

[1]  1.36523 44.00000

Example 5: Outputs and Errors

bisect2(f,1,2,11,r)

[1] "r =  1.3652300134141"
     Midpts       Errors
1  1.500000 1.347700e-01
2  1.250000 1.152300e-01
3  1.375000 9.769987e-03
4  1.312500 5.273001e-02
5  1.343750 2.148001e-02
6  1.359375 5.855013e-03
7  1.367188 1.957487e-03
8  1.363281 1.948763e-03
9  1.365234 4.361586e-06
10 1.364258 9.722009e-04
11 1.364746 4.839197e-04

bisect3(f,1,2,11,r)

plot of chunk unnamed-chunk-12

Convergence of Bisection Method

Suppose \( f(x) \) is continuous on \( [a,b] \) with \( f(a)\cdot f(b) < 0 \). Then the Bisection method generates a sequence of midpoints \( p_n \) that converge to a root \( p \) of \( f \) with error bound given by

\[ |p-p_n| \leq \frac{b-a}{2^n} \]

This follows from halving the interval length at each step:

\[ \begin{aligned} |p - p_1| &\leq \frac{b-a}{2} \\ |p - p_2| &\leq \frac{b-a}{2^2} \end{aligned} \]

Convergence and Error Bounds

Errors can fluctuate but interval midpoints converge to root.

\[ |p-p_n| \leq \frac{b-a}{2^n} \]

plot of chunk unnamed-chunk-13plot of chunk unnamed-chunk-13

Algebra and Convergence

We can use the error bound to determine how many iterations are required to guarantee a specified level of accuracy:

\[ \begin{aligned} \frac{b-a}{2^n} &< \epsilon \\ 2^{n} & > \frac{b-a}{\epsilon} \\ n \log(2) & > \log \left(\frac{b-a}{\epsilon}\right) \\ n & > \frac{1}{\log(2)}\log \left(\frac{b-a}{\epsilon}\right) \end{aligned} \]

Example 6

\[ f(x) = x^3+4x^2-10 \]

For \( \epsilon = 10^{-3} \) and \( [1,2] \):

\[ \begin{aligned} n & > \frac{1}{\log2)}\log \left(\frac{b-a}{\epsilon}\right) \\ n & > \frac{1}{\log2)}\log \left(\frac{2-1}{10^{-3}}\right) \\ n & > \frac{1}{\log(2)}\log \left(10^3\right) \\ n & > \frac{3\log(10)}{\log(2)} \cong 9.97 \\ n & \geq 10 \end{aligned} \]

References

[1] The Bisection Method, https://amsi.org.au/ESA_Senior_Years/SeniorTopic3/3j/3j_2content_1.html, retrieved on 11/15/2022.

[2] Numerical Analysis, 10e, Richard L. Burden, J. Douglas Faires, Annette M. Burden, Cengage Learning, 2016.