org.apache.commons.math.analysis
Class MullerSolver

java.lang.Object
  extended by org.apache.commons.math.analysis.UnivariateRealSolverImpl
      extended by org.apache.commons.math.analysis.MullerSolver
All Implemented Interfaces:
java.io.Serializable, UnivariateRealSolver

public class MullerSolver
extends UnivariateRealSolverImpl

Implements the Muller's Method for root finding of real univariate functions. For reference, see Elementary Numerical Analysis, ISBN 0070124477, chapter 3.

Muller's method applies to both real and complex functions, but here we restrict ourselves to real functions. Methods solve() and solve2() find real zeros, using different ways to bypass complex arithmetics.

Since:
1.2
Version:
$Revision: 620312 $ $Date: 2008-02-10 12:28:59 -0700 (Sun, 10 Feb 2008) $
See Also:
Serialized Form

Field Summary
private static long serialVersionUID
          serializable version identifier
 
Fields inherited from class org.apache.commons.math.analysis.UnivariateRealSolverImpl
absoluteAccuracy, defaultAbsoluteAccuracy, defaultFunctionValueAccuracy, defaultMaximalIterationCount, defaultRelativeAccuracy, f, functionValueAccuracy, iterationCount, maximalIterationCount, relativeAccuracy, result, resultComputed
 
Constructor Summary
MullerSolver(UnivariateRealFunction f)
          Construct a solver for the given function.
 
Method Summary
 double solve(double min, double max)
          Find a real root in the given interval.
 double solve(double min, double max, double initial)
          Find a real root in the given interval with initial value.
 double solve2(double min, double max)
          Find a real root in the given interval.
 
Methods inherited from class org.apache.commons.math.analysis.UnivariateRealSolverImpl
clearResult, getAbsoluteAccuracy, getFunctionValueAccuracy, getIterationCount, getMaximalIterationCount, getRelativeAccuracy, getResult, isBracketing, isSequence, resetAbsoluteAccuracy, resetFunctionValueAccuracy, resetMaximalIterationCount, resetRelativeAccuracy, setAbsoluteAccuracy, setFunctionValueAccuracy, setMaximalIterationCount, setRelativeAccuracy, setResult, verifyBracketing, verifyInterval, verifySequence
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

serialVersionUID

private static final long serialVersionUID
serializable version identifier

See Also:
Constant Field Values
Constructor Detail

MullerSolver

public MullerSolver(UnivariateRealFunction f)
Construct a solver for the given function.

Parameters:
f - function to solve
Method Detail

solve

public double solve(double min,
                    double max,
                    double initial)
             throws MaxIterationsExceededException,
                    FunctionEvaluationException
Find a real root in the given interval with initial value.

Requires bracketing condition.

Parameters:
min - the lower bound for the interval
max - the upper bound for the interval
initial - the start value to use
Returns:
the point at which the function value is zero
Throws:
MaxIterationsExceededException - if the maximum iteration count is exceeded or the solver detects convergence problems otherwise
FunctionEvaluationException - if an error occurs evaluating the function
java.lang.IllegalArgumentException - if any parameters are invalid

solve

public double solve(double min,
                    double max)
             throws MaxIterationsExceededException,
                    FunctionEvaluationException
Find a real root in the given interval.

Original Muller's method would have function evaluation at complex point. Since our f(x) is real, we have to find ways to avoid that. Bracketing condition is one way to go: by requiring bracketing in every iteration, the newly computed approximation is guaranteed to be real.

Normally Muller's method converges quadratically in the vicinity of a zero, however it may be very slow in regions far away from zeros. For example, f(x) = exp(x) - 1, min = -50, max = 100. In such case we use bisection as a safety backup if it performs very poorly.

The formulas here use divided differences directly.

Parameters:
min - the lower bound for the interval
max - the upper bound for the interval
Returns:
the point at which the function value is zero
Throws:
MaxIterationsExceededException - if the maximum iteration count is exceeded or the solver detects convergence problems otherwise
FunctionEvaluationException - if an error occurs evaluating the function
java.lang.IllegalArgumentException - if any parameters are invalid

solve2

public double solve2(double min,
                     double max)
              throws MaxIterationsExceededException,
                     FunctionEvaluationException
Find a real root in the given interval.

solve2() differs from solve() in the way it avoids complex operations. Except for the initial [min, max], solve2() does not require bracketing condition, e.g. f(x0), f(x1), f(x2) can have the same sign. If complex number arises in the computation, we simply use its modulus as real approximation.

Because the interval may not be bracketing, bisection alternative is not applicable here. However in practice our treatment usually works well, especially near real zeros where the imaginary part of complex approximation is often negligible.

The formulas here do not use divided differences directly.

Parameters:
min - the lower bound for the interval
max - the upper bound for the interval
Returns:
the point at which the function value is zero
Throws:
MaxIterationsExceededException - if the maximum iteration count is exceeded or the solver detects convergence problems otherwise
FunctionEvaluationException - if an error occurs evaluating the function
java.lang.IllegalArgumentException - if any parameters are invalid