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.
Best Answer
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}$$