TEST_ZERO
Zero Finder Tests

TEST_ZERO is a C++ library which defines nonlinear functions that may be used to test zero finders.

Zero finders are programs that seek a (scalar) root of a scalar equation F(X) = 0. Some zero finders require that an initial "change-of-sign" interval [A,B] be supplied, with the function having opposite sign at the two endpoints, thus guaranteeing that there is some value C between A and B for which F(C) = 0 (assuming that the function F is continuous). In other cases, a particular zero finder may want information about the first or second derivative of the function. And some zero finders can handle situations where the function has a multiple root, or where the function is a polynomial.

TEST_ZERO supplies a set of nonlinear functions, along with change of sign interval, first and second derivatives, suggested starting points, so that the behavior of any zero finder can be analyzed.

TEST_ZERO also includes implementations of some simple zero finders, as a demonstration of how the package might be used.

The functions, which are accessible by number, are

1. f(x) = sin ( x ) - x / 2.
2. f(x) = 2 * x - exp ( - x ).
3. f(x) = x * exp ( - x ).
4. f(x) = exp ( x ) - 1 / ( 10 * x )^2.
5. f(x) = ( x + 3 ) * ( x - 1 )^2.
6. f(x) = exp ( x ) - 2 - 1 / ( 10 * x )^2 + 2 / ( 100 * x )^3.
7. f(x) = x^3.
8. f(x) = cos ( x ) - x.
9. the Newton Baffler.
10. the Repeller.
11. the Pinhead.
12. Flat Stanley.
13. Lazy Boy.
14. the Camel.
15. a pathological function for Newton's method.
16. Kepler's Equation.
17. f(x) = x^3 - 2*x - 5, Wallis's function.
18. f(x) = (x-1)^7, written term by term.
19. f(x) = cos(100*x)-4*erf(30*x-10), the jumping cosine.

Licensing:

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

Languages:

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

Related Data and Programs:

BISECTION_RC, a C++ 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 reverse communication.

BRENT, a C++ library which contains Richard Brent's routines for finding the zero, local minimizer, or global minimizer of a scalar function of a scalar argument, without the use of derivative information.

GSL, a C++ library which includes rootfinding routines.

ZERO_RC, a C++ library which seeks solutions of a scalar nonlinear equation f(x) = 0, or a system of nonlinear equations, using reverse communication.

Reference:

1. Richard Brent,
   Algorithms for Minimization without Derivatives,
   Dover, 2002,
   ISBN: 0-486-41998-3,
   LC: QA402.5.B74.
2. Peter Colwell,
   Solving Kepler's Equation Over Three Centuries,
   Willmann-Bell, 1993,
   ISBN: 0943396409,
   LC: QB355.5.C65.
3. George Donovan, Arnold Miller, Timothy Moreland,
   Pathological Functions for Newton's Method,
   American Mathematical Monthly, January 1993, pages 53-58.
4. Arnold Krommer, Christoph Ueberhuber,
   Numerical Integration on Advanced Computer Systems,
   Springer, 1994,
   ISBN: 3540584102,
   LC: QA299.3.K76.
5. Jean Meeus,
   Astronomical Algorithms,
   Second Edition,
   Willman-Bell, 1998,
   ISBN: 0943396611,
   LC: QB51.3.E43M42.

Source Code:

• test_zero.cpp, the source code;
• test_zero.hpp, the include file;
• test_zero.sh, commands to compile the source code;

Examples and Tests:

• test_zero_prb.cpp, the calling program;
• test_zero_prb.sh, commands to compile, link and run the calling program;
• test_zero_prb_output.txt, the output file.

PNG images of the graphs of some of the functions were made using MATLAB:

