Thread: Bisection method recursive

Code:

function recbisect(f,a,b,n,err)

c = a + ( b-a)/2;

fx= inline(f);

fc= feval(fx,c);

fprintf('\n n c fc %g %g %g' , n,c,fc );

if fc < err
   return 
end
    
sa = sign(feval(fx,a));
sb = sign(feval(fx,b));
sc = sign(fc);

if ( sa == sc ) 
recbisect(f,a,c,n,err);    
else
 recbisect(f,c,b,n,err);
end

end

I get a

??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit. Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Error in ==> iscellstr at 22

How can i stop the recursion when the if condition is met.

Please help.

okay i got it.

Originally Posted by AUCC

Code:

function recbisect(f,a,b,n,err)

c = a + ( b-a)/2;

fx= inline(f);

fc= feval(fx,c);

fprintf('\n n c fc %g %g %g' , n,c,fc );

if fc < err
   return 
end
    
sa = sign(feval(fx,a));
sb = sign(feval(fx,b));
sc = sign(fc);

if ( sa == sc ) 
recbisect(f,a,c,n,err);    
else
 recbisect(f,c,b,n,err);
end

end

I get a

??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit. Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Error in ==> iscellstr at 22

How can i stop the recursion when the if condition is met.

Please help.

There is no return value from this function (as well as no terminating condition)

CB

does this recursive implementation backtrack.

Earlier i had a error value which was very small so thats why it had to recurse until a stack error came.

Then later i increased the error value and the recursive calls terminated.

I don't see any backtracking taking place?

Why is that?

Originally Posted by AUCC

does this recursive implementation backtrack.

Earlier i had a error value which was very small so thats why it had to recurse until a stack error came.

Then later i increased the error value and the recursive calls terminated.

I don't see any backtracking taking place?

Why is that?

Your termination condition should be when abs(a-b) is small not when abs(fc) is small (let alone fc< err, as you have no guarantee that fc is positive).

Also

Code:

if ( sa == sc ) 
  recbisect(f,a,c,n,err);    
else
  recbisect(f,c,b,n,err);
end

is wrong you always should be calling recbisect with arguments which for which the function evaluates to opposite signs, the above does the reverse or worse).

CB

This is untested but something more like this should work better:

Code:

function [cc,ll,uu,fcc]=recbisect(f,a,b,n,err)
 
  c = (a+b)/2;
 
  fx= inline(f);  %I will assume this works, though I don't see why it should
 
  fc= feval(fx,c);
 
  fprintf('\n n c fc %g %g %g' , n,c,fc );
 
  if abs(a-b) < err
     cc=c;ll=a;uu=b;fcc=fc;
     return  
  end
 
  if ( (feval(fx,a)*feval(fx,c)) < 0 ) 
    [cc,ll,uu,fcc]=recbisect(f,a,c,n,err);    
  else
    [cc,ll,uu,fcc]=recbisect(f,c,b,n,err);
  end
 
end

CB

Code:

function [cc,ll,uu,fcc]=recbisect(f,a,b,n,err)

what does this assignment [cc,ll,uu,fcc]=recbisect(f,a,b,n,err) really do.

and also

Code:

if ( (feval(fx,a)*feval(fx,c)) < 0 ) 
    [cc,ll,uu,fcc]=recbisect(f,a,c,n,err);    
  else
    [cc,ll,uu,fcc]=recbisect(f,c,b,n,err);
  end

Why all these assignment's [cc,ll,uu,fcc]=recbisect(f,a,c,n,err); and
[cc,ll,uu,fcc]=recbisect(f,c,b,n,err);

I cannot understand.

Please help.

Here is a cut down version that might work for you:

Code:

function y = recbisect(f,a,b,n,err)
 if n == 0;error('Cannot Find Solution in n Iterations');end
  c = (a+b)/2;
  if abs(a-b) < err
     y = c;
     return  
  end
  if f(a)*f(c) < 0  
    y = recbisect(f,a,c,n-1,err);    
  else
    y = recbisect(f,c,b,n-1,err);
  end

Here is a test:

Code:

EDU>> f = @(x)x^2+2*x-10

f = 

    @(x)x^2+2*x-10

EDU>> recbisect(f,-100,100,100,0.000001)

ans =

   -4.3166

EDU>> roots([1 2 -10])

ans =

   -4.3166
    2.3166

EDU>>

Sorry I cant elaborate more, I am a little short of time this afternoon.

Regards Elbarto

Originally Posted by AUCC

Code:

function [cc,ll,uu,fcc]=recbisect(f,a,b,n,err)

what does this assignment [cc,ll,uu,fcc]=recbisect(f,a,b,n,err) really do.

and also

Code:

if ( (feval(fx,a)*feval(fx,c)) < 0 ) 
    [cc,ll,uu,fcc]=recbisect(f,a,c,n,err);    
  else
    [cc,ll,uu,fcc]=recbisect(f,c,b,n,err);
  end

Why all these assignment's [cc,ll,uu,fcc]=recbisect(f,a,c,n,err); and
[cc,ll,uu,fcc]=recbisect(f,c,b,n,err);

I cannot understand.

Please help.

They are there to provide return values from the function so you have the final estimate of the solution "cc", the lower and upper limits of the interval containing the actual solution and the function value at the estimated solution.

CB