Previous page Next page Navigation bar

Programs

Mathematics Programs

Newton’s Method

Summary

Programs:

NEWTON, 1NEWTON

Version:

3.0, 5 May 2002

Description:

This program finds a real zero (root) of a real-valued function through applying Newton’s root-finding method. One program is callable from any program; the other is a main program which may be used by a calculator user.

Compatibility:

Is compatible CFX-9850G

Compatible with CFX-9850G

Is compatible FX-7400G

Compatible with FX-7400G

Other programs
required:

VRPRE, VRSAVFJ, VRRESFJ

Detailed Description

Like the bisection method, Newton’s method is a way of finding zeroes of a function. Newton’s method approximates a function f in a neighborhood near a point xn by a tangent line to the function graph. The point where the tangent line intersects the X axis — where the tangent line has a zero — is used as the next approximation xn+1. Under many circumstances, the sequence {xn} will converge to a zero of the function f. The approximation process ends when a true zero is found, when the function f is flat at some xn (that is, f'(xn) = 0) and the tangent line does not intersect the X axis, or when the step size |xn+1 - xn| becomes so small that xn+1 is not different from xn due to round off error.

Newton’s method, however, can fail to converge for a number of reasons. This can occur when f(xn+1) is not less in absolute value than f(xn). This can be repaired by making the next estimate a point between xn and the computed xn+1. Since the tangent line points “down” to xn+1, the function f decreases in that direction, so there is a point between xn and xn+1 where the function f takes on a value smaller in absolute value than at xn. The program 1NEWTON goes through this modified Newton’s method process for a function f programmed in F0. The program NEWTON is a user interface wrapper around 1NEWTON so the initial estimate can be entered at the keyboard.

Other Programs

Most program collections have a Newton’s method zero finder. There are three advantages to the Newton’s method presented here. Firstly, the modification to Newton’s method increases the likelihood of convergence. Secondly, the splitting of Newton’s method into a user interface and a zero finding engine lets a program easily use Newton’s method on a function. Finally, the Newton’s method program calls user-written subroutines F0 and F1 for the function value and its derivative. This frees the function for which a zero is to be found from the limitations on function memory, and lets the user decide whether an analytical derivative or numerical approximation is to be used.

Usage

Load the programs NEWTON, 1NEWTON, VRPRE, VRSAVFJ, and VRRESFJ. Program the function f in program F0, and program the function derivative f' in program F1. These programs must take their argument from variable A and leave their result in variable B. Run the program NEWTON.

NEWTON displays the prompt:

Start?

Enter a value close to a zero of the function f. NEWTON will go through the modified Newton’s method described above. If it reaches a point where the derivative is zero, it will report it with the message

0 deriv

NEWTON cannot continue in that case. Otherwise, when NEWTON finds a zero of f, it will report it with the label

Zero at

Program Source

The programs are available as a text file with .CAT contents, or may be entered as shown below. A semicolon (“;”) marks the beginning of a comment, and is not to be entered into the calculator. Remember that these programs are copyrighted; see the copyright issues page for limitations on redistribution.

Program NEWTON (66 bytes):

; Program NEWTON
;
; Description:
;   Calls 1NEWTON to find a zero of a differentiable function
;
; Variables:
;   A-E are used for subroutine communication
;
; Calling sequence:
;   None; main program
;
; Implicit inputs:
;   None.
;
; Implicit outputs:
;   List 6: the variable save stack.
;   Z: the stack pointer for the variable save stack.
;
; Side effects:
;   None.
;
; Symbols used:
;   -> is assignment arrow
;   _ is display triangle
 
Prog "VRPRE"       ; Set up variable save stack
While 1            ; Infinite loop asking for starting point
"Start"?->A        ;   Get starting point into A
Prog "1NEWTON"     ;   Call 1NEWTON
"Zero at"          ;   Label the zero output
B_                 ;   Report the zero
WhileEnd           ; [End of infinite loop asking for starting point]

Program 1NEWTON (178 bytes):

; Program 1NEWTON
;
; Description:
;   Provides a modified Newton's method to find a zero of a
;   differentiable function.
;
;   Newton's method is x1 = x0 - f(x0)/f'(x0). The modification to
;   Newton's method ensures that f(x1) is less in magnitude than f(x0)
;   and, if not, moves x1 closer to x0.
;
;   The function f must be programmed into the program F0. The
;   function f' must be programmed into the program F1. Both of these
;   programs must accept their argument in variable A and return their
;   value in variable B.
;
; Variables:
;   A is the point at which to start the iteration [input]
;   B is the zero found [output]
;   C-E are unused
;   F is the current value of x0
;   G is f at the current value of x0
;   H is f' at the current value of x0
;   I is the trial x1
;   J is the saved value of A
;
; Calling sequence:
;   {initial point}->A
;   Prog "1NEWTON"
;   B->{zero of function}
;
; Implicit inputs:
;   List 6: the variable save stack.
;   Z: the stack pointer for the variable save stack.
;
; Implicit outputs:
;   List 6: the variable save stack.
;   Z: the stack pointer for the variable save stack.
;
; Side effects:
;   Calls the programs F0 and F1.
;
; Symbols used:
;   -> is assignment arrow
;   => is conditional jump
;   / is division operator
 
Prog "VRSAVFJ"     ; Save variables F through J
A->F               ; Get starting point x0
A->J               ; Save initial contents of A
Prog "F0"          ; Get f(x0)
B->G               ; Put f(x0) into G
Lbl 0              ; Loop until approximation good enough
G=0=>Goto 4        ;   If we have a zero, we are done
F->A               ;   Get the current x0 value
Prog "F1"          ;   Get f'(x0)
B->H               ;   Put f'(x0) into H
H=0=>Goto 3        ;   If f is flat, exit abruptly
F-G/H->I           ;   Compute x1
Lbl 1              ;   Loop until x1 provides improvement
F=I=>Goto 4        ;     If x1=x0, we are done
I->A               ;     Get x1
Prog "F0"          ;     Get f(x1)
Abs B<Abs G=>Goto 2;     If x1 provides improvement, accept it
(F+I)/2->I         ;     Pick half way between x0 and x1
Goto 1             ;   [End of loop until x1 provides improvement]
Lbl 2              ;   Accept x1
I->F               ;   Replace x0 by x1
B->G               ;   Replace f(x0) by f(x1)
Goto 0             ; [End of loop until approximation good enough]
Lbl 3              ; Zero derivative
"0 deriv"          ; Issue an error message
Stop               ; And just stop
Lbl 4              ; Zero found
J->A               ; Restore original A value
I->B               ; Put found zero in B
Prog "VRRESFJ"     ; Restore registers

Sample program F0 (25 bytes):

; Program F0
;
; Description:
;   ***SAMPLE***
;   Function encoding a function for which a zero is to be found.  The
;   function is ln(x) - 1, which has a zero at e, Euler's number.  A
;   reasonable starting point is between 1 and 5.
;
; Variables:
;   A is the x value at which the function is to be evaluated [input]
;   B is the function value for the x value given in A [output]
;
; Calling sequence:
;   {x value}->A
;   Prog "F0"
;   B->{function value}
;
; Implicit inputs:
;   List 6: the variable save stack.
;   Z: the stack pointer for the variable save stack.
;   [These are available for functions that need them.]
;
; Implicit outputs:
;   List 6: the variable save stack.
;   Z: the stack pointer for the variable save stack.
;   [These are available for functions that need them.]
;
; Side effects:
;   None.
;
; Symbols used:
;   -> is assignment arrow
 
(ln A)-1->B

Sample program F1 (21 bytes):

; Program F1
;
; Description:
;   ***SAMPLE***
;   Program encoding the derivative of a function for which a zero is
;   to be found.  The function is ln(x) - 1, which has a zero at e,
;   Euler's number.  The derivative is 1/x.
;
; Variables:
;   A is the x value at which the derivative is to be evaluated [input]
;   B is the derivative value for the x value given in A [output]
;
; Calling sequence:
;   {x value}->A
;   Prog "F1"
;   B->{derivative value}
;
; Implicit inputs:
;   List 6: the variable save stack.
;   Z: the stack pointer for the variable save stack.
;   [These are available for functions that need them.]
;
; Implicit outputs:
;   List 6: the variable save stack.
;   Z: the stack pointer for the variable save stack.
;   [These are available for functions that need them.]
;
; Side effects:
;   None.
;
; Symbols used:
;   x^-1 is the reciprocal operator
;   -> is assignment arrow
 
Ax^-1->B

[ Previous page | Top of page | Next page ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.

Brian’s Casio Calculator Corner

Home

Programs

Index

Linkage Conventions

Mathematics

Index

Factorization

Bisection

Newton’s Method

Complex Zeroes

Best Fraction Approximation

Pseudorandom Numbers

Romberg Integration

First Degree ODE

Rounding

Permutations

Finance

Physics

Utility

Tutorial

Puzzles

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data