Small Solver Program

[Albert Chan]

(11-03-2019 03:14 PM)Albert Chan Wrote:  Except for r=1, rate formula work even if iterations diverges (|r| > 1)

Proof:

Assumed rate r = Δx_i+1 / Δx_i = constant, we extrapolate for the converged value.

if |r| < 1: x_∞ = x₀ + (x₁ - x₀) + (x₂ - x₁) + ... = x₀ (1 + r + r² + ...) = x₀/(1-r)

if |r| > 1: we can visualize it as iterate back-in-time, with rate of 1/r

x₀ - x_-∞ = (x₀ - x_-1) + (x_-1 - x_-2) + (x_-2 - x_-3) + ... = x₀ (1 + 1/r + 1/r² + ...)

x_-∞ = x₀ (1 - 1/(1-1/r)) = x₀/(1-r)

x_∞ and x_-∞ have the same expression !

x₀/(1-r) = (x₁ - (x₁ - x₀)) / (1-r) = (f(x₀) - r x₀) / (1-r)

rate iteration formula: x ← (f(x) - r x) / (1-r)