jvx.numeric

Class PnRootFinder

java.lang.Object

jvx.numeric.PnRootFinder

public class PnRootFinder
extends java.lang.Object

Find roots of a real-valued function in one variable or defined on a 1-dimensional curve.

Author:

Konrad Polthier

Version:

05.05.01, 1.10 revised (kp) Two methods findValue and findZero moved from jv.function.PuFunction.
29.09.99, 1.00 created (kp)

Constructor Summary

Constructors

Constructor and Description
PnRootFinder()

Method Summary

Modifier and Type	Method and Description
static PdVector	findRoots(PuFunction fx, double x1, double x2, int maxRoots) Given a function fx on the interval I=[x1,x2] and a subdivision of I into maxRoots equally spaced subintervals, then find those subintervals with zero crossing and compute a root for each subinterval.
static double[]	findValue(PuFunction fx, double[] a, double[] b, double value) Finds the position of a value on a straight line segment between two vertices using a bisection algorithm.
static double[]	findZero(PuFunction fx, double[] a, double[] b) Finds the zero position on a straight line segment between two vertices using a bisection algorithm.
static double[]	zbrac(PuFunction fx, double x1, double x2) Given a function fx and initial interval I=[x1,x2], then the method expands the range until a root is bracketed by the returned array.
static int	zbrak(PuFunction fx, double x1, double x2, int len, double[] xb1, double[] xb2, int nb) Given a function fx on the interval I=[x1,x2] and a subdivision of I into len equally spaced subintervals, then find those subintervals with zero crossing and return them as array brackets.
static double	zbrent(PuFunction fx, double x1, double x2, double tol) Given a function fx find a root known to lie in the interval I=[x1,x2].

Methods inherited from class java.lang.Object

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

Constructor Detail

PnRootFinder

public PnRootFinder()

Method Detail

findZero

public static double[] findZero(PuFunction fx,
                                double[] a,
                                double[] b)

Finds the zero position on a straight line segment between two vertices using a bisection algorithm. The function must be defined on the full straight line segment.

This method just calls #findValue with value of zero.

Parameters:

a - a double[] with one vertex

b - a double[] with another vertex

Returns:

a double[] with the zero crossing point

Author:

Samy Khadem-Al-Charieh

Version:

05.05.01, 1.50 revised (kp) Moved from jv.function.PuFunction, method made static.
22.02.00, 1.00 created (sk)

findValue

public static double[] findValue(PuFunction fx,
                                 double[] a,
                                 double[] b,
                                 double value)

Finds the position of a value on a straight line segment between two vertices using a bisection algorithm. The function must be defined on the full straight line segment.

First the function is evaluated at the two end points. If either of them is already equal to the value, then a copy of this vertex is returned. If both values are bigger or smaller, then a warning message is issued and the first vertex is returned.

Otherwise the bisection starts by computing the midpoint of the interval, choosing the section with different signs for the difference, bisecting this subinterval again and so on until one of the function values becomes equal. This vertex is finally returned.

HACK: Method should use more efficient root finding algorithm.

Parameters:

a - coordinates of the first vertex

b - coordinates of the second vertex

value - function value to search for its argument vertex

Returns:

vertex in the given interval whose function value is equal to the given value.

Author:

Samy Khadem-Al-Charieh

Version:

05.05.01, 1.55 revised (kp) Code optimized.
05.05.01, 1.50 revised (kp) Moved from jv.function.PuFunction, method made static.
22.02.00, 1.01 revised (sk) name changed from findZero to findValue and new parameter value added.
08.09.99, 1.00 created (sk)

findRoots

public static PdVector findRoots(PuFunction fx,
                                 double x1,
                                 double x2,
                                 int maxRoots)

Given a function fx on the interval I=[x1,x2] and a subdivision of I into maxRoots equally spaced subintervals, then find those subintervals with zero crossing and compute a root for each subinterval.

Method uses zbrak to find subintervals with zero crossings, and use zbrent to compute the root on each subinterval which is known to contain a root.

Parameters:

fx - Function to evaluate for zero crossings.

x1 - Original interval [x1,x2].

x2 - Original interval [x1,x2].

maxRoots - Number of subintervals to in which to divide interval [x1,x2].

Returns:

Vector with roots, at most one root per subinterval.

See Also:

zbrak(jv.function.PuFunction, double, double, int, double[], double[], int), zbrent(jv.function.PuFunction, double, double, double)

Author:

Konrad Polthier

Version:

02.10.99, 1.00 (kp) created.

zbrac

public static double[] zbrac(PuFunction fx,
                             double x1,
                             double x2)

Given a function fx and initial interval I=[x1,x2], then the method expands the range until a root is bracketed by the returned array.

Parameters:

fx - Function to evaluate for zero crossings.

x1 - Original interval [x1,x2].

x2 - Original interval [x1,x2].

Returns:

Array with bracketing values, or null if maximal num of tries exceeded.

See Also:

zbrak(jv.function.PuFunction, double, double, int, double[], double[], int)

Author:

Konrad Polthier

Version:

02.10.99, 1.00 (kp) created from Numerical Recipes method.

zbrak

public static int zbrak(PuFunction fx,
                        double x1,
                        double x2,
                        int len,
                        double[] xb1,
                        double[] xb2,
                        int nb)

Given a function fx on the interval I=[x1,x2] and a subdivision of I into len equally spaced subintervals, then find those subintervals with zero crossing and return them as array brackets.

Parameters:

fx - Function to evaluate for zero crossings.

x1 - Original interval [x1,x2].

x2 - Original interval [x1,x2].

len - Number of subintervals to in which to divide interval [x1,x2].

xb1 - Array of size len to store the brackets of zero crossings [xb1,xb2].

xb2 - Array of size len to store the brackets of zero crossings [xb1,xb2].

nb - Requested maximal number of zero crossings.

Returns:

Number of subintervals found with zero crossings.

See Also:

zbrac(jv.function.PuFunction, double, double)

Author:

Konrad Polthier

Version:

02.10.99, 1.00 (kp) created from Numerical Recipes method.

zbrent

public static double zbrent(PuFunction fx,
                            double x1,
                            double x2,
                            double tol)

Given a function fx find a root known to lie in the interval I=[x1,x2]. Root is computed up to requested precision using Brent's method for root finding. Root is returned.

Parameters:

fx - Function to evaluate.

x1 - Interval [x1,x2] containing a root of fx.

x2 - Interval [x1,x2] containing a root of fx.

tol - Required precision.

Returns:

double Root, if found, otherwise return x1-1.

See Also:

zbrac(jv.function.PuFunction, double, double)

Author:

Konrad Polthier

Version:

02.10.99, 1.00 (kp) created from Numerical Recipes method 'zbrent'.