NUMAL Section 5.1.1.1.1
BEGIN SECTION : 5.1.1.1.1 (October, 1975)
AUTHORS: J. C. P. BUS AND T. J. DEKKER.
CONTRIBUTOR: J. C. P. BUS.
INSTITUTE: MATHEMATICAL CENTRE.
RECEIVED: 750615.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS TWO PROCEDURES FOR FINDING A ZERO OF A GIVEN
FUNCTION IN A GIVEN INTERVAL;
ZEROIN APPROXIMATES A ZERO MAINLY BY LINEAR INTERPOLATION AND
EXTRAPOLATION;
ZEROINRAT APPROXIMATES A ZERO BY INTERPOLATION WITH RATIONAL
FUNCTIONS.
ZEROIN IS PREFERABLE FOR SIMPLE (I.E. CHEAPLY TO CALCULATE)
FUNCTIONS AND/OR WHEN NO HIGH PRECISION IS REQUIRED. ZEROINRAT IS
PREFERABLE FOR COMPLICATED (I.E. EXPENSIVE) FUNCTIONS WHEN A ZERO
IS REQUIRED IN RATHER HIGH PRECISION AND ALSO FOR FUNCTIONS HAVING
A POLE NEAR THE ZERO. WHEN THE ANALYTIC DERIVATIVE OF THE FUNCTION
IS EASILY OBTAINED, THEN ZEROINDER (SECTION 5.1.1.1.2) SHOULD BE
TAKEN INTO CONSIDERATION.
KEYWORDS:
ZERO SEARCHING,
ANALYTIC EQUATIONS,
SINGLE NON-LINEAR EQUATION.
SUBSECTION: ZEROIN.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE READS :
"BOOLEAN" "PROCEDURE" ZEROIN(X, Y, FX, TOLX);
"REAL" X, Y, FX, TOLX;
"CODE" 34150;
ZEROIN SEARCHES FOR A ZERO OF A REAL FUNCTION F DEFINED ON A
CERTAIN INTERVAL J;
ZEROIN := "TRUE" WHEN A (SUFFICIENTLY SMALL) SUBINTERVAL OF
J CONTAINING A ZERO OF F HAS BEEN FOUND; OTHERWISE,
ZEROIN := "FALSE";
LET A REAL FUNCTION T DEFINED ON J, DENOTE 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 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 ZEROIN 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 ZEROIN 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;
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;
EXECUTION FIELD LENGTH: NO AUXILIARY ARRAYS ARE DECLARED IN ZEROIN.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE METHOD USED IS DESCRIBED IN DETAIL IN [1].
THE NUMBER OF EVALUATIONS OF FX 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 TOLX ON THE INITIAL INTERVAL. IF UPON ENTRY X AND Y
SATISFY F(X) * F(Y) <= 0, THEN CONVERGENCE IS GUARANTEED AND THE
ASYMPTOTIC ORDER OF CONVERGENCE IS 1.618 FOR SIMPLE ZEROES.
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;
X:= 0; Y:= 1;
"IF" ZEROIN(X, Y, F(X), ABS(X) * "-14 + "-14) "THEN"
OUTPUT(71, "("/4B,"("CALCULATED ZERO:")"B+.15D"+3D")", X)
"ELSE" OUTPUT(71, "("/4B,"("NO ZERO FOUND")"")")
"END"
RESULT:
CALCULATED ZERO: +.489702748548240"+000
SUBSECTION: ZEROINRAT.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE READS:
"BOOLEAN" "PROCEDURE" ZEROINRAT(X, Y, FX, TOLX);
"REAL" X, Y, FX, TOLX;
"CODE" 34436;
ZEROINRAT SEARCHES FOR A ZERO OF A REAL FUNCTION F DEFINED ON A
CERTAIN INTERVAL J;
ZEROINRAT := "TRUE" WHEN A (SUFFICIENTLY SMALL) SUBINTERVAL
OF J CONTAINING A ZERO OF F HAS BEEN FOUND; OTHERWISE,
ZEROINRAT := "FALSE";
LET A REAL FUNCTION T DEFINED ON J, DENOTE 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 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 ZEROINRAT 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 ZEROINRAT 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;
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;
EXECUTION FIELD LENGTH: NO AUXILIARY ARRAYS ARE DECLARED IN ZEROINRAT.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE METHOD USED IS DESCRIBED IN DETAIL IN [1].
THE NUMBER OF EVALUATIONS OF FX AND TOLX IS AT MOST
5 * 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 TOLX ON THE INITIAL INTERVAL. IF UPON ENTRY X AND Y
SATISFY F(X) * F(Y) <= 0, THEN CONVERGENCE IS GUARANTEED AND THE
ASYMPTOTIC ORDER OF CONVERGENCE IS 1.839 FOR SIMPLE ZEROES.
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;
X:= 0; Y:= 1;
"IF" ZEROINRAT(X, Y, F(X), ABS(X) * "-14 + "-14) "THEN"
OUTPUT(71, "("/4B,"("CALCULATED ZERO:")"B+.15D"+3D")", X)
"ELSE" OUTPUT(71, "("/4B,"("NO ZERO FOUND")"")")
"END"
RESULT:
CALCULATED ZERO: +.489702748548240"+000
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).
SOURCE TEXT(S):
"CODE" 34150;
"CODE" 34436;