The Newton-Raphson Algorithm for Finding the Root of One Non-Linear Equation1
Given: , , initial approximation to root = , tolerance = , “small number” = , maximum number of iterations = MAXITER
Set:
Repeat (not exceeding MAXITER)
Set:
If, then
Note: ‘flat spot’
Else
Set:
If, then
Note: ‘solved’
Until ‘solved’ or ‘flat spot’
(or limit on number of iterations reached)
If ‘solved’, then
Record: root, residual, number of iterations used
If ‘limit’, then
Record: last approximation to root
If ‘flat spot’, then
Record: last approximation to root
A graph illustrating the method in a simple case is shown on the next page.
An animated illustration of the method may be found at:
An illustration of the Newton-Raphson iterative method:2
A Program to Implement Newton’s Method to Find a Root of a Non-Linear Function
The following program uses the Newton-Raphson method to find the root of a non-linear function . The inputs to the program are:
a) An external function, which is f(x); b) An external function, which is f’(x), c) An initial estimated value of the root, obtained possibly through use of another method such as the bisection method, d) The maximum number of iterations to be performed, in case convergence is not achieved, and e) A tolerance value, a small number used to indicate convergence.
The outputs are one or more of the following:
a) The final estimate of the root, b) An indicator that the maximum number of iterations have been reached, c) An indicator that the function has been found to be flat in a neighborhood of the root, d) The count of the number of iterations performed, e) The residual value at the estimated root, and/or f) The specified tolerance value used to indicate convergence.
PROGRAM NEWTON
INTEGER COUNT, FLAT, ITRATE, LIMIT, MAXITER, N00FIT, SOLVED, STATUS
REAL DX, F, FDASH, FX, FDX, LASTX, NEWX, OLDX, X0, RESID, ROOT, TINY, TOL
PARAMETER (TINY=1.E-10)
PARAMETER (ITRATE = -1, SOLVED = 0, LIMIT = 1, FLAT = 2)
PRINT*, 'Input the initial estimated root.'
READ*, X0
PRINT*, 'Input the maximum number of allowable iterations.'
READ*, MAXITER
PRINT*, 'Input the tolerance.'
READ*, TOL
NEWX = X0
STATUS = ITRATE
DO 10 COUNT = 1, MAXITER
FDX = FDASH(NEWX)
IF (ABS(FDX) .LE. TINY) THEN
STATUS = FLAT
PRINT*, 'Function is flat in a neighborhood of the root.'
GO TO 12
ELSE
OLDX = NEWX
FX = F(OLDX)
DX = -FX/FDX
NEWX = OLDX + DX
IF (ABS(DX) .LE. ABS(OLDX)*TOL) STATUS = SOLVED
END IF
IF (STATUS .NE. ITRATE) GO TO 11
10 CONTINUE
STATUS = LIMIT
PRINT*, 'Convergence was not achieved in the maximum allowed iterations.'
11 IF (STATUS .EQ. SOLVED) THEN
N00FIT = COUNT
ROOT = NEWX
RESID = F(ROOT)
PRINT*, 'The number of iterations needed was: ', N00FIT, '.'
PRINT*, 'The root (approximate) is: ', ROOT, '.'
PRINT*, 'The residual value at the root is: ', RESID, '.'
PRINT*, 'The tolerance value used for convergence was: ', TOL, '.'
END IF
12 IF (STATUS .EQ. LIMIT .OR. STATUS .EQ. FLAT) THEN
LASTX = NEWX
PRINT*, 'The final approximation to the root was: ', LASTX, '.'
END IF
END
REAL FUNCTION F(Y)
F = Y - EXP(1/Y)
RETURN
END
REAL FUNCTION FDASH(Y)
FDASH = 1 + (EXP(1/Y)/(Y**2))
RETURN
END
1Numerical Methods with FORTRAN 77: A Practical Introduction, by L. V. Atkinson, P. J. Harley, and J. D. Hudson; Addison-Wesley Publishing Co., Wokingham, England, UK. 1989.
2