2.7 High-order fixed-point iteration

In the proof of Theorem 11, we showed

\[\begin{equation*} \lim_{n\rightarrow\infty}\frac{|p_{n+1}-p|}{|p_{n}-p|}=|g'(p)| \end{equation*}\]

which implied that the fixed-point iteration has linear convergence, if \(g'(p)\neq 0\).

If this limit were zero, then we would have

\[\begin{equation*} \lim_{n\rightarrow\infty}\frac{|p_{n+1}-p|}{|p_{n}-p|}=0, \end{equation*}\]

which means the numerator is decreasing at a larger rate than the denominator. We could then ask if

\[\begin{equation*} \lim_{n\rightarrow\infty}\frac{|p_{n+1}-p|}{|p_{n}-p|^{\alpha}}=\text{nonzero constant} \end{equation*}\]

for some \(\alpha>1\).

Theorem 12

Assume \(p\) is a solution of \(g(x)=x\) where \(g\in C^\alpha (I)\) for some interval \(I\) that contains \(p\), and for some \(\alpha\geq2\). Furthermore assume

\[\begin{equation*} g'(p)=g''(p)=...=g^{(\alpha-1)}(p)=0,\text{ and }g^{(\alpha)}(p)\neq0. \end{equation*}\]

Then if the initial guess \(p_{0}\) is sufficiently close to \(p\), the fixed-point iteration \(p_{n}=g(p_{n-1}),n\geq1\), will have order of convergence of \(\alpha\), and

\[\begin{equation*} \lim_{n\rightarrow\infty}\frac{p_{n+1}-p}{(p_{n}-p)^{\alpha}}=\frac{g^{(\alpha)}(p)}{\alpha!}. \end{equation*}\]

Proof. From Taylor’s theorem,

\[\begin{align*} p_{n+1} & =g(p_{n})=g(p)+(p_{n}-p)g'(p)+...+\frac{(p_{n}-p)^{\alpha-1}}{(\alpha-1)!}g^{(\alpha-1)}(p) +\frac{(p_{n}-p)^{\alpha}}{\alpha!}g^{(\alpha)}(\xi_{n}) \end{align*}\]

where \(\xi_{n}\) is a number between \(p_{n}\) and \(p\), and all numbers are in \(I\). From the hypothesis, this simplifies as

\[\begin{equation*} p_{n+1}=p+\frac{(p_{n}-p)^{\alpha}}{\alpha!}g^{(\alpha)}(\xi_{n})\Rightarrow\frac{p_{n+1}-p}{(p_{n}-p)^{\alpha}}=\frac{g^{(\alpha)}(\xi_{n})}{\alpha!}. \end{equation*}\]

From Theorem 11, if \(p_{0}\) is chosen sufficiently close to \(p\), then \(\lim_{n\rightarrow\infty}p_{n}=p\). The order of convergence is \(\alpha\) with

\[\begin{equation*} \lim_{n\rightarrow\infty}\frac{|p_{n+1}-p|}{|p_{n}-p|^{\alpha}}=\lim_{n\rightarrow\infty}\frac{|g^{(\alpha)}(\xi_{n})|}{\alpha!}=\frac{|g^{(\alpha)}(p)|}{\alpha!}\neq0. \end{equation*}\]

Application to Newton’s Method

Recall Newton’s iteration

\[\begin{equation*} p_{n}=p_{n-1}-\frac{f(p_{n-1})}{f'(p_{n-1})}. \end{equation*}\]

Put \(g(x)=x-\frac{f(x)}{f'(x)}.\) Then the fixed-point iteration \(p_{n}=g(p_{n-1})\) is Newton’s method. We have

\[\begin{equation*} g'(x)=1-\frac{[f'(x)]^{2}-f(x)f''(x)}{[f'(x)]^{2}}=\frac{f(x)f''(x)}{[f'(x)]^{2}} \end{equation*}\]

and thus

\[\begin{equation*} g'(p)=\frac{f(p)f''(p)}{[f'(p)]^{2}}=0. \end{equation*}\]

Similarly,

\[\begin{equation*} g''(x)=\frac{\left(f'(x)f''(x)+f(x)f'''(x)\right)(f'(x))^{2}-f(x)f''(x)2f'(x)f''(x)}{[f'(x)]^{4}} \end{equation*}\]

which implies

\[\begin{equation*} g''(p)=\frac{\left(f'(p)f''(p)\right)(f'(p))^{2}}{[f'(p)]^{4}}=\frac{f''(p)}{f'(p)}. \end{equation*}\]

If \(f''(p)\neq0\) (recall that Newton’s method assumes \(f'(p)\ne 0\)), then Theorem 12 implies Newton’s method has quadratic convergence with

\[\begin{equation*} \lim_{n\rightarrow\infty}\frac{p_{n+1}-p}{(p_{n}-p)^{2}}=\frac{f''(p)}{2f'(p)} \end{equation*}\]

which was proved earlier in Theorem 7.

Exercise 2.7-1

Let \(g(x)=3^{-x}\).

a. Prove that \(g(x)\) has a unique fixed-point on \([1/4,1].\) (Hint: Use Theorem 9 and Remark 6.)

b. Prove that the fixed-point iteration \(p_n=g(p_{n-1})\) converges to the unique fixed-point of \(g\) for any starting point \(p_0 \in [1/4,1]\). (Hint: Use Theorem 10 and Remark 7.)

c. Pick some \(p_0 \in [1/4,1]\), and use Corollary 3, part 4, to find the number of iterations necessary to achieve \(10^{-10}\) accuracy. Call this number \(N\).

d. Modify the Python code for fixed-point iteration as follows: remove the stopping criterion \(|p_1-p_0|<\text{ eps}\) and make the code run until \(N\) iterations, printing pzero as the output \(p\) at the end. Using the new code, and your answer to the previous part, compute the fixed-point of \(g(x)\) with an accuracy of \(10^{-10}\).

Exercise 2.7-2

Let \(g(x)=2x-cx^{2}\) where \(c\) is a positive constant. Prove that if the fixed-point iteration \(p_n=g(p_{n-1})\) converges to a non-zero limit, then the limit is \(1/c\).

Exercise 2.7-3

Leonardo of Pisa (1175-1250), also known as Fibonacci, showed that the only real root of the cubic polynomial \(x^3 + 2 x^2 + 10x − 20\) is (Brown and Brunson [2008])

\[\begin{equation*} 1+\frac{22}{60}+\frac{7}{60^2} + \frac{42}{60^3} + \frac{33}{60^4} + \frac{4}{60^5} + \frac{40}{60^6}. \end{equation*}\]

Use any one of the methods of this chapter to find how good Fibonacci’s approximation was.

BB08

E. Brown and J.C. Brunson. Fibonacci's forgotten number. The College Mathematics Journal, 39:112–120, 2008.