Cellular approximation theorem

2013-09-20T19:02:50Z

155.41.82.240: /* Idea of proof */ spurious comma

In [[numerical analysis]], the '''Shanks transformation''' is a [[non-linear]] [[series acceleration]] method to increase the [[rate of convergence]] of a [[sequence]]. This method is named after [[Daniel Shanks]], who rediscovered this sequence transformation in 1955. It was first derived and published by R. Schmidt in 1941.<ref>Weniger (2003).</ref>

{{Quote box
| quote=One can calculate only a few terms of a [[perturbation theory|perturbation expansion]], usually no more than two or three, and almost never more than seven. The resulting series is often slowly convergent, or even divergent. Yet those few terms contain a remarkable amount of information, which the investigator should do his best to extract.<br> This viewpoint has been persuasively set forth in a delightful paper by Shanks (1955), who displays a number of amazing examples, including several from [[fluid mechanics]].
| source= [[Milton Van Dyke|Milton D. Van Dyke]] (1975) ''Perturbation methods in fluid mechanics'', p. 202.
| width= 60%
| align= right
}}

==Formulation==

For a sequence <math>\left\{a_m\right\}_{m\in\mathbb{N}}</math> the series

:<math>A = \sum_{m=0}^\infty a_m\,</math>

is to be determined. First, the partial sum <math>A_n</math> is defined as:

:<math>A_n = \sum_{m=0}^n a_m\,</math>

and forms a new sequence <math>\left\{A_n\right\}_{n\in\mathbb{N}}</math>. Provided the series converges, <math>A_n</math> will approach in the limit to <math>A</math> as <math>n\to\infty.</math>
The Shanks transformation <math>S(A_n)</math> of the sequence <math>A_n</math> is defined as<ref name=BenderOrszag368>Bender & Orszag (1999), pp. 368–375.</ref><ref name=VanDyke>Van Dyke (1975), pp. 202–205.</ref>

:<math>S(A_n) = \frac{A_{n+1}\, A_{n-1}\, -\, A_n^2}{A_{n+1}-2A_n+A_{n-1}}</math>

and forms a new sequence. The sequence <math>S(A_n)</math> often converges more rapidly than the sequence <math>A_n.</math>
Further speed-up may be obtained by repeated use of the Shanks transformation, by computing <math>S^2(A_n)=S(S(A_n)),</math> <math>S^3(A_n)=S(S(S(A_n))),</math> etc.