• p01_fx.png, an image of P01_FX(X) over [-4,+4].
• p02_fx.png, an image of P02_FX(X) over [-0.5, +3.0].
• p03_fx.png, an image of P03_FX(X) over [-0.1,+4].
• p04_fx.png, an image of P04_FX(X) over [-4,+2].
• p05_fx.png, an image of P05_FX(X) over [-4,+2].
• p06_fx.png, an image of P06_FX(X) over [-4,+2].
• p07_fx.png, an image of P07_FX(X) over [-1,+1].
• p08_fx.png, an image of P08_FX(X) over [-4,+4].
• p09_fx.png, an image of P09_FX(X) over [5,7].
• p10_fx.png, an image of P10_FX(X) over [-2,+2].
• p11_fx.png, an image of P11_FX(X) over [+1,+10].
• p12_fx.png, an image of P12_FX(X) over [-0.5,+0.5].
• p13_fx.png, an image of P13_FX(X) over [0,100].
• p14_fx.png, an image of P14_FX(X) over [-0.5,+2.0].
• p15_fx.png, an image of P15_FX(X) over [-4,+4].
• p16_fx.png, an image of P16_FX(X) over [0,50].
• p17_fx.png, an image of P17_FX(X) over [-2,+4].
• p18_fx.png, an image of P18_FX(X) over [0.988,1.012].
• p19_fx.png, an image of P19_FX(X) over [0.0,1.0].

List of Routines:

