Bisection method recursive

Apr 2010
23
0
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.
 

CaptainBlack

MHF Hall of Fame
Nov 2005
14,972
5,271
someplace
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
 
Apr 2010
23
0
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?
 

CaptainBlack

MHF Hall of Fame
Nov 2005
14,972
5,271
someplace
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
 

CaptainBlack

MHF Hall of Fame
Nov 2005
14,972
5,271
someplace
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
 
  • Like
Reactions: AUCC
Apr 2010
23
0
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.
 
Mar 2007
206
33
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
 

CaptainBlack

MHF Hall of Fame
Nov 2005
14,972
5,271
someplace
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