Section 3.3 Fixed Point Iteration Schemes
Thus far, in this chapter we have seen the bisection method and later we will see Newton’s Method (which we saw briefly in Subsection 2.2.1). This and other rootfinding techniques fall into a general scheme called fixed point iteration schemes. In short, if we have a function \(g(x)\) and a sequence can be generated by knowing \(x_{0}\) and then for subsequence terms, \(x_{n+1}= g(x_{n})\text{,}\) this is a fixed point iteration.
Example 3.3.2.
Show graphically that there is a fixed point of the function \(g(x)=\cos x\text{.}\)
Since the function crosses the line \(y=x\text{,}\) there is a fixed point.
A fixed point iteration creates a sequence \(x_{n+1}= g(x_{n})\) for a given function \(g\) and initial point. The following using the function shown in the plot above.
Example 3.3.4.
Iterate with \(x_{n+1}= \cos x_{n}\) where \(x_{0}=1\) and \(n=1,2,3,\ldots,24\text{.}\) That is evaluate the fixed point iteration for \(g(x)=\cos x\) with given initial point.
Solution.
\begin{equation*}
\begin{aligned}x_{0} \amp = 1 \amp x_{1} \amp = 0.5403 \amp x_{2} \amp = 0.8575 \\ x_{3} \amp = 0.6543 \amp x_{4} \amp = 0.7935 \amp x_{5} \amp = 0.7014 \\ \amp \vdots \\ x_{22} \amp = 0.7390183 \amp v_{23} \amp = 0.7391302 \amp x_{24} \amp = 0.7390547\end{aligned}
\end{equation*}
This appears to be converging to about the value of 0.7391.
From the last example, it appears that if we iterate a function, we can find where it crosses the line \(y=x\text{.}\) Consider the function \(g(x)= x^{4}-2.5x^{2}+1\) and note that it crosses the line \(y=x\) in two locations from the following plot:
Example 3.3.6.
Iterate \(x_{n+1}= g(x_{n})\) for \(x_{0}=1\) when the function is \(g(x)=x^{4}-2.5x^{2}+1\) for \(n=1,2,\ldots, 24\text{.}\)
Solution.
\begin{equation*}
\begin{aligned}x_{0} \amp = 1 \amp x_{1} \amp = -0.5 \amp x_{2} \amp = 0.4375 \\ x_{3} \amp = 0.55812072 \amp x_{4} \amp = 0.31828460 \amp x_{5} \amp = 0.75699999 \\ x_{6} \amp =-0.10423734 \amp x_{7} \amp = 0.97295449 \amp x_{8} \amp = -0.47047298 \\ x_{9} \amp = 0.49563145 \amp x_{10} \amp = 0.44621783 \amp x_{11} \amp = 0.54186904 \\ x_{12} \amp = 0.35215876 \amp x_{13} \amp = 0.70534042 \amp x_{14} \amp =0.003748557 \\ x_{15} \amp =0.999964870 \amp x_{16} \amp =-0.499964866 \amp x_{17} \amp =0.437570265 \\ x_{18} \amp =0.557990551 \amp x_{19} \amp =0.318557335 \amp x_{20} \amp =0.756601001 \\ x_{21} \amp =-0.103419325 \amp x_{22} \amp =0.973375502 \amp x_{23} \amp =-0.470969469 \\ x_{24} \amp =0.494670067\end{aligned}
\end{equation*}
Notice in this case that the iteration did not converge nor result in finding the intersection point.
A question is why did it work in the first case, and not in the second. We will find out, but need a few more basic analysis first. This next theorem gives some conditions when the fixed point is unique.
Theorem 3.3.7. Fixed Point Theorem.
Let \(g\) be a continuous function on the closed interval \([a,b]\) with \(g: [a,b] \rightarrow [a,b]\text{.}\) Then \(g\) has a fixed point \(p \in [a,b]\text{.}\) Furthermore, if \(g\) is differentiable on \((a,b)\) and there exists a positive constant \(k \lt 1\) such that \(|g'(x)|\leq k \lt 1\) for all \(x \in (a,b)\text{,}\) then the fixed point in \([a,b]\) is unique.
Proof.
First, we will prove the existence of a fixed point. Let \(h(x) = g(x)-x\text{.}\) Since both \(g(x)\) and \(x\) are continuous, then \(h\) is continuous on \([a,b]\text{.}\) The roots of \(h\) are the fixed points of \(g\text{.}\)
Because the range of \(g\) is a subset of \([a,b]\text{,}\) \(\min_{x \in [a,b]}g(x) \geq a\) and \(\max_{x \in [a,b]}g(x) \leq b\text{.}\) Therefore
\begin{equation*}
\begin{aligned} h(a) \amp = g(a)-a \geq 0 \amp \text{and} \amp \amp h(b) \amp = g(b)-b \leq 0 \end{aligned}
\end{equation*}
If either \(h(a)=0\) or \(h(b)=0\text{,}\) then we have found a root of \(h\) and therefore a fixed point of \(g\text{.}\) If not, the condition \(h(b) \lt 0 \lt h(a)\) and the intermediate value theorem guarantees a value \(p \in (a,b)\) such that \(h(p)=0\text{,}\) and thus \(p\) is a fixed point of \(g\) or \(g(p)=p\text{.}\)
The next step is to prove the uniqueness of the fixed point. Suppose that both \(q\) and \(p\) are fixed points of \(g\text{.}\) That is \(g(p)=p\) and \(g(q)=q\text{.}\) Therefore,
\begin{equation*}
\begin{aligned}|p-q| \amp = |g(p)-g(q)| \amp \amp \text{By MVT}\\ \amp = |g'(\xi)(p-q)| \\ \amp = |g'(\xi)| |p-q| \amp \amp \text{Using $|g'(x)|\leq k \lt 1$}\\ \amp \leq k |p-q| \lt |p-q|\end{aligned}
\end{equation*}
which is a contradiction therefore the fixed point is unique.
What can we say about the previous two examples in light of this theorem? First, when \(g(x)=\cos x\text{,}\) we saw above that the fixed point was 0.739 (to 3 decimal places). And since the derivative near this point is important \(g'(0.739) = -0.674\text{.}\) Since \(g\) is continuous and differential, there is an interval \([a,b]\) containing 0.739 such that \(|g'(x)| \lt 1\text{.}\) Therefore the iteration scheme converged to the unique fixed point.
In the second case, when \(g(x)=x^{4}-2.5x^{2}+1\text{,}\) there are two fixed points. Using a different method, \(p_{1}=0.4790137621\) and \(p_{2}= 1.655034382\) are both fixed points and
\begin{equation*}
\begin{aligned}f'(p_{1}) \amp = -1.955421962 \amp f'(p_{2}) \amp = 9.858303690\end{aligned}
\end{equation*}
and in both cases the absolute value is greater than 1. The fact that if \(|f'(p)| \gt 1\) the sequence diverges is not a consequence of Theorem 3.3.7, but may explain why we see the results.
Subsection 3.3.1 Additional Analysis of Fixed Point Iterations
Theorem 3.3.7 is extremely helpful for analyzing fixed points—especially to determine where an iteration will converge to a fixed point or not. In this section, we go further with the analysis. The last two theorems will determine the order of converge to the fixed point. First, however, we examine a theorem that determines how close an term of the sequence is to the fixed point.
Theorem 3.3.8. Bounds on Fixed Point Iterations.
Let \(g\) be continuous on the closed interval \([a,b]\) with \(g:[a,b]\rightarrow [a,b]\text{.}\) Furthermore, suppose that \(g\) is differentiable on the open interval \((a,b)\) and there exists a positive constant \(k \lt 1\) such that \(|g'(x)|\leq k \lt 1\) for all \(x \in (a,b)\text{.}\) Then
-
The sequence \(\{p_{n}\}\) generated by \(p_{n} = g(p_{n-1})\) converges to the fixed point \(p\) for any \(p_{0} \in (a,b)\text{;}\)
-
\(|p_{n}-p|\leq k^{n} \max(p_{0}-a,b-p_{0})\text{;}\) and
-
\(|p_{n}-p| \leq \frac{k^{n}}{1-k}|p_{1}-p_{0}|\text{.}\)
First, note that the hypotheses of the theorem are the same as the fixed point theorem (Theorem 3.3.7), so we know that there is a unique fixed point. This theorem gives us much more information about the iterations.
Proof.
-
To prove convergence, we need to prove that \(\lim_{n\rightarrow \infty}p_{n} = p\text{,}\) or \(\lim_{n \rightarrow \infty}|p_{n}-p| = 0\text{,}\)\begin{equation*} \begin{aligned}|p_{n} - p| \amp = |g(p_{n-1}) - g(p)|, \amp \amp \text{and by MVT,}\\ \amp = |g'(\xi)| |p_{n-1}- p|, \\ \amp \leq k |p_{n-1}-p|, \\ \amp \leq k^{2} |p_{n-2}- p|, \\ \amp \vdots \\ \amp \leq k^{n} |p_{0} - p|,\end{aligned} \end{equation*}and since \(k \lt 1\text{,}\)\begin{equation*} \begin{aligned}\lim_{n \rightarrow \infty}|p_{n}-p| \amp \leq \lim_{n\rightarrow \infty}k^{n} |p_{0} - p| = |p_{0}-p| \lim_{n\rightarrow \infty}k^{n} = 0,\end{aligned} \end{equation*}so the sequence \(\{ p_{n} \}\) converges to \(p\text{.}\)
-
Since \(|p_{0}-p| \leq \max(p_{0}-a,b-p_{0})\) and use of \(|p_{n}-p| \leq k^{n} |p_{0}-p|\) establishes\begin{equation*} \begin{aligned}|p_{n} - p| \leq k^{n} \max(p_{0}-a,b-p_{0}).\end{aligned} \end{equation*}
-
First, the following needs to be established\begin{equation*} \begin{aligned}|p_{n+1}-p_{n}| \amp = |g(p_{n+1})-g(p_{n})|, \amp \amp \text{by MVT,}\\ \amp = |g'(\xi)| |p_{n+1}- p_{n}|, \\ \amp \leq k |p_{n+1}-p_{n}|, \\ \amp \leq k^{n} |p_{1} - p_{0}|.\end{aligned} \end{equation*}Next, if \(m \gt n\text{,}\)\begin{equation*} \begin{aligned}|p_{m}-p_{n}| \amp = |p_{m}-p_{m-1}+ p_{m-1}- p_{m-2}+\cdots+ p_{n+1}-p_{n}|, \\ \amp \leq | p_{m}-p_{m-1}| + |p_{m-1}- p_{m-2}| + \cdots+ | p_{n+1}-p_{n}|, \\ \amp \leq k^{m-1}|p_{1}-p_{0}| + k^{m-2}|p_{1} -p_{0}|+ \cdots +k^{n} |p_{1} -p_{0}|, \\ \amp = k^{n} |p_{1} -p_{0}| (1 + k + k^{2} + \cdots k^{m-n-1}), \end{aligned} \end{equation*}Taking the limit as \(m \rightarrow \infty\text{:}\)\begin{equation*} \begin{aligned}|p - p_{n}| \amp \leq k^{n} |p_{1} -p_{0}| \sum_{i=0}^{\infty}k^{i}, \\ \amp = \frac{k^{n}}{1-k}|p_{1} -p_{0}|.\end{aligned} \end{equation*}And thus the conclusions of the theorem are verified.
This theorem gives quite a bit of insight into fixed point iterations. Let’s examine the three consequences of the theorem:
-
The first item determines convergence. Given a fixed point iteration formula with the conditions on \(g\text{,}\) we are guaranteed convergence. This is good!
-
By establishing a bound on \(|p_{n} -p|\text{,}\) we can guarantee an error bound on the \(n\)th iterate. If we have some method that applies to finding \(\sqrt{65}\text{,}\) this part will determine how close a term of the sequence is to \(\sqrt{65}\) or usually more importantly, this can be used to determine the number of terms it takes to get within some tolerance of \(\sqrt{65}\text{.}\)
-
Same as in #2.
Subsection 3.3.2 Linear Convergence of Fixed Point Iterations
The follow theorem extends the Fixed Point Theorem (thm:fixed:pt) to determine when a sequence resulting from fixed point iteration converges linearly.
Theorem 3.3.9. Linear Convergence of Fixed Point Iterations.
Let \(g\) be a continuous function on the closed interval \([a,b]\) with \(g: [a,b] \rightarrow [a,b]\) and suppose that \(g'\) is continuous on the open interval \((a,b)\) with \(|g'(x)|\leq k \lt 1\) for all \(x \in (a,b)\text{.}\) If \(g'(p) \neq 0\text{,}\) where \(p\) satisfies \(p=g(p)\text{,}\) then the sequence \(p_{n+1}= g(p_{n})\) converges only linearly to \(p\text{.}\)
Proof.
First, the hypotheses of the theorem imply that there is a unique fixed point \(p \in (a,b)\) and the sequence converges to \(p\text{.}\) We only need to show that if \(g'(p) \neq 0\text{,}\) then the sequence converges linearly.
This means that we need to show that
\begin{equation*}
\begin{aligned}\lim_{n \rightarrow \infty}\frac{|p_{n+1}- p|}{|p_{n} -p|} \amp \gt 0.\end{aligned}
\end{equation*}
Next, consider
\begin{equation*}
\begin{aligned}|p_{n+1}-p| \amp = |g(p_{n}) - g(p)|, \amp \amp \text{by MVT,}\\ \amp = |g'(\xi_{n})||p_{n}-p|,\end{aligned}
\end{equation*}
where \(\xi_{n}\) is between the points \(p\) and \(p_{n}\) for each \(n\text{.}\) Since \(\{p_{n}\}\) converges to \(p\text{,}\) then \(\xi_{n}\) also converges to \(p\text{.}\) Taking the limit
\begin{equation*}
\begin{aligned}\lim_{n \rightarrow \infty}\frac{|p_{n+1}- p|}{|p_{n} -p|} \amp = \lim_{n \rightarrow \infty}\frac{ |g'(\xi_{n})| |p_{n}-p|}{|p_{n}-p|}, \\ \amp = \lim_{n \rightarrow \infty}|g'(\xi_{n})| = |g'(p)|.\end{aligned}
\end{equation*}
and by the hypothesis of the problem since \(g'(p)\neq 0\) and \(|g'(p)| \lt 1\text{,}\) this converges linearly by definition of linear convergence.
This theorem gives a simple way to determine if a fixed point iteration converges linearly.
Example 3.3.10.
Show that the fixed point iteration given by \(x_{n+1}= \cos x_{n}\) converges only linearly on the interval \([0,1]\text{.}\)
We know that \(p \in (0,1)\) and since \(g'(p)=\sin p\) is never zero in this interval (it is 0 on the boundary), this means that this sequence converges linearly.
The next theorem allows one to determine the order of convergence by extending that in Theorem 3.3.9
Theorem 3.3.11. Higher-Order Convergence of Fixed Point Iterations.
Let \(g\) be a continuous function on the closed interval \([a,b]\) with \(\alpha \gt 1\) continuous derivatives on the open interval \((a,b)\text{.}\) Further, let \(p \in (a,b)\) be a fixed point of \(g\text{.}\) If
\begin{equation*}
\begin{aligned}g'(p) = g''(p) = \cdots \ g^{(\alpha-1)}(p) = 0\end{aligned}
\end{equation*}
but \(g^{(\alpha)}(p) \neq 0\text{,}\) then there exists a \(\delta \gt 0\) such that for any \(p_{0} \in [p-\delta,p+\delta]\text{,}\) the sequence \(p_{n} = g(p_{n-1})\) converges to \(p\) of order \(\alpha\) with asymptotic error constant
\begin{equation*}
\begin{aligned}\lambda \amp = \lim_{n \rightarrow \infty}\frac{|e_{n+1}|}{|e_{n}^{\alpha}|}= \frac{|g^{(\alpha)}(p)|}{\alpha!}\end{aligned}
\end{equation*}
Proof.
- Proof of convergence
- Since \(\alpha \gt 1\) and \(g\) and \(g'\) are continuous on \((a,b)\text{,}\) with \(g(p)=p\) and \(g'(p)=0\) that by continuity of \(g\) and continuity of \(g'\) there exists an interval \((a^{\star},b^{\star}) \subset (a,b)\text{,}\) where \(p \in (a^{\star},b^{\star})\) and \(|g'(x)|\leq k \lt 1\text{.}\) If we let \(\delta = \min(p-a^{\star},b^{\star}-p)\text{,}\) then using Theorem 3.3.7, the for any \(p_{0}\in [p-\delta,p+\delta]\text{,}\) the sequence given by \(g_{n+1}=g(p_{n})\) converges.
- Proof of rate of convergence
-
Let \(x \in I\) and expand \(g\) in a Taylor’s Series above the fixed point \(x=p\text{:}\)\begin{equation*} \begin{aligned}g(x) \amp = g(p) + g'(p) (x-p)+ \cdots + \frac{g^{(\alpha-1)}(p)}{(\alpha-1)!}(x-p)^{\alpha-1}+ \frac{g^{(\alpha)}(\xi)}{\alpha!}(x-p)^{\alpha}\end{aligned} \end{equation*}where \(\xi\) is between \(x\) and \(p\text{.}\)Since \(g'(p)= g''(p)= \cdots = g^{(\alpha-1)}(p) = 0\text{,}\) we have\begin{equation*} \begin{aligned}g(x) \amp = g(p) + \frac{g^{(\alpha)}(\xi)}{\alpha!}(x-p)^{\alpha}.\end{aligned} \end{equation*}Letting \(x=p_{n}\) and \(g(p_{n})= p_{n+1}\text{,}\) then\begin{equation*} \begin{aligned}p_{n+1}- p \amp = \frac{g^{(\alpha)}(\xi)}{\alpha!}(p_{n}-p)^{\alpha}.\end{aligned} \end{equation*}
- Order \(\alpha\) convergence
- \begin{equation*} \begin{aligned}\lim_{n \rightarrow \infty}\frac{ |e_{n+1}|}{|e_{n}|^{\alpha}|}\amp = \lim_{n \rightarrow \infty}\frac{|p_{n+1}-p|}{|p_{n} - p|^{\alpha}}\\ \amp = \lim_{n \rightarrow \infty}\frac{\frac{|g^{(\alpha)}(\xi)|}{\alpha!}|p_{n}-p|^{\alpha}}{|p_{n} - p|^{\alpha}}\\ \amp = \frac{|g^{(\alpha)}(p)|}{\alpha!}\end{aligned} \end{equation*}which shows that the order of convergence is \(\alpha\) with asymptotic error constant \(|g^{(\alpha)}(p)|/\alpha!\text{.}\)
In Example 2.3.18, we showed directly that the fixed point iteration given by the formula \(x_{n+1}=\frac{1}{2}(x_{n}+a/x_{n})\) converges quadratically. We will use the above theorem to show this.
Example 3.3.12.
Prove using Theorem 3.3.11 that the method given by
\begin{equation*}
g(x) = \frac{1}{2}\biggl( x + \frac{a}{x}\biggr)
\end{equation*}
converges to \(p=\sqrt{a}\) quadratically and find the asymptotic error constant,
\begin{equation*}
\lambda = \frac{1}{2 \sqrt{a}}
\end{equation*}
First, note that \(g(x)\) is continuous and differentiable (to any order) on an interval not containing \(x=0\text{.}\)
Next, note that
\begin{equation*}
\begin{aligned}g(\sqrt{a}) = \frac{1}{2}\biggl(\sqrt{a}+ \frac{a}{\sqrt{a}}\biggr) = \sqrt{a}\end{aligned}
\end{equation*}
so \(x=\sqrt{a}\) is a fixed point.
\begin{equation*}
\begin{aligned}g'(x) \amp = \frac{1}{2}\biggl(1 - \frac{a}{x^{2}}\biggr) \\ g'(\sqrt{a}) \amp = 0 \\ g''(x) \amp = \frac{a}{x^{3}}\\ g''(\sqrt{a}) \amp = \frac{1}{\sqrt{a}}\end{aligned}
\end{equation*}
Since \(g'(p)=0\) and \(g''(p) \neq 0\text{,}\) this method converges and converges quadratically. The asymptotic error constant is \(g''(p)/2 = 1/(2 \sqrt{a})\text{,}\) which we saw in Example 2.3.15.
In light of the above example, the next one seeks a higher-order method for finding square roots. To do this, we’ll assume a functional form and then force the function to have \(g^{(i)}(p)=0\) for as many \(i\) as possible.
Example 3.3.13.
Use Theorem 3.3.11 to find a third-order method to find \(\sqrt{a}\text{.}\) In particular find \(A\text{,}\) \(B\) and \(C\) such that the fixed point iteration given by
\begin{equation*}
g(x) = \frac{Ax+Bx^{3}}{1+Cx^{2}}
\end{equation*}
converges cubically.
Using Theorem 3.3.11, we need \(g\) to satisfy:
\begin{equation*}
\begin{aligned}g(\sqrt{a}) \amp = \sqrt{a} \amp g'(\sqrt{a}) \amp = 0 \amp g''(\sqrt{a}) \amp = 0\end{aligned}
\end{equation*}
Skipping the algebra, we can find that
\begin{equation*}
\begin{aligned}A \amp = 3 \amp B \amp = \frac{1}{a} \amp C \amp = \frac{3}{a}\end{aligned}
\end{equation*}
so
\begin{equation*}
\begin{aligned}g(x) \amp = \frac{3 x + (1/a) x^{3}}{1 + (3/a) x^{2}}\\ \amp = \frac{3ax+x^{3}}{a+3x^{2}}\end{aligned}
\end{equation*}
This method is in fact third-order and the asymptotic error constant \(\lambda=g'''(\sqrt{a})/3! = \frac{1}{4a}\text{.}\)
To illustrate the speed of convergence of this, we will use this to find \(\sqrt{65}\text{.}\) If we let \(x_{0}=1\) and iterate, then
\begin{equation*}
\begin{aligned}x_{1} \amp = g(x_{0}) = \frac{3(65)(1)+(1)^{3}}{65+3(1)^{2}}= 2.8823529411764706 \\ x_{2} \amp = g(x_{1}) = \frac{3(65)(2.8823529411764706) + (2.8823529411764706)^{3}}{65+3(2.8823529411764706)^{2}} \\
\amp = 6.516681907486712 \\ x_{3} \amp = 8.043068292088401 \\ x_{4} \amp = 8.062257721023464 \\ x_{5} \amp = 8.062257748298551\end{aligned}
\end{equation*}
And even though we showed above that the method is third-order, we will also show this numerically. Recall from Section 2.3 that if \(e_{n} = x_{n}-\sqrt{65}\text{,}\) then if \(e_{n+1}= \lambda |e_{n}|^{3}\text{,}\) then the method is third-order (or cubic). Using these above,
| \(n\) | \(\dfrac{e_{n+1}}{|e_n|^3}\) |
| 1 | 0.0147058823529411764 |
| 2 | 0.0111205171617669693 |
| 3 | 0.0051974665879438180 |
| 4 | 0.0038599182753288449 |
| 5 | 0.0038461538656714881 |
which shows that the method is cubic with \(\lambda = 0.0038462\text{,}\) which is consistent with the value \(\frac{1}{4a}\) found above with \(a=65\text{.}\)
Lastly, on a practical matter, a cubic method usually triples the digits of accuracy with each step and this one has about 600 digits of accuracy after 10 steps.
