Quelltext der Seite Differenzenrechnung

Die '''Differenzenrechnung''' ist ein Teilgebiet der [[Mathematik]], das die [[diskret]]e Entsprechung zur [[Analysis]] ([[Differentialrechnung|Differenzial-]] und [[Integralrechnung]]) bildet. Während sich die Analysis mit Funktionen beschäftigt, die auf kontinuierlichen Räumen definiert sind (um einen Grenzwertbegriff etablieren zu können), im Besonderen mit Funktionen auf den [[Reelle Zahl|reellen Zahlen]], interessiert man sich in der Differenzenrechnung für Funktionen auf den [[Ganze Zahl|ganzen Zahlen]] ℤ. Die Differenzenrechnung kann zur Berechnung von [[Reihe (Mathematik)|Reihen]] angewandt werden.

== Differenzen und Summen ==
Die bekannte [[Kontinuum (Mathematik)|kontinuierliche]] Differentialrechnung basiert auf dem [[Differential (Mathematik)|Differenzialoperator]] <math>\mathrm{D}</math>, der wie folgt definiert ist:
:<math>\mathrm{D}f(x) = \lim_{h \rightarrow 0} \frac{f(x+h)-f(x)}{h}</math>

Die Differenzenrechnung hingegen verwendet einen sogenannten ''Differenzenoperator'' <math>\Delta</math>:
:<math>\Delta f(x) = f(x+1)-f(x)</math>.

Die umgekehrte Operation wird nicht wie in der kontinuierlichen Differentialrechnung mit dem [[Integralrechnung|unbestimmten Integral]], sondern mit einer ''unbestimmten Summe'' <math>\sum f(x)</math> erreicht, die sich zum Differenzenoperator wie folgt verhält:
:<math>g(x) = \Delta f(x) \quad \Longleftrightarrow \quad \sum g(x)\; \delta x = f(x) + C</math>.
<math>\delta</math> verhält sich hier zu <math>\Delta</math> wie <math>\mathrm{d}</math> zu <math>\mathrm{D}</math> in der kontinuierlichen Differentialrechnung. <math>C</math> steht für den Wert einer beliebigen Funktion, die für ganzzahlige <math>x</math> konstant ist (<math>C(x+1) = C(x)</math>).

Das Pendant zu bestimmten Integralen sind ''bestimmte Summen.'' Diese entsprechen gewöhnlichen Summen ohne den Wert am höchsten Index:
:<math>\sideset{}{_a^b} \sum f(x)\; \delta x = \sum_{k=a}^{b-1} f(k) = [F(x)]_a^b = F(b) - F(a)</math>.

== Eigenschaften ==
=== Invariante Funktion ===
Eine unter dem Differenzialoperator [[Invariante (Mathematik)|invariante]] Funktion ist die [[Exponentialfunktion]] der Basis ''[[Eulersche Zahl|e]].'' In der Differenzenrechnung ist die Exponentialfunktion der Basis 2 invariant, wie sich leicht ermitteln lässt:
:<math>\begin{align}
& \Delta f(x) = f(x) \\
\Longleftrightarrow \quad & f(x+1) - f(x) = f(x) \\
\Longleftrightarrow \quad & f(x+1) = 2f(x) \\
\Longleftrightarrow \quad & \exists C: f(x) = C\cdot 2^x \\
\end{align}</math>

=== Fallende Fakultäten ===
Eine einfache Rechenregel gibt es für [[Pochhammer-Symbol|fallende Fakultäten]], die für jede Ganzzahl <math>m</math> wie folgt definiert sind:
:<math>x^{\underline{m}} = \frac{x!}{(x-m)!} =
\begin{cases}
\overbrace{x(x-1) \ldots (x-m+1)}^{m \text{ Faktoren}} & \text{, wenn } m \ge 0\\
& \\
\underbrace{\frac{1}{(x+1)(x+2) \ldots (x-m)}}_{|m| \text{ Faktoren}} & \text{, wenn } m < 0
\end{cases}</math>

Dieser Ausdruck verhält sich in der Differenzenrechnung folgendermaßen:
* <math>\Delta(x^{\underline{m}}) = mx^{\underline{m-1}}</math>
* <math>\sideset{}{_a^b} \sum x^{\underline{m}}\; \delta x =
\begin{cases}
\left[\frac{x^{\underline{m+1}}}{m+1}\right]_a^b & \text{, wenn } m \neq -1 \\
\left[ H_x\right]_a^b & \text{, wenn } m = -1
\end{cases}
</math>
wobei <math>H_n</math> die <math>n</math>-te [[Harmonische Reihe|harmonische Zahl]] ist. Die harmonische Reihe ist somit das Gegenstück zum [[Logarithmus|natürlichen Logarithmus]]. Die Übereinstimmung geht so weit, dass <math>\Delta (x\cdot H_x - x) = H_x</math> ebenfalls gilt.

