Math 441

Fixed-point Methods cont.

Iterative methods

Approximating a solution \(p\) of the equation \(g(x) = x\) …

… by iterating the function \(g\).

Start by choosing \(p_0\). Then, for \(n \ge 1\), define

\[p_n = g(p_{n-1})\]

If \(g\) is a continuous contraction on an interval \([a,b]\), and if you choose \(p_0 \in [a,b]\), then \(p_n\) will converge to \(p\).

Error estimates

Suppose \(g\) is a continuous contraction on \([a,b]\), and \(p_0 \in [a,b]\). Then for all \(n > 0\):

1. \(\displaystyle\left\lvert p_n - p\right\rvert < \lambda\left\lvert p_{n-1} - p\right\rvert\)
2. \(\displaystyle\left\lvert p_n - p\right\rvert \le \frac{1}{1-\lambda}\left\lvert p_{n+1} - p_n\right\rvert\)
3. \(\displaystyle\left\lvert p_n - p\right\rvert \le \frac{\lambda^n}{1-\lambda}\left\lvert p_1 - p_0\right\rvert\)
4. \(\displaystyle\left\lvert p_{n+1} - p\right\rvert \le \frac{\lambda}{1-\lambda}\left\lvert p_{n+1} - p_n\right\rvert\)
5. \(\displaystyle\left\lvert p_n - p\right\rvert \le \lambda^n \max\{p_0 - a, b - p_0\}\)

The inequality 1. means the convergence is linear.

The code

function fixedpoint(g :: Function, p₀, ϵ, N = 100)
    pₙ = p₀
    for n in 1:N
        pₙ₊₁ = g(pₙ)
        if abs(pₙ₊₁ - pₙ) < ϵ
            return IterationResult(pₙ₊₁, n, true)
        end
        pₙ = pₙ₊₁
    end

    IterationResult(pₙ, N, false)
end

Newton’s Method

function Newton(f :: Function, fp :: Function, p₀, ϵ, N = 100)
    pₙ = p₀
    for n in 1:N
        pₙ₊₁ = newton_step(f, fp, pₙ)
        if abs(pₙ₊₁ - pₙ) < ϵ
            return IterationResult(pₙ₊₁, n, true)
        end
        pₙ = pₙ₊₁
    end

    IterationResult(pₙ, N, false)
end

The Newton’s method is a fixedpoint method.

Speed of Convergence

• Newton’s method has quadratic convergence
• Fixedpoint method only guarantees linear convergence
• What gives?

• function newton_step(f :: Function, fp :: Function, pₙ)
      pₙ - f(pₙ)/fp(pₙ)
  end

• \(g(x) = x - \frac{f(x)}{f'(x)}\)
• \(\displaystyle g'(x) = 1 - \frac{\left(f'\left(x\right)\right)^2 - f(x)f''(x)}{\left(f'\left(x\right)\right)^2}\)

Convergence Theorem

Suppose \(f \in \mathcal{C}^\alpha(I)\) for some interval \(I\) and some \(\alpha \ge 2\). Suppose \(p \in I\) is a solution of the equation \(g(x) = x\), and \[g'(p) = g''(p) = \cdots = g^{(\alpha - 1)}(p) = 0\] and \(g^{(\alpha)}(p) \neq 0\).

Then, if the initial guess \(p_0\) is close enough to \(p\), then the sequence defined recursively by \(p_n = g(p_{n-1})\) for \(n \ge 1\) converges to \(p\) with order of convergence \(\alpha\), and \[\lim_{n\to \infty} \frac{p_{n+1} - p}{(p_n - p)^\alpha} = \frac{g^{(\alpha)}(p)}{\alpha!}.\]

Proof

• \(f \in \mathcal{C}^\alpha(I)\) for some \(\alpha \ge 2\).
  
• \(p \in I\), \(g(p) = p\)
• \(g'(p) = g''(p) = \cdots = g^{(\alpha - 1)}(p) = 0\)
• \(g^{(\alpha)}(p) \neq 0\).

---

• Show \(p_n \to p\) as \(p \to \infty\).
• Apply Taylor’s Theorem.
• Combine both.

Geometry of Fixedpoint Method