Class RootFinder.Newton<P>

java.lang.Object
org.bzdev.math.RootFinder<P>
org.bzdev.math.RootFinder.Newton<P>
Enclosing class:
RootFinder<P>

public abstract static class RootFinder.Newton<P> extends RootFinder<P>
RootFinder class using Newton's method. Newton's algorithm solves the equation f(x) = 0 by starting with an initial guess x0 and generating a sequence such that xn+1 = xn - f(xn)/f'(xn).

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.

  • Constructor Details

    • Newton

      public Newton()
      Constructor.
    • Newton

      public Newton(P parameters)
      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 as RootFinder.solveCubic(double[],double[]) or RootFinder.solvePolynomial(double[],int,double[]) use instances of RootFinder.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 class RootFinder<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 by function(x). The default implementation returns the same value as RootFinder.getEpsilon() when epsilon was set in absolute mode and the value of function(x) multiplied by epsilon when epsilon was set in relative mode. Callers are encouraged to override this method when feasible.
      Specified by:
      ferror in class RootFinder<P>
      Parameters:
      x - the argument passed to function(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 call b.solve(x, xl, ux) where b is a suitably initialized instance of RootFinder.Brent. As the iteration continues, the interval will become smaller.

      Specified by:
      solve in class RootFinder<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 failed
      MathException - an error occurred calling the function f or one of its derivatives.
    • newInstance

      public static RootFinder.Newton newInstance(RealValuedFunction f)
      Create a new instance of RootFinder.Newton using a RealValuedFunction to provide the root finder's function and its first derivative.

      The RealValuedFunction's RealValuedFunction.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

      public static RootFinder.Newton newInstance(RealValuedFunction f, RealValuedFunctOps ef)
      Create a new instance of RootFinder.Newton using a RealValuedFunction to provide the root finder's function and its first derivative, plus an error function.

      The RealValuedFunction's RealValuedFunction.secondDerivAt(double) method does not have to be implemented as this method is not used. The function ef will be used to implement the method RootFinder.ferror(double).

      Parameters:
      f - a function
      ef - a function providing the error for the value f(x)
      Returns:
      a new root finder
    • newInstance

      public static RootFinder.Newton newInstance(DoubleUnaryOperator f, DoubleUnaryOperator df)
      Create a new instance of RootFinder.Newton using an instance of DoubleUnaryOperator or RealValuedFunctOps to provide the root finder's function and its first derivative.
      Parameters:
      f - the function for the root finder
      df - the derivative of f
      Returns:
      a new root finder
    • newInstance

      Create a new instance of RootFinder.Newton using an instance of DoubleUnaryOperator or RealValuedFunctOps to provide the root finder's function and its first derivative. The function provided as the second argument will be used to implement the method RootFinder.ferror(double).
      Parameters:
      f - the function for the root finder
      df - the derivative of f
      ef - a function providing the error in the computation of f
      Returns:
      a new root finder