Bisection method for many different types of functions not converging when the search range includes/is nearby a local minimum

243 Views Asked by At

I've been teaching a couple of lessons in computer-aided engineering at university, and part of the lessons have involved using recursive algorithms to find roots such as the Bisection method, Newton-Raphson method, and Secant method. My question is specifically regarding the Bisection method.

I've noticed that when I use the following algorithm in an attempt to find the roots of functions when the following conditions are met, the method does not converge and behaves strangely. I will explain after the presenting the algorithm here.

for i=1:length(a)
    k = 1;  % start the iterations out at 1 at the beginning of each new search
    while errorCalc>errorTol % while the error calculated remains larger than the tolerance
        c = (a + b)/2;    % calculate the midpoint

        fc = f(r);  % evaluate the function at the midpoint, f is the anonymous function representing the equation to find the root
        
        errorCalc = abs(fc);  % since the error is compared to zero I will use the absolute value

        if fc<0
            a = c;   % replace the lower bound with the midpoint
        elseif fc>0
            b = c;   % replace the upper bound with the midpoint
        end
        k = k+1;
    end
end

When the equation f has a 1) derivative equal to zero within the original search range, 2) the local extrema is just outside but close to the boundaries of the search range, or 3) derivative of f becomes negative anywhere within the search range this algorithm fails to find any root.

In fact, it always converges to the location of the minimum or whichever boundary value is closest to the minimum. When I modify the equations so that there is a maximum just outside the domain instead it is able to find the root without any problems.

I have tried this with polynomials such as $0.8x^4-2.48x^3-1.992x^2+11.3792x-8.79472$ as well as other combinations of transcendental functions without much success. I've only been successful after changing any equation I select to not fit these criteria.

I'm not very experienced with this so it is possible there is some nuance I am missing in my algorithm, or maybe it's an inability built-in to the bisection method. This is my first year teaching too so that isn't helping much.