Math 441

Fixed-point Methods last

Convergence Results

• If \(g \in \mathcal{C}^1([a,b])\) and \(0 < \left\lvert g'(p) \right\rvert < 1\): linear convergence and \[\lim_{n\to \infty} \frac{\left\lvert p_{n+1} - p\right\rvert}{\left\lvert p_n - p\right\rvert} = \left\lvert g'(p)\right\rvert\]
• If \(g \in \mathcal{C}^\alpha([a,b])\) and \(g'(p) = g''(p) = \cdots = g^{(\alpha-1)}(p) = 0\) and \(g^{(\alpha)}(p) \neq 0\): convergence of order \(\alpha\) and \[\lim_{n\to \infty} \frac{p_{n+1} - p}{\left( p_n - p\right)^\alpha} = \frac{g^{(\alpha)}(p)}{\alpha !}\]

Tracing Convergence

We would like to experimentally verify these results.

Problem: The method only returns the final result, not the whole sequence.

We need to modify it so it will return all the \(p_n\)’s.

There is some code on page 85, but it has number of issues.

The Textbook Code

function fixedpt2(g::Function,pzero,eps,N)
    n=1
    global list
    list=Float64[]
    error=1.
    while n<N && error>10^-5.
        pone=g(pzero)
        error=abs(pone-pzero)
        append!(list,(pone-2^0.5)/(pzero-2^0.5))
        pzero=pone
        n=n+1
    end
    return(list)
end

This is supposed to track convergence.

Why is it called fixedpt2?

list should not be global!

Use push! rahter than append!!

Where is eps even used?

Why is “error” handled this way? It is not even an error!

What if we want to analyze nonlinear convergence?

Only works if the fixed point is \(\sqrt{2}\)!

Approximate \(\sqrt{3}\)

Solve \(x^2 - 3 = 0\).

We need to turn it into the form \(g(x) = x\).

One option: Newton’s method

How about \(x + x^2 - 3 = x\)?

Why not \(x - (x^2 - 3) = x\)?

Try this: \(x - \frac{1}{2}(x^2 - 3) = x\).

Another Example

Approximate the solution of \(x^3 - 2x^2 - 1 = 0\) on \([1,3]\)

\(f(x) = x^2 - 2x^2 - 1\)

Try \(g(x) = x - f(x)\).

Try \(g(x) = x - cf(x)\) for some \(c\).

Rewrite the equation:

\(x^3 = 2x^2 + 1\), or \(x = (2x^2 + 1)^{1/3}\).