numericalMethods.calculus.rootFinding
Class NewtonRaphson

java.lang.Object
  |
  +--numericalMethods.calculus.rootFinding.NewtonRaphson

public class NewtonRaphson
extends java.lang.Object

Newton-Raphson method's for finding roots of real and complex functions. This is defitnitly most famos root-finding methods for one dimensional problems. It requires the function and its derivative. It is well known that Newton´s method has only poor global convergence properties, but near a root it converges quadratically. Therefor a common strategie is to use a globally more stable method first and than, when you are near to a root, to perform a few steps of Newton´s methods, which approxiamtely doubles the number of significant digits with each step.

In the real case the function gand its derivative is provided as a mapping

x |-> ( x, g(x), g´(x) ) .

This map is given by an object pair (f,F), where f implements the interface DoubleParametrized and F the interface DoubleArrayValued. Simular in the complex case: here the data for the function gis provided by

( re(z), im(z) ) |-> ( re(z), im(z), re(f(z)), im(f(z)), re(f´(z)), im(f´(z)) ) ,

given by a pair implementing DoubleArrayParametrized and DoubleArrayValued.

See Also:
ExampleNewtonRaphson, numericalMethods.function

Field Summary
static double ACC
          Default accuracy: 1e-12.
static boolean DEBUG
          Switches debug output on and off; the default is false.
static int MAX_NUM_OF_STEPS
          Default maximum number of steps performed in Newton´s method: 50.
 
Method Summary
static void search(numericalMethods.function.DoubleArrayParametrized P, numericalMethods.function.DoubleArrayValued V, double x, double y, double[] rootValues)
          Performs Newton´s method starting at z=x+iy.
static void search(numericalMethods.function.DoubleArrayParametrized P, numericalMethods.function.DoubleArrayValued V, double x, double y, double[] rootValues, double acc)
          Performs Newton´s method starting at z=x+iy.
static void search(numericalMethods.function.DoubleArrayParametrized P, numericalMethods.function.DoubleArrayValued V, double x, double y, double[] rootValues, double acc, double accX, double accY, double xMin, double xMax, double yMin, double yMax, int maxNumOfSteps, boolean panicIfMaxNumOfStepsAreExeeded)
          Performs Newton´s method starting at z=x+iy and restricting itself to the rectangle [xMin,xMax]x[yMin,yMax].
static void search(numericalMethods.function.DoubleParametrized P, numericalMethods.function.DoubleArrayValued V, double x, double[] rootValues)
          Performs Newton´s method starting at x.
static void search(numericalMethods.function.DoubleParametrized P, numericalMethods.function.DoubleArrayValued V, double x, double[] rootValues, double acc)
          Performs Newton´s method starting at x.
static void search(numericalMethods.function.DoubleParametrized P, numericalMethods.function.DoubleArrayValued V, double x, double[] rootValues, double acc, double accX, double xMin, double xMax, int maxNumOfSteps, boolean panicIfMaxNumOfStepsAreExeeded)
          Performs Newton´s method starting at x and restricting itself to the interval [xMin,xMax].
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

ACC

public static double ACC
Default accuracy: 1e-12.

MAX_NUM_OF_STEPS

public static int MAX_NUM_OF_STEPS
Default maximum number of steps performed in Newton´s method: 50.

DEBUG

public static boolean DEBUG
Switches debug output on and off; the default is false. If this flag is true, the methods will list all the evaluated values.
Method Detail

search

public static void search(numericalMethods.function.DoubleParametrized P,
                          numericalMethods.function.DoubleArrayValued V,
                          double x,
                          double[] rootValues)
Performs Newton´s method starting at x. The method returns the root xr of a real function g, given by the pair (P,V), in the first entry of rootValues. The second and third entry of rootValues are assigned with g(xr) and g´(xr). The algorithm terminates if the approximation of the root value changes relatively less than ACC or the function at this value drops below ACC.
Parameters:
P - parameter object of function; recieves x
V - value object of function; assigns triple: (x,g(x),g´(x))
x - start position
rootValues - array of length 3 for the result
Throws:
java.lang.RuntimeException - when MAX_NUM_OF_STEPS was exeeded

search

public static void search(numericalMethods.function.DoubleParametrized P,
                          numericalMethods.function.DoubleArrayValued V,
                          double x,
                          double[] rootValues,
                          double acc)
Performs Newton´s method starting at x. The method returns the root xr of a real function g, given by the pair (P,V), in the first entry of rootValues. The second and third entry of rootValues are assigned with g(xr) and g´(xr). The algorithm terminates if the approximation of the root value changes relatively less than acc or the function at this value drops below acc.
Parameters:
P - parameter object of function; recieves x
V - value object of function; assigns triple: (x,g(x),g´(x))
x - start position
rootValues - array of length 3 for the result
Throws:
java.lang.RuntimeException - when MAX_NUM_OF_STEPS was exeeded

search

