- Enclosing class:
- RootFinder<P>
If an iteration limit is exceeded, Newton's method is assumed to not converge. Otherwise Newton's method is assumed to converge if either of two conditions hold:
- for some n, f(xn) = 0 and for all smaller values of n, the convergence criteria hold.
- for all n, |f(xn)| > |f(xn+1)|.
If Newton's method will not converge, the implementation will attempt to use Brent's method. If 0 is in the interval (f(xn), f(xn+1)) then Brent's algorithm will be used with upper and lower initial values of xn and xn+1. Otherwise if 0 is in the interval (f'(xn), f'(xn+1)), Brent's algorithm is used to compute a value xm such that f'(xm) = 0, and if 0 is in the interval (f(x),f(xm), Brent's algorithm is used to find the root. If Brent's algorithm cannot be used in either of these cases to find the root, an exception is thrown to indicate non-convergence.
-
Nested Class Summary
Nested classes/interfaces inherited from class org.bzdev.math.RootFinder
RootFinder.Brent<P>, RootFinder.ConvergenceException, RootFinder.Halley<P>, RootFinder.Newton<P>
-
Field Summary
Fields inherited from class org.bzdev.math.RootFinder
maxLimit
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptiondouble
ferror
(double x) The error in the value returned byfunction
(x).abstract double
firstDerivative
(double x) The first derivative of the function f(x, p) with respect to x.abstract double
function
(double x) The function f in the equation y = f(x, p).boolean
Determine if this instance optimizes its result.static RootFinder.Newton
Create a new instance of RootFinder.Newton using an instance ofDoubleUnaryOperator
orRealValuedFunctOps
to provide the root finder's function and its first derivative.static RootFinder.Newton
Create a new instance of RootFinder.Newton using an instance ofDoubleUnaryOperator
orRealValuedFunctOps
to provide the root finder's function and its first derivative.static RootFinder.Newton
Create a new instance of RootFinder.Newton using aRealValuedFunction
to provide the root finder's function and its first derivative.static RootFinder.Newton
Create a new instance of RootFinder.Newton using aRealValuedFunction
to provide the root finder's function and its first derivative, plus an error function.void
setOptimized
(boolean optimized) Set whether or not this instance optimizes its results.double
solve
(double y, double... initialArgs) Solve an equation.Methods inherited from class org.bzdev.math.RootFinder
findRoot, getEpsilon, getParameters, refineSolution, setEpsilon, setEpsilon, setLimit, setParameters, solveBezier, solveCubic, solveCubic, solvePolynomial, solvePolynomial, solvePolynomial, solveQuadratic, solveQuadratic, solveQuartic
-
Constructor Details
-
Newton
public Newton()Constructor. -
Newton
Constructor given parameters.- Parameters:
parameters
- the parameters
-
-
Method Details
-
isOptimized
public boolean isOptimized()Determine if this instance optimizes its result.- Returns:
- true if results will be optimized; false otherwise
- See Also:
-
setOptimized
public void setOptimized(boolean optimized) Set whether or not this instance optimizes its results. The default value is true. Setting the value to false will speed up the computation by terminating the computation as soon as the convergence criteria are satisfied.When set to true, methods that compute a root will call the method
RootFinder.refineSolution(DoubleUnaryOperator,DoubleUnaryOperator,double,double)
to improve the value computed. Static methods such asRootFinder.solveCubic(double[],double[])
orRootFinder.solvePolynomial(double[],int,double[])
use instances ofRootFinder.Newton
, with optimization turned off, and then explicitly call refineSolution using a more accurate implementation of the function, thereby reducing running time (the more accurate implementations in these cases use Kahan's addition algorithm for a sum of terms that should add to zero when a root is found).- Parameters:
optimized
- true if the results will be optimized; otherwise false
-
function
public abstract double function(double x) The function f in the equation y = f(x, p). The function f(x, p) is used with x varied and with the parameters p constant.- Specified by:
function
in classRootFinder<P>
- Parameters:
x
- the argument of the function- Returns:
- the value of the function f
- See Also:
-
ferror
public double ferror(double x) The error in the value returned byfunction
(x). The default implementation returns the same value asRootFinder.getEpsilon()
when epsilon was set in absolute mode and the value offunction
(x) multiplied by epsilon when epsilon was set in relative mode. Callers are encouraged to override this method when feasible.- Specified by:
ferror
in classRootFinder<P>
- Parameters:
x
- the argument passed tofunction(double)
- Returns:
- the error for
function
(x)
-
firstDerivative
public abstract double firstDerivative(double x) The first derivative of the function f(x, p) with respect to x. The function f(x, p) is used with x varied and with the parameters p constant.- Parameters:
x
- the varying argument to the function f- Returns:
- the function f's first derivative
-
solve
public double solve(double y, double... initialArgs) Solve an equation. Starting from an initial guess, findRoot returns the value of x that satisfies f(x, p) = y, where p represents the current parameters. The implementation used Newton's method but if the algorithm is not converging and guesses have bracketed the solution, Brent's method will be tried.If Newton's method does not converge and if there are two arguments giving an interval containing the solution, Brent's method will be used until Newton's method would provide a better solution. . The initial interval must bracket the solution: if the interval is [xl, xu], then f(xl, p) - y and f(xu, p) - y must have opposite signs. For example,
solve(y, guess, xl, xu)
will use Newton's method with an initial guess (guess
) and if that does not converge, it will callb.
wheresolve
(x, xl, ux)b
is a suitably initialized instance ofRootFinder.Brent
. As the iteration continues, the interval will become smaller.- Specified by:
solve
in classRootFinder<P>
- Parameters:
y
- the desired value of f(x, p)initialArgs
- a single mandatory argument providing a guess and optionally two additional arguments giving a range over which a solution is bracketed- Returns:
- the value of x that satisfies f(x, p) = y
- Throws:
RootFinder.ConvergenceException
- the method failedMathException
- an error occurred calling the function f or one of its derivatives.
-
newInstance
Create a new instance of RootFinder.Newton using aRealValuedFunction
to provide the root finder's function and its first derivative.The
RealValuedFunction
'sRealValuedFunction.secondDerivAt(double)
method does not have to be implemented as this method is not used.- Parameters:
f
- a function- Returns:
- a new root finder
-
newInstance
Create a new instance of RootFinder.Newton using aRealValuedFunction
to provide the root finder's function and its first derivative, plus an error function.The
RealValuedFunction
'sRealValuedFunction.secondDerivAt(double)
method does not have to be implemented as this method is not used. The function ef will be used to implement the methodRootFinder.ferror(double)
.- Parameters:
f
- a functionef
- a function providing the error for the value f(x)- Returns:
- a new root finder
-
newInstance
Create a new instance of RootFinder.Newton using an instance ofDoubleUnaryOperator
orRealValuedFunctOps
to provide the root finder's function and its first derivative.- Parameters:
f
- the function for the root finderdf
- the derivative of f- Returns:
- a new root finder
-
newInstance
public static RootFinder.Newton newInstance(DoubleUnaryOperator f, DoubleUnaryOperator df, DoubleUnaryOperator ef) Create a new instance of RootFinder.Newton using an instance ofDoubleUnaryOperator
orRealValuedFunctOps
to provide the root finder's function and its first derivative. The function provided as the second argument will be used to implement the methodRootFinder.ferror(double)
.- Parameters:
f
- the function for the root finderdf
- the derivative of fef
- a function providing the error in the computation of f- Returns:
- a new root finder
-