Solution. Here \(p_n = p_{n-1}-\frac {p_{n-1}^3+4p_{n-1}^2-10}{3p_{n-1}^2+8p_{n-1}}\), and

The number of correct digits roughly doubles at each step: \(2\), \(4\), \(9\), then full double precision. The last column settles at \(0.490\), and Theorem 2.4.5 below explains this number: it is \(\frac {f''(p)}{2f'(p)} = \frac {6p+8}{2(3p^2+8p)} = 0.4902\).

Solution. With \(f(x) = \cos x-x\) and \(f'(x) = -\sin x-1\), \[p_n = p_{n-1}-\frac {\cos p_{n-1}-p_{n-1}}{-\sin p_{n-1}-1}.\] The iterates are \(p_1 = 0.7395361335\), \(p_2 = 0.7390851781\), \(p_3 = 0.7390851332\), with errors \(4.5\times 10^{-4}\), \(4.5\times 10^{-8}\) and \(4\times 10^{-16}\). Three Newton steps give full accuracy, against \(32\) steps of the fixed-point iteration \(p_n = \cos p_{n-1}\) for an error of \(10^{-6}\) (Example 2.3.9).

Proof. Newton’s method is fixed-point iteration with \(g(x) = x-\frac {f(x)}{f'(x)}\). Since \(f'\) is continuous and \(f'(p)\neq 0\), there is \(\delta _1>0\) with \(f'(x)\neq 0\) on \([p-\delta _1,p+\delta _1]\subseteq [a,b]\), so \(g\) is defined and continuous there. Its derivative is \[g'(x) = 1-\frac {f'(x)^2-f(x)f''(x)}{f'(x)^2} = \frac {f(x)f''(x)}{f'(x)^2},\] which is continuous on \([p-\delta _1,p+\delta _1]\) and equals \(0\) at \(p\) because \(f(p) = 0\). So for any \(k\in (0,1)\) there is \(0<\delta <\delta _1\) with \(|g'(x)|\leq k\) on \([p-\delta ,p+\delta ]\). For \(x\) in this interval the Mean Value Theorem gives \[|g(x)-p| = |g(x)-g(p)| = |g'(\xi )|\,|x-p|\leq k|x-p|<\delta ,\] so \(g\) maps \([p-\delta ,p+\delta ]\) into itself. By the Fixed-Point Theorem the iterates converge to \(p\). □

Proof. Taylor’s Theorem about \(p_n\), evaluated at \(p\), gives \[0 = f(p) = f(p_n)+(p-p_n)f'(p_n)+\frac {(p-p_n)^2}{2}f''(\xi _n),\] with \(\xi _n\) between \(p_n\) and \(p\). Divide by \(f'(p_n)\) and rearrange: \[p_n-\frac {f(p_n)}{f'(p_n)}-p = \frac {f''(\xi _n)}{2f'(p_n)}(p_n-p)^2,\] that is, \[p_{n+1}-p = \frac {f''(\xi _n)}{2f'(p_n)}(p_n-p)^2 .\] As \(n\longrightarrow \infty \), \(\xi _n\longrightarrow p\) and \(p_n\longrightarrow p\), and the continuity of \(f'\) and \(f''\) gives the limit. □

Solution. (a) \(f'(x) = \frac 13x^{-2/3}\), so \(p_n = p_{n-1}-\frac {p_{n-1}^{1/3}}{\frac 13p_{n-1}^{-2/3}} = p_{n-1}-3p_{n-1} = -2p_{n-1}\). From \(p_0 = 0.1\) the iterates are \(-0.2, 0.4, -0.8, 1.6,\dots \): each step doubles the distance from the root \(0\). The theorems do not apply, since \(f'(0)\) does not exist.

(b) \(f(0) = 2\), \(f'(0) = -2\) give \(p_1 = 1\); then \(f(1) = 1\), \(f'(1) = 1\) give \(p_2 = 0\), and the iterates cycle between \(0\) and \(1\) for ever (Figure 4, right). The only real root is \(p = -1.7693\), far from the starting value.

(c) \(\arctan \) is very flat far from \(0\), so its tangent lines cross the axis far away. From \(p_0 = 1.5\) the iterates are \(-1.694, 2.321, -5.114, 32.30,\dots \), which diverge. From \(p_0 = 1.3\) they are \(-1.162, 0.859, -0.374, 0.034,\dots \) and converge to \(0\). There is a critical starting value \(1.3917\) between the two behaviours.

Solution.

The secant method takes one or two more steps than Newton’s method, but each step costs one evaluation of \(f\) instead of one of \(f\) and one of \(f'\). On the test problem its first two steps coincide with false position (Example 2.2.2); from the third step on it uses the two latest points, leaves the fixed end point behind, and accelerates: the number of correct digits grows by a factor of about \(1.6\) per step.

Proof. Let \(q(x) = f(x_0)+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)\). Direct substitution shows \(q(x_0) = f(x_0)\) and \(q(x_1) = f(x_1)\), and a short calculation using the definitions shows \(q(x_2) = f(x_2)\). So \(f-q\) vanishes at three distinct points, and by the Generalized Rolle’s Theorem (Theorem 1.1.4) \((f-q)''(\xi ) = f''(\xi )-2f[x_0,x_1,x_2] = 0\) for some \(\xi \). □

Proof. In divided-difference notation the method is \(p_{n+1} = p_n-\frac {f(p_n)}{f[p_{n-1},p_n]}\). Since \(f(p) = 0\), \(f(p_n) = f[p_n,p]\,e_n\), and \[e_{n+1} = e_n-\frac {f[p_n,p]}{f[p_{n-1},p_n]}e_n = \frac {f[p_{n-1},p_n]-f[p_n,p]}{f[p_{n-1},p_n]}\,e_n = \frac {f[p_{n-1},p_n,p](p_{n-1}-p)}{f[p_{n-1},p_n]}\,e_n,\] using the definition of \(f[p_{n-1},p_n,p]\). This is the first formula. By the Mean Value Theorem and Lemma 2.4.8, \(f[p_{n-1},p_n] = f'(\eta _n)\) and \(f[p_{n-1},p_n,p] = \frac 12f''(\xi _n)\) with \(\eta _n,\xi _n\longrightarrow p\), which gives the approximation.

For the order, write \(C = \left |\frac {f''(p)}{2f'(p)}\right |\) and suppose \(|e_{n+1}|\approx A|e_n|^\alpha \). Then \(|e_n|\approx A|e_{n-1}|^\alpha \), so \(|e_{n-1}|\approx (|e_n|/A)^{1/\alpha }\), and the relation \(|e_{n+1}|\approx C|e_n||e_{n-1}|\) becomes \[A|e_n|^\alpha \approx C A^{-1/\alpha }|e_n|^{1+1/\alpha }.\] For this to hold as \(e_n\longrightarrow 0\) the exponents must agree: \(\alpha = 1+\frac 1\alpha \), that is \(\alpha ^2-\alpha -1 = 0\), whose positive root is \(\alpha = \frac {1+\sqrt 5}{2}\). (A rigorous version of this argument, with explicit bounds, is in the texts by Atkinson and by Süli and Mayers.) □