TVM solve for interest rate, revisited

[Albert Chan]

(06-10-2022 08:25 PM)Albert Chan Wrote:  lua code to automatic rate search, using Newton's 1-sided convergence property.

On 2nd thought, I re-post code here, in case Plus42 repository turned private.

Quote:Newton's method 1-sided convergence is proven. I used it here.

Code:

function edge_i(n,pv,pmt,fv)
    local a, b = pmt/fv, -pmt/pv
    if abs(a)>abs(b) and b>-1 or b~=b then a,b = b,a end
    return a, b  -- a = small edge or NaN
end

function iter_i(n, pv, pmt, fv, i)
    pmt, fv = pmt or -1, fv or 0
    i = i or edge_i(n, pv, pmt, fv)
    return function()
        if i==0 then
            local a, b = (pv+fv)/n, pv-fv
            local f, fp = (a+pmt), (a+b)*0.5
            i = -f/fp
            return i, i, f
        end
        local x = i/expm1(n*log1p(i))
        local k, y = (pv+fv)*x, n*x-1
        local f = k + pv*i + pmt
        local num, den = y+(n-1)*i, i+i*i
        x = f*den / (k*num-pv*den)
        i = i + x   -- Newton's method
        return i, x, f
    end
end

function find_rate(n,pv,pmt,fv,BEGIN,i0)
    if BEGIN then pv, fv = pv+pmt, fv-pmt end
    local g = iter_i(n,pv,pmt,fv,i0)
    if i0 then g() end  -- throw away iteration
    local i,eps,f = g() -- 1-sided convergence
    repeat
        local f0 = f
        i,eps,f = g()
        if f*f0 <= 0 then return i,eps end
    until not (abs(f0) > abs(f))
    return nil
end

Note: NaN edge moved up front, for rate search early termination.
All examples shown in this issue.

Code:

lua> find_rate(10,50,-30,80)
-0.3689336987417774     0
lua> find_rate(10,50,-30,100)
-0.284435998880256      -4.284106772739964e-017
lua> find_rate(10,50,-30,100,true) -- BEGIN mode
-0.20399537076838428    0
lua> find_rate(36,-10000,500,-6000)
0.018066231336911785    1.454230867769741e-017
lua> find_rate(36,-10000,500,-9000)
nil

Update: find_rate() now allow user to enter rate guess.
This is rarely needed, unless we wanted solution (if any) from the other edge.
To maintain 1-sided convergence, first possibly overshooted iteration throw away.

Example below used guesses between 2 roots.
Note: the safe guess is again start from the edge.
Newton's method may fail, if guess get too near where f'=0.

Code:

lua> find_rate(30,6500,-1000,50000,nil,0.09)
0.08960585626123246     0
lua> find_rate(30,6500,-1000,50000,nil,0.11)
0.11100328640549173     -0