Fallende Fakultäten und Potenzen können stets mittels [[Stirling-Zahl]]en erster bzw. zweiter Art ineinander umgewandelt werden:
:<math>x^{\underline m} = \sum_k\left[\begin{matrix} m \\ k \end{matrix}\right] (-1)^{m-k}x^k</math>,
:<math>x^m=\sum_k\left\{\begin{matrix}m\\k\end{matrix}\right\}x^{\underline k}</math>
Außerdem gilt der [[Binomischer Lehrsatz|binomische Lehrsatz]] auch für fallende Fakultäten.

<div style="margin: 1em 2em 0 2em; border: 1px solid #448800; padding: 0.4em;">
Beispiel zur Berechnung der Summe der ersten <math>n</math> Quadratzahlen:
:<math>\sum_{k=0}^n k^2 = \sideset{}{_0^{n+1}} \sum x^2 \delta x = \sideset{}{_0^{n+1}} \sum (x^{\underline{2}}\, +\, x^{\underline{1}})\delta x = \frac{(n+1)^{\underline{3}}}{3} + \frac{(n+1)^{\underline{2}}}{2} = \frac{n(n+\frac{1}{2})(n+1)}{3}</math>.
</div>

=== Produktregel und partielle Summation ===
Die [[Produktregel]] der kontinuierlichen Differentialrechnung ist in folgender Form gültig:
:<math>\Delta(u(x)v(x)) = u(x)\Delta v(x) + v(x+1)\Delta u(x)</math>.
Diese Regel lässt sich durch Einführung eines ''Verschiebeoperators'' <math>\mathrm{E}</math>, definiert als <math>\mathrm{E}f(x) = f(x+1)</math>, kompakter ausdrücken:
:<math>\Delta(uv) = u\Delta v + \mathrm{E}v\Delta u</math>.

Die Umstellung der Terme führt zur Formel der ''partiellen Summation'' ähnlich der [[Partielle Integration|partiellen Integration]]:
:<math>\sum u\,\Delta v = uv - \sum \mathrm{E}v\,\Delta u</math>.

<div style="margin: 1em 2em 0 2em; border: 1px solid #448800; padding: 0.4em;">
Beispiel zur Berechnung der Summe <math>\sum_{k=0}^n k2^k</math>:

Hier ist <math>u(x) = x</math> und <math>\Delta v(x) = 2^x</math>, sodass <math>\Delta u(x) = 1</math>, <math>v(x) = 2^x</math> und <math>\mathrm{E} v(x) = 2^{x+1}</math>.

Die Formel zur partiellen Summation ergibt:
<math>\sum x2^x\; \delta x = x2^x - \sum 2^{x+1}\; \delta x = x2^x - 2^{x+1} + C</math>.

Dies führt schließlich zur Lösung:

:<math>\begin{align}
\sum_{k=0}^n k2^k & = \sideset{}{_0^{n+1}} \sum x2^x\; \delta x \\
& = \left[ x2^x - 2^{x+1} \right ]_0^{n+1} \\
& = (n-1)2^{n+1} + 2
\end{align}</math>
</div>

== Siehe auch ==
* [[Koeffizienten für Differenzenquotienten]]
* [[Differenzengleichung]]

== Literatur ==
* [[Alexander Ossipowitsch Gelfond|A. O. Gelfond]]: ''Differenzenrechnung.'' Dt. Verlag d. Wiss., Berlin, 1958
* Ronald Graham u. a.: ''[[Concrete Mathematics]].'' Addison-Wesley, Upper Saddle River 2008, ISBN 0-201-55802-5
* [[Niels Erik Nørlund|N. E. Nörlund]]: ''Vorlesungen über Differenzenrechnung.'' Springer-Verlag, Berlin, 1924; Reprint Chelsea, New York, 1954

== Weblinks ==
* [https://homepages.math.uic.edu/~kauffman/DCalc.pdf Brian Hamrick: Discrete Calculus] (PDF, 70 kB)

[[Kategorie:Folgen und Reihen]]
[[Kategorie:Numerische Mathematik]]