Fixed-Point Iteration Method
To solve an equation \(f(x)=0\), I rewrite it as \(x=g(x)\), choose an initial value \(x_0\), and generate successive approximations.
Choose the function and transformation
Transformation and convergence checks
- Maximum sampled |g′(x)|
- —
- Interval invariance (sampled)
- —
Fixed-point cobweb graph
The blue curve is \(y=g(x)\), the gray diagonal is \(y=x\). The orange staircase shows the successive iterations. On smaller screens, scroll the graph horizontally.
Results
Iteration table
| n | xₙ | f(xₙ) | g(xₙ) = xₙ₊₁ | |xₙ₊₁ − xₙ| |
|---|
How the method works
I choose a transformation \(g(x)\) and calculate \(x_1=g(x_0)\), \(x_2=g(x_1)\), and so on. If the approximations converge to \(\alpha\) and \(g\) is continuous there, then \(g(\alpha)=\alpha\).
To obtain a root of the original equation, the fixed points of \(g\) must agree with the zeros of \(f\). The transformation \(g(x)=x+k f(x)\), with \(k\ne0\), preserves these solutions algebraically. An arbitrary transformation may introduce or lose solutions.
The contraction theorem gives a sufficient condition for convergence when \(g\) maps a complete interval into itself and \(|g'(x)|\leq q<1\) throughout the interval. Checking a finite set of points, as this tool does, cannot establish these conditions rigorously.