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

[Namir]

I introduce an HP-42s 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-42s 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.

While the HP-42s has a built-in SOLVE command, I am using this calculator to work with named registers and illustrate the algorithm. They are easier to read than numerical register used in earlier HP calculators.

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-42s code with the test function f(x)=exp(x) – 3*x^2:

Code:

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