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 xreal
>>> f = lambda x: x * x * x - 28
>>> guess = 2.33;  factor = 2.0; is_rising = True; get_digits = 64;  maxit = 20
>>> res = xreal.BracketRoot(f, guess, factor, is_rising, get_digits, maxit)
>>> print("res (x0, error, iter): ", res)

The same routine in Visual Basic:

Function F10 (ByVal x As xreal) As xreal
    Dim fx As New xreal
    fx = x*x*x - 27
    'Console.WriteLine("In F1: x: {0}, f(x): {1}", x, fx)
    Return fx
End Function

Sub DemoBracketRoot()
    Console.WriteLine("BracketRoot")
    Dim guess = 2.33
    Dim factor = 2.0
    Dim is_rising = True
    Dim get_digits = 150
    Dim maxit = 14
    Dim res1  = xreal.BracketRoot(AddressOf F10, guess, factor, is_rising, get_digits, maxit)
    Console.WriteLine("res1 (x0, error, iter): {0}", res1)
End Sub

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 xreal
>>> 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 = xreal.NewtonRaphson(f, df1, guess, xmin, xmax, get_digits, maxit)
>>> print("res2 (x0, iter): ", result3)

The same routine in Visual Basic:

Function F10 (ByVal x As xreal) As xreal
    Dim fx As New xreal
    fx = x*x*x - 27
    'Console.WriteLine("In F1: x: {0}, f(x): {1}", x, fx)
    Return fx
End Function

Function DF10 (ByVal x As xreal) As xreal
    Dim df1x As New xreal
    df1x = 3*x*x
    'Console.WriteLine("In DF1: x: {0}, df1(x): {1}", x, df1x)
    Return df1x
End Function

Sub DemoNewtonRaphson()
    Console.WriteLine("Newton-Raphson")
    Dim guess = 2.33
    Dim xmin = 1.0
    Dim xmax = 4.0
    Dim get_digits = 140
    Dim maxit = 14
    Dim res2  = xreal.NewtonRaphson(AddressOf F10, AddressOf DF10, guess, xmin, xmax, get_digits, maxit)
    Console.WriteLine("res2 (x0, iter): {0}", res2)
    Console.WriteLine()
End Sub

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 xreal
>>> 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 = xreal.Halley(f, df1, df2, guess, xmin, xmax, get_digits, maxit)
>>> print("res (x0, iter): ", res)

The same routine in Visual Basic:

Function F10 (ByVal x As xreal) As xreal
    Dim fx As New xreal
    fx = x*x*x - 27
    'Console.WriteLine("In F1: x: {0}, f(x): {1}", x, fx)
    Return fx
End Function

Function DF10 (ByVal x As xreal) As xreal
    Dim df1x As New xreal
    df1x = 3*x*x
    'Console.WriteLine("In DF1: x: {0}, df1(x): {1}", x, df1x)
    Return df1x
End Function

Function D2F10 (ByVal x As xreal) As xreal
    Dim df2x As New xreal
    df2x = 6*x
    'Console.WriteLine("In DF2: x: {0}, df2(x): {1}", x, df2x)
    Return df2x
End Function

Sub DemoHalley()
    Console.WriteLine("Halley")
    Dim guess = 2.33
    Dim xmin = 1.0
    Dim xmax = 4.0
    Dim get_digits = 140
    Dim maxit = 14
    Dim res3  = xreal.Halley(AddressOf F10, AddressOf DF10, AddressOf D2F10, _
        guess, xmin, xmax, get_digits, maxit)
    Console.WriteLine("res3 (x0, iter): {0}", res3)
    Console.WriteLine()
End Sub

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 xreal
>>> 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 = xreal.Schroeder(f, df1, df2, guess, xmin, xmax, get_digits, maxit)
>>> print("res (x0, iter): ", res)

The same routine in Visual Basic:

Function F10 (ByVal x As xreal) As xreal
    Dim fx As New xreal
    fx = x*x*x - 27
    'Console.WriteLine("In F1: x: {0}, f(x): {1}", x, fx)
    Return fx
End Function

Function DF10 (ByVal x As xreal) As xreal
    Dim df1x As New xreal
    df1x = 3*x*x
    'Console.WriteLine("In DF1: x: {0}, df1(x): {1}", x, df1x)
    Return df1x
End Function

Function D2F10 (ByVal x As xreal) As xreal
    Dim df2x As New xreal
    df2x = 6*x
    'Console.WriteLine("In DF2: x: {0}, df2(x): {1}", x, df2x)
    Return df2x
End Function

Sub DemoSchroeder()
    Console.WriteLine("Schroeder")
    Dim guess = 2.33
    Dim xmin = 1.0
    Dim xmax = 4.0
    Dim get_digits = 140
    Dim maxit = 14
    Dim res4  = xreal.Schroder(AddressOf F10, AddressOf DF10, AddressOf D2F10, _
        guess, xmin, xmax, get_digits, maxit)
    Console.WriteLine("res4 (x0, iter): {0}", res4)
    Console.WriteLine()
End Sub

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 xreal
>>> f = lambda x: (x + 3) * (x - 1) * (x - 1)
>>> bracket_min = 0.5; bracket_max = 1.5;  bits = 125;  maxit = 20
>>> res = xreal.Brent_Minimum(f, bracket_min, bracket_max, bits, maxit)
>>> print("res5 (x0, fx0, iter): ", result3)

The same routine in Visual Basic:

Function F12 (ByVal x As xreal) As xreal
    Dim fx As New xreal
    fx = (x + 3) * (x - 1) * (x - 1)
    'Console.WriteLine("In F2: x: {0}, f(x): {1}", x, fx)
    Return fx
End Function

Sub DemoBrentMinimum()
    Console.WriteLine("Brent_Minimum")
    Dim bracket_min = 0.5
    Dim bracket_max = 1.5
    Dim bits As Int32 = 125
    Dim maxit = 14
    Dim res5 = xreal.Brent_Minimum(AddressOf F12, bracket_min, bracket_max, bits, maxit)
    Console.WriteLine("res5 (x0, fx0, iter): {0}", res5)
    Console.WriteLine()
End Sub

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