(12C) Newton's Method

[Dieter]

(03-24-2018 01:31 PM)Dieter Wrote:  Here is my attempt at a corrected version:
...
- store the tolerance in R2
- enter a guess, start with R/S

Gamo, in the Regula Falsi thread you said that using the Newton solver is a bit cumbersome as – in the original version you posted – both the tolerance and an initial guess have to be prestored. The latter can be fixed easily (cf. the version I posted above), but also the exit condition can be simplified so that no user interaction is required.

The above versions use a fixed tolerance that is prestored by the user. On the other hand my Regula Falsi program quits as soon at the last two approximation agree to display precision. Here is another option: the following Newton solver iterates until the relative difference between the last two approximations drops below 5 E–9. This should provide 8 correct digits, but since the Newton method converges quadratically, in most cases the result should be close to exact.

Here is the code:

Code:

01 STO 1
02 1
03 STO 0
04 RCL 1
05 GTO 47
06 RCL 0
07 x=0?
08 GTO 25
09 Rv
10 STO 4
11 x=0?
12 GTO 45
13 0
14 STO 0
15 RCL 1
16 x=0?
17 e^x
18 EEX
19 4
20 /
21 STO 3
22 RCL 1
23 +
24 GTO 47
25 Rv
26 RCL 4
27 -
28 RCL 3
29 /
30 RCL 4
31 x<>y
32 /
33 STO-1
34 RCL 3
35 /
36 2
37 EEX
38 5
39 +
40 LstX
41 -
42 x=0?
43 GTO 45
44 GTO 02
45 RCL 1
46 GTO 00
47 .       start f(x) here
   .
   .
nn GTO 06  end f(x) with this line

Try it with your example function 3^x – x^3 = 0.

Code:

g [GTO] 46
f [P/R]      46-43,33 00

47 3
48 x<>y
49 y^x
50 LstX
51 3
52 y^x
53 -
54 GTO 06

f [P/R]

Now try this with an initial guess of 2:

Code:

 2  [R/S]  =>  2,478052683

You can always add one more iteration by pressing [R/S] again.
In the above case the result remains the same, with 10 digit precision f(2,478052683) yields exactly 0.

Now start with a guess of 2,5 which is even closer to the solution:

Code:

2,5 [R/S]  =>  2,478052686

The result differs in the last digit.
Now press [R/S] again and see what you get:

Code:

    [R/S]  =>  2,478052680
    [R/S]  =>  2,478052686
    [R/S]  =>  2,478052680
    [R/S]  =>  2,478052686
     ...

See? The iteration oscillates between 2,478052680 and ...86. That's why it is not a good idea to continue until the last two approximations match exactly (which would have caused an infinite loop here). The method in the above program stops if they agree in at least 8 digits, which usually means that it will not get more accurate anyway. Nevertheless you can always press [R/S] again and see if the result improves.

This way an infinite loops is avoided (well, at least in most cases). Try the function with a guess of 6 and you see that it would otherwise oscillate endlessly between 3,000000002 and 2,999999998.

In detail: line 34-35 divides the last correction term by h, and since h = x / 1E+4 this yields the current relative error times 1E+4. Dividing by h instead of x automatically handles the x=0 case for which h is set to 1E–4. Then 2E+5 is added and subtracted again, which shifts a sufficiently small error beyond the 10th digit so that the result is zero if the error is small enough. Selecting a constant with more or less digits (2E+6 or 2E+4 etc.) changes the error threshold, but I think 2E+5 is just right for a 10-digit calculator while h = x / 1E+4.

Dieter