Fixed point Iteration


Back to Numerical Page

On this page:


Existence of Fixed Points

A classic example is a function $f\in C[a, b]$ that maps $[a, b]$ back into $[a, b]$. Then one can show that there is a fixed point by applying the IVT to $g(x) = f(x) - x$.

Unique Fixed Point

If $f$ satisfies the same criterion as above and $f$ is differentiable on $[a, b]$ such that $|f’(x)| < 1$, then the Mean Value Theorem implies that there is a unique fixed point.

Does the iteration x_{k+1} = f(x_k)$ converge to a fixed point $p$?

This happens if $f’(p)< 1$ since the mean value theorem implies
\[\begin{align*} |x_{k+1} - p| = |f(x_k) - f(p)| = |f'(\xi)||x_k - p| < |x_k - p|. \end{align*}\]

And then the rest is an induction argument.

Newton’s Method Stuff

Recall that Newton’s method setup is

\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.\]

If $p$ is a non-simple zero, then you automatically have linear convergence. In that case, you can write

\[f(x) = (x - p)^nh(x)\]

and things will cancel nicely usually. If $p$ is a simple zero, find the smeallest $n > 1$ s.t. $f^{(n)}(p) \neq 0$. We say that $n$ is the order of convergence.

Worked Problems

[example] [extitle]KU Quals Jan 2025 Problem 1.[/extitle]

Suppose that

\[g(x) = \frac{x}{2} + \frac{2}{x}.\]

(a) Prove that there is a unique fixed point $p$ on [3/2, 3]$.

(b) For an initial $p_0 \in [3/2, 3]$, does the sequence $p_k = g(p_{k-1})$ converge?

(c) [/example]

[solution] (a) We will prove existence and uniqueness separately.

(Existence) Note that

\[\begin{align*} g\left(\frac{3}{2}\right) = \frac{3/2}{2} + \frac{2}{3/2} = \frac{3}{4} + \frac{4}{3} = \frac{9}{12} + \frac{16}{12} = \frac{25}{12}. \end{align*}\]

Since

\[\begin{align*} g(3) = \frac{3}{2} + \frac{2}{3} = \frac{9}{6} + \frac{4}{6} = \frac{13}{6} = \frac{26}{12}. \end{align*}\]

For critical points, consider the derivative

\[g'(x) = \frac{1}{2} - \frac{2}{x^2}.\]

If $g’(x) = 0$, then

\[\frac{1}{2} = \frac{2}{x^2} \quad\implies\quad x = 2.\]

As

\[g(2) = \frac{2}{2} + \frac{2}{2} = 2,\]

it follows that $g([a, b]) \subseteq [a, b]$. The continuity of $g$ guarantees there is a fixed point as desired.

(Uniqueness) We will use the criterion above. Consider

\[\frac{3}{2} \le x \le 3 \quad\iff\quad \frac{1}{3} \le \frac{1}{x} \le \frac{2}{3}.\]

Squaring gives

\[\frac{1}{9} \le \frac{1}{x^2} \le \frac{4}{9}.\]

Multiplying by 2 gives

\[\frac{2}{9} \le \frac{2}{x^2} \le \frac{8}{9}.\]

Negating the entire expression gives

\[\frac{-16}{18} \le \frac{-2}{x^2} \le \frac{-4}{18}.\]

So

\[\frac{-1}{2} \le \frac{-7}{18} \le \frac{1}{2} - \frac{2}{x^2} \le \frac{5}{18} \le \frac{1}{2}\]

which implies

\[\left|\frac{1}{2} - \frac{2}{x^2}\right| \le \frac{1}{2} < 1.\]

So $|g’(x)| < 1$ for $x \in [3/2, 3]$.

(b) It suffices to show that the pointwise norm of the image is less than $1$. So the claim follows immediately from our work in (a).

(c) For rate of convergence, we have the criterion

\[\begin{align*} & 0 < |g'(2)| < 1 \qquad\text{ linear}, \\ & |g'(2)| = 0 \qquad\text{ at least quadratic}, \\ & \text{smallest } n \text{ s.t. }|g^{(n)}(2)| \neq 0|,\text{ ROC is order } n. \end{align*}\]

So for us, $g’‘(x) = 4/x^2$ and $g’‘(2) = 1/2$ is nonzero. So we have quadratic convergence. [/solution]

[example] [extitle]KU Quals August 2021[/extitle]

Suppose we have

\[\begin{align*} g(x) = ax^{1 - p}, \qquad f(x) = x + \lambda(g(x) - x) \end{align*}\]

where $p \ge 2$ is an integer, $a > 0$, and $x > 0$.

(a) Does $x_{n+1} = g(x_n)$ converge to $a^{1/p}$?

(b) For what values of $\lambda$ does $f$ converge to $a^{1/p}$.

(c) Whats the optimal value of $\lambda$ which leads to the fastest convergence?

(d) Write Newton’s iteration for $h(x) = x^p - a$. What’s the order of convergence? [/example]

[solution] (a) Remember our criterion:

\[\begin{align*} |g'(a^{1/p})| &< 1 \implies \text{ converges}\\ |g'(a^{1/p})| &> 1 \implies \text{ diverges} \\ |g'(a^{1/p})| &= 1 \implies \text{ don't know}. \end{align*}\]

Computing $g’$ gives

\[\begin{align*} g'(x) = a(1 - p)x^{-p} = \frac{a(1 - p)}{x^p} \end{align*}\]

then

\[\begin{align*} |g'(a^{1/p})| = \left|\frac{a(1 - p)}{a}\right| - |1 - p|. \end{align*}\]

So if $p > 2$, the expression above is larger than $1$ so we have divergence. But if $p = 2$, then we’re at an inconclusive situation so we need to continue investigating. Notice that if we compute the fixed point iteration for $p = 2$, then we get the sequence

\[x_0, \quad \frac{a}{x_0}, \quad x_0, \quad \frac{a}{x_0}, \quad x_0, \ldots.\]

So as long as $x_0 \neq a^{1/2}$, then the fixed point iteration diverges.

(b) Again, we will use the derivative criterion:

\[f(x) = x + \lambda(g(x) - x).\]

Then

\[f'(x) = 1 + \frac{\lambda a (1 - p)}{x^p} - \lambda.\]

So

\[f'(a^{1/p}) = 1 + \lambda(1 - p) - \lambda = 1 - \lambda p.\]

If

\[|1 - \lambda p| < 1 \quad\iff\quad -1 < 1 - \lambda p < 1\]

this implies that $0 < \lambda < 2/p$. Now just run the above steps backwards to prove the result.

(c) The idea here will be to make the derivative vanish at $a^{1/p}$ because that implies at least quadratic rate of convergence. Consider that

\[|f'(a^{1/p})| = 1 - \lambda p.\]

So this means the optimal value for $\lambda$ is $1/p$.

(d)

\[x_{n+1} = x_n - \frac{x_{n}^p - a}{px_n^{p-1}}.\]

Since $h’(a^{1/p}) - p(a^{1/p})^{(p-1)} \neq 0$ (since $a> 0$ and $p\ge 2$ in this problem), we know that $a^{1/p}$ is a simple zero of $h$. So we look for the smallest $n$ for which $h^{(n)}(a^{1/p})$ vanishes. In our case, it is easily seen that $n = 2$. So $h$ has quadratic convergence. [/solution]