edu.northwestern.at.utils.math.rootfinders
Class Secant

java.lang.Object
  edu.northwestern.at.utils.math.rootfinders.Secant

All Implemented Interfaces:

MonadicFunctionRootFinder

public class Secant
extends java.lang.Object
implements MonadicFunctionRootFinder

Find roots of equations using variants of the Method of Secants.

The Method of Secants is a root-finding method which requires an initial interval [x0,x1] bracketing a root, that the function be continuous, and that the derivative exist at each point in the interval.

An updated estimate of the root value is given by the formula:

x[i+1] = x[i] - ( f(x[i]) * ( x[i] - x[i-1]) ) / (f(x[i]) - f(x[i-1]))

To avoid problems with overflow and division by zero, we rewrite this update formula as follows:

r[i+1] = f(x[i+1]) / f(x[i]) )
x[i+1] = x[i] + ( r[i+1] / ( 1 - r[i+1] ) ) * ( x[i] - x[i-1] )

and only perform the division when the divisor ( 1 - s[i+1] ) is large enough.

The updated root estimate x[i+1] is the point where the secant to f(x) intersects the x axis, hence the name of the method.

The plain vanilla version of the Method of Secants does not keep the root bracketed between successive estimates and can diverge. The Method of False Position is a variant which ensures that the two estimates used to calculate the secant to f(x) always bracket the root. It does this by retaining an old end point as long as necessary to keep the root bracketed. This ensures convergence at the cost of extra iterations. False Position modifies the root estimate selection as follows.

• If ( f(x[i+1] * f(x[i])) < 0, ( x[i-1] , f(x[i-1]) ) is replaced by ( x[i] , f(x[i] ) as above.
• If ( f(x[i+1] * f(x[i])) > 0, ( x[i-1] , F(x[i-1]) )is replaced by ( x[i-1] , f(x[i-1])/2 ).

The Illinois method is a another variant which modifies the root estimate selection process as follows.

• If ( f(x[i+1] * f(x[i])) < 0, ( x[i-1] , f(x[i-1]) ) is replaced by ( x[i] , f(x[i] ) as above.
• If ( f(x[i+1] * f(x[i])) > 0, ( x[i-1] , F(x[i-1]) )is replaced by ( x[i-1] , f(x[i-1])/2 ).

These modifications prevent retention of an endpoint and speed convergence in many cases.

The Illinois variant is the recommended version of the Method of Secants for practical use. For most purposes, it is better to use Brent rather than the Method of Secants because Brent's Method handles ill-behaved functions better and converges more quickly in such cases.

Field Summary

static int	FALSEPOSITION Constant defining the plain Method of Secants.
static int	ILLINOIS Constant defining the plain Method of Secants.
static int	PLAIN Constant defining the plain Method of Secants.

Constructor Summary

Secant()
Constructor if RootFinder interface used.

Method Summary

double	findRoot(double x0, double x1, double tol, int maxIter, MonadicFunction function, MonadicFunction derivativeFunction, RootFinderConvergenceTest convergenceTest, RootFinderIterationInformation iterationInformation) Implementation for MonadicFunctionRootFinder interface.
static double	secant(double x0, double x1, double tol, int maxIter, MonadicFunction function) Find root using the Method of Secants.
static double	secant(double x0, double x1, double tol, int maxIter, MonadicFunction function, int variant) Find root using the Method of Secants.
static double	secant(double x0, double x1, double tol, int maxIter, MonadicFunction function, RootFinderConvergenceTest convergenceTest, RootFinderIterationInformation iterationInformation, int variant) Find root using the Method of Secants.
static double	secant(double x0, double x1, double tol, int maxIter, MonadicFunction function, RootFinderIterationInformation iterationInformation) Find root using the Method of Secants.
static double	secant(double x0, double x1, MonadicFunction function) Find root using the Method of Secants.

Methods inherited from class java.lang.Object

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

Field Detail

PLAIN

public static final int PLAIN

Constant defining the plain Method of Secants.

See Also:

Constant Field Values

FALSEPOSITION

public static final int FALSEPOSITION

Constant defining the plain Method of Secants.

See Also:

Constant Field Values

ILLINOIS

public static final int ILLINOIS

Constant defining the plain Method of Secants.

See Also:

Constant Field Values

Constructor Detail

Secant

public Secant()

Constructor if RootFinder interface used.

Method Detail

secant

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

Find root using the Method of Secants.

Parameters:

x0 - First approximation to root value.

x1 - Second approximation to root value.

tol - Desired accuracy for root value.

maxIter - Maximum number of iterations.

function - Class implementing MonadicFunction interface to provide function values.

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.

variant - Variant of the method of secants to use. = PLAIN : Unmodified Method of Secants. = FALSEPOSITION : Method of False Position. = ILLINOIS : Illinois method.

Returns:

Approximation to root of function.

Throws:

java.lang.IllegalArgumentException - if [x0,x1] cannot be expanded to bracket a root (if FALSEPOSITION variant selected) or function is null.

When the FALSEPOSITION variant is chosen, we try to ensure that the the two initial approximations bracket the root by expanding the interval as needed.

secant

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

Find root using the Method of Secants.

Parameters:

x0 - First approximation to root value.

x1 - Second approximation to root value.

tol - Desired accuracy for root value.

maxIter - Maximum number of iterations.

function - Class implementing MonadicFunction interface to provide function values.

variant - Variant of the method of secants to use. = PLAIN : Unmodified Method of Secants. = FALSEPOSITION : Method of False Position. = ILLINOIS : Illinois method.

Returns:

Approximation to root of function.

Throws:

java.lang.IllegalArgumentException - if [x0,x1] cannot be expanded to bracket a root or function is null.

This implementation always starts by attempting to expand the root- bracketing interval to enclose a root.

secant

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

Find root using the Method of Secants.

Parameters:

x0 - First approximation to root value.

x1 - Second approximation to root value.

tol - Desired accuracy for root value.

maxIter - Maximum number of iterations.

function - Class implementing MonadicFunction interace to provide function values.

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:

Approximation to root of function.

Throws:

java.lang.IllegalArgumentException - if [x0,x1] cannot be expanded to bracket a root or function is null.

The Illinois variant of the Method of Secants is used to find the function.

secant

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

Find root using the Method of Secants.

Parameters:

x0 - First approximation to root value.

x1 - Second approximation to root value.

tol - Desired accuracy for root value.

maxIter - Maximum number of iterations.

function - Class implementing MonadicFunction interface to provide function values.

Returns:

Approximation to root of the function.

Throws:

java.lang.IllegalArgumentException - if [x0,x1] cannot be expanded to bracket a root or function is null.

The Illinois variant of the Method of Secants is used to find the function.

secant

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

Find root using the Method of Secants.

Parameters:

x0 - First approximation to root value.

x1 - Second approximation to root value.

function - Class implementing MonadicFunction interface to provide function values.

Returns:

Approximation to root of the function.

Throws:

java.lang.IllegalArgumentException - if [x0,x1] cannot be expanded to bracket a root or function is null.

The Illinois variant of the Method of Secants is used to find the function. The tolerance used is Constants.MACHEPS, and up to 100 iterations are attempted.

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