1.3 Algorithms and convergence
An algorithm is a finite sequence of unambiguous steps that produces an approximate solution of a problem. Algorithms in this course are written in a plain step-by-step form, giving the input, the output and the steps.
Two questions are asked of every algorithm: does the error introduced at one stage grow or die out at later stages, and how fast does the approximation approach the answer?
Definition 1.3.1. Suppose an error of size \(E_0>0\) is introduced at some stage of a calculation, and \(E_n\) denotes its size after \(n\) further operations. If \(E_n\approx CnE_0\) for a constant \(C\), the growth is linear; if \(E_n\approx C^nE_0\) with \(C>1\), it is exponential. An algorithm is stable if small changes in the initial data produce correspondingly small changes in the results, and unstable otherwise. Linear growth is usually acceptable; exponential growth is not.
Example 1.3.2. For any constants \(c_1, c_2\) the sequence \(p_n = c_1\left (\frac 13\right )^n+c_23^n\) satisfies the recurrence \[p_n = \tfrac {10}{3}p_{n-1}-p_{n-2},\qquad n = 2,3,\dots \] With \(p_0 = 1\) and \(p_1 = \frac 13\) the solution is \(p_n = \left (\frac 13\right )^n\). Compute \(p_n\) from the recurrence in five-digit rounding arithmetic.
Solution. That every such \(p_n\) satisfies the recurrence is checked by substitution: \(\frac {10}3\cdot \frac 13 - 1 = \frac 19\) and \(\frac {10}3\cdot 3-1 = 9\), and these are exactly the ratios \(\left (\frac 13\right )^2\) and \(3^2\). The computed values are:
| \(n\) | computed \(\hat p_n\) | exact \(p_n\) | error |
| \(0\) | \(1.0000\) | \(1.0000\) | \(0\) |
| \(1\) | \(0.33333\) | \(0.33333\ldots \) | \(3.3\times 10^{-6}\) |
| \(2\) | \(0.11110\) | \(0.11111\) | \(1.1\times 10^{-5}\) |
| \(3\) | \(0.037000\) | \(0.037037\) | \(3.7\times 10^{-5}\) |
| \(4\) | \(0.012230\) | \(0.012346\) | \(1.2\times 10^{-4}\) |
| \(5\) | \(0.0037660\) | \(0.0041152\) | \(3.5\times 10^{-4}\) |
| \(6\) | \(0.00032300\) | \(0.0013717\) | \(1.0\times 10^{-3}\) |
| \(7\) | \(-0.0026893\) | \(0.00045725\) | \(3.1\times 10^{-3}\) |
| \(8\) | \(-0.0092872\) | \(0.00015242\) | \(9.4\times 10^{-3}\) |
The rounding of \(p_1\) (and of \(\frac {10}{3}\)) means the computation actually follows a solution with a tiny non-zero \(c_2\). The term \(c_23^n\) triples at each step, so the error grows exponentially, by a factor of about \(3\) per step, and by \(n = 7\) the computed values have the wrong sign. The recurrence is unstable for this problem. By contrast the recurrence \(p_n = 2p_{n-1}-p_{n-2}\), whose solutions \(c_1+c_2n\) grow only linearly, started from the same values gives errors that grow only linearly: after eight steps in the same arithmetic the error is \(1.7\times 10^{-4}\).
Rates of convergence
Definition 1.3.3. Suppose \(\beta _n\longrightarrow 0\) and \(\alpha _n\longrightarrow \alpha \). If there is a constant \(K\) such that \(|\alpha _n-\alpha |\leq K|\beta _n|\) for all large \(n\), then \(\alpha _n\) converges to \(\alpha \) with rate of convergence \(O(\beta _n)\), and we write \(\alpha _n = \alpha +O(\beta _n)\). Usually \(\beta _n = \frac {1}{n^p}\), and we look for the largest \(p\).
Similarly, if \(G(h)\longrightarrow 0\) and \(F(h)\longrightarrow L\) as \(h\longrightarrow 0\), and \(|F(h)-L|\leq K|G(h)|\) for all sufficiently small \(h\), we write \(F(h) = L+O(G(h))\). Usually \(G(h) = h^p\).
Example 1.3.4. Show that \(\alpha _n = \frac {n+1}{n^2}\) and \(\hat \alpha _n = \frac {n+3}{n^3}\) both converge to \(0\), with rates \(O\left (\frac 1n\right )\) and \(O\left (\frac 1{n^2}\right )\).
Solution. For \(n\geq 1\), \(\alpha _n = \frac 1n+\frac 1{n^2}\leq \frac 2n\) and \(\hat \alpha _n = \frac 1{n^2}+\frac 3{n^3}\leq \frac 4{n^2}\), so \(K = 2\) and \(K = 4\) will do. At \(n = 100\), \(\alpha _n = 0.0101\) and \(\hat \alpha _n = 0.000103\): the second sequence is about \(100\) times closer to its limit, as the rates predict.
Example 1.3.5. Show that \(\dfrac {\sin h}{h} = 1+O(h^2)\) and \(\cos h + \frac 12h^2 = 1+O(h^4)\) as \(h\longrightarrow 0\).
Solution. By Taylor’s Theorem, \(\sin h = h - \frac {h^3}{6}+\frac {h^5}{120}\cos \xi \), so \[\left |\frac {\sin h}{h}-1\right | = \left |-\frac {h^2}{6}+\frac {h^4}{120}\cos \xi \right |\leq \frac {h^2}{6}+\frac {h^4}{120}\leq \frac {h^2}{5}\] for \(|h|\leq 1\). Similarly \(\cos h = 1-\frac {h^2}{2}+\frac {h^4}{24}\cos \tilde \xi \), so \(\left |\cos h+\frac {h^2}{2}-1\right |\leq \frac {h^4}{24}\). Numerically, \(\frac {\sin 0.1}{0.1} = 0.998334\) and \(\frac {\sin 0.01}{0.01} = 0.99998333\): reducing \(h\) by a factor of \(10\) reduces the error by a factor of \(100\), as \(O(h^2)\) predicts.
Definition 1.3.6. Suppose \(p_n\longrightarrow p\) with \(p_n\neq p\) for all \(n\). If there are constants \(\lambda >0\) and \(\alpha \geq 1\) with \[\lim _{n\rightarrow \infty }\frac {|p_{n+1}-p|}{|p_n-p|^\alpha } = \lambda ,\] then \(\{p_n\}\) converges to \(p\) with order \(\alpha \) and asymptotic error constant \(\lambda \). Order \(\alpha = 1\) (with \(\lambda <1\)) is linear convergence and \(\alpha = 2\) is quadratic convergence.
Example 1.3.7. Compare a linearly convergent sequence with \(\frac {|p_{n+1}-p|}{|p_n-p|} = 0.5\) and a quadratically convergent sequence with \(\frac {|p_{n+1}-p|}{|p_n-p|^2} = 0.5\), both starting with \(|p_0-p| = 1\). How many terms does each need to reach an error of \(10^{-14}\)?
Solution. For the linear sequence \(|p_n-p| = 0.5^n\), which first falls below \(10^{-14}\) when \(n = 47\). For the quadratic one, \(|p_n-p| = 0.5|p_{n-1}-p|^2\), which gives \(|p_n-p| = 0.5^{2^n-1}\): \[0.5,\quad 0.125,\quad 7.8\times 10^{-3},\quad 3.1\times 10^{-5},\quad 4.7\times 10^{-10},\quad 1.1\times 10^{-19},\] so six steps suffice, against \(47\). Quadratic convergence roughly doubles the number of correct digits at each step. This difference is why Newton’s method, which converges quadratically, is so widely used.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.