• BISECTION carries out the bisection method to seek a root of F(X) = 0.
• BRENT implements the Brent bisection-based zero finder.
• MULLER carries out Muller's method for seeking a real root of a nonlinear function.
• NEWTON carries out Newton's method to seek a root of F(X) = 0.
• P00_FX evaluates a function specified by problem number.
• P00_FX1 evaluates the first derivative of a function specified by problem number.
• P00_FX2 evaluates the second derivative of a function specified by problem number.
• P00_PROB_NUM returns the number of problems available.
• P00_RANGE returns an interval bounding the root for any problem.
• P00_ROOT returns a known root for any problem.
• P00_ROOT_NUM returns the number of known roots for a problem.
• P00_START returns starting point for any problem.
• P00_START_NUM returns the number of starting points for a problem.
• P00_TITLE returns the title for a given problem.
• P01_FX evaluates sin ( x ) - x / 2.
• P01_FX1 evaluates the derivative of the function for problem 1.
• P01_FX2 evaluates the second derivative of the function for problem 1.
• P01_RANGE returns an interval bounding the root for problem 1.
• P01_ROOT returns a root for problem 1.
• P01_ROOT_NUM returns the number of known roots for problem 1.
• P01_START returns a starting point for problem 1.
• P01_START_NUM returns the number of starting point for problem 1.
• P01_TITLE returns the title of problem 1.
• P02_FX evaluates 2 * x - exp ( - x ).
• P02_FX1 evaluates the derivative of the function for problem 2.
• P02_FX2 evaluates the second derivative of the function for problem 2.
• P02_RANGE returns an interval bounding the root for problem 2.
• P02_ROOT returns a root for problem 2.
• P02_ROOT_NUM returns the number of known roots for problem 2.
• P02_START returns a starting point for problem 2.
• P02_START_NUM returns the number of starting point for problem 2.
• P02_TITLE returns the title of problem 2.
• P03_FX evaluates x * exp ( - x ).
• P03_FX1 evaluates the derivative of the function for problem 3.
• P03_FX2 evaluates the second derivative of the function for problem 3.
• P03_RANGE returns an interval bounding the root for problem 3.
• P03_ROOT returns a root for problem 3.
• P03_ROOT_NUM returns the number of known roots for problem 3.
• P03_START returns a starting point for problem 3.
• P03_START_NUM returns the number of starting point for problem 3.
• P03_TITLE returns the title of problem 3.
• P04_FX evaluates exp ( x ) - 1 / ( 10 * x )^2.
• P04_FX1 evaluates the derivative of the function for problem 4.
• P04_FX2 evaluates the second derivative of the function for problem 4.
• P04_RANGE returns an interval bounding the root for problem 4.
• P04_ROOT returns a root for problem 4.
• P04_ROOT_NUM returns the number of known roots for problem 4.
• P04_START returns a starting point for problem 4.
• P04_START_NUM returns the number of starting point for problem 4.
• P04_TITLE returns the title of problem 4.
• P05_FX evaluates ( x + 3 ) * ( x - 1 )^2.
• P05_FX1 evaluates the derivative of the function for problem 5.
• P05_FX2 evaluates the second derivative of the function for problem 5.
• P05_RANGE returns an interval bounding the root for problem 5.
• P05_ROOT returns a root for problem 5.
• P05_ROOT_NUM returns the number of known roots for problem 5.
• P05_START returns a starting point for problem 5.
• P05_START_NUM returns the number of starting point for problem 5.
• P05_TITLE returns the title of problem 5.
• P06_FX evaluates exp ( x ) - 2 - 1 / ( 10 * x )^2 + 2 / ( 100 * x )^3.
• P06_FX1 evaluates the derivative of the function for problem 6.
• P06_FX2 evaluates the second derivative of the function for problem 6.
• P06_RANGE returns an interval bounding the root for problem 6.
• P06_ROOT returns a root for problem 6.
• P06_ROOT_NUM returns the number of known roots for problem 6.
• P06_START returns a starting point for problem 6.
• P06_START_NUM returns the number of starting point for problem 6.
• P06_TITLE returns the title of problem 6.
• P07_FX evaluates x^3.
• P07_FX1 evaluates the derivative of the function for problem 7.
• P07_FX2 evaluates the second derivative of the function for problem 7.
• P07_RANGE returns an interval bounding the root for problem 7.
• P07_ROOT returns a root for problem 7.
• P07_ROOT_NUM returns the number of known roots for problem 7.
• P07_START returns a starting point for problem 7.
• P07_START_NUM returns the number of starting point for problem 7.
• P07_TITLE returns the title of problem 7.
• P08_FX evaluates cos ( x ) - x.
• P08_FX1 evaluates the derivative of the function for problem 8.
• P08_FX2 evaluates the second derivative of the function for problem 8.
• P08_RANGE returns an interval bounding the root for problem 8.
• P08_ROOT returns a root for problem 8.
• P08_ROOT_NUM returns the number of known roots for problem 8.
• P08_START returns a starting point for problem 8.
• P08_START_NUM returns the number of starting point for problem 8.
• P08_TITLE returns the title of problem 8.
• P09_FX evaluates the Newton Baffler.
• P09_FX1 evaluates the derivative of the function for problem 9.
• P09_FX2 evaluates the second derivative of the function for problem 9.
• P09_RANGE returns an interval bounding the root for problem 9.
• P09_ROOT returns a root for problem 9.
• P09_ROOT_NUM returns the number of known roots for problem 9.
• P09_START returns a starting point for problem 9.
• P09_START_NUM returns the number of starting point for problem 9.
• P09_TITLE returns the title of problem 9.
• P10_FX evaluates the Repeller.
• P10_FX1 evaluates the derivative of the function for problem 10.
• P10_FX2 evaluates the second derivative of the function for problem 10.
• P10_RANGE returns an interval bounding the root for problem 10.
• P10_ROOT returns a root for problem 10.
• P10_ROOT_NUM returns the number of known roots for problem 10.
• P10_START returns a starting point for problem 10.
• P10_START_NUM returns the number of starting point for problem 10.
• P10_TITLE returns the title of problem 10.
• P11_FX evaluates the Pinhead.
• P11_FX1 evaluates the derivative of the function for problem 11.
• P11_FX2 evaluates the second derivative of the function for problem 11.
• P11_RANGE returns an interval bounding the root for problem 11.
• P11_ROOT returns a root for problem 11.
• P11_ROOT_NUM returns the number of known roots for problem 11.
• P11_START returns a starting point for problem 11.
• P11_START_NUM returns the number of starting point for problem 11.
• P11_TITLE returns the title of problem 11.
• P12_FX evaluates Flat Stanley.
• P12_FX1 evaluates the derivative of the function for problem 12.
• P12_FX2 evaluates the second derivative of the function for problem 12.
• P12_RANGE returns an interval bounding the root for problem 12.
• P12_ROOT returns a root for problem 12.
• P12_ROOT_NUM returns the number of known roots for problem 12.
• P12_START returns a starting point for problem 12.
• P12_START_NUM returns the number of starting point for problem 12.
• P12_TITLE returns the title of problem 12.
• P13_FX evaluates Lazy Boy.
• P13_FX1 evaluates the derivative of the function for problem 13.
• P13_FX2 evaluates the second derivative of the function for problem 13.
• P13_RANGE returns an interval bounding the root for problem 13.
• P13_ROOT returns a root for problem 13.
• P13_ROOT_NUM returns the number of known roots for problem 13.
• P13_START returns a starting point for problem 13.
• P13_START_NUM returns the number of starting point for problem 13.
• P13_TITLE returns the title of problem 13.
• P14_FX evaluates the Camel.
• P14_FX1 evaluates the derivative of the function for problem 14.
• P14_FX2 evaluates the second derivative of the function for problem 14.
• P14_RANGE returns an interval bounding the root for problem 14.
• P14_ROOT returns a root for problem 14.
• P14_ROOT_NUM returns the number of known roots for problem 14.
• P14_START returns a starting point for problem 14.
• P14_START_NUM returns the number of starting point for problem 14.
• P14_TITLE returns the title of problem 14.
• P15_FX evaluates a pathological function for Newton's method.
• P15_FX1 evaluates the derivative of the function for problem 15.
• P15_FX2 evaluates the second derivative of the function for problem 15.
• P15_RANGE returns an interval bounding the root for problem 15.
• P15_ROOT returns a root for problem 15.
• P15_ROOT_NUM returns the number of known roots for problem 15.
• P15_START returns a starting point for problem 15.
• P15_START_NUM returns the number of starting point for problem 15.
• P15_TITLE returns the title of problem 15.
• P16_FX evaluates Kepler's Equation.
• P16_FX1 evaluates the derivative of the function for problem 16.
• P16_FX2 evaluates the second derivative of the function for problem 16.
• P16_RANGE returns an interval bounding the root for problem 16.
• P16_ROOT returns a root for problem 16.
• P16_ROOT_NUM returns the number of known roots for problem 16.
• P16_START returns a starting point for problem 16.
• P16_START_NUM returns the number of starting point for problem 16.
• P16_TITLE returns the title of problem 16.
• P17_FX evaluates Wallis's function, f(x) = x^3 - 2*x - 5.
• P17_FX1 evaluates the derivative of the function for problem 17.
• P17_FX2 evaluates the second derivative of the function for problem 17.
• P17_RANGE returns an interval bounding the root for problem 17.
• P17_ROOT returns a root for problem 17.
• P17_ROOT_NUM returns the number of known roots for problem 17.
• P17_START returns a starting point for problem 17.
• P17_START_NUM returns the number of starting point for problem 17.
• P17_TITLE returns the title of problem 17.
• R8_ABS returns the absolute value of an R8.
• R8_ADD adds two R8's.
• R8_CSQRT returns the complex square root of an R8.
• R8_CUBE_ROOT returns the cube root of an R8.
• R8_EPSILON returns the R8 roundoff unit.
• R8_HUGE returns a "huge" R8.
• R8_MAX returns the maximum of two R8's.
• R8_SIGN returns the sign of an R8.
• R8POLY2_RROOT returns the real parts of the roots of a quadratic polynomial.
• REGULA_FALSI carries out the Regula Falsi method to seek a root of F(X) = 0.
• SECANT carries out the secant method to seek a root of F(X) = 0.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.