Misplaced Pages

Van Wijngaarden transformation

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

In mathematics and numerical analysis, the van Wijngaarden transformation is a variant on the Euler transform used to accelerate the convergence of an alternating series.

One algorithm to compute Euler's transform runs as follows:

Compute a row of partial sums s 0 , k = ∑ n = 0 k ( − 1 ) n a n {\displaystyle s_{0,k}=\sum _{n=0}^{k}(-1)^{n}a_{n}} and form rows of averages between neighbors s j + 1 , k = s j , k + s j , k + 1 2 {\displaystyle s_{j+1,k}={\frac {s_{j,k}+s_{j,k+1}}{2}}} The first column s j , 0 {\displaystyle s_{j,0}} then contains the partial sums of the Euler transform.

Adriaan van Wijngaarden's contribution was to point out that it is better not to carry this procedure through to the very end, but to stop two-thirds of the way. If a 0 , a 1 , … , a 12 {\displaystyle a_{0},a_{1},\ldots ,a_{12}} are available, then s 8 , 4 {\displaystyle s_{8,4}} is almost always a better approximation to the sum than s 12 , 0 {\displaystyle s_{12,0}} . In many cases the diagonal terms do not converge in one cycle so process of averaging is to be repeated with diagonal terms by bringing them in a row. (For example, this will be needed in a geometric series with ratio − 4 {\displaystyle -4} .) This process of successive averaging of the average of partial sum can be replaced by using the formula to calculate the diagonal term.

For a simple-but-concrete example, recall the Leibniz formula for pi

1 − 1 3 + 1 5 − 1 7 + ⋯ = π 4 = 0.7853981 … {\displaystyle 1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+\cdots ={\frac {\pi }{4}}=0.7853981\ldots } (1)

The algorithm described above produces the following table:

Computing the Euler transform of (1); highlighted values are final results
1.00000000 0.66666667 0.86666667 0.72380952 0.83492063 0.74401154 0.82093462 0.75426795 0.81309148 0.76045990 0.80807895 0.76460069 0.80460069
0.83333333 0.76666667 0.79523810 0.77936508 0.78946609 0.78247308 0.78760129 0.78367972 0.78677569 0.78426943 0.78633982 0.78460069
0.80000000 0.78095238 0.78730159 0.78441558 0.78596959 0.78503719 0.78564050 0.78522771 0.78552256 0.78530463 0.78547026
0.79047619 0.78412698 0.78585859 0.78519259 0.78550339 0.78533884 0.78543410 0.78537513 0.78541359 0.78538744
0.78730159 0.78499278 0.78552559 0.78534799 0.78542111 0.78538647 0.78540462 0.78539436 0.78540052
0.78614719 0.78525919 0.78543679 0.78538455 0.78540379 0.78539555 0.78539949 0.78539744
0.78570319 0.78534799 0.78541067 0.78539417 0.78539967 0.78539752 0.78539847
0.78552559 0.78537933 0.78540242 0.78539692 0.78539860 0.78539799
0.78545246 0.78539087 0.78539967 0.78539776 0.78539829
0.78542166 0.78539527 0.78539871 0.78539803
0.78540847 0.78539699 0.78539837
0.78540273 0.78539768
0.78540021

These correspond to the following algorithmic outputs:

Accuracy of final results
Algorithm Term used Value for π / 4 {\displaystyle \pi /4} Relative error
Naïve partial sums s 0 , 12 {\displaystyle s_{0,12}} 0.8046006... +2.4%
Euler transform s 12 , 0 {\displaystyle s_{12,0}} 0.7854002... +2.6×10
van Wijngaarden result s 8 , 4 {\displaystyle s_{8,4}} 0.7853982... +4.7×10

References

  1. A. van Wijngaarden, in: Cursus: Wetenschappelijk Rekenen B, Proces Analyse, Stichting Mathematisch Centrum, (Amsterdam, 1965) pp. 51-60
  2. Values calculated via the J expression 'b11.8'8!:2-:&(}:+}.)^:n+/\(_1^n)*%1+2*n=.i.13

See also

Categories: