zerosFunction¶
Finds the real zeros of a real, continuous, univariate function.
Synopsis¶
zerosFunction (fcn)
Required Arguments¶
- float
fcn
(x
) (Input/Output) - User-supplied function to compute the value of the function of which the zeros will be found.
Return Value¶
An array containing the zeros of the function. The zeros are in increasing
order. If fewer than the requested number of zeros were found, the final
entries are set to NaN. If there is a fatal error, then None
is
returned.
Optional Arguments¶
numRoots
, int (Input)The number of zeros to be found.
Default:
numRoots
= 1.numRootsFound
(Output)- The number of zeros actually found.
nEvals
(Output)- The actual number of function evaluations used.
bound
, floata
, floatb
(Input)The closed interval in which to search for the roots. The function must be defined for all values in this interval.
Default: The search for the roots is not bounded.
maxEvals
(Input)The maximum number of function evaluations allowed. Once this limit is reached, the roots found are returned.
Default:
maxEvals
= 100xguess
, float[]
(Input)- Array with
numRoots
components containing initial guesses for the zeros. If a bound on the zeros is also given, the guesses must satisfy the bound condition. errAbs
, float (Input)A convergence criterion. A root is accepted if the absolute value of the function at the point is less than or equal to
errAbs
.Default:
err
_abs= 100 ɛ, where ɛ is the machine precision.errX
, float (Input)A convergence criterion. A root is accepted if it is bracketed within an interval of length
errX
.Default:
errX
= 100 ɛ /xscale
, where ɛ is the machine precision.toleranceMuller
, float (Input)Müller’s method is started if, during refinement, a point is found for which the absolute value of the function is less than
toleranceMuller
and the point is not near an already discovered root. IftoleranceMuller
is less than or equal to zero Müller’s method is never used.Default:
toleranceMuller
= ɛ /errAbs
, where ɛ is the machine precision. With the default value oferrAbs
, this equals 0.01.minSeparation
, float (Input)The minimum separation between accepted roots. If two points both satisfy the convergence criteria, but are within
minSeparation
of each other, only one of the roots is accepted.Default:
minSeparation
= \(\varepsilon^{1/2}\)/xscale
, where ɛ is the machine precision.xscale
, float (Input)The scaling in the x-coordinate. The absolute value of the roots divided by
xscale
should be about one.Default:
xscale
= 1.0
Description¶
The function zerosFunction
computes numRoots
real zeros of a real,
continuous, univariate function. The search for the zeros of the function
can be limited to a specified interval, or extended over the entire real
line. The code is generally more efficient if an interval is specified. The
user supplied function must return valid results for all values in the
specified interval. If no interval is given, the user-supplied function must
return valid results for all real numbers.
The function has two convergence criteria. The first criterion accepts a root, x, if
where \(\tau\) = errX
.
The second criterion accepts a root if it is known to be inside of an
interval of length at most errAbs
.
A root is accepted if it satisfies either criteria and is not within
minSeparation
of another accepted root.
If initial guesses for the roots are given, Müller’s method (Müller 1956) is used for each of these guesses. For each guess, the Müller iteration is stopped if the next step would be outside of the bound, if given. The iteration is also stopped if it cannot make further progress in finding a root.
If no guess for the zeros were given, or if Müller’s method with the guesses did not find the requested number of roots, a meta-algorithm, combining Müller’s and Brent’s methods, is used. Müller’s method is used primarily to find the roots of functions, such as \(f(x)=x^2\), where the function does not cross the \(y=0\) line. Brent’s method is used to find other types of roots.
The meta-algorithm successively refines the interval using a one-dimensional
Faure low-discrepancy sequence. If the optional argument bound
is used
to specify a bounded interval, [a,b], the Faure sequence is scaled from
(0,1) to (a,b).
If no bound on the function’s domain is given, the entire real line must be searched for roots. In this case the Faure sequence is scaled from (0, 1) to (-∞,+∞) using the mapping
where xscale
is given by the optional argument xscale
.
At each step of the iteration the next point in the Faure sequence is added to the list of breakpoints defining the subintervals. Call the points \(x_0=a,x_1=b,x_2,x_3,\ldots\). The new point, \(x_s\) splits an existing subinterval, \(\left[x_p,x_q\right]\).
The function is evaluated at \(x_s\). If its value is small enough, specifically if
then Müller’s method is used with \(x_p\), \(x_q\) and \(x_s\) as starting values. If a root is found, it is added to the list of roots. If more roots are required, the new Faure point is used.
If Müller’s method did not find a root using the new point, the function value at the point is compared with the function values at the endpoints of the subinterval it divides. If \(f \left( x_p \right) f \left( x_s \right)<0\) and no root has previously been found in \(\left[ x_p,x_s \right]\) then Brent’s method is used to find a root in this interval. Similarly, if the function changes sign over the interval \(\left[ x_s,x_q \right]\), and a root has not already been found in the subinterval, Brent’s method is used there.
Examples¶
Example 1¶
This example finds a real zero of the function.
from __future__ import print_function
from numpy import *
from pyimsl.math.zerosFunction import zerosFunction
def fcn(x):
return exp(x) - 3.0
x = zerosFunction(fcn)
print("fcn(%6.3f) = %12.3e" % (x[0], fcn(x[0])))
Output¶
fcn( 1.099) = 2.220e-15
Example 2¶
This example finds two real zeros of function
on the interval [0,20].
from numpy import *
from pyimsl.math.zerosFunction import zerosFunction
from pyimsl.math.writeMatrix import writeMatrix
def fcn(x):
return sqrt(x) * exp(-x) - 0.3
nFound = []
x = zerosFunction(fcn,
numRoots=2,
bound={'a': 0.0, 'b': 20.0},
numRootsFound=nFound)
writeMatrix("x", x)
Output¶
x
1 2
0.113 1.356
Warning Errors¶
IMSL_ZEROS_MAX_EVALS_EXCEEDED |
The maximum number of function evaluations allowed has been exceeded. Any zeros found are returned. |
Fatal Errors¶
IMSL_STOP_USER_FCN |
Request from user supplied function to stop algorithm. User flag = “#”. |