1.3 Speed

In numerical analysis, we typically know that a sequence converges, unlike Intro to Real Analysis, so instead we are concerned with the speed of convergence.

We have a sequence $⟨ p_{n} ⟩$ with $lim_{n \to \infty} p_{n} = p$ .

Order of Convergence of a Sequence

$⟨ p_{n} ⟩$ converges with order $α \geq 1$ if

\lim_{n \to \infty} \frac{| p_{n + 1} - p |}{| p_{n} - p |^{α}} = λ

for some real number $λ > 0$

α \approx \frac{\ln | \frac{p_{n + 2} - p}{p_{n + 1} - p} |}{\ln | \frac{p_{n + 1} - p}{p_{n} - p} |} .

Order and Significant Digits

Relating this to significant digits we get:

\begin{array}{rcl} | p_{n + 1} - p | & \approx & λ | p_{n} - p |^{α} \\ | \frac{p_{n + 1} - p}{p} | & \approx & λ {| \frac{p_{n} - p}{p} |}^{α} \cdot | p |^{α - 1} \\ - \log | \frac{p_{n + 1} - p}{p} | & \approx & - \log {| \frac{p_{n} - p}{p} |}^{α} - \log (λ | p |^{α - 1}) \\ d (p_{n + 1}) & \approx & α d (p_{n}) - \log (λ | p |^{α - 1}) . \end{array}

for linear convergence $(α = 1), d (p_{n + 1}) \approx d (p_{n}) - l o g λ$ , so each term has a fixed number more significant digits of accuracy (approximately equal to $- l o g λ$ ) than the previous;
for quadratic convergence $(α = 2), d (p_{n + 1}) \approx 2 d (p_{n}) - l o g (λ | p |)$ , so each term has double the number of significant digits of accuracy of the previous, give or take some;
for cubic convergence $(α = 3), d (p_{n + 1}) \approx 3 d (p_{n}) - l o g (λ | p |^{2})$ , so each term has triple the number of significant digits of accuracy of the previous, give or take some

and so on

It can be shown for $α > 1$ that

d (p_{n_{0} + k}) \approx (d_{n_{0}} - C) α^{k} + C

where

C = \frac{\log (λ | p |^{α - 1})}{α - 1} .

Rate of Convergence

The sequence $⟨ p_{n} ⟩$ converges to p with the rate of convergence $O (b_{n})$ if

$⟨ b_{n} ⟩$ converges to 0 and

| p_{n} - p | \leq λ | b_{n} |

for some real number $λ > 0$ and all sufficiently large $n$

usual comparison:

$b_{n} = \frac{1}{n^{P}}$ or $\frac{1}{a^{n}}$