brent-zero-generator

brent-zero-generator

This module implements Brent's algorithm to find a root of a function f(). The module provides 3 functions: zero(), zero_generator(), and zero_generator2(). The functions zero_generator() and zero_generator2() facilitate solving asynchronous functions, and provide a lot of flexibility (see example below). For typical use, the simpler zero() function should be sufficient.

WARNING: the Ignorant Suffer

Before you consider using another similar code, have a look at the README.md of my BrentZeroTester.JS repository, where several alternative codes are compared. Both horrible performances, and wrong results happen in some of these codes.

TIP: T.R. Chandrupatla's zero

The package chandrupatla-zero contains my JavaScript implementation of T.R. Chandrupatla's algorithm. The repository compare-zeros, in my opinion, shows it is a bit better than Brent's algorithm.

Usage

The JavaScript code in this module follows Brent's original code of the Algol 60 procedure zero() very closely. In the first comment in that code, Brent describes procedure zero() as:

Procedure zero retuns a zero x of the function f in the given interval [a, b], to within a tolerance (4 macheps |x| + 2 t), where macheps is the relative machine precision and t is a positive tolerance. The procedure assumes that f(a) and f(b) have different signs

Parameters

Parameter	Description
f	the function f() for which the root is sought. Only for the utility function zero().
a	the finite lowerbound of the interval in which to search the root
b	the finite upperbound of the interval in which to search the root
macheps	the relative tolerance. This parameter may be increased if a higher relative error is acceptable, but it should not be decreased, for then rounding errors might prevent convergence. (optional, default: Number.EPSILON)
t	the absolute tolerance. (optional, default: 0.0)

Functions

• zero_generator2(a, b, macheps, t), and
• zero_generator(a, b, macheps, t), and
• zero(f, a, b, macheps, t).

Yields and returns

The generator functions zero_generator() and zero_generator2() only yield, the 'x' values, to request function evaluations. When the zero_generator2() function is 'done', it returns an array with the following contents:

• res[0]: the x-value thought to be closest to the root,
• res[1]: the corresponding y-value,
• res[2]: the x-value closest to, but on the other side of the root,
• res[3]: the corresponding y-value.

The functions zero_generator() and zero() only return the x-value, thought to be closest to the root.

Notes

• f(a) and f(b) should have different signs.
• the algorithm ends when f(x) == 0 is found, or the interval [a, b] has been sufficiently shrunk to be sure the x is within the tolerance. This says nothing about the value of f(x). For example the function x => x < 3 ? -1 : 2, will find a "root" close to 3, but f(x) will be -1.
• the original comment in the Algol 60 code mentions 'a tolerance (6 macheps |x| + 2 t)'. The code of the algorithm limits the tolerance to 4 macheps |x| + 2 t. Brent adds '2 macheps |x|' due to inprecision in the calculation of the function values. I think this is confusing, so I changed the quote.

Some Examples

The following examples shows simple usage. Given a function f(x) = x² - 5.

1. Simplest zero() example

const brents = require('brent-zero-generator');

const f = x => x * x - 5;

console.log( brents.zero(f, 1, 4).toFixed(6) );
// expect 2.236068

2. Simple zero_generator2() example

const gen = brents.zero_generator2(-3, -2);

let result = gen.next();
while ( ! result.done ) {
    const x = result.value;
    const y = f(x);

    result = gen.next(y)    
}
console.log( result.value.toFixed(6) );
// expect [ -2.236068, 8.8e-16, -2.236068, -3.5e-15 ]

3. Modified zero_generator() example

Often implementations have additional parameters for maximum number of iterations (max_iter), or an allowed tolerance for the root's function value (yTol). Brent's original code does not have these options, and I am fairly sure he would not agree with them. However, using the generator function, they are easily implemented, as the following example function shows:

function myZero(f, a, b, max_iter, yTol) {
    const gen = zero_generator(a, b);

    let result = gen.next();
    for (let i=0; i<max_iter && ! result.done; ++i) {
        const x = result.value;
        const y = f(x);
        if (Math.abs(y) < yTol) break;

        result = gen.next(y)    
    }

    return result.value;
}

API changes

• 1.1 Added zero_generator2() as an export.

Further Documentation

The ultimate documentation on this algorithm can be found on Emeritus Professor Richard P. Brent's page dedicated to his book Algorithms for Minimization Without Derivatives.
On that page, not only the errata for the different editions of the book are available, but also a scanned copy of the Prentice-Hall edition is also available for download.

C, C++, Fortran66/Fortran77 and Fortran90 codes can be found on John Burkardt's homepage.

A Wolfram-MathWorld page explains the way in which the inverse quadratic interpolation, which is important for the numerical stability, is implemented.

License

ISC