public static void search(numericalMethods.function.DoubleParametrized P,
                          numericalMethods.function.DoubleArrayValued V,
                          double x,
                          double[] rootValues,
                          double acc,
                          double accX,
                          double xMin,
                          double xMax,
                          int maxNumOfSteps,
                          boolean panicIfMaxNumOfStepsAreExeeded)
Performs Newton´s method starting at x and restricting itself to the interval [xMin,xMax]. The method returns the root xr of a real function g, given by the pair (P,V), in the first entry of rootValues. The second and third entry of rootValues are assigned with g(xr) and g´(xr). The algorithm terminates if the approximation of the root value changes relatively less than accX or the function at this value drops below acc.
Parameters:
P - parameter object of function; recieves x
V - value object of function; assigns triple: (x,g(x),g´(x))
x - start position in the interval [xMin,xMax]
rootValues - array of length 3 for the result
acc - accuracy of the zero (absolute)
accX - accuracy of root (relative)
xMin - lower bound of search interval
xMax - upper bound of search interval
panicIfMaxNumOfStepsAreExeeded - controls whether an exception is thrown if maximum number of steps are exeeded
Throws:
java.lang.RuntimeException - when the algorithm leaves the search interval [xMin,xMax]
java.lang.RuntimeException - when maxNumOfSteps was exeeded and panicIfMaxNumOfStepsAreExeeded is true

search

public static void search(numericalMethods.function.DoubleArrayParametrized P,
                          numericalMethods.function.DoubleArrayValued V,
                          double x,
                          double y,
                          double[] rootValues)
Performs Newton´s method starting at z=x+iy. The method returns the root zr of a complex function g, given by the pair (P,V), in the first two entries of rootValues. The third to the sixth entry of rootValues are assigned with re(g(zr), im(g(zr), re(g´(zr)) and g´(im(zr)). The algorithm terminates if the approximation of the root value changes relatively less than ACC or the function at this value drops below ACC.
Parameters:
P - paramter object of function; recieves tuple x,y
V - value object of function; assigns 6-tuple: (x,y,re(g(x)),im(g(x)),re(g´(x)),im(g´(x))),
x - real part of start position
y - imaginary part of start position
rootValues - array of length 6 for the result
Throws:
java.lang.RuntimeException - when MAX_NUM_OF_STEPS was exeeded

search

public static void search(numericalMethods.function.DoubleArrayParametrized P,
                          numericalMethods.function.DoubleArrayValued V,
                          double x,
                          double y,
                          double[] rootValues,
                          double acc)
Performs Newton´s method starting at z=x+iy. The method returns the root zr of a complex function g, given by the pair (P,V), in the first two entries of rootValues. The third to the sixth entry of rootValues are assigned with re(g(zr), im(g(zr), re(g´(zr)) and g´(im(zr)). The algorithm terminates if the approximation of the root value changes relatively less than acc or the function at this value drops below acc.
Parameters:
P - paramter object of function; recieves tuple x,y
V - value object of function; assigns 6-tuple: (x,y,re(g(x)),im(g(x)),re(g´(x)),im(g´(x))),
x - real part of start position
y - imaginary part of start position
rootValues - array of length 6 for the result
Throws:
java.lang.RuntimeException - when MAX_NUM_OF_STEPS was exeeded

search

public static void search(numericalMethods.function.DoubleArrayParametrized P,
                          numericalMethods.function.DoubleArrayValued V,
                          double x,
                          double y,
                          double[] rootValues,
                          double acc,
                          double accX,
                          double accY,
                          double xMin,
                          double xMax,
                          double yMin,
                          double yMax,
                          int maxNumOfSteps,
                          boolean panicIfMaxNumOfStepsAreExeeded)
Performs Newton´s method starting at z=x+iy and restricting itself to the rectangle [xMin,xMax]x[yMin,yMax]. The method returns the root zr of a complex function g, given by the pair (P,V), in the first two entries of rootValues. The thrid to the forth entry of rootValues are assigned with re(g(zr), im(g(zr), re(g´(zr)) and g´(im(zr)). The algorithm terminates if the approximation of the root value changes relatively less than accX in the real component and accY in the imaginary or the function at this value drops below acc.
Parameters:
P - parameter object of function; recieves x
V - value object of function; assigns triple: (x,g(x),g´(x)))
x - start position in the interval [xMin,xMax]
rootValues - array of length 6 for the result
acc - accuracy of the zero (absolute)
accX - accuracy of real part of root (relative)
accY - accuracy of imaginary part of root (relative)
xMin - lower bound of real part of searach rectangle
xMax - upper bound of real part of searach rectangle
yMin - lower bound of imaginary part of searach rectangle
yMax - upper bound of imaginary part of searach rectangle
panicIfMaxNumOfStepsAreExeeded - controls whether an exception is thrown if maximum number of steps are exeeded
Throws:
java.lang.RuntimeException - when the algorithm leaves the search rectangle [xMin,xMax]x[yMin,yMax]
java.lang.RuntimeException - when maxNumOfSteps was exeeded and panicIfMaxNumOfStepsAreExeeded is true