Variant of the Secant Method

[Albert Chan]

Let's compare inverse-interpolation vs improved-secant (code from previous post)

Code:

function test(f, x0, x1, n)   -- n = 1 (linear) to 3 (cubic)
    local y0, y1 = f(x0), f(x1)
    local t0 = {y0,x0, y1,x1} -- inverse interpolate
    local t1 = {x0,y0, x1,y1} -- improved secant
    n = (n or 3)*2 + 1
    for i = 4,18,2 do         -- i = table length
        x0 = interp(unpack(t0, math.max(1,i-n)))
        x1 = secant(unpack(t1, math.max(1,i-n)))
        t0[i+1], t0[i+2] = f(x0), x0
        t1[i+1], t1[i+2] = x1, f(x1)
        print(i/2, x0, x1)
    end
end

lua> function f(x) return x^3 - 8 end

lua> test(f, 5, 4, 2) -- https://arxiv.org/pdf/2012.04248.pdf, Table 2
2      3.081967213114754        3.081967213114754
3      2.3945608933295457      2.2862188297178117
4      2.0980163342039635      2.010344209437878
5      2.0088865345029276      1.99979593345267
6      2.0001129292461193      2.0000000722313933
7      2.0000000388749792      2.000000000000015
8      2.0000000000000164      2
9      2                                    2

Last column is improved secant, fitting data up to quadratic (slope by linear interpolation)
Middle column is inverse-interpolation for x, at y = 0, also fitting up to quadratic.

Improved secant uses the last point as the "base", then does correction.
Inverse-interpolation is not as good, probably due to putting equal weight to its points.

Let's try again, but with up to cubic fit.

lua> test(f, 5, 4, 3)
2      3.081967213114754        3.081967213114754
3      2.3945608933295457      2.2862188297178117
4      2.082744738020821        2.034337291023909
5      2.0058425366743506      2.000576313421517
6      2.0000383915262443      2.000000166004798
7      2.0000000023200664      2.0000000000000138
8      1.9999999999999998      2
9      2                                    2

Based on above, anything more than a cubic fit probably not worth the trouble.
For example, lets see how Newton's method does (actual slope)

lua> function df(x) return 3*x*x end
lua> x = 4
lua> for i=2, 9 do x = x - f(x)/df(x); print(i, x) end
2      2.833333333333333
3      2.221068819684737
4      2.0212735368091126
5      2.0002231146078984
6      2.0000000248863623
7      2.0000000000000004
8      2
9      2