File Exchange

image thumbnail

Bisection Method Root Finding

version 1.16 (6.95 KB) by Sky Sartorius
Very simple to use and robust method that takes array inputs, so it even has advantages over fzero.

65 Downloads

Updated 16 May 2021

From GitHub

View Version History

View license on GitHub

BISECTION is a fast, simple-to-use, and robust root-finding method that handles n-dimensional arrays.

Additional optional inputs and outputs for more control and capabilities that don't exist in other implementations of the bisection method or other root finding functions like fzero.
This function really shines in cases where fzero would have to be implemented in a loop to solve multiple cases, in which case this will be much faster.

It can find zero or non-zero roots.

This code can be a bit cryptic. This is for the sake of speed and increased capability. See the many acknowledged other submissions for simpler, easier-to-follow implementations to understand the basics of the bisection method.

Cite As

Sky Sartorius (2021). Bisection Method Root Finding (https://github.com/sky-s/bisection), GitHub. Retrieved .

Comments and Ratings (30)

Niket Parikh

Hello Sky,

I am getting NaN as the output and I am not sure what to do, could you please help me?
Is there some error from my side here:
bisection(@(phi) sqrt(1-phi'*phi)*(I*phi) + hat(phi)*(I*phi) - .5*dt*p - .5*dt*dt*tauhist(:,k+1),[-1;-1;-1],[1;1;1])
I is a 3x3 matrix, dt is a real no., tauhist(:,k+1) and p are 3D vectors and all these are known. Please let me know if you need more details.
Thanks a lot!

Emin Tasdelen

Xiangyuan ZHENG

A very nice code, but I'm wondering if it can solve coupled nonlinear equations, say x(1)^2-x(2)^2+3*x(3)-5=0, x(1)^2+x(3)^2-4*x(1)*x(2)*x(3)+89=0, x(1)*x(2)-x(3)^3-23=0

Abdel-Rahman Ashraf

Elizabeth Case

Sky Sartorius

Issues brought up by Alex are now fixed. Thank you, Alex!

Berke Gogce

Muhtesem bir dosya... Emegi gecen herkesin amk...

Sky Sartorius

Hi Alex,
Thank you for the suggestions. I will look into getting rid of the extra function evaluation at each iteration. I also put bisection up on GitHub if you would like to contribute there.

Alex

It would be good to change the first line, to clarify that the function satisfies one of the objective functions, not both (OR not AND)

Also line 167: outsideTolX = (ub - lb) > tolX;
Should be: outsideTolX = (x - lb) > tolX;

Alex

This is very nice, there is room for some optimization though. Currently the function f is called twice in every iteration, only once is necessary.

You can replace the main loop with the code below to speed things up (you can then also remove the section that optionally flips the ub and lb):

lb_sign = sign(f(lb));
while true
x = (lb + ub) / 2;
fx = f(x);
conX = abs(ub - x) < tolX;
conFun = abs(fx) < tolFun;
con = conX | conFun;
if all(con(:))
break;
end
select = sign(fx) == lb_sign;
lb(select) = x(select);
ub(~select) = x(~select);
end

Sky Sartorius

tbaracu: The function requires at least three inputs, e.g. bisection(@cos,-3,3).

tbaracu

It doesn't work:

>> bisection
Not enough input arguments.

Error in bisection (line 115)
ub_in = ub; lb_in = lb;

robert

Tim DeWolf

Gail Gutierrez

Great Function!!!

David Vicente

Thomas

praydz 96

MK

Herbert

Ole

If there are several root in the interval does it find the first closes to LB only ?

Chi-Fu

great program, saved me a lot of time, thank you!

The vectorization feature is really really helpful. I was vexed with having to put fzero into for loops.

Philip Ohnewein

Works brilliantly in my case. Replaces a loop with ~1 million iterations, brings down execution time by several orders of magnitude.
Plus it is well-written and well-documented and a numerically robust method.

Fabian

Excellent file. Much faster than using fzero in a long loop!

Siegmar W

Thanks! Had a similar file of my own, but yours is better!

Umberto Picchini

I am so glad I found this submission and I'm very grateful to the author for providing an excellent, well-documented code. I had my custom Newton-Raphson algorithm (with provided analytical gradient) invoked thousands of times inside a for loop. I substituted the loop with a single invocation to bisection.m and achieved a 15x acceleration! Awesome.

Sky Sartorius

I just uploaded an entirely new function with almost all new code and documentation and a lot of added features. With so much new code, please let me know if you find a bug.

This is about as far as I'll take this function. I would love to see MathWorks or someone in the community develop a vectorized implementation of Brent's method, i.e. make FZERO vectorized to be able handle array problems. A vectorized FZERO (with a TolFun feature) would be superior to this in every way.

Yoshiaki

There seems to be a typo on line 80:
jnk = f(UB+LB)/2; % test if f returns multiple outputs

It should be
f((UB+LB)/2)

Matthew

Excellent documentation with example. Simple function that works as advertised.

MATLAB Release Compatibility
Created with R2015a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!