1
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you write it without the "O" notation? $\endgroup$ – Arman Malekzadeh Oct 26 '17 at 12:31
  • $\begingroup$ 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. $\endgroup$ – LutzL Oct 26 '17 at 12:36
  • $\begingroup$ Ok, So please explain that how the limit i write in the question equals to $0$ $\endgroup$ – Arman Malekzadeh Oct 26 '17 at 12:49
  • $\begingroup$ 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. $\endgroup$ – LutzL Oct 26 '17 at 12:51
  • $\begingroup$ $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$. $\endgroup$ – LutzL Oct 26 '17 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.