Boost/Math: Root Finding and Minimization Algorithms

Boost/Math: Root Finding and Minimization Algorithms#

Root Finding Without Derivatives (TOM 748 algorithm)#

ctxboost.BracketRoot(f, guess, factor, is_rising, get_digits, maxit)#

where ctx is ctxboost.

Parameters:

  • f – the function for which a root is determined.

  • guess – an intial guess.

  • factor – a multiplication factor used when searching for the bracket.

  • is_rising – an indicator whether the function is rising.

  • get_digits – the targeted number of accurate digits.

  • maxit – the maximal number of iterations.

Returns:

a tuple (root, error, iter), where root is an approximation to a root of the function f, using the TOM 748 algorithm for finding a zero; error is an estimate of the modulus of the error of the approximation; and iter is the actual number of iterations.

See also: BoostMath [44], Alefeld et al. [8].

The routine in Python:

>>> from xlcalcnet import ereal
>>> f = lambda x: x * x * x - 28
>>> guess = 2.33;  factor = 2.0; is_rising = True; get_digits = 64;  maxit = 20
>>> res = ereal.BracketRoot(f, guess, factor, is_rising, get_digits, maxit)
>>> print("res (x0, error, iter): ", res)

boost.bracket_root(f, guess, factor, is_rising, get_digits, maxit
result:  3.036588971875662

Root Finding With Derivatives: Newton-Raphson#

ctxboost.NewtonRaphson(f, df, guess, xmin, xmax, get_digits, maxit)#

where ctx is ctxboost.

Parameters:

  • f – the function for which a root is determined.

  • df – the first derivative of the function f.

  • guess – an intial guess.

  • xmin – the left border of the search interval.

  • xmax – the right border of the search interval.

  • get_digits – the targeted number of accurate digits.

  • maxit – the maximal number of iterations.

Returns:

a tuple (root, iter), where root is an approximation to a root of the function f in the interval (xmin, xmax), using the Newton algorithm for finding a zero; and iter is the actual number of iterations.

See also: Wikipedia [1186], BoostMath [54], MathWorld [880].

The routine in Python:

>>> from xlcalcnet import ereal
>>> f = lambda x: x * x * x - 28
>>> df1 = lambda x: 3 * x * x
>>> guess = 2.33; xmin = 1.0; xmax = 4.0; get_digits = 64;  maxit = 20
>>> result3 = ereal.NewtonRaphson(f, df1, guess, xmin, xmax, get_digits, maxit)
>>> print("res2 (x0, iter): ", result3)

boost.newton_raphson(f, df, guess, xmin, xmax, get_digits, maxit)
result:  3.0365889718756627

Root Finding With Derivatives: Halley#

ctxboost.Halley(f, df, d2f, guess, xmin, xmax, get_digits, maxit)#

where ctx is ctxboost.

Parameters:

  • f – the function for which a root is determined.

  • df – the first derivative of the function f.

  • df2 – the second derivative of the function f.

  • guess – an intial guess.

  • xmin – the left border of the search interval.

  • xmax – the right border of the search interval.

  • get_digits – the targeted number of accurate digits.

  • maxit – the maximal number of iterations.

Returns:

a tuple (root, iter), where root is an approximation to a root of the function f in the interval (xmin, xmax), using the Halley algorithm for finding a zero; and iter is the actual number of iterations.

See also: Wikipedia [1183], BoostMath [54], MathWorld [875].

The routine in Python:

>>> from xlcalcnet import ereal
>>> f = lambda x: x * x * x - 28
>>> df1 = lambda x: 3 * x * x
>>> df2 = lambda x: 6 * x
>>> guess = 2.33; xmin = 1.0; xmax = 4.0; get_digits = 64;  maxit = 20
>>> res = ereal.Halley(f, df1, df2, guess, xmin, xmax, get_digits, maxit)
>>> print("res (x0, iter): ", res)

boost.halley(f, df, df2, guess, xmin, xmax, get_digits, maxit)
result:  3.0365889718756627

Root Finding With Derivatives: Schröder#

ctxboost.Schroeder(f, df, d2f, guess, xmin, xmax, get_digits, maxit)#

where ctx is ctxboost.

Parameters:

  • f – the function for which a root is determined.

  • df – the first derivative of the function f.

  • df2 – the second derivative of the function f.

  • guess – an intial guess.

  • xmin – the left border of the search interval.

  • xmax – the right border of the search interval.

  • get_digits – the targeted number of accurate digits.

  • maxit – the maximal number of iterations.

Returns:

a tuple (root, iter), where root is an approximation to a root of the function f in the interval (xmin, xmax), using the Schröder algorithm for finding a zero; and iter is the actual number of iterations.

See also: BoostMath [54], MathWorld [885], Schröder [521].

The routine in Python:

>>> from xlcalcnet import ereal
>>> f = lambda x: x * x * x - 28
>>> df1 = lambda x: 3 * x * x
>>> df2 = lambda x: 6 * x
>>> guess = 2.33; xmin = 1.0; xmax = 4.0; get_digits = 64;  maxit = 20
>>> res = ereal.Schroeder(f, df1, df2, guess, xmin, xmax, get_digits, maxit)
>>> print("res (x0, iter): ", res)

boost.schroder(f, df, df2, guess, xmin, xmax, get_digits, maxit)
result:  3.0365889718756627

Locating Function Minima using Brent’s algorithm#

ctx.BrentMinimum(f, a, b, get_digits, maxit)#

where ctx is ctxboost.

Parameters:

  • f – the function for which a local minimum is determined.

  • a – the left border of the search interval.

  • b – the right border of the search interval.

  • get_digits – the targeted number of accurate digits.

  • maxit – the maximal number of iterations.

Returns:

a tuple (localmin, fx0, iter), where localmin is an approximation to a local minimum of the function f in the interval (a,b), using Brent’s algorithm; fx0 is the value of f(localmin); and iter is the number of iterations.

See also: Wikipedia [1178], Zhang [1655], Brent [41], BoostMath [53].

The routine in Python:

>>> from xlcalcnet import ereal
>>> f = lambda x: (x + 3) * (x - 1) * (x - 1)
>>> bracket_min = 0.5; bracket_max = 1.5;  bits = 125;  maxit = 20
>>> res = ereal.Brent_Minimum(f, bracket_min, bracket_max, bits, maxit)
>>> print("res5 (x0, fx0, iter): ", result3)

boost.brent_minimum(f3, a, b, get_digits, maxit)
x0:  2.9086877250246185e-09
Contents