# Prove that Aitken's method improves the speed of convergence

About Aitken's $\Delta^2$ Method:

The objective is to find the fixed point of a function. But with the other methods, we may have a sequence which converges to our fixed point very slowly. The Aitken method provides a new sequence with respect to the previous one, which converges to the fixed point faster. If we denote the previous sequence by $\{\ p_n \}$, the new sequence which Aitken method gives us is defined as below:

$\large\hat{p}_n := p_n - \frac{(p_{n+1}-p_n)^2}{p_n-2p_{n+1}+p_{n+2}}$

Question:

Suppose that $\{p_n\}$ is a sequence that converges linearly to $p$ and for all sufficiently large values of $n$ we have $(p_n-p)(p_{n+1}-p) \gt 0$ . Then the sequence $\{ \hat{p}_n \}$ generated by Aitken's $\Delta^2$ method converges to $p$ faster than $\{p_n\}$ in the sense that :
$\operatorname{lim}_{n\to\infty} \frac{\hat{p}_n-p}{p_n-p}=0$

My try:

$\large\operatorname{lim}_{n\to\infty} \frac{\hat{p}_n-p}{p_n-p} = \operatorname{lim}_{n\to\infty} \frac{p_n - \frac{(p_{n+1}-p_n)^2}{p_n-2p_{n+1}+p_{n+2}}-p}{p_n-p} =1- \operatorname{lim}_{n\to\infty} \frac{\frac{(p_{n+1}-p_n)^2}{p_n-2p_{n+1}+p_{n+2}}}{p_n-p}$

So, it suffices to show that $\operatorname{lim}_{n\to\infty} \frac{\frac{(p_{n+1}-p_n)^2}{p_n-2p_{n+1}+p_{n+2}}}{p_n-p}=1$

But how can we continue this? It seems like a dead-end...

Any idea?

Note: The question is picked from this link. (Page 3)

If your fixed point iteration is $$x_+=f(x)$$, then you need to consider that the sequence produced by the Aitken iteration restarts the slower iteration at each new value. That is, after $$\hat p_n$$ is computed, the next step starts with a sequence $$p_n^0=\hat p_n$$, $$p_n^1=f(p_n^0)$$, $$p_n^2=f(p_n^1)$$ and then computes $$\hat p_{n+1}=p_n^0-\frac{(p_n^1-p_n^0)^2}{p_n^2-2p_n^1+p_n^0}$$ If you do not take this into account, the sequence $$\hat p_n$$ is "riding piggy-back" on the sequence $$p_n$$, $$\hat p_n$$ being computed from the triple $$p_n,p_{n+1},p_{n+2}$$. This will eliminate the leading geometric term of the error, to be replaced by another geometric leading term.

Writing $$g(x)=f(x)-x$$, the Aitken iteration can also be written via the formula of Steffensen's method $$\hat p_{n+1}=\hat p_n-\frac{g(\hat p_n)^2}{g(\hat p_n+g(\hat p_n))-g(\hat p_n)}$$ where the superlinear convergence follows from its closeness to Newton's method.

It may help to express the error iteration in the errors $$e_n=p_n-p$$ so that then in your notation $$\frac{\hat p_n-p}{p_n-p}=1-\frac{(e_{n+1}-e_n)^2}{e_n(e_{n+2}-2e_{n+1}+e_n)} =\frac{e_ne_{n+2}-e_{n+1}^2}{e_n(e_{n+2}-2e_{n+1}+e_n)}$$ Now if $$e_{n+1}=qe_n+o(e_n)$$ then $$e_{n+2}=q^2e_n+o(e_n)$$ and $$\frac{\hat p_n-p}{p_n-p}=\frac{q^2e_n^2-q^2e_n^2+o(e_n^2)}{e_n(q^2e_n-2qe_n+e_n+o(e_n))}=\frac{o(1)}{(1-q)^2+o(1)}$$ This means by the definition of the Landau notation that $$\lim_{n\to\infty}\frac{\hat p_n-p}{p_n-p}=0$$. The piggy-backed Aitken series converges faster than the original series. But how much faster?

If the iteration formula $$f$$ is twice differentiable, then considering the quadratic Taylor expansion in $$p$$ gives $$e_{n+1}=f(p+e_n)-p=qe_n+re_n^2+o(e_n^2)$$ Then the next iterate is $$e_{n+2}=q^2e_n+qre_n^2+rq^2e_n^2+o(e_n^2)$$ and thus the result of the Aitken formula \begin{align} \hat p_n-p &=\frac{q^2e_n^2+r(q+q^2)e_n^3-(q^2e_n^2+2rqe_n^3)+o(e_n^3)}{(q^2e_n+qre_n^2+rq^2e_n^2)-2(qe_n+re_n^2)+e_n+o(e_n^2)}\\[1em] &=\frac{-rq(1-q)e_n^3+o(e_n^3)}{(1-q)^2e_n+r(q+q^2-2)e_n^2+o(e_n)} \\[1em] &=-\frac{rq}{(1-q)-(2+q)re_n}e_n^2+o(e_n^2). \end{align} This result gives two insights. First, the convergence of the piggy-backed series $$\hat p_n$$ is still linear, however now with the smaller quotient $$q^2$$. The second insight is that $$\frac{\hat p_n-p}{(p_n-p)^2}\to-\frac{rq}{1-q}$$ is bounded, which can be interpreted as quadratic convergence for the continuously restarted Aitken iteration.

• Can you write it without the "O" notation? – Arman Malekzadeh Oct 26 '17 at 12:31
• I could, but why? Instead of $e_{n+1}=qe_n+o(e_n)$ one would have to write $e_{n+1}=q_ne_n$ with $q_n\to q$ or $e_{n+1}=(q+d_n)e_n$ with $d_n\to 0$ which introduces lots of auxiliary null sequences and their combinations to again different null sequences. – LutzL Oct 26 '17 at 12:36
• Ok, So please explain that how the limit i write in the question equals to $0$ – Arman Malekzadeh Oct 26 '17 at 12:49
• The $q_n$ way might work, the to be considered fraction then becomes $\frac{(q_{n+1}-q_n)q_n}{(1-q_n)^2+(q_{n+1}-q_n)q_n}$ which converges to zero as $q_{n+1}-q_n$ does. – LutzL Oct 26 '17 at 12:51
• $o(1)$ or $o(e_n^0)$ is a class of sequences that converges towards zero, as in general $u_n\in o(e_n^k)$ means that $u_n/e_n^k\to 0$. – LutzL Oct 26 '17 at 12:53