Fixed point Iteration
On this page:
- Existence of Fixed Points
- Unique Fixed Point
- Does the iteration x_{k+1} = f(x_k)$ converge to a fixed point $p$?
- Newton’s Method Stuff
- Worked Problems
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 |
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]