Exercises on the bisection method/Solution

Template:S Template:Center topTemplate:FontTemplate:Center bottom
Template:Navigation bar

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

$k\ge {\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 $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 $\alpha$ we need to show that the hypothesis roots theorem are satisfied. The first hypothesis requires $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

   $f(-2)\approx -3.86,f(0)=1⟹f(a)f(b)<0$.

   File:NumericalAnalysis BisectionExercise 2.png

   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 $f$ is monotone and in fact

   $f^{\prime }(x)=e^x-2x>0\mathrm{\forall }x\in [-2,0]$.

2. The number of iterations need is given by

   $k\ge {\log }_2\frac{b-a}{ϵ}={\log }_{2}2\cdot 10^8\approx 25.8$,

   and so we have $k\ge 26$.

3. The interval $[-2,-1]$ does not contain aany root as the second hypotesis of the roots theorem fails, in fact

   $f(-2)\approx -3.86,f(-1)=-0.63⟹f(a)f(b)>0$.

4. $\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 $e_k$.

Exercise 3

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