Convergence acceleration

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

Accelerated convergence is the term used to describe the replacement of a sequence by another that converges more quickly to the same limit value .

There are a number of different methods of accelerating convergence to choose from depending on the properties of the original sequence. Typical applications are iterative calculations, the evaluation of series and integration ( Romberg method ).

definition

One episode

${\displaystyle T=\{t_{n}\}_{n\in \mathbb {N} _{0}}}$

with the limit converges faster than any other sequence ${\displaystyle s}$

${\displaystyle S=\{s_{n}\}_{n\in \mathbb {N} _{0}}}$

with the same limit, if the limit

${\displaystyle \lim _{n\to \infty }{\frac {\|t_{n}-s\|}{\|s_{n}-s\|}}}$

exists and is zero. Obtained from a convergent sequence by a sequence transformation of the shape ${\displaystyle T}$ ${\displaystyle S}$

${\displaystyle T=F(S)}$,

so one speaks of convergence acceleration.

example

The sequence converges with the order of convergence as against . The asymptotic development applies ${\displaystyle a_{n}=\sum _{k=1}^{n}{\frac {1}{k^{2}}}}$ ${\displaystyle {\frac {1}{n}}}$ ${\displaystyle {\frac {\pi ^{2}}{6}}}$

${\displaystyle \sum _{k=1}^{n}{\frac {1}{k^{2}}}={\frac {\pi ^{2}}{6}}-{\frac {1}{n}}+{\frac {1}{2n^{2}}}-{\frac {1}{6n^{3}}}+{\frac {1}{30n^{5}}}-{\frac {1}{42n^{7}}}+{\frac {1}{30n^{9}}}-{\frac {5}{66n^{11}}}+{\mathcal {O}}\!\left({\frac {1}{n^{13}}}\right),\quad n\to \infty }$

This asymptotic series generates the Bernoulli numbers .

The terms in the sum of the series under consideration can pass for k> 1

${\displaystyle {\frac {1}{k(k+1)}}<{\frac {1}{k^{2}}}<{\frac {1}{(k+1)(k-1)}}}$

be estimated. The rows for the estimates on the left and right are telescope rows ,

${\displaystyle {\frac {3}{2}}-{\frac {1}{n+1}}\leq 1+\sum _{k=2}^{n}{\frac {1}{k^{2}}}\leq {\frac {7}{4}}-{\frac {n+{\frac {1}{2}}}{n(n+1)}}}$.

The difference between the last two terms is

${\displaystyle \sum _{k=2}^{n}{\frac {1}{k^{2}-1}}-\sum _{k=2}^{n}{\frac {1}{k^{2}}}=\sum _{k=2}^{n}{\frac {1}{k^{2}(k^{2}-1)}}}$

Thus also applies

${\displaystyle {\frac {\pi ^{2}}{6}}={\frac {7}{4}}-\sum _{k=2}^{\infty }{\frac {1}{k^{2}(k^{2}-1)}}}$.

The n -th partial sum of the series occurring in it converges with the order of convergence as , so much faster. ${\displaystyle {\frac {1}{n^{3}}}}$

This process can be continued at will, so the difference between the last row and the telescope row can be observed. ${\displaystyle \sum _{k=2}^{\infty }{\frac {1}{(k-1)k(k+1)(k+2)}}}$