F 2.8.4 The King and the Anderson-Björck-King Methods, the Illinois Method
SUBROUTINE ZERORF(FCT,ABSERR,RELERR,FAB,MAXIT,IMETH,IEXTRA,
+ DELX,X1,X2,X3,F1,F2,F3,NUMIT,IHELP1,
+ IHELP2,INCL,IERR)
C
C*****************************************************************
C *
C The SUBROUTINE ZERORF is the governing program for several *
C subroutines that determine zeros of a continuous real-valued *
C function FCT. The methods used are primarily intended for *
C simple zeros and zeros of odd order. *
C This SUBROUTINE adapts its approach depending on whether *
C the starting values enclose a zero of the function FCT or not.*
C If a zero is enclosed, an iteration sequence is constructed *
C using one of several iteration methods: Pegasus, *
C Anderson/Bjoerck, or King. These methods ensure that inclusion*
C is preserved. All methods used work without derivatives and *
C each possesses a convergence order of P > 1.6. *
C If no two starting estimates are known that enclose a *
C functional zero, then two identical starting values X1, X2 *
C may be specified. *
C The SUBROUTINE ZERORF will construct a *
C second starting value X2 by adding DELX to the starting value *
C X1. DELX has to be chosen by the user. *
C If there is still no enclosure, linear extrapolation is tried,*
C or, following the first secant step, quadratic extrapolation *
C using the tangent line of an interpolating parabola through *
C three different interpolation points is used. If enclosure *
C is finally achieved, the program continues with one of the *
C three special iterative methods as chosen by the user. *
C NOTE: Extensive tests have shown that the number of iteration *
C steps required per zero for the same degree of *
C accuracy is the largest for the Pegasus-method *
C (SUBROUTINE PEG) and by far the smallest for the *
C combination of the Anderson/Bjoerck and King *
C methods (SUBROUTINE ANDBJK). *
C *
C *
C INPUT PARAMETERS: *
C ================= *
C FCT : real-valued function for which a zero is to be *
C determined. It is declared as *
C DOUBLE PRECISION FUNCTION FCT(X) *
C and has to be defined as EXTERNAL within the *
C calling program (or as INTRINSIC if a FORTRAN *
C standard function is used). *
C ABSERR : ) error bounds both of which have to be >= 0.0. *
C RELERR : ) Their sum has to be > 0.0. The following mixed *
C test is used as a break-off criterion: *
C ABS(X1-X2) <= ABS(X2)*RELERR+ABSERR. *
C Thus if RELERR=0.0 is chosen, this tests for the *
C absolute error, if ABSERR=0.0, this tests for the*
C relative error. *
C The values entered for ABSERR and RELERR are *
C accepted unchanged by the program if they *
C both exceed four times the machine constant, or, *
C if one is zero, then the other has to exceed *
C four times the machine constant. If this is not *
C the case, then both or one of the bounds is set *
C internally to this value. *
C FAB : break-off criterion constant for the functional *
C value at the last approximation of the zero. The *
C value for FAB can be chosen between zero and four *
C times the machine constant. If it is chosen *
C negative or larger than four times the machine *
C constant, it is set to that value internally. *
C MAXIT : maximum number of functional evaluations. *
C (this equals the number of iteration steps) *
C IMETH : = 1, use the Pegasus-method. *
C = 2, use the King-method. *
C = 3, use the Anderson/Bjoerck-method. *
C = 4, use the method of Anderson/Bjoerck and King. *
C IEXTRA : = 0, quadratic extrapolation shall be allowed. *
C = 1, only linear extrapolation is acceptable (if *
C e.g. a double root is expected or if setting *
C IEXTRA=0 has resulted in IERR=0). *
C If the starting values do not enclose a zero, i.e.,*
C if ( F1*F2 > 0.0, one may predetermine via IEXTRA, *
C whether only linear extrapolation should be tried *
C or whether quadratic extrapolation is also *
C acceptable. If no double zero is expected, then *
C IEXTRA=0 should be used first. *
C DELX : is used for altering a starting value in case two *
C identical starting values were entered. A meaning- *
C ful choice for DELX would be: *
C DELX=1E-6 or DELX=1E-8. *
C X1,X2 : starting values for the iteration; if only one *
C starting value is known, setting X2=X1 is *
C acceptable. By adding DELX to one of the two *
C identical starting values, the program will create *
C two different starting values and proceed. *
C *
C *
C OUTPUT PARAMETERS: *
C ================== *
C ABSERR : ) error bounds actually used. *
C RELERR : ) *
C X1,X2,X3 : approximate values for the desired zero. *
C (see IERR). *
C F1,F2,F3 : functional values FCT(X1), FCT(X2), FCT(X3). *
C NUMIT : number of functional evaluations performed. *
C INCL : = 0, starting values with no enclosure. *
C = 1, starting values with known enclosure. *
C IERR : = 0, zero was not found. *
C = 1, zero lies between X1 and X2 (of the two *
C values the one with the smaller absolute *
C functional value should be chosen as the *
C zero). *
C The absolute error of the computed zero is *
C smaller than or equal to ABS(X1-X2). *
C = 2, X2 is a zero of FCT: F2=0.0 (machine zero). *
C = 3, X3 is a zero with ABS(F3) < 4 * machine *
C constant. *
C = 4, zero of FCT is at X2 (enclosure interval *
C not definable). *
C = 5, maximum number MAXIT of functional evaluations*
C exceeded. *
C = 6, ABSERR or RELERR are negative, or both are *
C equal to zero, or MAXIT < 1. *
C *
C *
C AUXILIARY PARAMETERS: *
C ===================== *
C IHELP1,IHELP2 : internal variables. *
C *
C----------------------------------------------------------------*
C *
C subroutines required: EXCHG, PEG, PEGK, ANDBJ, ANDBJK, *
C SUB1, SUB2, MACHPD *
C *
C *
C sources: 1. Anderson/Bjoerck, see [ANDE73]. *
C 2. Dowell/Jarrat, see [DOWE71], [DOWE72]. *
C 3. King, see [KING73]. *
C 4. unpublished manuscript by R. Wodicka, *
C RWTH Aachen. *
C *
C*****************************************************************
C *
C author : Gisela Engeln-Muellges *
C date : 08.26.1985 *
C source : FORTRAN 77 *
C *
C*****************************************************************
C
IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
C if two identical starting values are initially given (X1=X2),
C a second starting value is internally generated.
C
IF(X1 .EQ. X2) THEN
X1=X1+DELX
END IF
C
C initializing the parameters IERR and NUMIT.
C
IERR=1
NUMIT=2
C
C calculation of the machine constant FMACHP.
C
FMACHP=1.0D0
10 FMACHP=0.5D0*FMACHP
IF(MACHPD(1.0D0+FMACHP) .EQ. 1) GOTO 10
FMACHP=2.0D0*FMACHP
C
C testing the validity of the error bounds and MAXIT.
C
IF(ABSERR .GE. 0.0D0 .AND. RELERR .GE. 0.0D0 .AND.
+ ABSERR+RELERR .GT. 0.0D0 .AND. MAXIT .GE. 1) GOTO 20
IERR=6
RETURN
20 DUMMY=4.0D0*FMACHP
IF(RELERR .EQ. 0.0D0) THEN
IF(ABSERR .LT. DUMMY) ABSERR=DUMMY
ELSE IF(ABSERR .EQ. 0.0D0) THEN
IF(RELERR .LT. DUMMY) RELERR=DUMMY
ELSE
IF(ABSERR .LT. DUMMY) ABSERR=DUMMY
IF(RELERR .LT. DUMMY) RELERR=DUMMY
END IF
C
C testing the validity of the break-off parameter FAB for the
C functional value at the approximate zero.
C
IF(FAB .LT. 0.0D0 .OR. FAB .GT. DUMMY) FAB=DUMMY
C
C calculating the functional values at the starting points.
C
F1=FCT(X1)
F2=FCT(X2)
C
C labelling the zeros, so that ABS(F2) <= ABS(F1) holds.
C
IF(DABS(F2) .GT. DABS(F1)) THEN
CALL EXCHG(X1,X2,F1,F2)
END IF
C
C test whether X2 already is a zero of FCT,
C in which case IERR=2.
C
IF(F2 .EQ. 0.0D0) THEN
IERR=2
RETURN
END IF
C
C test whether the starting values X1, X2 enclose a zero of FCT.
C If so, the internal variables are set to INCLUD=1, IHELP2=1,
C otherwise INCLUD=0.
C IHELP2=1 indicates that the next iteration step is to be a secant step.
C
IF(F1*F2 .GT. 0.0D0) THEN
INCLUD=0
F3=F2
ELSE
INCLUD=1
IHELP2=1
END IF
INCL=INCLUD
C
C iteration loop to find a new approximate value X3. We account for
C the fact here whether we have inclusion or not. The new
C approximate value X3 is taken as the x-intercept of the straight
C line connecting (X2, F2) and (X1, F1). Unless a secant step is
C performed, F1 is changed: in case of enclosure according to
C the specified method, otherwise by using quadratic extrapolation
C (see above remarks).
C
30 IF(INCLUD .EQ. 0) THEN
F1DF2=F1/F2
IF(F1DF2 .GT. 1.0D0) THEN
C
C check whether linear extrapolation is the only acceptable
C method or whether quadratic extrapolation is also allowed.
C
IF(IEXTRA .EQ. 0) THEN
IF((F1DF2-F1/F3) .GT. 1.0D0) THEN
G=1.0D0-F2/F3
F1=G*F1
END IF
END IF
ELSE
C
C now F1/F2 <= 1.0. If moreover F1/F2 < 0.0, then we have enclosure.
C
IF(F1DF2 .LT. 0.0D0) THEN
INCLUD=1
IF(DABS(X1-X2) .LE. DABS(X2)*RELERR+ABSERR) THEN
IERR=1
RETURN
ELSE
IHELP2=1
END IF
ELSE
C
C if there is no enclosure, then a zero cannot be found
C because of ABS(F1) <= ABS(F2).
C
IERR=0
RETURN
END IF
END IF
END IF
C
C calculation of the scaling factor Q for X3=X2+Q(X1-X2).
C
Q=F2/(F2-F1)
C
C calculation of the new approximate value.
C
X3=X2+Q*(X1-X2)
C
C testing whether the new approximate value X3 differs from both
C X1 and X2. If this is not the case, an alternate value
C X3NEW is calculated for X3. If there is no enclosure and
C X2=X3=X3NEW, then the program is stopped with setting
C IERR=4 (zero of FCT is at X2).
C
IF(INCLUD .EQ. 0) THEN
IF(X2 .EQ. X3) THEN
X3NEW=X2+(X2-X1)/9.0D0
IF(X2 .EQ. X3NEW) THEN
IERR=4
RETURN
ELSE
X3=X3NEW
END IF
ELSE
IF(X2 .EQ. X3) THEN
X3NEW=X2+(X1-X2)/3.0D0
IF(X2 .EQ. X3NEW) THEN
IERR=1
RETURN
ELSE
40 Q=2.0D0*Q
X3NEW=X2+Q*(X1-X2)
IF(X3NEW .EQ. X2) GOTO 40
IF(X3NEW .EQ. X1) THEN
IERR=1
RETURN
ELSE
X3=X3NEW
END IF
END IF
ELSE
IF(X1 .EQ. X3) THEN
X3NEW=X1+(X2-X1)/3.0D0
IF(X3NEW .EQ. X1) THEN
IERR=1
RETURN
ELSE
Q=F1/(F1-F2)
50 Q=2.0D0*Q
X3NEW=X1+Q*(X2-X1)
IF(X3NEW .EQ. X1) GOTO 50
IF(X3NEW .EQ. X2) THEN
IERR=1
RETURN
ELSE
X3=X3NEW
END IF
END IF
END IF
END IF
END IF
END IF
C
C now X3 differs from both X1 and X2, and F3 has been calculated.
C
F3=FCT(X3)
C
C increasing the counter NUMIT.
C
NUMIT=NUMIT+1
C
C test whether |F3| is less than four times the
C machine constant. In this case, X3 is a zero with IERR=3.
C
IF(DABS(F3) .LE. FAB) THEN
IERR=3
RETURN
END IF
C
C test whether the maximum number of functional evaluations
C allowed has been exceeded.
C
IF(NUMIT .GE. MAXIT) THEN
IERR=5
RETURN
END IF
C
C the approximate values and their functional values
C are relabelled by applying the SUBROUTINE EXCHG.
C If F2*F3 > 0.0, the auxiliary variable IHELP1 is set to 0;
C if F2*F3 < 0.0, it is set to IHELP1=1.
C
IF(INCLUD .EQ. 0) THEN
CALL EXCHG(X1,X2,F1,F2)
ELSE
IF(F2*F3 .LT. 0.0D0) THEN
CALL EXCHG(X1,X2,F1,F2)
IHELP1=1
ELSE
IHELP1=0
END IF
END IF
CALL EXCHG(X2,X3,F2,F3)
C
C if we have enclosure, we check whether the break-off criterion
C holds for the new enclosure interval. If the break-off condition
C is met, the iteration is stopped with IERR=1.
C Otherwise the user specified method is used to determine F1.
C
IF(INCLUD .EQ. 1) THEN
IF(DABS(X1-X2) .GT. DABS(X2)*RELERR+ABSERR) THEN
IF(IMETH .EQ. 1) THEN
CALL PEG(IHELP1,F1,F2,F3)
ELSE IF(IMETH .EQ. 2) THEN
CALL PEGK(IHELP1,IHELP2,F1,F2,F3)
ELSE IF(IMETH .EQ. 3) THEN
CALL ANDBJ(IHELP1,F1,F2,F3)
ELSE
CALL ANDBJK(IHELP1,IHELP2,F1,F2,F3)
END IF
ELSE
IERR=1
RETURN
END IF
END IF
GOTO 30
END
C
C
SUBROUTINE PEG(IHELP1,F1,F2,F3)
C
C*****************************************************************
C *
C This SUBROUTINE uses the Pegasus-method to calculate a new *
C functional value F1 for the governing program ZERORF. *
C *
C *
C INPUT PARAMETERS: *
C ================= *
C IHELP1 : auxiliary variable, as specified by the *
C governing program ZERORF. *
C F1,F2,F3 : functional values FCT(X1), FCT(X2), FCT(X3). *
C *
C *
C OUTPUT PARAMETERS: *
C ================== *
C F1 : new functional value at X1. *
C *
C----------------------------------------------------------------*
C *
C subroutines required: SUB1 *
C *
C *
C sources: Dowell/Jarrat, see at [DOWE71], [DOWE72]. *
C *
C*****************************************************************
C *
C author : Gisela Engeln-Muellges *
C date : 08.26.1985 *
C source : FORTRAN 77 *
C *
C*****************************************************************
C
IMPLICIT DOUBLE PRECISION (A-H,O-Z)
IF(IHELP1 .EQ. 0) THEN
CALL SUB1(F1,F2,F3)
END IF
RETURN
END
C
C
C
SUBROUTINE PEGK(IHELP1,IHELP2,F1,F2,F3)
C
C*****************************************************************
C *
C This SUBROUTINE uses an improved version of the Pegasus *
C method by King for calculating a new functional value F1 *
C for use in the governing program ZERORF. *
C *
C *
C INPUT PARAMETERS: *
C ================= *
C IHELP1 : ) auxiliary variables that are specified by the *
C IHELP2 : ) governing program ZERORF. *
C F1,F2,F3 : functional values FCT(X1), FCT(X2), FCT(X3). *
C *
C *
C OUTPUT PARAMETER: *
C ================= *
C F1 : new functional value at X1. *
C *
C----------------------------------------------------------------*
C *
C subroutines required: SUB1 *
C *
C *
C sources: method of King, see at [KING73]. *
C *
C*****************************************************************
C *
C author : Gisela Engeln-Muellges *
C date : 08.26.1985 *
C source : FORTRAN 77 *
C *
C*****************************************************************
C
IMPLICIT DOUBLE PRECISION (A-H,O-Z)
IF(IHELP2 .EQ. 1) THEN
IHELP2=0
CALL SUB1(F1,F2,F3)
ELSE IF(IHELP1 .EQ. 0) THEN
CALL SUB1(F1,F2,F3)
ELSE
IHELP2=1
END IF
RETURN
END
C
C
C
SUBROUTINE ANDBJ(IHELP1,F1,F2,F3)
C
C*****************************************************************
C *
C This SUBROUTINE uses the Anderson / Bjoerck method to calcu- *
C late a new functional value F1 for the governing program *
C ZERORF. *
C *
C *
C INPUT PARAMETERS: *
C ================= *
C IHELP1 : auxiliary variable that is determined in the *
C governing program ZERORF. *
C F1,F2,F3 : functional values FCT(X1), FCT(X2), FCT(X3). *
C *
C *
C OUTPUT PARAMETER: *
C ================= *
C F1 : new functional value at X1. *
C *
C----------------------------------------------------------------*
C *
C subroutines required: SUB2 *
C *
C *
C sources: method of Anderson/Bjoerck, see at [ANDE73]. *
C *
C*****************************************************************
C *
C author : Gisela Engeln-Muellges *
C date : 08.26.1985 *
C source : FORTRAN 77 *
C *
C*****************************************************************
C
IMPLICIT DOUBLE PRECISION (A-H,O-Z)
IF(IHELP1 .EQ. 0) THEN
CALL SUB2(F1,F2,F3)
END IF
RETURN
END
C
C
SUBROUTINE ANDBJK(IHELP1,IHELP2,F1,F2,F3)
C
C*****************************************************************
C *
C This SUBROUTINE uses a combination of the Anderson/Bjoerck *
C and King methods suggested by King to calculate a new func- *
C tional value F1 for use in the governing program ZERORF. *
C *
C *
C INPUT PARAMETERS: *
C ================= *
C IHELP1 : ) auxiliary variables set by the governing *
C IHELP2 : ) program ZERORF. *
C F1,F2,F3 : functional values FCT(X1), FCT(X2), FCT(X3). *
C *
C *
C OUTPUT PARAMETER: *
C ================= *
C F1 : new functional value at X1. *
C *
C----------------------------------------------------------------*
C *
C subroutines required: SUB2 *
C *
C *
C sources: 1. method of Anderson/Bjoerck, see at [ANDE73]. *
C 2. method of King, see at [KING73]. *
C *
C*****************************************************************
C *
C author : Gisela Engeln-Muellges *
C date : 08.26.1985 *
C source : FORTRAN 77 *
C *
C*****************************************************************
C
IMPLICIT DOUBLE PRECISION (A-H,O-Z)
IF(IHELP2 .EQ. 1) THEN
IHELP2=0
CALL SUB2(F1,F2,F3)
ELSE IF(IHELP1 .EQ. 0) THEN
CALL SUB2(F1,F2,F3)
ELSE
IHELP2=1
END IF
RETURN
END
C
C
SUBROUTINE EXCHG(X,Y,FX,FY)
C
C*****************************************************************
C *
C This SUBROUTINE exchanges X and Y, and FX and FY. *
C *
C*****************************************************************
C
IMPLICIT DOUBLE PRECISION (A-H,O-Z)
DUMMY=X
X=Y
Y=DUMMY
DUMMY=FX
FX=FY
FY=DUMMY
RETURN
END
C
C
SUBROUTINE SUB1(F1,F2,F3)
C
C*****************************************************************
C *
C Auxiliary routine for subroutines PEG and PEGK. *
C *
C*****************************************************************
C
IMPLICIT DOUBLE PRECISION (A-H,O-Z)
G=F3/(F2+F3)
F1=G*F1
RETURN
END
C
C
SUBROUTINE SUB2(F1,F2,F3)
C
C*****************************************************************
C *
C Auxiliary routine for subroutines ANDBJ and ANDBJK. *
C *
C*****************************************************************
C
IMPLICIT DOUBLE PRECISION (A-H,O-Z)
G=1.0D0-F2/F3
IF(G .LE. 0.0D0) THEN
G=0.5D0
END IF
F1=G*F1
RETURN
END