Bisection method without any given interval

I want to make a matlab code for given condition

"provide no interval as an initial guess but provide a tolerance of 10−5 and enable the print flag so we can see the method in action."

I have a really hard time with this question now

here is my approach. my code is not work at all. Could you help me with this code?

clear
f = @(x) x^2 + 2*x - 8;
[interval1,nstepmax1,tol1,print_flag1] = bisect(f)


function [interval,nstepmax,tol,print_flag] = bisect(varargin)

default_interval = randi([0 10], 1, 2);
default_tol = 10^-8;
default_nstepmax = 1000;
default_print_flag = false;

p = inputParser;
addRequired(p,'f') 
addParameter(p,'Interval',default_interval,@isnumeric); 
addParameter(p,'MaxSteps',default_nstepmax);  
addParameter(p,'Tolerance',default_tol);
addParameter(p,'Print',default_print_flag);

parse(p,varargin{:})


f = p.Results.f;
interval = p.Results.Interval;
nstepmax = p.Results.MaxSteps;
tol = p.Results.Tolerance;
print_flag = p.Results.Print;

p.Results.Interval(1,1) 
p.Results.Interval(1,2)

if (p.Results.Interval(1,1)*p.Results.Interval(1,2)) >= 0
    error
else
fa = f(p.Results.Interval(1,1));
fb = f(p.Results.Interval(1,2));
while (p.Results.Interval(1,2) - p.Results.Interval(1,1))/2 > tol
    c = (p.Results.Interval(1,2) + p.Results.Interval(1,1))/2;
    fc = f(c);
    if fc == 0
        break
    end
    if sign(fc)*sign(fa) < 0
        b = c;
        fb = fc;
    else
        a = c;
        fa = fc;
    end
end
xc = (a+b)/2;
fprintf("the root is: ", xc);
end
end

Answer 1

[Walter Roberson]

In the form stated, the question is not possible to implement. We can see from

f = @(x) x^2 - 2*x + 8;

that your code is expected to be able to handle functions that have an even number of zero crossings. However, you cannot use bisection methods until you have identified an interval that has an odd number of zero crossings, and you have been assured that the function is finite everywhere over the interval.

When you do not already have a search interval and any given interval might have an even number of crossings (including no crossings) then you cannot use bisection methods to find a crossing.

Suppose for example you have the hypothesis that there is a zero crossing between x = 10^5 and x = 10^20, but that the function is positive at both those end points. You could look at the center of the interval near 5*10^19 and find that the function is positive there too. Ask yourself which situation you are facing:

• there is a non-zero even number of crossings in the left interval and no crossings in the right interval
• there are no crossings in the left interval and a non-zero even number of crossings in the right interval
• there is a non-zero even number of crossings in the left interval and a non-zero even number of crossings in the right interval.
• there are not actually any crossings in either of the two intervals and the initial guess was wrong

What information do we have to decide which of those four situations we are facing? All we know is that the function is positive at the left, positive at the middle, and positive at the right. All we can do is queue both of the sub-intervals for examination by bisection.

So now we examine the queue and see we are working on the subintervals x = 10^5 to near 5*10^19. We search in the middle again, find a positive value, and again we have the same four possibilities. So we have to queue both sub-intervals, and try again.

And for each of those subintervals that are queued, we need to bisect it, and keep bisecting, and keep bisecting, until we find a zero crossing, or until we have bisected to the point that our endpoints are adjacent representable numbers (indicating that there were in fact no zero crossings in that sub-interval). And then we have to do the same thing for all of the other subintervals.

Effectively we end up having to check every representable number between the initial start and end guess just to determine whether there were any zero-crossings in the initial guess range. And we might find out that the initial range guess was wrong.

Thus, the problem cannot be solved in the general case -- not by bisection methods.

The problem potentially might be solvable under constraints, such as if we are promised that there are an odd number of zero crossings.. and no asymptopes.

... Of course the problem is also potentially solvable if you forgot to mention some very important context, such as the possibility that you had previously been instructed that if no interval was passed in to the function, that you were to default to a particular interval... in which you are promised that there will be an odd number of zero crossings.

[Hyun Suk Song]

Sorry, function is x^2 + 2*x - 8 I will modify it

[Walter Roberson]

syms x
f = x^2 + 2*x - 8

f = 

fplot(f, [-5 5])

roots([1 2 -8])

ans = 2×1

-4 2

Now we know from calculus methods where the roots are, by examination of the function. But your bisection routine is not permitted to analyze the function (and naive calculus methods might not be productive.)

Suppose you were given

OFF = (rand() - 1/2) * realmax * 2;
f = @(x) x^2 + 2*x - OFF

f = function_handle with value:
    @(x)x^2+2*x-OFF

Where are the zeros for that function? You could even examine its source code but you cannot read out what the value of OFF is, so without using techniques beyond what can be done using bisection alone, you have no idea where the zeros are, and so have no idea what starting interval to use is.

You now have one of a small number of cases:

1. Maybe it is just not something you can do with pure bisection methods;
2. Maybe you have been told constraints, promised that there is at least one zero within a particular range of values
3. Maybe earlier in the assignment you were told that when no initial interval is passed in, that you are are to assume a particular interval