Proof. If the derivatives vanish as stated, Taylor’s Theorem of order \(m-1\) about \(p\) gives \(f(x) = \frac {f^{(m)}(\xi (x))}{m!}(x-p)^m\), so \(q(x) = \frac {f^{(m)}(\xi (x))}{m!}\longrightarrow \frac {f^{(m)}(p)}{m!}\neq 0\). Conversely, suppose \(f(x) = (x-p)^mq(x)\) with \(q(x)\longrightarrow L\neq 0\). If some \(f^{(j)}(p)\neq 0\) with \(j<m\), take the smallest such \(j\); by what was just shown, \(f(x) = (x-p)^jr(x)\) with \(r(x)\longrightarrow \frac {f^{(j)}(p)}{j!}\neq 0\), and then \((x-p)^{m-j}q(x) = r(x)\) would tend both to \(0\) and to a non-zero limit. So \(f^{(j)}(p) = 0\) for \(j<m\); and \(f^{(m)}(p) = m!\,L\neq 0\) by the first part. □

Proof. We prove it for \(f(x) = (x-p)^mq(x)\) with \(q\) differentiable and \(q(p)\neq 0\). Then \(f'(x) = (x-p)^{m-1}\bigl (mq(x)+(x-p)q'(x)\bigr )\) and \[g(x) = x-\frac {f(x)}{f'(x)} = x-\frac {(x-p)q(x)}{mq(x)+(x-p)q'(x)} .\] Hence \begin {align*} \frac {g(x)-p}{x-p} &= 1-\frac {q(x)}{mq(x)+(x-p)q'(x)}\\ &\longrightarrow 1-\frac {q(p)}{mq(p)} = 1-\frac 1m\quad (x\longrightarrow p). \end {align*}

So \(g'(p) = 1-\frac 1m\in (0,1)\), and Corollary 2.3.10 gives linear convergence with this constant. □

Solution. Newton’s method. The iterates are \[0.582,\ 0.319,\ 0.168,\ 0.0863,\ 0.0438,\ 0.0221,\ 0.0111,\ 0.00554,\ 0.00278,\ 0.00139,\] each almost exactly half the previous one, as Theorem 2.5.3 predicts with \(m = 2\). Ten steps give only three correct decimals.

Remedy 1: using the multiplicity. If \(m\) is known, the iteration \(p_n = p_{n-1}-m\frac {f(p_{n-1})}{f'(p_{n-1})}\) restores quadratic convergence (Problem 2.6.6). With \(m = 2\) the iterates are \(1.6\times 10^{-1}\), \(4.5\times 10^{-3}\), \(3.3\times 10^{-6}\), \(1.1\times 10^{-11}\).

Remedy 2: modified Newton. If \(m\) is unknown, apply Newton’s method to \(\mu (x) = \frac {f(x)}{f'(x)}\), which has a simple zero at \(p\) (if \(f = (x-p)^mq\) then \(\mu = \frac {(x-p)q}{mq+(x-p)q'}\)). Since \(\mu ' = \frac {f'^2-ff''}{f'^2}\), this gives \[p_n = p_{n-1}-\frac {f(p_{n-1})f'(p_{n-1})}{f'(p_{n-1})^2-f(p_{n-1})f''(p_{n-1})} .\] The iterates are \(-2.3\times 10^{-1}\), \(-8.5\times 10^{-3}\), \(-1.2\times 10^{-5}\), \(-4.2\times 10^{-11}\), and then they stop improving.

The stall is a round-off effect, not a flaw of the method. Near a double root \(f(x)\approx \frac {x^2}{2}\) is computed as the difference of nearly equal numbers \(e^x\) and \(x+1\), with an absolute error of order \(10^{-16}\); so \(f\) cannot be distinguished from \(0\) once \(\frac {x^2}{2}\lesssim 10^{-16}\), that is \(|x|\lesssim 10^{-8}\), and no method can locate a double root more accurately than about the square root of the machine precision. The modified formula, which divides by a difference of small quantities, loses a little more.

Proof. Write \(e_n = p_n-p\) and \(e_{n+1} = (\lambda +\delta _n)e_n\) with \(\delta _n\longrightarrow 0\). Then \begin {align*} \Delta p_n &= e_{n+1}-e_n = (\lambda -1+\delta _n)e_n,\\ \Delta ^2p_n &= e_{n+2}-2e_{n+1}+e_n = \bigl ((\lambda +\delta _{n+1})(\lambda +\delta _n)-2(\lambda +\delta _n)+1\bigr )e_n . \end {align*}

Hence \begin {align*} \frac {\hat p_n-p}{p_n-p} &= 1-\frac {(\Delta p_n)^2}{e_n\Delta ^2p_n} = 1-\frac {(\lambda -1+\delta _n)^2}{(\lambda +\delta _{n+1})(\lambda +\delta _n)-2(\lambda +\delta _n)+1}\\ &\longrightarrow 1-\frac {(\lambda -1)^2}{(\lambda -1)^2} = 0, \end {align*}

where \(\lambda \neq 1\) ensures that the denominator tends to \((\lambda -1)^2\neq 0\). □

Solution. (a)

The accelerated values are several times closer to \(1\), and the advantage grows with \(n\).

(b) From \(p_0 = 1\), the first Aitken values are \(0.72801\), \(0.73367\), \(0.73691\), \(0.73805\), \(0.73864\), with errors decreasing from \(1.1\times 10^{-2}\) to \(4.5\times 10^{-4}\), compared with \(2.6\times 10^{-1}\) to \(5.4\times 10^{-2}\) for the corresponding \(p_n\). The iteration itself is untouched; the extra accuracy comes from post-processing three consecutive terms.

Solution. The successive Aitken values are \[0.728010361468,\quad 0.739066966909,\quad 0.739085133166,\] with errors \(1.1\times 10^{-2}\), \(1.8\times 10^{-5}\) and \(4.9\times 10^{-11}\). Each new error is roughly the square of the previous one times a constant: quadratic convergence from an iteration that, used plainly, converges linearly with ratio \(0.674\). Each Steffensen step costs two evaluations of \(g\).