Looking for TVM contributions

[Albert Chan]

(06-16-2024 05:18 PM)robve Wrote:  When solving roots we cannot expect nor should we visualize function \( f(x) \) to cut a perfect skinny line through the x-axis at which there is a single point \( x \) that is the root \( f(x)=0 \) to find. No! Instead, it is a fat line with some thickness \( \varepsilon \). This thickness depends on the inaccuracy of evaluating \( y=f(x) \). This fat line cuts the x-axis with an interval \( [x-\varepsilon,x+\varepsilon] \) on which all \( x \) values return \( f(x)=0 \). If \( f(x) \) becomes shallow close to the root, then the fat line may project an even wider interval (any deviation in the height \( y \) moves \( x \) faster along the axis). Root finders like Newton and Secant jump to the next point \( x \) closer to the root based on the behavior (slope) of the function and its derivative at the previous point \( x \). But we only see a fat line at the previous point \( x \), not a skinny line. Getting accurate values of \( f(x) \) and \( f'(x) \) to stay on course to converge to the root is problematic with a fat line. What is the value of \( f(x) \) exactly? And what is the slope \( f'(x) \) at this point? Since we cannot get highly accurate answers, we may end up jumping away from the root and far enough to cause an overcorrection in the next step to jump to the other side of the root and so on, possibly ad infinitum.

Nicely put. BTW, fat line may not be smooth, due to rounding errors.

We should stop Newton's iteration when f(x) cannot be trusted.
This is why Plus42 does final half-correction, to reduce error radius.
The idea is: f is likely no good, but perhaps we can trust its sign?

The best we could hope for is solved x actually get f(x) = 0
Since f=npmt, should we use npmt(final i) as accuracy metric?
I would think round-trip for PMT is what we wanted, not FV.

My setup tried to make line skinny, with time-symmetry.

Code:

local s = EFF(i,n)
local k = (pv+fv)/s
local d = k*(1-n*(s+1)/(s+s/i)) + pv
f = (k + pv)*i + pmt
eps = -f / d

Note the + pv in f and d

If pv is big relatively to fv, we can apply time-symmetry --> n, pv, fv = -n, -fv, -pv
For real life financial situations, many times pv or fv is 0, thus make the line very skinny!

lua> n,i,pv,pmt,fv = 48,nil,19198,-450,0 -- test sample #12

For reference, Plus42 to get I%YR: 4.918000645880570070062687539208835e-1

find_rate() has time-symmetry flip disabled (tvm() does the flipping)

lua> find_rate(n,i,pv,pmt,fv, true)
0.023439941660589644    220.49758413166887
0.006730726899179227    19.372332869813135
0.004940893361022922    0.24155367517261084
0.004918004408642906    3.96964566675706e-05
0.004918000645880669    1.0231815394945443e-12
0.004918000645880572    -5.684341886080802e-14
0.004918000645880574

By design, f(i) would not overshoot, if calculated accurately.
The fact that it does, suggested f(i) is not very sharp.

For this example, even sign of final f is wrong!
Final half-correction make it worse, errors = 5 ULP.
But at least it is better than full correction, error = 8 ULP

If we apply Secant's method from last 2 points, error = 8 ULP too.
Based on this example alone, Secant's method is not better.
Secant's slope is no where near its true value.

secant slope  = 11117.714285714286 -- from last 2 points, almost touching
newton slope = 10549.817399409634 -- from lua code last d value
correct slope  = 10549.817399409620 -- mpmath with mp.dps=34

lua> find_rate(-n,i,-fv,pmt,-pv, true)
0.023439941660589644    220.49758413166887
0.006730726899179217    19.37233286981302
0.004940893361022924    0.24155367517272452
0.004918004408642897    3.969645661072718e-05
0.004918000645880665    1.0231815394945443e-12
0.004918000645880568    0
0.004918000645880568

With time-symmetry, we have PV=0, which make f(i) sharper. No overshoot, errors = -2 ULP

Comment 6/17/24:
After some thought, this does not show time-symmetry version is better.
The few ULP's gain in accuracy may be simply lucky

Overshoot can happen by accumulated rounding errors.
Even sharp f may overshoot, even though technically it shouldn't.