BISECTION_RC
Nonlinear Equation Solver Using Bisection, with Reverse Communication


BISECTION_RC is a Python library which demonstrates the simple bisection method for solving a scalar nonlinear equation in a change of sign interval, using reverse communication (RC).

The routine assumes that an interval [a,b] is known, over which the function f(x) is continuous, and for which f(a) and f(b) are of opposite sign. By repeatedly computing and testing the midpoint, the halving change of sign interval may be reduced, so that either the uncertainty interval or the magnitude of the function value becomes small enough to satisfy the user as an approximation to the location of a root of the function.

This routine is in part a demonstration of the idea of reverse communication. Many zero finders require that the user define f(x) by writing a function with a very specific set of input and output arguments, and sometimes with a specific name, so that the user can call the zero finder, which in turn can call the function. This is sometimes an awkward formulation to follow. Reverse communication instead allows the user's calling program to retain control of the function evaluation.

To use the reverse communication zero finder, the user defines the values of A and B, and sets a parameter JOB to zero to indicate that this is the first call. From then on, the zero finder repeatedly returns a value X, asking the user to evaluate the function there. Once the user has evaluated FX = f(X), the user may accept this approximation to the root, or else call the zero finder again, passing the just-computed value of FX so that it can take another bisection step.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

BISECTION_RC is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

BACKTRACK_BINARY_RC, a Python library which carries out a backtrack search for a set of binary decisions, using reverse communication (RC).

BISECT, a Python library which seeks a solution to the equation F(X)=0 using bisection within a user-supplied change of sign interval [A,B]. The procedure is written using classes.

CG_RC, a Python library which implements the conjugate gradient (CG) method for solving a positive definite sparse linear system A*x=b, using reverse communication (RC).

LOCAL_MIN_RC, a Python library which finds a local minimum of a scalar function of a scalar variable, without the use of derivative information, using reverse communication (RC), by Richard Brent.

ROOT_RC, a Python library which seeks a solution of a scalar nonlinear equation f(x) = 0, or a system of nonlinear equations, using reverse communication (RC), by Gaston Gonnet.

ROOTS_RC, a Python library which seeks a solution of a system of nonlinear equations f(x) = 0, using reverse communication (RC), by Gaston Gonnet.

SORT_RC, a Python library which can sort a list of any kind of objects, using reverse communication (RC).

ZERO_RC, a Python library which seeks a solution of a scalar nonlinear equation f(x) = 0, using reverse communication (RC), by Richard Brent.

Reference:

  1. Werner Rheinboldt,
    Algorithms for finding zeros of a function,
    UMAP Journal,
    Volume 2, Number 1, 1981, pages 43-72.
  2. Werner Rheinboldt,
    Methods for Solving Systems of Nonlinear Equations,
    SIAM, 1998,
    ISBN: 089871415X,
    LC: QA214.R44.

Source Code:

You can go up one level to the Python source codes.


Last revised on 29 January 2016.