Exercises on the bisection method/Solution

Solution of the exercises on the bisection method

Exercise 1

• The following is a possible implementation of the bisection method with Octave/MATLAB:
function [x e iter]=bisection(f,a,b,err,itermax)
%The function bisection find the zeros of function
%with the bisection algorithm.
%It returns the zero x, the error e, and the number of iteration needed iter
%
%HOW TO USE IT:
%Example
%>>f=@(x)x.^3;
%>>a=-1; b=2;
%>>err=1e-5; itermax=1000;
%>>[x e iter]=bisection(f,a,b,err,itermax);

e=b-a;
iter=0;
fa=f(a);
if( fa .* f(b) >= 0 )
x =[];
disp("f(a) *  f(b) >= 0! No solution!")
else
while( e > err )
iter = iter + 1;
x = 0.5 * ( b + a )
e = abs(b - x);
fx = f(x);
if( fx == 0 )
break;
elseif( fx * fa > 0 )
a = x;
fa = fx;
else
b = x;
end
if( iter == itermax)
break;
end
end
end

• The solution of the points 1, 2 e 3 can be found in the example of the bisection method.

For point 4 we have

${\displaystyle k\geq \log _{2}3\cdot 10^{2}0\pi \approx 69.8}$,

so we would need at least 70 iterations. The chance of convergence with such a small precision depends on the calculatord: in particular, with Octave, the machine precision is roughly ${\displaystyle 2\cdot 10^{-16}}$. For this reason it does not make sense to choose a smaller precision. The number of iterations, if we don't specify a maximum number, would be infinite.

Exercise 2

1. To verify the existence of a root ${\displaystyle \alpha }$ we need to show that the hypothesis roots theorem are satisfied. The first hypothesis requires ${\displaystyle f}$ to be continuous. Obviosly this is a continuous function since it is sum of two continuous functions. The second hypotheses requires the function to have oppiste signs at the interval extrema, and in fact we find
${\displaystyle f(-2)\approx -3.86,\quad f(0)=1\quad \implies f(a)f(b)<0}$.
Comparison of the average and actual errors computed with the bisection method in logarithmic scale..
To show the uniqueness of the root we need to prove that the function ${\displaystyle f}$ is monotone and in fact
${\displaystyle f'(x)=e^{x}-2x>0\quad \forall x\in [-2,0]}$.
2. The number of iterations need is given by
${\displaystyle k\geq \log _{2}{\frac {b-a}{\epsilon }}=\log _{2}2\cdot 10^{8}\approx 25.8}$,
and so we have ${\displaystyle k\geq 26}$.
3. The interval ${\displaystyle [-2,-1]}$ does not contain aany root as the second hypotesis of the roots theorem fails, in fact
${\displaystyle f(-2)\approx -3.86,\quad f(-1)=-0.63\quad \implies f(a)f(b)>0}$.
4. ${\displaystyle \alpha \approx -0.7035}$
5. In the plot we show in red the average errorand in blu the actual error. From the graph, it is clear that the actual error is not a monotone function. Moreover, note that the global behavior of both curves is the same, clarifying the term average error for ${\displaystyle \displaystyle e_{k}}$.

Exercise 3

For the solution look at the convergence analysis in the bisection method page.