End of file
Contents
Index

F 2 Nonlinear Equations in One Variable

F 2.5.1 The Newton Method for Simple Roots


      SUBROUTINE NEWPSZ(FCT,FDER,X0,MAXIT,ABSERR,RELERR,X,F,
     +                  NUMIT,IERR)
C
C*****************************************************************
C                                                                *
C  This SUBROUTINE determines an approximate value X for a zero  *
C  of the function FCT with known derivative FDER by applying    *
C  Newton's method for simple zeros.                             *
C  The iteration function is:                                    *
C                 PHI(X):=X-FCT(X)/FDER(X).                      *
C  For a simple zero the order of convergence is P=2 with        *
C  efficiency E=1.414...                                         *
C  If FCT is an algebraic polynomial the                         *
C  SUBROUTINE NEWPOL should be applied instead.                  *
C  For multiple zeros the modified Newton method                 *
C  (SUBROUTINE NEWMOD) is recommended.                           *
C  Although the order of                                         *
C  convergence is slightly lower for methods that do not use     *
C  derivatives such as SUBROUTINE ZERORF, PEGASU and others,     *
C  they are preferable to Newton's method. Their efficiency is   *
C  generally better since they only require one functional       *
C  evaluation per iteration step.                                *
C                                                                *
C                                                                *
C  INPUT PARAMETERS:                                             *
C  =================                                             *
C  FCT      : function for which a zero is to be found.          *
C             It has the form                                    *
C                 DOUBLE PRECISION FUNCTION FCT(X)               *
C             and has to be declared as EXTERNAL within the      *
C             calling program (or as INTRINSIC if a FORTRAN      *
C             standard function is used).                        *
C  FDER     : 1st derivative of the function FCT.                *
C             It is declared as                                  *
C                 DOUBLE PRECISION FUNCTION FDER(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  X0       : starting value for the iteration.                  *
C  MAXIT    : maximum number of iteration steps (MAXIT >= 1).    *
C  ABSERR   : ) error parameters. Both have be set to >= 0.0     *
C  RELERR   : ) their sum has to be > 0.0. The following mixed   *
C               test is used:                                    *
C                   ABS(X1-X2) <= ABS(X2)*RELERR+ABSERR.         *
C               Thus if RELERR=0.0, we test for the absolute     *
C               error; if ABSERR=0.0 is chosed, then the         *
C               relative error is tested for.                    *
C               The values entered for ABSERR and RELERR are     *
C               accepted unchanged by the program if they both   *
C               exceed four times the machine constant, or in    *
C               case one of them equals zero, the other exceeds  *
C               four times the machine constant.                 *
C               If this is not the case for both or one of the   *
C               values, they are set to that value internally.   *
C                                                                *
C                                                                *
C  OUTPUT PARAMETERS:                                            *
C  ==================                                            *
C  ABSERR   : ) error parameters actually used.                  *
C  RELERR   : )                                                  *
C  X        : last approximate value for the zero of FCT         *
C  F        : function value of FCT at the last approximate      *
C             value X.                                           *
C  NUMIT    : number of iteration steps performed. The number    *
C             of functional evaluations is two times NUMIT.      *
C  IERR     : = 0, input parameter are not as specified.         *
C             = 1, zero found; break-off criterion for the       *
C                  difference between the last two approximations*
C                  has been met.                                 *
C             = 2, zero X found.                                 *
C                      ABS(FCT(X)) < 4 * machine constant.       *
C             = 3, starting value X0 is a zero of FCT:           *
C                      FCT(X0)=0.0 (machine zero).               *
C             = 4, zero not found. The maximum number of         *
C                  iterations was reached without meeting        *
C                  the break-off criterion. Possibly the         *
C                  error parameters were chosen too small or     *
C                  the starting value X0 was not close enough to *
C                  a zero position of FCT.                       *
C                                                                *
C----------------------------------------------------------------*
C                                                                *
C  subroutines required: MACHPD                                  *
C                                                                *
C*****************************************************************
C                                                                *
C  author     : Gisela Engeln-Muellges                           *
C  date       : 09.23.1985                                       *
C  source     : FORTRAN 77                                       *
C                                                                *
C*****************************************************************
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
C  initializing the iteration step counter NUMIT.
C
      NUMIT=0
C
C  testing the validity of the input parameters ABSERR, RELERR and MAXIT.
C
      IF(ABSERR .LT. 0.0D0 .OR. RELERR .LT. 0.0D0 .OR. ABSERR+RELERR
     +   .LE. 0.0D0 .OR. MAXIT .LT. 1) THEN
         IERR=0
         RETURN
      END IF
C
C  test whether X0 already is a zero of FCT:
C        FCT(X0)=0.0 (machine zero).
C
      X=X0
      F=FCT(X)
      IF(F .EQ. 0.0D0) THEN
         IERR=3
         RETURN
      END IF
C
C  computation 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  in case ABSERR and/or RELERR were chosen too small, they are now set
C  to four times the machine constant.
C
      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  iteration loop for calculating a new approximate value X for
C  the desired zero. First it we check whether F=FCT(X) is less
C  than four times the machine constant.
C  If this is true the program is ended by setting IERR=2.
C
   20 IF(DABS(F) .LT. DUMMY) THEN
         IERR=2
         RETURN
      ELSE
C
C  calculation of the 1st derivative FD of the function FCT at X;
C  if this turns out to be zero, the derivative will be set to 1.E-6
C  in order to prevent division by zero.
C
         FD=FDER(X)
         IF(DABS(FD) .LT. DUMMY) THEN
            FD=DSIGN(1.0D-6,FD)
         END IF
C
C  increase the iteration step counter by 1 and calculate
C  a new approximation for the zero and its corresponding
C  functional value.
C
         NUMIT=NUMIT+1
         DIFF=F/FD
         X=X-DIFF
         F=FCT(X)
C
C  test whether the break-off criterion is met for the last two
C  approximations or whether the maximum number MAXIT of
C  iterations has been reached.
C
         IF(DABS(DIFF) .LE. DABS(X)*RELERR+ABSERR) THEN
            IERR=1
            RETURN
         ELSE IF(NUMIT .GE. MAXIT) THEN
            IERR=4
            RETURN
         END IF
      END IF
      GOTO 20
      END


Begin of file
Contents
Index