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;