Rate of Convergence

Convergence Has a Speed as Well as a Limit

Knowing that \(a_n\to L\) tells us that the terms eventually lie as close as we wish to \(L\). It does not tell us how many terms are needed to achieve a given accuracy. For that, we study the error \(e_n=|a_n-L|\) and how it changes from one index to the next. This is the rate of convergence.

The previous tutorial considered fixed points and recursive sequences. When a recursion converges to a fixed point, the error often gives more information than the fixed-point equation alone: it can reveal whether the iteration approaches the fixed point at a roughly geometric pace or accelerates as it gets closer. We will first define rates in terms of errors, then prove that a limiting error ratio below one gives a geometric error bound.

Definition: Let \(a_n\to L\), and define the error \(e_n=|a_n-L|\). If \(e_n>0\) for all sufficiently large \(n\), the asymptotic error ratio is the limit, when it exists, of \(e_{n+1}/e_n\). If this limit is \(q\) with \(0<q<1\), the sequence converges linearly with asymptotic ratio \(q\). If the limit is \(0\), the sequence converges superlinearly. If \(e_n=0\) from some index onward, the sequence reaches its limit in finitely many steps instead.

The ratio compares consecutive errors, not consecutive terms of the original sequence. An asymptotic ratio \(q\) near zero indicates strong error reduction at each step; a ratio nearer one indicates less reduction. Linear convergence does not mean that the terms \(a_n\) form a linear sequence. The word describes the eventual proportional decrease in error.

A Ratio Below One Gives a Geometric Error Bound

Theorem (Geometric Error Bound from an Error Ratio): Suppose \(a_n\to L\), \(e_n=|a_n-L|>0\) for all sufficiently large \(n\), and \(e_{n+1}/e_n\to q\) for some \(q\in[0,1)\). For every \(r\) with \(q<r<1\), there are a constant \(C>0\) and an index \(N\) such that \(e_n\leq Cr^n\) for every \(n\geq N\).

Proof. Fix \(r\) with \(q<r<1\). Since \(e_{n+1}/e_n\to q\), the definition of convergence, applied with the positive tolerance \(r-q\), gives an index \(N\) such that

\left|\frac{e_{n+1}}{e_n}-q\right|<r-q \qquad\text{for every }n\geq N.

In particular, \(e_{n+1}/e_n<q+(r-q)=r\). Because the errors are positive, this implies \(e_{n+1}<re_n\) for every \(n\geq N\). Repeated application gives, for each integer \(k\geq0\),

e_{N+k}\leq e_Nr^k.

Set \(C=e_Nr^{-N}\), which is positive because \(e_N>0\). For \(n\geq N\), take \(k=n-N\) in the preceding inequality:

e_n\leq e_Nr^{n-N}=e_Nr^{-N}r^n=Cr^n.

This proves the claimed geometric bound. The ratio limit gives a bound with every \(r\) strictly larger than \(q\); it does not, in general, give the exact inequality \(e_n\leq Cr^n\) with \(r=q\). \(\square\)

Worked Example: An Affine Recursion Has a Geometric Rate

Consider \(a_{n+1}=\frac13a_n+\frac23\), with any initial value \(a_0\in\mathbb{R}\). The value \(L=1\) is a fixed point because \(\frac13(1)+\frac23=1\). Subtracting this equation from the recursion gives

a_{n+1}-1=\frac13(a_n-1).

Taking absolute values shows that \(e_{n+1}=\frac13e_n\), so, if \(a_0\neq1\), induction yields \(e_n=|a_0-1|(1/3)^n\). In particular, the error ratio is exactly \(1/3\) at every index. The sequence converges to \(1\), and its error decreases by the same factor on every step. If \(a_0=1\), it is already at the limit and remains there.

Root Rates and Their Relation to Error Ratios

There is another way to express a geometric rate: take the \(n\)-th root of the error. Under a limiting error ratio, this root has the same limit. The root rate measures the average multiplicative decrease across the first \(n\) steps, whereas the ratio measures the decrease in a single step.

Theorem (Root Rate from a Limiting Error Ratio): Suppose \(e_n>0\) for all sufficiently large \(n\), and \(e_{n+1}/e_n\to q\in[0,1)\). Then \(e_n^{1/n}\to q\).

Proof. Fix any \(r\) with \(q<r<1\). By the geometric error bound just proved, there are \(C>0\) and \(N\) such that \(e_n\leq Cr^n\) for \(n\geq N\). Taking \(n\)-th roots gives

e_n^{1/n}\leq C^{1/n}r.

Since \(C^{1/n}\to1\), this implies \(\limsup e_n^{1/n}\leq r\). As this holds for every \(r>q\), the upper limit is at most \(q\). More explicitly, if the upper limit were larger than \(q\), one could choose \(r\) strictly between \(q\) and that upper limit, contradicting the bound.

If \(q=0\), the errors are nonnegative, and the upper-limit bound for every \(r>0\) gives \(e_n^{1/n}\to0\). Now suppose \(q>0\). Choose any \(s\) with \(0<s<q\). The ratio limit gives an index \(N_s\) such that \(e_{n+1}/e_n>s\) whenever \(n\geq N_s\). Iterating this inequality yields

e_n\geq e_{N_s}s^{n-N_s} \qquad\text{for }n\geq N_s.

Taking \(n\)-th roots shows that the lower limit of \(e_n^{1/n}\) is at least \(s\), since \((e_{N_s}s^{-N_s})^{1/n}\to1\). This is true for every \(s\) with \(0<s<q\), so the lower limit is at least \(q\). Together with the upper-limit bound, this proves \(e_n^{1/n}\to q\). \(\square\)

Worked Example: Factorial Errors Converge Superlinearly