Note that the non-linear transformation as used in the Shanks transformation is of similar form as used in [[Aitken's delta-squared process]]. But while Aitken's method operates on the coefficients <math>\left\{a_m\right\}</math> of the original sequence, the Shanks transformation operates on the partial sums <math>A_n.</math>

==Example==

[[Image:Shanks transformation.svg|thumb|400px|right|Absolute error as a function of <math>n</math> in the partial sums <math>A_n</math> and after applying the Shanks transformation once or several times: <math>S(A_n),</math> <math>S^2(A_n)</math> and <math>S^3(A_n).</math> The series used is <math>\scriptstyle 4\left(1-\frac13+\frac15-\frac17+\frac19-\cdots\right),</math> which has the exact sum <math>\pi.</math>]]
As an example, consider the slowly convergent series<ref name=VanDyke/>

:<math> 4 \sum_{k=0}^\infty (-1)^k \frac{1}{2k+1} = 4 \left( 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots \right) </math>

which has the exact sum ''π'' ≈ 3.14159265. The partial sum <math>A_6</math> has only one digit accuracy, while six-figure accuracy requires summing about 400,000 terms.

In the table below, the partial sums <math>A_n</math>, the Shanks transformation <math>S(A_n)</math> on them, as well as the repeated Shanks transformations <math>S^2(A_n)</math> and <math>S^3(A_n)</math> are given for <math>n</math> up to 12. The figure to the right shows the absolute error for the partial sums and Shanks transformation results, clearly showing the improved accuracy and convergence rate.

{| class="wikitable" style="text-align:center; width:40%"
|-
! width="10% | <math>n</math>
! width="20% | <math>A_n</math>
! width="20% | <math>S(A_n)</math>
! width="20% | <math>S^2(A_n)</math>
! width="20% | <math>S^3(A_n)</math>
|-
| 0 || 4.00000000 || — || — || —
|-
| 1 || 2.66666667 || 3.16666667 || — || —
|-
| 2 || 3.46666667 || 3.13333333 || 3.14210526 || —
|-
| 3 || 2.89523810 || 3.14523810 || 3.14145022 || 3.14159936
|-
| 4 || 3.33968254 || 3.13968254 || 3.14164332 || 3.14159086
|-
| 5 || 2.97604618 || 3.14271284 || 3.14157129 || 3.14159323
|-
| 6 || 3.28373848 || 3.14088134 || 3.14160284 || 3.14159244
|-
| 7 || 3.01707182 || 3.14207182 || 3.14158732 || 3.14159274
|-
| 8 || 3.25236593 || 3.14125482 || 3.14159566 || 3.14159261
|-
| 9 || 3.04183962 || 3.14183962 || 3.14159086 || 3.14159267
|-
| 10 || 3.23231581 || 3.14140672 || 3.14159377 || 3.14159264
|-
| 11 || 3.05840277 || 3.14173610 || 3.14159192 || 3.14159266
|-
| 12 || 3.21840277 || 3.14147969 || 3.14159314 || 3.14159265
|}

The Shanks transformation <math>S(A_1)</math> already has two-digit accuracy, while the original partial sums only establish the same accuracy at <math>A_{24}.</math> Remarkably, <math>S^3(A_3)</math> has six digits accuracy, obtained from repeated Shank transformations applied to the first seven terms <math>A_0</math>, ... , <math>A_6.</math> As said before, <math>A_n</math> only obtains 6-digit accuracy after about summing 400,000 terms.

==Motivation==

The Shanks transformation is motivated by the observation that — for larger <math>n</math> — the partial sum <math>A_n</math> quite often behaves approximately as<ref name=BenderOrszag368/>

:<math>A_n = A + \alpha q^n, \,</math>

with <math>|q|<1</math> so that the sequence converges [[transient (oscillation)|transient]]ly to the series result <math>A</math> for <math>n\to\infty.</math>
So for <math>n-1,</math> <math>n</math> and <math>n+1</math> the respective partial sums are:

:<math>A_{n-1} = A + \alpha q^{n-1} \quad , \qquad A_n = A + \alpha q^n \qquad \text{and} \qquad A_{n+1} = A + \alpha q^{n+1}.</math>

These three equations contain three unknowns: <math>A,</math> <math>\alpha</math> and <math>q.</math> Solving for <math>A</math> gives<ref name=BenderOrszag368/>

:<math>A = \frac{A_{n+1}\, A_{n-1}\, -\, A_n^2}{A_{n+1}-2A_n+A_{n-1}}.</math>

In the (exceptional) case that the denominator is equal to zero: then <math>A_n=A</math> for all <math>n.</math>

==Generalized Shanks transformation==

The generalized ''k''th-order Shanks transformation is given as the ratio of the [[determinant]]s:<ref name=BenderOrszag389>Bender & Orszag (1999), pp. 389–392.</ref>
:<math>
S_k(A_n)
= \frac{
\begin{vmatrix}
A_{n-k} & \cdots & A_{n-1} & A_n \\
\Delta A_{n-k} & \cdots & \Delta A_{n-1} & \Delta A_{n} \\
\Delta A_{n-k+1} & \cdots & \Delta A_{n} & \Delta A_{n+1} \\
\vdots & & \vdots & \vdots \\
\Delta A_{n-1} & \cdots & \Delta A_{n+k-2} & \Delta A_{n+k-1} \\
\end{vmatrix}
}{
\begin{vmatrix}
1 & \cdots & 1 & 1 \\
\Delta A_{n-k} & \cdots & \Delta A_{n-1} & \Delta A_{n} \\
\Delta A_{n-k+1} & \cdots & \Delta A_{n} & \Delta A_{n+1} \\
\vdots & & \vdots & \vdots \\
\Delta A_{n-1} & \cdots & \Delta A_{n+k-2} & \Delta A_{n+k-1} \\
\end{vmatrix}
},
</math>
with <math>\Delta A_p = A_{p+1} - A_p.</math> It is the solution of a model for the convergence behaviour of the partial sums <math>A_n</math> with <math>k</math> distinct transients:

:<math>A_n = A + \sum_{p=1}^k \alpha_p q_p^n.</math>

This model for the convergence behaviour contains <math>2k+1</math> unknowns. By evaluating the above equation at the elements <math>A_{n-k}, A_{n-k+1}, \ldots, A_{n+k}</math> and solving for <math>A,</math> the above expression for the ''k''th-order Shanks transformation is obtained. The first-order generalized Shanks transformation is equal to the ordinary Shanks transformation: <math>S_1(A_n)=S(A_n).</math>

The generalized Shanks transformation is closely related to [[Padé approximant]]s and [[Padé table]]s.<ref name=BenderOrszag389/>

==See also==
*[[Aitken's delta-squared process]]
*[[Rate of convergence]]
*[[Richardson extrapolation]]
*[[sequence transformation]]

==Notes==
{{reflist}}

==References==
*{{citation | first=D. | last=Shanks | authorlink=Daniel Shanks | year=1955 | title=Non-linear transformation of divergent and slowly convergent sequences | journal=Journal of Mathematics and Physics | volume = 34 | pages=1–42 }}
*{{citation | first=R. | last=Schmidt | title=On the numerical solution of linear simultaneous equations by an iterative method | journal=Philosophical Magazine | volume=32 | year=1941 | pages=369–383 }}
*{{citation | first=M.D. | last=Van Dyke | authorlink=Milton Van Dyke | title=Perturbation methods in fluid mechanics | publisher=Parabolic Press | year=1975 | edition=annotated | isbn=0-915760-01-0 }}
*{{citation | first1=C.M. | last1=Bender | authorlink1=Carl M. Bender | first2=S.A. | last2=Orszag | authorlink2=Steven A. Orszag | title=Advanced mathematical methods for scientists and engineers | publisher=Springer | year=1999 | isbn=0-387-98931-5 }}
*{{cite arxiv | author=Weniger, E.J. | title=Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series| eprint=math.NA/0306302 | year=2003 | version=v1 }}

[[Category:Numerical analysis]]
[[Category:Asymptotic analysis]]

formulasearchengine - User contributions [en]

Cellular approximation theorem