Convergence acceleration

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)}}}$