ZUNI
Finds a zero of a real univariate function.
Required Arguments
F — User-supplied function of which a zero will be found. The form is F(X [,…]),
where:
Function Return Value
F — The computed function value at the point X. (Output)
Required Arguments
X — The point at which the function is evaluated. (Input)
X should not be changed by F.
Optional Arguments
FCN_DATA — A derived type, s_fcn_data, which may be used to pass additional information to/from the user-supplied function. For a detailed description of this argument see FCN_DATA below.
F must be declared EXTERNAL in the calling program.
A — See B. (Input/Output)
B — Two points at which the user-supplied function can be evaluated. (Input/Output)
On input, if F(A) and F(B) are of opposite sign, the zero will be found in the interval [A, B] and on output B will contain the value of X at which F(X)=0. If F(A)*F(B) > 0, and A ≠ B then a search along the x number line is initiated for a point at which there is a sign change and ∣B – A∣ will be used in setting the step size for the initial search. If A = B on entry then the search is started as described in the description section below. On output, B is the abscissa at which |F(x)| had the smallest value. If F(B) ≠ 0 on output, A will contain the nearest abscissa to output B at which F(x) was evaluated and found to have the opposite sign from F(B).
Optional Arguments
TOL— Error tolerance. (Input)
If TOL > 0.0, the zero is to be isolated to an interval of length less than TOL.
If TOL < 0.0, an x is desired for which |F(x)| is ≤ |TOL|.
If TOL = 0.0, the iteration continues until the zero of F(x) is isolated as accurately as possible.
Default: TOL = 0.0.
MAXFN — The number of function evaluations. (Input/Output)
On input, MAXFN specifies an upper bound on the number of function evaluations required for convergence. Set MAXFN to 0 if the number of function evaluations is to be unbounded. On output, MAXFN will contain the actual number of function evaluations used.
Default: MAXFN = 0 so the number of function evaluations is unbounded.
FCN_DATA — A derived type, s_fcn_data, which may be used to pass additional information to/from the user-supplied function.
The derived type, s_fcn_data, is defined as:
type s_fcn_data
real(kind(1e0)), pointer, dimension(:) :: rdata
integer, pointer, dimension(:) :: idata
end type
in module mp_types. The double precision counterpart to s_fcn_data is named d_fcn_data. The user must include a use mp_types statement in the calling program to define this derived type. Note that if this optional argument is used then this argument must also be used in the user-supplied function. (Input/Output)
FORTRAN 90 Interface
Generic: CALL ZUNI (F, A, B [, …])
Specific: The specific interface names are S_ZUNI and D_ZUNI.
Description
ZUNI is based on the JPL Library routine SZERO. The algorithm used is attributed to Dr. Fred T. Krogh, JPL, 1972. Tests have shown ZUNI to require fewer function evaluations, on average, than a number of other algorithms for finding a zero of a continuous function. Also, unlike ZBREN which restricts the user to supplying points A and B such that f(A) and f(B) are opposite in sign, ZUNI will accept any two points A and B and initiate a search on the number line for an x such that f(x) = 0 when there is no sign difference between f(A) and f(B). In either case, B is updated with a new value on each successive iteration. The algorithm description follows.
When f(A) × f(B) > 0 at the initial point, iterates for x are generated according to the formula x = xmin + (xmin ‑ xmax) × ρ, where the subscript “min” is associated with the ( f, x) pair that has the smallest value for ∣f∣, the subscript “max” is associated with the ( f, x) pair that has the largest value for ∣f∣, and ρ is 8 if r = fmin / (fmax – fmin) ≥ 8, else ρ = max(κ/4, r), where κ is a count of the number of iterations that have been taken without finding f’s with opposite signs. If A and B have the same value initially, then the next x is a distance 0.008 + |xmin∣/4 from xmin taken toward 0. (If A = B = 0, the next x is -.008.)
Let x1 and x2 denote the first two x values that give f values with different signs. Let α < β be the two values of x that bracket the zero as tightly as is known. Thus α = x1 or α = x2 and β is the other when computing x3. The next point, x3, is generated by treating x as the linear function q(f) that interpolates the points (f (x1), x1) and (f (x2), x2), and then computing x3 = q(0), subject to the condition that α + ɛ ≤ x3 ≤ β - ɛ, where ɛ = 0.875 × max(TOL, machine precision). (This condition on x3 with updated values for α and β is also applied to future iterates.)
Let x4, x5, …, xm denote the abscissae on the following iterations. Let a = xm, b = xm-1, and c = xm-2. Either α or β (defined as above) will coincide with a, and β will frequently coincide with either b or c. Let p(x) be the quadratic polynomial in x that passes through the values of f evaluated at a, b, and c. Let q(f) be the quadratic polynomial in f that passes through the points (f(a), a), (f(b), b), and f(c), c).
Let ζ = α or β, selected so that ζ ≠ a. If the sign of f has changed in the last 4 iterations and p′(a) × q′(f(a)) and p′ (ζ)) × q′ (f(ζ)) are both in the interval [1/4, 4], then x is set to q(0). (Note that if p is replaced by f and q is replaced by x, then both products have the value 1.) Otherwise x is set to a – (a-ζ ) ( φ/(1+φ)), where φ is selected based on past behavior and is such that 0 < φ. If the sign of f () does not change for an extended period, φ gets large.
Comments
Informational error
|
Type |
Code |
Description |
|
4 |
1 |
The error tolerance criteria was not satisfied. B contains the abscissa at which ∣F(x)∣ had the smallest value. |
Example
This example finds a zero of the function
f(x) = x2 + x – 2
in the interval [ – 10.0, 0.0].
USE ZUNI_INT
USE UMACH_INT
IMPLICIT NONE
! Declare variables
INTEGER NOUT, MAXFN
REAL A, B, F
EXTERNAL F
! Set values of A, B, MAXFN
A = -10.0
B = 0.0
MAXFN = 0
!
CALL UMACH (2, NOUT)
! Find zero of F
CALL ZUNI (F, A, B, MAXFN=MAXFN)
!
WRITE (NOUT,99999) B, MAXFN
99999 FORMAT (' The best approximation to the zero of F is equal to', &
F5.1, '.', /, ' The number of function evaluations', &
' required was ', I2, '.', //)
!
END
!
REAL FUNCTION F (X)
REAL X
!
F = X*X + X - 2.0
RETURN
END
The best approximation to the zero of F is equal to -2.0.
The number of function evaluations required was 10.
