# What is the convergence order and asymptotic error constant for these results?

Define order of convergence and asymptotic error constant for a numerical method for equation solving. Two different methods have been used to solve the equations f(x)=0. Runs in Matlab give the results

Metod 1                Metod 2
=======                =======
x dx                   x           dx
4.1667e-01 -8.3333e-02 3.7500e-01 -1.2500e-01
3.9120e-01 -2.5463e-02 3.8194e-01 6.9444e-03
3.8435e-01 -6.8569e-03 3.8197e-01 2.1567e-05
3.8257e-01 -1.7726e-03 3.8197e-01 2.0801e-10
3.8212e-01 -4.5316e-04
3.8201e-01 -1.1551e-04
3.8198e-01 -2.9421e-05
3.8197e-01 -7.4924e-06
3.8197e-01 -1.9079e-06
3.8197e-01 -4.8584e-07


x is an approximation to the root and dx is the number with which the previous approximation has been corrected. Which conclusions can be drawn about the convergence of the methods (order of convergence, asumptotic error constant) ?

I know that the order of a method is p iff

lim as n goes to infinity for (X(n)-B)/(X(n-1)-B)^p=constant and not zero.

where B is the true number and X is the measure. But I don't know how to apply this knowledge to this actual case.

-
Assuming that the dx is a good measure of distance to a root, then method 1 looks linearly convergent with rate $\approx \frac{1}{4}$, and method 2 looks quadratic. With linear convergence, the exponents are roughly linear in iteration, with quadratic the exponents double with each iteration (roughly). –  copper.hat Sep 20 '12 at 5:54
@copper.hat: I think you could post that comment as an answer? –  joriki Sep 20 '12 at 8:19
yes, I think copper.hat's comment answers the question but it could be expanded with a more detailed explaination since this is a homework question that also is asking for some background about the methods in use. Thank you for your comments. –  Niklas in Stockholm Sep 21 '12 at 6:03

Following Joriki's suggestion:

When looking at convergence rates, a common estimate of error used is $e_{n+1} \leq K e_n^p$, with $p \geq 1$, $K >0$ and $e_n\geq 0$. It is simpler to split the approach into two cases, $p=1$ and $p >1$.

$p=1$ is referred to as linear convergence, and it is straightforward to see that $e_n \leq K^n e_0$. $K$ is referred to as the rate, and is only meaningful in this context if $K<1$. Taking log of the bound gives $n \log K + \log e_0$, so assuming that $e_{n+1} \approx K e_n$, plotting $\log e_n$ vs. $n$ will be roughly a straight line which will give an estimate of $K$. (An estimate of $K$ can also be found by just computing $\frac{e_{n+1}}{e_n}$.)

Assuming that $e_n \approx |\text{dx}|$ above, plotting $\log e_n$ vs. $n$ gives the following for Method 1.

This is about as straight as one can hope for, with slope $-1.3392$ which gives $K \approx e^{-1.3392} \approx 0.26$. Hence Method 1 is linear with a rate of about a quarter.

Plotting $\log e_n$ vs. $n$ for Method 2 gives:

so this doesn't fit a linear (affine) model nicely. In fact, it converges considerably faster. This lead us to the second case:

$p>1$ is referred to as superlinear convergence. In this case, the rate $K$ is of much less consequence (assuming $e_n \to 0$, of course), and $p$ is referred to as the order. Superlinear convergence is dramatically faster than linear convergence, and is very desirable.

To get a handle on superlinear convergence, we multiply the error estimate by $K^{\frac{1}{p-1}}$ to get $K^{\frac{1}{p-1}} e_{n+1} \leq K^{\frac{1}{p-1}} K e_n^p = (K^{\frac{1}{p-1}} e_n)^p$. This gives $K^{\frac{1}{p-1}} e_n \leq (K^{\frac{1}{p-1}} e_0)^{p^k}$. This illustrates how quickly the error is reduced and, of course, is only useful if $K^{\frac{1}{p-1}} e_0 < 1$.

One way of estimating $p$ is to again assume $e_{n+1} \approx K e_n^p$ and take logs, which gives $\log e_{n+1} \approx \log K + p \log e_n$. If we plot $\log e_{n+1}$ vs. $\log e_n$, we should be able to estimate $p$ from the slope. So, plotting $\log e_{n+1}$ vs. $\log e_n$ for Method 2 gives:

which is pretty straight. A quick slope estimate using the end points gives $p \approx 1.993 \approx 2$. Hence this is likely to be quadratically convergent.

Note that from a numerical standpoint, the exponent of the error (as in exponent and mantissa of the decimal representation) is a quick proxy for $\log e_n$. Hence for linear convergence, we expect the exponent to decrease linearly (well, affinely) with iteration. For quadratic convergence, we expect the exponent to double with each iteration. A quick glance will indeed confirm this to be the case above.

-