Let \(a_n=1+\frac{1}{(n+1)!}\), so \(a_n\to1\) and \(e_n=\frac{1}{(n+1)!}\). Direct calculation gives

\frac{e_{n+1}}{e_n} = \frac{1/(n+2)!}{1/(n+1)!} = \frac{(n+1)!}{(n+2)!} = \frac{1}{n+2} \longrightarrow0.

Thus the sequence converges superlinearly. The error ratio records the increasingly strong reduction: the next error is the current error divided by \(n+2\). The root-rate theorem also gives \(e_n^{1/n}\to0\). This example illustrates that superlinear convergence is more than having a fixed geometric factor less than one: the factor itself tends to zero.

Higher-Order Convergence

An error can decrease faster than linearly in a more specific way. A common situation is that the next error is approximately a constant times a power of the current error. This leads to the standard notion of order of convergence.

Definition: Suppose \(e_n>0\) eventually. The convergence has order \(p\) with asymptotic error constant \(\lambda\) if \(p\geq1\), \(\lambda>0\), and \(e_{n+1}/e_n^p\to\lambda\). When \(p=1\), this is linear convergence with ratio \(\lambda\), provided \(0<\lambda<1\). When \(p>1\), it is superlinear convergence; \(p=2\) is called quadratic convergence.

For \(p>1\), the ratio \(e_{n+1}/e_n\) tends to zero when the errors tend to zero, because

\frac{e_{n+1}}{e_n} = \frac{e_{n+1}}{e_n^p}e_n^{p-1},

where the first factor tends to \(\lambda\) and the second tends to zero. Thus a verified order \(p>1\) implies superlinear convergence. The converse need not identify an order greater than one: a ratio tending to zero alone does not say that the error behaves like a particular power of its previous value.

Worked Example: Newton’s Method Has Quadratic Error for the Square Root of Two

Start with \(x_0=2\) and define \(x_{n+1}=\frac12(x_n+2/x_n)\). We verify both that the iterates approach \(\sqrt2\) and that their errors have order two. If \(x_n>\sqrt2\), then

x_{n+1}-\sqrt2 = \frac{x_n+2/x_n-2\sqrt2}{2} = \frac{(x_n-\sqrt2)^2}{2x_n} >0.

Also, \(x_{n+1}\leq x_n\) whenever \(x_n^2\geq2\), because \(x_n+2/x_n\leq2x_n\) is equivalent, after multiplying by \(x_n>0\), to \(2\leq x_n^2\). Since \(x_0=2>\sqrt2\), induction shows that \(x_n>\sqrt2\) and \(x_{n+1}\leq x_n\) for every \(n\). The sequence is decreasing and bounded below, so the Monotone Convergence Theorem gives a limit \(L\geq\sqrt2\). The recursion is continuous for positive inputs, so the theorem A Continuous Recursive Limit Is a Fixed Point gives \(L=\frac12(L+2/L)\). Multiplying by \(2L\) yields \(2L^2= L^2+2\), hence \(L^2=2\); since \(L\geq\sqrt2\), \(L=\sqrt2\).

Now put \(e_n=x_n-\sqrt2\), which is positive. The exact error identity above gives

\frac{e_{n+1}}{e_n^2}=\frac{1}{2x_n}\longrightarrow\frac{1}{2\sqrt2}.

Therefore this iteration converges quadratically, with asymptotic error constant \(1/(2\sqrt2)\). The formula says that, sufficiently near the limit, each new error is approximately a fixed constant times the square of the previous error.

Why a Ratio of One Does Not Settle the Rate

A ratio tending to one is not evidence that a sequence fails to converge. It means that the ratio test used above does not supply a geometric factor strictly below one. Different sequences can all have ratio one while their errors decrease at different speeds.

Worked Example: Two Polynomial Error Rates with the Same Ratio Limit

For \(a_n=1+\frac{1}{n+1}\), the error is \(e_n=1/(n+1)\), which tends to zero. Its ratio is

\frac{e_{n+1}}{e_n} = \frac{1/(n+2)}{1/(n+1)} = \frac{n+1}{n+2} \longrightarrow1.

For \(b_n=1+\frac{1}{(n+1)^2}\), the error is \(d_n=1/(n+1)^2\), which also tends to zero, and

\frac{d_{n+1}}{d_n} = \frac{1/(n+2)^2}{1/(n+1)^2} = \left(\frac{n+1}{n+2}\right)^2 \longrightarrow1.

Both sequences have ratio limit one, yet the second error is the square of the first error at every index: \(d_n=e_n^2\). Thus the limiting ratio alone does not distinguish these polynomial rates. In particular, it cannot be used to conclude that convergence is geometric, linear, or slow.

When measuring convergence, check what the chosen quantity actually tells you. A ratio tending to \(q<1\) gives an eventual geometric bound, while a ratio tending to zero gives superlinear convergence. An order calculation such as \(e_{n+1}/e_n^2\to\lambda>0\) provides more precise information about how a recursive method behaves near its limit. If the ratio tends to one, use another estimate—such as an explicit error formula—to compare rates.

Check Your Understanding

Use the definitions and results in this tutorial to answer the following questions.

What quantity is compared in the asymptotic error ratio, and why is it different from the difference \(a_{n+1}-a_n\)?
If \(e_{n+1}/e_n\to q\) with \(0\leq q<1\), why can one obtain a geometric bound with any factor \(r\) satisfying \(q<r<1\)?
What does the root-rate theorem say about \(e_n^{1/n}\) when the error ratio tends to \(q\in[0,1)\)?
Why does an error ratio tending to one fail to determine a unique convergence rate?
In the Newton iteration example, what limit does \(e_{n+1}/e_n^2\) have, and what does that say about the order of convergence?

What You'll Learn