End of file
Contents
Index



F 2.5.3 Newton's Method for Multiple Zeros; a Modified Newton's Method


      SUBROUTINE NEWMOD(FCT,FDER,F2DER,X0,MAXIT,LUN,ABSERR,
     +                  RELERR,X,F,J,NUMIT,IERR)
C
C*****************************************************************
C                                                                *
C  This SUBROUTINE determines an approximation X for a J-fold    *
C  zero of the function FCT by applying the modified Newton      *
C  method for the starting value X0.                             *
C  The iteration function is :                                   *
C             PHI:=X-J(X)*FCT(X)/FDER(X), where                  *
C          J(X)=1./(1.-FCT(X)*F2DER(X)/FDER(X)**2).              *
C  The values J(X) converge towards the order J of the zero X.   *
C  The method converges quadratically. However, its efficiency   *
C  is only E=1.26, since each iteration step requires three      *
C  functional evaluations.                                       *
C                                                                *
C                                                                *
C  INPUT PARAMETERS:                                             *
C  =================                                             *
C  FCT      : function whose zero is to be determined.           *
C             It has the form                                    *
C                 DOUBLE PRECISION FUNCTION FCT(X)               *
C             and must be declared as EXTERNAL by the            *
C             calling program (or as INTRINSIC if a FORTRAN      *
C             standard function is used).                        *
C  FDER     : 1st derivative of the function FCT. It has the     *
C             form                                               *
C                 DOUBLE PRECISION FUNCTION FDER(X)              *
C             and has to be declared as EXTERNAL by the          *
C             calling program (or as INTRINSIC if a FORTRAN      *
C             standard function is used).                        *
C  F2DER    : 2nd derivative of the function FCT. It has the     *
C             form                                               *
C                 DOUBLE PRECISION FUNCTION F2DER(X)             *
C             and has to be declared as EXTERNAL in 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  LUN      : > 0, tape unit onto which the iteration values X   *
C             and their corresponding orders J(X) are stored.    *
C  ABSERR   : ) error bounds that both must be >= 0.0, while     *
C  RELERR   : ) their sum has to be > 0.0. The following mixed   *
C               test will be used inside the subroutine:         *
C                  ABS(X1-X2) <= ABS(X2)*RELERR+ABSERR.          *
C               Thus if RELERR was chosen as 0.0, this tests for *
C               the absolute error; if ABSERR=0.0 is chosen this *
C               tests for the relative error.                    *
C               The values chosen for ABSERR and RELERR are      *
C               used unaltered by the program if they both       *
C               exceed the machine constant by a factor of five, *
C               unless one of their values is zero, in which     *
C               case the other must exceed the machine constant  *
C               by a factor of five.                             *
C               If this is not the case, then both, or one of    *
C               the error bounds are set to five times the       *
C               machine constant 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                  *
C             approximate value X.                               *
C  J        : order of the zero X.                               *
C             (see remark below)                                 *
C  NUMIT    : number of iteration steps performed.               *
C  IERR     : = 0, input parameter are faulty                    *
C             = 1, zero found; break-off criterion for the       *
C                  difference of the last two approxiations      *
C                  has been met.                                 *
C             = 2, zero X found.                                 *
C                  ABS(FCT(X)) < 5 * machine constant.           *
C             = 3, starting value X0 already is a zero           *
C                  of FCT(X0)=0.0 (machine zero).                *
C             = 4, zero not found. The maximum number of         *
C                  iterations reached without meeting the        *
C                  break-off criterion.                          *
C                  The error bounds might have been chosen too   *
C                  small or the starting value X0 is not close   *
C                  enough to a zero of FCT.                      *
C                                                                *
C                                                                *
C                                                                *
C  NOTE  : The quotients FCT/FDER and FCT*F2DER/FDER**2 become   *
C          indeterminant in a neighborhood of the (multiple)     *
C          zero. Thus, even for small error bounds the zero can  *
C          only be determined with limited precision.            *
C          In some rare test cases the value for the order J of  *
C          the zero was computed incorrectly due to the inde-    *
C          terminate expression for J(X). Therefore the results  *
C          should always be inspected on TAPE unit # LUN and     *
C          interpreted according to [ENGE87], p.51.              *
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  test for 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 already a zero of FCT: FCT(X0)=0.0
C  (machine zero).
C
      X=X0
      F=FCT(X)
      IF(F .EQ. 0.0D0) THEN
         IERR=3
         RETURN
      END IF
C
C  compute the machine constant and, if necessary,
C  adjust the error bounds.
C
      FMACHP=1.0D0
   10 FMACHP=0.5D0*FMACHP
      IF(MACHPD(1.0D0+FMACHP) .EQ. 1) GOTO 10
      FMACHP=2.0D0*FMACHP
      DUMMY=5.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.
C
      WRITE(LUN,900)
   20 IF(DABS(F) .LT. DUMMY) THEN
         IERR=2
         WRITE(LUN,910)NUMIT,X
         WRITE(LUN,*)
         RETURN
      ELSE
         FD=FDER(X)
         F2D=F2DER(X)
         IF(DABS(FD) .LT. DUMMY) THEN
            FD=DSIGN(1.0D-6,FD)
         END IF
         XJ=1.0D0/(1.0D0-F*F2D/(FD*FD))
         WRITE(LUN,910)NUMIT,X,XJ
         DIFF=XJ*F/FD
         X=X-DIFF
         NUMIT=NUMIT+1
         F=FCT(X)
         J=INT(XJ+0.5D0)
C
C  test whether the break-off criterion is met.
C
         IF(DABS(DIFF) .LT. DABS(X)*RELERR+ABSERR) THEN
            IERR=1
            WRITE(LUN,910)NUMIT,X
            WRITE(LUN,*)
            RETURN
         ELSE IF(NUMIT .GE. MAXIT) THEN
            IERR=4
            WRITE(LUN,910)NUMIT,X
            WRITE(LUN,*)
            RETURN
         END IF
      END IF
      GOTO 20
  900 FORMAT(1X,'Results of the iteration:',/,1X,25('*'),//,3X,
     +       'I',1X,'I',9X,'X(I)',9X,'I',7X,'J(X(I))',/,1X,
     +       49('='),/,5X,'I',22X,'I')
  910 FORMAT(1X,I3,2(' I ',D20.14))
      END


Begin of file
Contents
Index