Threaded Mode | Linear Mode

robve · 06-14-2024, 10:11 PM

(06-14-2024 06:40 PM)Albert Chan Wrote:
(06-14-2024 03:23 PM)robve Wrote: I suspected that the slope would be close to zero for it to jump that far from the root.

NPV iterating to infinity is not a rounding issue ... go figure!

Right! Initial guesses matter. Can happen with any TVM calc. In the TVM code that I had before I halved I% from an initial guess I%=0.01 until |Y-W| (unscaled "slope" sort of) is larger than the I% rate itself, which prevented this effectively. But that is very ad-hoc.

(06-14-2024 06:40 PM)Albert Chan Wrote:
Quote:After some experimentation in C code with double precision and in SHARP BASIC, I am not sure if others noticed this as well, but I noticed that Newton suffers from instability when TVM rates converge to zero.

Secant's method have this issue too.

Agree. But for Newton running on this 10 BCD machine the longer f(i)/f'(i) expression seems more likely to introduce floating point inaccuracies than the simpler Secant. Whereas the IEEE754 double precision version I have is more well behaved. It's one possible explanation.

(06-14-2024 06:40 PM)Albert Chan Wrote: Both methods need accurate f(ε) calculation.
It is not noticed because solved rate is not small enough, not hitting f(ε) issue yet.
Also, with 2 very close points, f'(ε) estimated from secant slope is likely worse.

The Secant slope estimation is very simple and it is not the true slope f'(ε), so surely Secant will dance around the root as well. That's what we know. I'm just seeing that it converges more nicely than Newton for small rates ε for the example cases we have and the convergence test to use is reliable too. A more expansive set of test examples could tell if this is an artifact of these examples or if this is general.

Here is one example. With Newton when pushing on to get to y=0 it hovers for a moment:

Code:

n=480 pv=100000 pmt=-208.333 fv=0

 1/12  i%=             1e-05  y=  0.00501045666647   9.99992016789144771e-06

 2/11  i%= 7.98321085531e-11  y=   3.999917908e-08   7.98320053540206081e-11

 3/10  i%= 1.03199085624e-16  y= 2.84217094304e-14   4.22703454717260951e-17

 4/9  i%= 6.09287401526e-17  y= 2.84217094304e-14   7.48692358995212396e-17

 5/8  i%=-1.39404957469e-17  y=                 0                         0

i%=0%

With Secant this converges right away:

Code:

n=480 pv=100000 pmt=-208.333 fv=0

i%=1e-05    y=0.00501046

 3/12  i%= 3.99161666854e-11  y= 1.99996748051e-08   4.99996008383331496e-06

 4/12  i%= 1.35138613467e-16  y= 2.84217094304e-14   3.99160315468350466e-11

 5/12  i%= 7.84135180081e-17  y=                 0   5.67250954586066735e-17

i%=0%

Now, this is just an example, so don't take my word for it.

What I see is that convergence issues with the Newton version just happen more in 10 BCD precision when there is a loss of 4 to 5 digits. Also when to stop is tricky. Even in IEEE754 double precision, such as for these:

n=40 pv=900 pmt=1000 fv=-1000 BGN
n=360 pv=0 pmt=-1000 fv=1e+06
n=5 pv=-369494 pmt=17500 fv=540000
n=30 pv=-3200 pmt=-717.44 fv=60000
n=60 pv=243400 pmt=-1363.29 fv=-222976
n=6 pv=-32000 pmt=0 fv=28347
n=60 pv=8000 pmt=-150.97 fv=0

(06-14-2024 06:40 PM)Albert Chan Wrote: After I use {f(0), f'(0), f''(0)} to estimate {f(ε), f'(ε)}, this issue mostly goes away.

Makes sense, but this code isn't using {f(0), f'(0), f''(0)}. Also, won't that increase the cost to execute?

(06-14-2024 06:40 PM)Albert Chan Wrote: If you like to try Newton's method, use this instead (convergence test using f(i), not i)
Convergence depends on ULP, not quadratic convergence, thus will never get stuck.
https://www.hpmuseum.org/forum/thread-16...#pid187993

The rate gets stuck to about 1E-5 in one case and 1E-7 in another which is too far from the root at zero to be detected as a possible zero. One explanation is the use of 10 to 12 BCD (2 guard digits) with lower precision EXPM1 and LOG1P. So losing as much as 4 to 5 digits which is not great. A reliable convergence test should take this into account.

(06-14-2024 06:40 PM)Albert Chan Wrote: Per function calls, Secant's method may beat Newtons.
However, f(i) and f'(i) shared expensive expm1(log1p(i)*n) factor.
My guess is f'(i) cost very little extra ... say 1/4 of a function call.
Secant's method needs to calculate slope too ... it is not free.

But it's almost free, right? Just iterate \( i_{\rm new} := i-(i-i_{\rm old})f/(f-f_{\rm old}) \) with one evaluation of npmt to get f(i) to update i.

(06-14-2024 06:40 PM)Albert Chan Wrote: Besides getting f(i) and slope, there are bookkeeping cost too.
Per timing, with less loops, my guess is Newtons beat Secant.

This is true for Newton that runs fewer iterations. But this benefit diminishes rapidly with more precise initial rate guesses, especially when we only use single precision or only 10 digits then only a few iterations suffice in both cases.

- Rob