(41C)Reducing the Number of Slope Evaluations for Newton's Method

[Namir]

I introduce an HP-41C program that solves the roots of nonlinear functions using Newton’s method. What is different about this program is that it reduces the number of function calls used in calculating the slope. The HP-41C program calculates the slope using the forward divided difference method:

Code:


f’(x) = (f(x+h) – f(x))/h                                        (1)

Where h = 0.001*(1 + |x|). Thus, calculating the slope requires two calls to the nonlinear function f(x)=0. If you re-implement the code to use a separate function to calculate the slope, that function should also count as a function call. So, either way a regular Newton's method iteration requires two function calls.

The program Root1 reduces the number of function calls, by using a counter k and maximum counter max, and the following steps:

• The first two iterations refine the guess for the root x by using equation (1) which requires two function calls per iteration. The values for k and max are initially set to zero and then to 1 after the first iteration.
• During the third iteration k has the value of 1 and max has the value of 2. Since max-k is 1, the root-seeking iteration skips the step to explicitly calculate a new slope and uses the previous value of the slope. This scheme saves one call to function f(x).
• During the fourth iteration k has the value of 2 and max has the value of 2. Since max-k is 0, the root-seeking iteration calculates an updated slope value by calling f(x) twice. The variables max is set to 3 and the variable k is set to 1.
• The next two iterations will skip updating the slope and use the current slope value.
• The seventh iteration will have max-k = 0 and evaluates a new slope value.
• The remaining iterations continue with incrementing max by 1 when k equals max, and resetting k to 1. Otherwise, the iterations simply increment k by 1 until k equals max.
• The iterations stop when the absolute value for the refined guess for the root is les than the root tolerance value.

Here is the HP-41C code with the test function f(x)=exp(x) – 3*x^2:

Memory Map
--------------

Code:

R00 = toler
R01 = x
R02 = h
R03 = f
R04 = fh
R05 = deriv
R06 = count
R07 = k
R08 = max

Listing
-------

Code:


01 LBL "ROOT1"
02 "X?"
03 PROMPT
04 STO 01
05 "TOLER?"
06 PROMPT
07 STO 00
08 0
09 STO 06
10 STO 07
11 STO 08
12 LBL 00
13 RCL 01
14 XEQ "FX"
15 STO 03
16 1
17 STO+ 06
18 RCL 07
19 RCL 08
20 X>Y?
21 GTO 01
22 RCL 01
23 ABS
24 1
25 STO 07
26 STO+ 08
27 STO+ 06
28 +
29 1.00E-03
30 *
31 STO 02
32 RCL 01
33 +
34 XEQ "FX"
35 STO 04
36 RCL 03
37 -
38 RCL 02
39 /
40 STO 05
41 GTO 02
42 LBL 01
43 1
44 STO+ 07
45 LBL 02
46 RCL 03
47 RCL 05
48 /
49 STO- 01
50 ABS
51 RCL 00
52 X<Y?
53 GTO 00
54 RCL 06
55 RCL 01
56 RTN
57 LBL "FX"
58 EXP
59 LASTX
60 X^2
61 3
62 *
63 -
64 RTN

The program Root1 prompts you for the values x and toler. The parameter x is the initial guess for the root. The parameter toler is the root tolerance value. The program returns count, the number of function calls, and x, the refined root value.

The program Root1 works better as the initial guess for the root is close to the actual root value.

Here are two sample calls to program Root1:

For x = 3 and toler 1E-8 we get 20 and 3.733079029 in the Y and X registers, respectively.

For x = 4 and toler 1E-8 we get 9 and 3.733079029 in the Y and X registers, respectively.