Practice versus asymptotic statements about the speed of convergence.

Question

In basic numerical analysis, it is shown that Aitken's method improves on the basic iteration method in speed of convergence in the asymptotic sense (see detail below if desired). Now it seems that this should be meaningless in practice, giving no guarantees of 'faster' for any finite number of iterations. I found that this is not only my feeling, but that this concern is echoed in this Wikipedia article:

Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of practical importance in dealing with a sequence of successive approximations for an iterative method, as then typically fewer iterations are needed to yield a useful approximation if the rate of convergence is higher. This may even make the difference between needing ten or a million iterations insignificant.

My questions then are

1. Barring empirical evidence, is there ANY formal way of turning the asymptotic result into a result in terms of finite iterations? Even at least probabilistically? Even when conditions are added? This would be an example of what I have in mind: Given a function with condition such and such (smooth, etc.), the convergence is indeed faster in $n$ iterations with probability $p(n)$.

2. If there are such results, can you point me to some of them?

3. If there are no such results, should there be no interest in trying to find them? If not why not?

4. Doesn't this state of affairs 'bother' numerical analysts? If not shouldn't it?

5. Do people reading this have their own 'intuitions' about when the speed of convergence holds in practice? What are these intuitions? Why not try to formalise them?

Detail

When the series $\{x_n\}$ generated using $x_i = f(x_{i-1})$ converges under the usual conditions, Aitken's method, generating the series $\{x'_n\}$ using $$ x'_n = x_n - \dfrac{(x_{n+1}-x_n)^2}{(x_{n+2}-2x_{n+1}+x_n)} $$ converges faster in the sense that, with $s$ being the solution $f(s)=s$, we have $$ \dfrac{x'_n-s}{x_n-s} \to 0, n \to \infty. $$

Answer 1

Doesn't this state of affairs 'bother' numerical analysts? If not shouldn't it?

No. It is a daily occurrence that a numerical analyst codes up an algorithm which has better theoretical scaling/convergence only to find out that another with 'worse' theoretical bounds performs better for the application at hand. An example is that Gauss-Kronrod quadrature is faster than double-exponential quadrature at double precision, even though double-exponential quadrature has faster theoretical convergence. (However, it turns out that for higher precision, double-exponential wins.)

Do people reading this have their own 'intuitions' about when the speed of convergence holds in practice? What are these intuitions? Why not try to formalise them?

I don't use my intuition because it's been wrong so often. I use logging and performance benchmarks to watch the convergence rate for the problem at hand. On the other hand, the ideas of backwards stability, condition number, algorithmic scaling and convergence are nonetheless the best theoretical guideposts we have.

Answer 2

1. Barring empirical evidence, is there ANY formal way of turning the asymptotic result into a result in terms of finite iterations? Even at least probabilistically? Even when conditions are added? This would be an example of what I have in mind: Given a function with condition such and such (smooth, etc.), the convergence is indeed faster in $n$ iterations with probability $p(n)$.

2. If there are such results, can you point me to some of them?

Most algorithms come equipped with fairly convoluted conditions and specifications for how fast they converge (findable in most papers which discuss the error analysis of a method). In your specific case, Aitken's method for fixed-point iteration depends on whether or not $g(x)=f(x)-x$ can be linearly approximated well near the root (out to how far your iterations start off). The precise measurement of "how well it can be linearly approximated" is given by $g''(x)/g'(x)=f''(x)/(f'(x)-1)$, which is known in some contexts as the curvature of $g$. The only remaining issue is then how sure you are that this curvature is small for your given function.

3. If there are no such results, should there be no interest in trying to find them? If not why not?

In the general asymptotic case, this is not important except in extreme cases. If the curvature is infinite i.e. $f'(x)=1$ then Aitken's method will converge slower than expected. If the curvature is $0$ then Aitken's method will converge faster than expected.

The issue, however, is that one usually does not know the curvature (or the relevant properties of the function for some method) when trying it out. More often it is the case that trying something out and seeing where it goes is easier than trying to work out the rigor, which may in fact be a harder problem to solve.

4. Doesn't this state of affairs 'bother' numerical analysts? If not shouldn't it?

As user14717 says, this is not a major issue. There is a saying that there is 'no free lunch', which means it should not be expected that there is a "one approach to solve every problem optimally". Different methods work better for different cases, this can only be expected.

5. Do people reading this have their own 'intuitions' about when the speed of convergence holds in practice? What are these intuitions? Why not try to formalise them?

Going back to the first point, Aitken's method depends most greatly on whether or not $f'(x)=1$ at the point of interest. Checking how $f(x)$ and $x$ look graphically is one way to gain some 'intuition' on how fast Aitken's method will converge, but going back to the first point, this often can't be done or is harder than the intended problem.