bisection method on $f(x) = \sqrt{x} − 1.1$

Question

the question goes something like this :

Apply the bisection method using the code in slides to find the root of the function $f(x) = \sqrt{x} − 1.1$ starting from the interval $[0, 2]$ with a tolerance of $\epsilon = 1.e-8$

• How many iterations are required ? Does the iteration count match the expectations, based on our convergence analysis ?
• What is the resulting absolute error ? Could this absolute error be predicted by our convergence analysis ?

the first part of the question is pretty easy to code out and here is my code for the same :

def func(x):
    return np.sqrt(x)-1.1

def bisection(a, b, tol):
 
    if (func(a) * func(b) >= 0):
        return
  
    c = a
    itercount=0
    while ((b-a) >= tol):
 
        c = (a+b)/2
  
        
        if (func(c) == 0.0):
            return c

        if (func(c)*func(a) < 0):
            b = c
        else:
            a = c
        itercount+=1
    return c, itercount

we get the theoretical number of iterations using the relation $n_{_{theoretical}} = \log_{_{2}} \left( \frac{b-a}{\epsilon}\right)$ which is very close to that counted by the programme ( $n_{_{calculated}} = 28$).

the absolute error = $8.94 \cdot 10^{-10}$ , but I have a problem understanding how this error could have been predicted by the convergence analysis, any hints or solutions are welcome.

Answer 1

Let $S_n$ be the $nth$ root approximation generated by the Bisection method, and $a_n,b_n$ denote the $nth$ $a,b$ for every iteration. We also have the exact root $S$ between the interval $(a,b)$ and $f(a)f(b)<0$ on the interval $[a,b] = [0, 2]$

For $n=1$, it is easy to see that $$b_1-a_1=b-a$$ For $n>1$, iterations of the Bisection method has been made so: $$b_n-a_n=\frac{b-a}{2^{n-1}}$$

From the Biscetion method: $$S_n=a_n+\frac{b_n-a_n}{2}$$ $$S_n-a_n=\frac{b_n-a_n}{2}$$ Obviously $S\in(a_n,b_n)$ so $$|S_n-S|\leqslant \frac{b_n-a_n}{2}$$ $$|S_n-S|\leqslant\frac{b-a}{2^n}$$

Let $\epsilon = |S_n-S|$ $$\epsilon \leqslant\frac{b-a}{2^n}$$ $$n\leqslant \log_2(\frac{b-a}{\epsilon})$$

We now see that the $nth$ iteration corresponds to the distance between $S_n$ and $S$, which is bounded by $$\frac{b-a}{2^n}$$