Summation by parts explained

In mathematics, summation by parts transforms the summation of products of sequences into other summations, often simplifying the computation or (especially) estimation of certain types of sums. It is also called Abel's lemma or Abel transformation, named after Niels Henrik Abel who introduced it in 1826.^[1]

Statement

Suppose

\{f _{k\}} and \{g _{k\}} are two sequences. Then,\sum ^{n} _{k = m} f _{k(g} _{k+1} - g _{k)} = \left(f _{n+1} g _{n+1} - f _{m} g _{m\right)} - \sum ^{n} _{k = m} g _{k+1} (f _{k+1} - f _{k} ). \Delta , it can be stated more succinctly as\sum ^{n} _{k = m} f _{k\Delta} g _{k} = \left(f _{n+1} g _{n+1} - f _{m} g _{m\right)} - \sum ^{n} _{k = m} g _{k+1} \Delta f _{k,}

Summation by parts is an analogue to integration by parts:

\int fdg = f g - \int gdf,

or to Abel's summation formula:

\sum ^{n} _{k = m +1} f(k)(g _{k} - g _{k-1} ) = \left(f(n)g _{n} - f(m) g _{m\right)} - \int ^{n} _{m} g _{\lfloor} f'(t) dt.

An alternative statement is

f _{n} g _{n} - f _{m} g _{m} = \sum ^{n -1} _{k = m} f _{k\Delta} g _{k} + \sum ^{n -1} _{k = m} g _{k\Delta} f _{k} + \sum ^{n -1} _{k = m} \Delta f _{k} \Delta g _{k} which is analogous to the integration by parts formula for semimartingales.

Although applications almost always deal with convergence of sequences, the statement is purely algebraic and will work in any field. It will also work when one sequence is in a vector space, and the other is in the relevant field of scalars.

Newton series

The formula is sometimes given in one of these - slightly different - forms

\begin{align} \sum ^{n} _{k =0} f _{k} g _{k} & = f _{0} \sum ^{n} _{k =0} g _{k+} \sum ^{n -1} _{j =0} (f _{j+1} - f _{j)} \sum ^{n} _{k = j +1} g _{k\\ &=} f _{n} \sum ^{n} _{k =0} g _{k} - \sum ^{n -1} _{j =0} \left( f _{j+1} - f _{j\right)} \sum ^{j} _{k =0} g _{k,} \end{align}

which represent a special case (

M = 1 ) of the more general rule\begin{align} \sum ^{n} _{k =0} f _{k} g _{k} & = \sum ^{M -1} _{i =0} f ^{(i)} _{0} G ^{(i +1 )} _{i} + \sum ^{n - M} _{j =0} f ^{(M)} _{j} G ^{(M)} _{j + M} = \\ & = \sum ^{M -1} _{i =0} \left( -1 \right) ^{i} f ^{(i)} _{n - i} \tilde{G} ^{(i +1 )} _{n - i} + \left( -1 \right) ^{M} \sum ^{n - M} _{j =0} f ^{(M)} _{j} \tilde{G} ^{(M)} _{j} ; \end{align}

both result from iterated application of the initial formula. The auxiliary quantities are Newton series:

f ^{(M)} _{j} : = \sum ^{M} _{k =0} \left( -1 \right) ^{M-k} {M \choose k} f _{j+k} and G ^{(M)} _{j} : = \sum ^{n} _{k = j} {k - j + M -1 \choose M -1 } g _{k,} \tilde{G} ^{(M)} _{j} : = \sum ^{j} _{k =0} {j - k + M -1 \choose M -1 } g _{k.}

A particular (

M = n +1 ) result is the identity\sum ^{n} _{k =0} f _{k} g _{k} = \sum ^{n} _{i =0} f ^{(i)} _{0} G ^{(i +1 )} _{i} = \sum ^{n} _{i =0} ( -1 ) ^{i} f ^{(i)} _{n - i} \tilde{G} ^{(i +1 )} _{n - i} .

Here, $$ is the binomial coefficient.

Method

For two given sequences

(a _{n)} and (b _{n)} , with n \in \N , one wants to study the sum of the following series: $$S\_N\; =\; \backslash sum\_^N\; a\_n\; b\_n$$

If we define $B\_n\; =\; \backslash sum\_^n\; b\_k,$ then for every

n> 0 , b _{n} = B _{n} - B _{n-1} and$$S\_N\; =\; a\_0\; b\_0\; +\; \backslash sum\_^N\; a\_n\; (B\_n\; -\; B\_),$$$$S\_N\; =\; a\_0\; b\_0\; -\; a\_1\; B\_0\; +\; a\_N\; B\_N\; +\; \backslash sum\_^\; B\_n\; (a\_n\; -\; a\_).$$

Finally $S\_N\; =\; a\_N\; B\_N\; -\; \backslash sum\_^\; B\_n\; (a\_\; -\; a\_n).$

This process, called an Abel transformation, can be used to prove several criteria of convergence for

S _{N} .

Similarity with an integration by parts

