com.numericalmethod.suanshu.analysis.uniroot

Class Newton

java.lang.Object

com.numericalmethod.suanshu.analysis.uniroot.Newton

All Implemented Interfaces:

Uniroot, java.io.Serializable

public class Newton
extends java.lang.Object
implements Uniroot

The Newton–Raphson method is as follows: one starts with an initial guess which is reasonably close to the true root, then the function is approximated by its tangent line (which can be computed using the tools of calculus), and one computes the x-intercept of this tangent line (which is easily done with elementary algebra). This x-intercept will typically be a better approximation to the function's root than the original guess, and the method can be iterated. It has the following properties.

• The function to be solved is assumed to be continuous and smooth (1st derivative exists).
• The solution converges quadratically, when the multiplicity of the root is 1; otherwise, it is linear.
• The solution may fail to converge when the derivative is or is close to 0.
• The solution may fail to converge if the initial guess is far away from the true value.

See Also:

Wikipedia: Newton's method, Serialized Form

Constructor Summary

Constructors

Constructor and Description
Newton(double tol, int maxIterations) Construct an instance of Newton's root finding algorithm.

Method Summary

Modifier and Type	Method and Description
double	solve(UnivariateRealFunction f, double guess)
double	solve(UnivariateRealFunction f, double lower, double upper, double... guess) Search for a root, x, in the interval [lower, upper] such that f(x) = 0.
double	solve(UnivariateRealFunction f, UnivariateRealFunction df, double guess) Search for a root, x, in the interval [lower, upper] such that f(x) = 0.

Methods inherited from class java.lang.Object

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

Constructor Detail

Newton

public Newton(double tol,
              int maxIterations)

Construct an instance of Newton's root finding algorithm.

Parameters:

tol - the convergence tolerance

maxIterations - the maximum number of iterations

Method Detail

solve

public double solve(UnivariateRealFunction f,
                    double lower,
                    double upper,
                    double... guess)
             throws NoRootFoundException

Description copied from interface: Uniroot

Search for a root, x, in the interval [lower, upper] such that f(x) = 0.

Specified by:

solve in interface Uniroot

Parameters:

f - a univariate function

lower - the lower bound of the bracketing interval

upper - the upper bound of the bracketing interval

guess - an initial guess of the root within [lower, upper]. Note that guess is a double[]. This signature allows multiple initial guesses for certain types of uniroot algorithms, e.g., Brent's algorithm.

Returns:

an approximate root

Throws:

NoRootFoundException - when the search fails to find a root

solve

public double solve(UnivariateRealFunction f,
                    double guess)
             throws NoRootFoundException

Throws:

NoRootFoundException

solve

public double solve(UnivariateRealFunction f,
                    UnivariateRealFunction df,
                    double guess)
             throws NoRootFoundException

Search for a root, x, in the interval [lower, upper] such that f(x) = 0.

Parameters:

f - a univariate function

df - the first order derivative

guess - an initial guess of the root within [lower, upper]

Returns:

an approximate root

Throws:

NoRootFoundException - when the search fails to find a root