Bisection Method - Multiple roots

I have correctly coded a bisection method. When i widen the interval that includes 2 or more roots it still only displays one root. How would i edit the code so that other roots are found? Thanks!!

Answer 1

[James Tursa]

You need to provide different starting positions that bracket only one root at a time. In general you can't guarantee which root the algorithm will converge to if you bracket more than one root.

[Tom Heart]

thanks for the reply, i understand from my current method that i need to bracket one root at a time, but how would i get matlab to automatically select this bracket without me looking at it on a graph?

[John D'Errico]

You will never be able to absolutely assure that you find every root using ANY method. I say that because any method that you choose can always be confused by carefully choosing a nasty function.

But you can do pretty well. For example, suppose you want to find the roots of cos(x), between 0 and 100? Yes, I know that is easy. But suppose you don't know where they are?

Just sample the function at a fine enough interval that you are confidant that no two roots lie in the same interval.

fun = @(x) cos(x);
x = linspace(0,100,500);
y = fun(x);

Look for sign changes

Sy = sign(y);
Sy = Sy(1:end-1).*Sy(2:end);
bracketind = find(Sy <= 0);

xbr = [x(bracketind)',x(bracketind + 1)']

xbr =
     1.4028       1.6032
     4.6092       4.8096
     7.8156        8.016
     10.822       11.022
     14.028       14.228
     17.234       17.435
      20.24       20.441
     23.447       23.647
     26.653       26.854
     29.659        29.86
     32.866       33.066
     36.072       36.273
     39.078       39.279
     42.285       42.485
     45.491       45.691
     48.497       48.697
     51.703       51.904
      54.91        55.11
     58.116       58.317
     61.122       61.323
     64.329       64.529
     67.535       67.735
     70.541       70.741
     73.747       73.948
     76.954       77.154
      79.96        80.16
     83.166       83.367
     86.373       86.573
     89.379       89.579
     92.585       92.786
     95.792       95.992
     98.798       98.998

The problem is if two roots are closer than the step in my sampling, thus here:

x(2) - x(1)
ans =
       0.2004

Of course, since we know that the roots of cos(x) are separated by exactly pi, then any sampling with an interval of less than pi would suffice. The trick is to choose a small enough interval to assure you catch them.

[Tom Heart]

Thanks a lot, that works great. As i have some roots below zero, when you change linspace to include these it does not display all of the roots? Currently I have the copied the code so that it runs twice. Once for linspace x = linspace(-100,0,500) and again for x = linspace(0,100,500). I then combine the outputs to get the end result with all the roots. This is fine but just wondering if there was a neater/quicker way to do it without copying the code? Thanks again for all your help.