The formula for an integration by parts is $\backslash int\_a^b\; f(x)\; g\text{'}(x)\backslash ,dx\; =\; \backslash left[f(x)\; g(x)\; \backslash right]\_^\; -\; \backslash int\_a^b\; f\text{'}(x)\; g(x)\backslash ,dx$.

Beside the boundary conditions, we notice that the first integral contains two multiplied functions, one which is integrated in the final integral (

g' becomes g ) and one which is differentiated (f becomes f' ).

The process of the Abel transformation is similar, since one of the two initial sequences is summed (

b _{n} becomes B _{n} ) and the other one is differenced (a _{n} becomes a _{n+1} - a _{n} ).

Applications

• It is used to prove Kronecker's lemma, which in turn, is used to prove a version of the strong law of large numbers under variance constraints.
• It may be used to prove Nicomachus's theorem that the sum of the first

n cubes equals the square of the sum of the first n positive integers.^[2]

• Summation by parts is frequently used to prove Abel's theorem and Dirichlet's test.
• One can also use this technique to prove Abel's test: If $\backslash sum\_n\; b\_n$ is a convergent series, and

a _{n} a bounded monotone sequence, then $S\_N\; =\; \backslash sum\_^N\; a\_n\; b\_n$ converges.

Proof of Abel's test. Summation by parts giveswhere a is the limit of

a _{n} . As $\backslash sum\_n\; b\_n$ is convergent, B _{N} is bounded independently of N , say by B . As a _{n-a} go to zero, so go the first two terms. The third term goes to zero by the Cauchy criterion for $\backslash sum\_n\; b\_n$. The remaining sum is bounded by$$\backslash sum\_^\; |B\_n|\; |a\_-a\_n|\; \backslash le\; B\; \backslash sum\_^\; |a\_-a\_n|\; =\; B|a\_N\; -\; a\_M|$$by the monotonicity of a _{n} , and also goes to zero as N \to inf ty .

Using the same proof as above, one can show that if

1. the partial sums

B _{N} form a bounded sequence independently of N ;\sum ^{inf ty} _{n =0} |a _{n+1} - a _{n|} < inf ty (so that the sum \sum ^{M -1} _{n = N} |a _{n+1} - a _{n|} goes to zero as N goes to infinity) \lim a _{n} = 0 then $S\_N\; =\; \backslash sum\_^N\; a\_n\; b\_n$ converges.

In both cases, the sum of the series satisfies:$$|S|\; =\; \backslash left|\backslash sum\_^\backslash infty\; a\_n\; b\_n\; \backslash right|\; \backslash le\; B\; \backslash sum\_^\backslash infty\; |a\_-a\_n|.$$

Summation-by-parts operators for high order finite difference methods

A summation-by-parts (SBP) finite difference operator conventionally consists of a centered difference interior scheme and specific boundary stencils that mimics behaviors of the corresponding integration-by-parts formulation.^{[3] [4]} The boundary conditions are usually imposed by the Simultaneous-Approximation-Term (SAT) technique.^[5] The combination of SBP-SAT is a powerful framework for boundary treatment. The method is preferred for well-proven stability for long-time simulation, and high order of accuracy.

See also

• Convergent series
• Divergent series
• Integration by parts
• Cesàro summation
• Abel's theorem
• Abel sum formula

References

Bibliography

• Niels Henrik . Abel . Niels Henrik Abel . Untersuchungen über die Reihe 1+ (m)/(x) + (m ⋅ (m -1 ))/(2 ⋅ 1) x ^{2} + (m ⋅ (m -1 ) ⋅ (m -2 ))/(3 ⋅ 2 ⋅ 1) x ^{3} + \ldots u.s.w. . . 1 . 1826 . 311–339.

Notes and References

1. Advances in Applied Mathematics . 39 . 4 . 2007 . 490-514 . Abel's lemma on summation by parts and basic hypergeometric series . Wenchang . Chu . 10.1016/j.aam.2007.02.001. free .
2. Edmonds . Sheila M. . Sheila May Edmonds . 10.2307/3609189 . The Mathematical Gazette . 3609189 . 96615 . 187–188 . Sums of powers of the natural numbers . 41 . 1957 . 337 .
3. Strand. Bo. January 1994. Summation by Parts for Finite Difference Approximations for d/dx. Journal of Computational Physics. 110. 1. 47–67. 10.1006/jcph.1994.1005.
4. Mattsson. Ken. Nordström. Jan. September 2004. Summation by parts operators for finite difference approximations of second derivatives. Journal of Computational Physics. 199. 2. 503–540. 10.1016/j.jcp.2004.03.001.
5. Carpenter. Mark H.. Gottlieb. David. Abarbanel. Saul. April 1994. Time-Stable Boundary Conditions for Finite-Difference Schemes Solving Hyperbolic Systems: Methodology and Application to High-Order Compact Schemes. Journal of Computational Physics. 111. 2. 220–236. 10.1006/jcph.1994.1057. 10.1.1.465.603.