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

$3

|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)

$3

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

$3

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.

$3

- 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.

$3

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

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

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

$3

` js
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

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:
` js
function myZero(f, a, b, max_iter, yTol) {
const gen = zero_generator(a, b);

let result = gen.next();
for (let i=0; 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