Diskrete Differentialrechnung

Die diskrete Differentialrechnung ist eine Form der Differentialrechnung, die nicht wie in der Analysis mit kontinuierlichen, sondern mit diskreten Mengen arbeitet und zur Berechnung von Reihen angewandt werden kann.

Differenzen und Summen

Die bekannte kontinuierliche Differentialrechnung basiert auf dem Differenzialoperator $\mathrm{D}$, der wie folgt definiert ist:

$\mathrm{D}f(x) = \lim_{h \rightarrow 0} \frac{f(x+h)-f(x)}{h}$

Die diskrete Differentialrechnung hingegen verwendet einen sogenannten Differenzoperator $\Delta$:

$\Delta f(x) = f(x+1)-f(x)$.

Die umgekehrte Operation wird nicht wie in der kontinuierlichen Differentialrechnung mit dem unbestimmten Integral, sondern mit einer unbestimmten Summe $\sum f(x)$ erreicht, die sich zum Differenzoperator wie folgt verhält:

$g(x) = \Delta f(x) \quad \Longleftrightarrow \quad \sum g(x)\; \delta x = f(x) + C$.

$\delta$ verhält sich hier zu $\Delta$ wie $\mathrm{d}$ zu $\mathrm{D}$ in der kontinuierlichen Differentialrechnung. $C$ steht für den Wert einer beliebigen Funktion, die für ganzzahlige $x$ konstant ist ($C(x+1) = C(x)$).

Das Pendant zu bestimmten Integralen sind bestimmte Summen. Diese entsprechen gewöhnlichen Summen ohne den Wert am höchsten Index:

$\sideset{}{_a^b} \sum f(x)\; \delta x = \sum_{k=a}^{b-1} f(k) = [F(x)]_a^b = F(b) - F(a)$.

Eigenschaften

Invariante Funktion

Eine unter dem Differenzialoperator invariante Funktion ist die Exponentialfunktion der Basis e. In der diskreten Differentialrechnung ist die Exponentialfunktion der Basis 2 invariant, wie sich leicht ermitteln lässt:

$\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}$

Fallende Fakultäten

Eine einfache Rechenregel gibt es für fallende Fakultäten, die für jede Ganzzahl $m$ wie folgt definiert sind:

$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}$

Dieser Ausdruck verhält sich in der diskreten Differentialrechnung folgendermaßen:

• $\Delta(x^{\underline{m}}) = mx^{\underline{m-1}}$
• $\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_m\right]_a^b & \text{, wenn } m = -1 \end{cases}$

wobei $H_n$ die $n$-te harmonische Zahl ist. Die harmonische Reihe ist somit das Gegenstück zum natürlichen Logarithmus. Die Übereinstimmung geht so weit, dass $\Delta (x\cdot H_x - x) = H_x$ ebenfalls gilt.

Fallende Fakultäten und Potenzen können stets mittels Stirling-Zahlen erster bzw. zweiter Art ineinander umgewandelt werden:

$x^{\underline m} = \sum_k\left[\begin{matrix} m \\ k \end{matrix}\right] (-1)^{m-k}x^k$,

$x^m=\sum_k\left\{\begin{matrix}m\\k\end{matrix}\right\}x^{\underline k}$

Außerdem gilt der binomische Lehrsatz auch für fallende Fakultäten.

Beispiel zur Berechnung der Summe der ersten $n$ Quadratzahlen:

$\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}$.

Produktregel und partielle Summation

Die Produktregel der kontinuierlichen Differentialrechnung ist in folgender Form gültig:

$\Delta(u(x)v(x)) = u(x)\Delta v(x) + v(x+1)\Delta u(x)$.

Diese Regel lässt sich durch Einführung eines Verschiebeoperators $\mathrm{E}$, definiert als $\mathrm{E}f(x) = f(x+1)$, kompakter ausdrücken:

$\Delta(uv) = u\Delta v + \mathrm{E}v\Delta u$.

Die Umstellung der Terme führt zur Formel der partiellen Summation ähnlich der partiellen Integration:

$\sum u\,\Delta v = uv - \sum \mathrm{E}v\,\Delta u$.

Beispiel zur Berechnung der Summe $\sum_{k=0}^n k2^k$:

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

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

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

$\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}$

Literatur

• Ronald Graham u. a.: Concrete Mathematics. Addison-Wesley, Upper Saddle River 2008, ISBN 0-201-55802-5

Weblinks

• Brian Hamrick: Discrete Calculus (PDF, 70 KB)