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.
For a sequence
{
a
m
}
m
∈
N
the series
A
=
∑
m
=
0
∞
a
m
is to be determined. First, the partial sum
A
n
is defined as:
A
n
=
∑
m
=
0
n
a
m
and forms a new sequence
{
A
n
}
n
∈
N
. Provided the series converges,
A
n
will also approach the limit
A
as
n
→
∞
.
The Shanks transformation
S
(
A
n
)
of the sequence
A
n
is the new sequence defined by
S
(
A
n
)
=
A
n
+
1
A
n
−
1
−
A
n
2
A
n
+
1
−
2
A
n
+
A
n
−
1
=
A
n
+
1
−
(
A
n
+
1
−
A
n
)
2
(
A
n
+
1
−
A
n
)
−
(
A
n
−
A
n
−
1
)
where this sequence
S
(
A
n
)
often converges more rapidly than the sequence
A
n
.
Further speed-up may be obtained by repeated use of the Shanks transformation, by computing
S
2
(
A
n
)
=
S
(
S
(
A
n
)
)
,
S
3
(
A
n
)
=
S
(
S
(
S
(
A
n
)
)
)
,
etc.
Note that the non-linear transformation as used in the Shanks transformation is essentially the same as used in Aitken's delta-squared process so that as with Aitken's method, the right-most expression in
S
(
A
n
)
's definition (i.e.
S
(
A
n
)
=
A
n
+
1
−
(
A
n
+
1
−
A
n
)
2
(
A
n
+
1
−
A
n
)
−
(
A
n
−
A
n
−
1
)
) is more numerically stable than the expression to its left (i.e.
S
(
A
n
)
=
A
n
+
1
A
n
−
1
−
A
n
2
A
n
+
1
−
2
A
n
+
A
n
−
1
). Both Aitken's method and Shanks transformation operate on a sequence, but the sequence the Shanks transformation operates on is usually thought of as being a sequence of partial sums, although any sequence may be viewed as a sequence of partial sums.
As an example, consider the slowly convergent series
4
∑
k
=
0
∞
(
−
1
)
k
1
2
k
+
1
=
4
(
1
−
1
3
+
1
5
−
1
7
+
⋯
)
which has the exact sum π ≈ 3.14159265. The partial sum
A
6
has only one digit accuracy, while six-figure accuracy requires summing about 400,000 terms.
In the table below, the partial sums
A
n
, the Shanks transformation
S
(
A
n
)
on them, as well as the repeated Shanks transformations
S
2
(
A
n
)
and
S
3
(
A
n
)
are given for
n
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.
The Shanks transformation
S
(
A
1
)
already has two-digit accuracy, while the original partial sums only establish the same accuracy at
A
24
.
Remarkably,
S
3
(
A
3
)
has six digits accuracy, obtained from repeated Shank transformations applied to the first seven terms
A
0
,
…
,
A
6
.
As said before,
A
n
only obtains 6-digit accuracy after about summing 400,000 terms.
The Shanks transformation is motivated by the observation that — for larger
n
— the partial sum
A
n
quite often behaves approximately as
A
n
=
A
+
α
q
n
,
with
|
q
|
<
1
so that the sequence converges transiently to the series result
A
for
n
→
∞
.
So for
n
−
1
,
n
and
n
+
1
the respective partial sums are:
A
n
−
1
=
A
+
α
q
n
−
1
,
A
n
=
A
+
α
q
n
and
A
n
+
1
=
A
+
α
q
n
+
1
.
These three equations contain three unknowns:
A
,
α
and
q
.
Solving for
A
gives
A
=
A
n
+
1
A
n
−
1
−
A
n
2
A
n
+
1
−
2
A
n
+
A
n
−
1
.
In the (exceptional) case that the denominator is equal to zero: then
A
n
=
A
for all
n
.
The generalized kth-order Shanks transformation is given as the ratio of the determinants:
S
k
(
A
n
)
=
|
A
n
−
k
⋯
A
n
−
1
A
n
Δ
A
n
−
k
⋯
Δ
A
n
−
1
Δ
A
n
Δ
A
n
−
k
+
1
⋯
Δ
A
n
Δ
A
n
+
1
⋮
⋮
⋮
Δ
A
n
−
1
⋯
Δ
A
n
+
k
−
2
Δ
A
n
+
k
−
1
|
|
1
⋯
1
1
Δ
A
n
−
k
⋯
Δ
A
n
−
1
Δ
A
n
Δ
A
n
−
k
+
1
⋯
Δ
A
n
Δ
A
n
+
1
⋮
⋮
⋮
Δ
A
n
−
1
⋯
Δ
A
n
+
k
−
2
Δ
A
n
+
k
−
1
|
,
with
Δ
A
p
=
A
p
+
1
−
A
p
.
It is the solution of a model for the convergence behaviour of the partial sums
A
n
with
k
distinct transients:
A
n
=
A
+
∑
p
=
1
k
α
p
q
p
n
.
This model for the convergence behaviour contains
2
k
+
1
unknowns. By evaluating the above equation at the elements
A
n
−
k
,
A
n
−
k
+
1
,
…
,
A
n
+
k
and solving for
A
,
the above expression for the kth-order Shanks transformation is obtained. The first-order generalized Shanks transformation is equal to the ordinary Shanks transformation:
S
1
(
A
n
)
=
S
(
A
n
)
.
The generalized Shanks transformation is closely related to Padé approximants and Padé tables.
