NUMAL Section 5.1.1.1.2
BEGIN SECTION : 5.1.1.1.2 (October, 1975)
AUTHOR: T.J. DEKKER.
CONTRIBUTORS: T.J. DEKKER AND T.H.P. REYMER.
INSTITUTE: UNIVERSITY OF AMSTERDAM.
RECEIVED: 750615.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS ONE PROCEDURE FOR FINDING A ZERO OF A GIVEN
DIFFERENTIABLE FUNCTION IN A GIVEN INTERVAL;
ZEROINDER APPROXIMATES A ZERO MAINLY BY MEANS OF CONFLUENT 3-POINT
RATIONAL INTERPOLATION USING NOT ONLY VALUES OF THE
GIVEN FUNCTION BUT ALSO OF ITS DERIVATIVE.
ZEROINDER IS TO PREFER TO ZEROIN OR ZEROINRAT (SECTION 5.1.1.1.1),
IF THE DERIVATIVE IS (MUCH) CHEAPER TO EVALUATE THAN THE FUNCTION.
KEYWORDS:
ZERO SEARCHING,
ANALYTIC EQUATIONS,
SINGLE NONLINEAR EQUATION,
DERIVATIVE AVAILABLE.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE READS:
"BOOLEAN" "PROCEDURE" ZEROINDER(X, Y, FX, DFX, TOLX);
"REAL" X, Y, FX, DFX, TOLX;
"CODE" 34453;
ZEROINDER SEARCHES FOR A ZERO OF A DIFFERENTIABLE REAL FUNCTION F
DEFINED ON A CERTAIN INTERVAL J;
ZEROINDER := "TRUE" WHEN A (SUFFICIENTLY SMALL) SUBINTERVAL
OF J CONTAINING A ZERO OF F HAS BEEN FOUND; OTHERWISE,
ZEROINDER := "FALSE";
LET DF AND T DENOTE REAL FUNCTIONS DEFINED ON J, WHERE DF
IS THE DERIVATIVE OF F AND T A TOLERANCE FUNCTION DEFINING
THE REQUIRED PRECISION OF THE ZERO; ( FOR INSTANCE
T(X) = ABS(X) * RE + AE,
WHERE RE AND AE ARE THE REQUIRED RELATIVE AND ABSOLUTE
PRECISION RESPECTIVELY);
THE MEANING OF THE FORMAL PARAMETERS IS:
X: <REAL VARIABLE>;
A JENSEN VARIABLE; THE ACTUAL PARAMETERS FOR FX, DFX AND
TOLX (MAY) DEPEND ON THE ACTUAL PARAMETER FOR X;
ENTRY: ONE ENDPOINT OF INTERVAL J IN WHICH A ZERO IS
SEARCHED FOR;
EXIT: A VALUE APPROXIMATING THE ZERO WITHIN THE TOLERANCE
2 * T(X) WHEN ZEROINDER HAS THE VALUE "TRUE", AND A
PRESUMABLY WORTHLESS ARGUMENT VALUE OTHERWISE;
Y: <REAL VARIABLE>;
ENTRY: THE OTHER ENDPOINT OF INTERVAL J IN WHICH A ZERO IS
SEARCHED FOR; UPON ENTRY X < Y AS WELL AS Y < X IS
ALLOWED;
EXIT: THE OTHER STRADDLING APPROXIMATION OF THE ZERO,
I.E. UPON EXIT THE VALUES OF Y AND X SATISFY
1. F(X) * F(Y) <= 0, 2. ABS(X - Y) <= 2 * T(X) AND
3. ABS(F(X)) <= ABS(F(Y)) WHEN ZEROINDER HAS THE
VALUE "TRUE", AND A PRESUMABLY WORTHLESS ARGUMENT
VALUE SATISFYING CONDITIONS 2 AND 3 BUT NOT 1
OTHERWISE;
FX: <ARITHMETIC EXPRESSION>;
DEFINES FUNCTION F AS A FUNCTION DEPENDING ON THE ACTUAL
PARAMETER FOR X;
DFX: <ARITHMETIC EXPRESSION>;
DEFINES THE DERIVATIVE DF OF F AS A FUNCTION DEPENDING ON
THE ACTUAL PARAMETER FOR X;
TOLX: <ARITHMETIC EXPRESSION>;
DEFINES THE TOLERANCE FUNCTION T WHICH MAY DEPEND ON THE
ACTUAL PARAMETER FOR X;
ONE SHOULD CHOOSE TOLX POSITIVE AND NEVER SMALLER THAN THE
PRECISION OF THE MACHINE'S ARITHMETIC AT X, I.E. IN THIS
ARITHMETIC X + TOLX AND X - TOLX SHOULD ALWAYS YIELD
VALUES DISTINCT FROM X; OTHERWISE THE PROCEDURE MAY GET
INTO A LOOP.
PROCEDURES USED: DWARF = CP30003;
REQUIRED CENTRAL MEMORY: NO AUXILIARY ARRAYS ARE DECLARED IN ZEROINDER.
RUNNING TIME: SEE METHOD AND PERFORMANCE.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE METHOD USED IS CONFLUENT 3-POINT RATIONAL INTERPOLATION, I.E.
THE INTERPOLATION FUNCTION OF THE FORM (X - A) / (BX + C) IS FITTED
EXACTLY AT 3 POINTS 2 OF WHICH ARE COINCIDING; MOREOVER, IN ORDER
TO IMPROVE THE GLOBAL BEHAVIOUR OF THE PROCESS, LINEAR
INTERPOLATION ON THE FUNCTION F / DF OR BISECTION ARE INCLUDED IN
SOME STEPS;
THE PERFORMANCE IS AS FOLLOWS:
THE NUMBER OF EVALUATIONS OF FX, DFX AND TOLX IS AT MOST
4 LOG(ABS(X - Y)) / TAU,
WHERE X AND Y ARE THE ARGUMENT VALUES GIVEN UPON ENTRY, LOG DENOTES
THE BASE 2 LOGARITHM, AND TAU IS THE MINIMUM OF THE TOLERANCE
FUNCTION ON J (I.E. ZEROINDER REQUIRES AT MOST 4 TIMES THE NUMBER
OF STEPS REQUIRED FOR BISECTION); IF UPON ENTRY X AND Y SATISFY
F(X) * F(Y) <= 0, THEN CONVERGENCE TO A ZERO IS GUARANTEED, SO THAT
UPON EXIT X AND Y SATISFY CONDITION 1 TO 3 MENTIONED ABOVE (SEE
PARAMETER Y) AND ZEROINDER HAS THE VALUE "TRUE";
FOR A SIMPLE ZERO OF F, THE ASYMPTOTIC ORDER OF CONVERGENCE
APPROXIMATELY EQUALS 2.414.
EXAMPLE OF USE:
THE ZERO OF THE FUNCTION EXP(-X * 3) * (X - 1) + X ** 3, IN THE
INTERVAL [0, 1], MAY BE CALCULATED BY THE FOLLOWING PROGRAM:
"BEGIN" "REAL" X, Y;
"REAL" "PROCEDURE" F(X); "VALUE" X; "REAL" X;
F:= EXP(-X * 3) * ( X - 1) + X ** 3;
"REAL" "PROCEDURE" DF(X); "VALUE" X; "REAL" X;
DF:= EXP(-X * 3) * (-3 * X + 4) + 3 * X ** 2;
X:= 0; Y:= 1;
"IF" ZEROINDER(X, Y, F(X), DF(X), ABS(X) * "-14 + "-14) "THEN"
OUTPUT(71, "("/4B,"("CALCULATED ZERO AND FUNCTION VALUE:")",
/8B, 2(B+.15D"+3D4B), /4B,
"("OTHER STRADDLING APPROXIMATION AND FUNCTION VALUE:")",
/8B, 2(B+.15D"+3D4B)")", X, F(X), Y, F(Y))
"ELSE" OUTPUT(71, "("/4B, "("NO ZERO FOUND")"")")
"END"
RESULT:
CALCULATED ZERO AND FUNCTION VALUE:
+.489702748548240"+000 -.444089209850060"-015
OTHER STRADDLING APPROXIMATION AND FUNCTION VALUE:
+.489702748548250"+000 +.177635683940030"-013
REFERENCES:
[1]: BUS, J.C.P. AND DEKKER, T.J.,
TWO EFFICIENT ALGORITHMS WITH GUARANTEED CONVERGENCE FOR
FINDING A ZERO OF A FUNCTION.
MATHEMATICAL CENTRE, REPORT NW 13/74, AMSTERDAM (1974),
(ALSO TO APPEAR IN TOMS 1975).
[2]: OSTROWSKI, A.M.,
SOLUTION OF EQUATIONS AND SYSTEMS OF EQUATIONS.
ACADEMIC PRESS 1966. CHAPTERS 3 AND 11.
SOURCE TEXT(S):
"CODE" 34453;