Programs: 
NEWTON, 1NEWTON 

Version: 
3.0, 5 May 2002 

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

Compatibility: 


Other programs 
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 x_{n} 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 x_{n+1}. Under many circumstances, the sequence {x_{n}} 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 x_{n} (that is, f'(x_{n}) = 0) and the tangent line does not intersect the X axis, or when the step size x_{n+1}  x_{n} becomes so small that x_{n+1} is not different from x_{n} due to round off error.
Newton’s method, however, can fail to converge for a number of reasons. This can occur when f(x_{n+1}) is not less in absolute value than f(x_{n}). This can be repaired by making the next estimate a point between x_{n} and the computed x_{n+1}. Since the tangent line points “down” to x_{n+1}, the function f decreases in that direction, so there is a point between x_{n} and x_{n+1} where the function f takes on a value smaller in absolute value than at x_{n}. 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.
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 userwritten 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.
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
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: ; AE 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] ; CE 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 FG/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 ]
Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.