edu.northwestern.at.utils.math.rootfinders

## Class Brent

- java.lang.Object
- - edu.northwestern.at.utils.math.rootfinders.Brent

- All Implemented Interfaces:
    MonadicFunctionRootFinder

      public class Brent
      extends java.lang.Object
      implements MonadicFunctionRootFinder

  Find a root of a function using Brent's method which combines quadratic interpolation with the method of bisection.

  Brent's method requires as input an initial interval [x0,x1] which brackets one (or an odd number) of roots.

  During each iteration Brent's method constructs an interpolation curve to approximate the function. For the initial iteration this is a simple linear interpolation using the initially supplied endpoints of the interval bracketing the root. For subsequent iterations the interpolation curve is an inverse quadratic fit to the last three points. The intercept of the interpolation curve with the x-axis provides the root approximation. If this value lies within the bounds of the current root bracketing interval the interpolation point is accepted and used to narrow the interval. If the interpolated value lies outside the bounds of the current interval the algorithm switches to bisection steps to narrow the interval. The algorithm switches between quadratic interpolation and bisection as often as necessary to ensure convergence.

  The best estimate of the root is taken from the most recent interpolation or bisection after the value is found to a specified tolerance or a specified number of iterations is exhausted.

  See Brent, Richard P. Algorithms for minimization without derivatives. Mineola, N.Y. : Dover Publications, 2002.

  and

  Brent, R. P. An algorithm with guaranteed convergence for finding the zero of a function. The Computer Journal vol. 14, no. 4, pp. 422-425.

  This Java code is a fairly straightforward translation of Brent's original Algol 60 version as published in his paper in The Computer Journal.

- - ### Constructor Summary

    Constructors
    Constructor and Description
    `Brent()` Constructor if RootFinder interface used.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `static double` | `brent(double x0, double x1, double tol, int maxIter, MonadicFunction function)` Find root of a function using Brent's method.
    `static double` | `brent(double x0, double x1, double tol, int maxIter, MonadicFunction function, RootFinderConvergenceTest convergenceTest, RootFinderIterationInformation iterationInformation)` Find root of a function using Brent's method.
    `static double` | `brent(double x0, double x1, MonadicFunction function)` Find root of a function using Brent's method.
    `double` | `findRoot(double x0, double x1, double tol, int maxIter, MonadicFunction function, MonadicFunction derivativeFunction, RootFinderConvergenceTest convergenceTest, RootFinderIterationInformation iterationInformation)` Implementation for `MonadicFunctionRootFinder` interface.

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Constructor Detail

    - #### Brent

          public Brent()

      Constructor if RootFinder interface used.

  - ### Method Detail

    - #### brent

          public static double brent(double x0,
                     double x1,
                     double tol,
                     int maxIter,
                     MonadicFunction function,
                     RootFinderConvergenceTest convergenceTest,
                     RootFinderIterationInformation iterationInformation)
                              throws java.lang.IllegalArgumentException

      Find root of a function using Brent's method.
      Parameters:
        `x0` - Left endpoint of interval containing root.
        `x1` - Right endpoint of interval containing root.
        `tol` - Convergence tolerance to which root is computed.
        `maxIter` - Maximum number of iterations.
        `function` - The function whose root to find.
        `convergenceTest` - RootFinderConvergenceTest which tests for convergence of the root-finding process.
        `iterationInformation` - Class implementing RootFinderIterationInformation for retrieving information about each iteration of root finding process. Set to null if you don't want this information.
      Returns:
        Root of function in interval [x0,x1] .
      Throws:
        `InvalidArgumentException` - when [x0,x1] does not contain root and the attempt to expand the interval to contain a root fails.

        Function must have an odd # of roots in the interval [x0,x1] .

        `java.lang.IllegalArgumentException`

    - #### brent

          public static double brent(double x0,
                     double x1,
                     double tol,
                     int maxIter,
                     MonadicFunction function)
                              throws java.lang.IllegalArgumentException

      Find root of a function using Brent's method.
      Parameters:
        `x0` - Left endpoint of interval containing root.
        `x1` - Right endpoint of interval containing root.
        `tol` - Convergence tolerance to which root is computed.
        `maxIter` - Maximum number of iterations.
        `function` - The function whose root to find.
      Returns:
        Root of function in interval [x0,x1] .
      Throws:
        `InvalidArgumentException` - when [x0,x1] does not contain root and the attempt to expand the interval to contain a root fails.

        Function must have an odd # of roots in the interval [x0,x1] .

        `java.lang.IllegalArgumentException`

    - #### brent

          public static double brent(double x0,
                     double x1,
                     MonadicFunction function)
                              throws java.lang.IllegalArgumentException

      Find root of a function using Brent's method.
      Parameters:
        `x0` - Left endpoint of interval containing root.
        `x1` - Right endpoint of interval containing root.
        `function` - The function whose root to find.
      Returns:
        Root of function in interval [x0,x1] .
      Throws:
        `InvalidArgumentException` - when [x0,x1] does not contain root and the attempt to expand the interval to contain a root fails.

        Function must have an odd # of roots in the interval [x0,x1] . Up to 100 iterations are attempted with a convergence tolerance set to Constants.MACHEPS .

        `java.lang.IllegalArgumentException`

    - #### findRoot

          public double findRoot(double x0,
                        double x1,
                        double tol,
                        int maxIter,
                        MonadicFunction function,
                        MonadicFunction derivativeFunction,
                        RootFinderConvergenceTest convergenceTest,
                        RootFinderIterationInformation iterationInformation)
                          throws java.lang.IllegalArgumentException

      Implementation for `MonadicFunctionRootFinder` interface.
      Specified by:
        `findRoot` in interface `MonadicFunctionRootFinder`
      Parameters:
        `x0` - Left bracket value for root.
        `x1` - Right bracket value for root. Not used by some root-finder (e.g., Newton/Raphson), set to same value as x0 in those cases.
        `tol` - Convergence tolerance.
        `maxIter` - Maximum number of iterations.
        `function` - MonadicFunction computes value for function whose root is being sought.
        `derivativeFunction` - MonadicFunction computes derivative value for function whose root is being sought. Currently used only by Newton/Raphson, set to null for other methods.
        `convergenceTest` - RootFinderConvergenceTest which tests for convergence of the root-finding process.
        `iterationInformation` - Method implementing the RootFinderIterationInformation interace. Allows retrieval of function, function derivative, and iteration number for each iteration in the root-finding process. Can be set to null if you don't want to get that information.
      Throws:
        `java.lang.IllegalArgumentException`