Small Solver Program

[Albert Chan]

(02-16-2019 03:58 AM)Thomas Klemm Wrote:  

(02-15-2019 09:16 PM)Albert Chan Wrote:  Amazingly, my rate formula is same as Aitken extrapolation formula !

That's not really a surprise, is it?
It's essentially the same idea: geometric series

\(1\,+\,r\,+\,r^{2}\,+\,r^{3}\,+\,\cdots \;=\;{\frac {1}{1-r}}\)

Except for r=1, rate formula work even if iterations diverges (|r| > 1)

Example, solve x = f(x) = 5 - x^3, guess = 1.5

Above setup, iterations diverges: 1.5 → 1.625 → 0.708984375 → 4.643622734 ...

First 3 numbers, r = (0.708984375 - 1.625) / (1.624 - 1.5) ≈ -7.328

Iterate with x = g(x) = p(5 - x^3) + (1-p)x, with p = 1/(1-r) ≈ 12.0% :

1.5
1.515000000
1.515928095
1.515977481
1.515980083
1.515980220
1.515980227
1.515980228 ← converged

We can speed up the convergence by using r = f'(guess) = -3 * 1.5^2 = -6.75
Iterate with same g(x), but p = 1/(1-r) ≈ 12.9% :

1.5
1.516125000
1.515977551
1.515980277
1.515980227
1.515980228 ← converged