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;