~XI: Quadratur – Integrale im Computer

Bisher ging es um Fourier-Summen, also Funktionen \(f\), die sich schreiben lassen als \[ f(x) = \sum_{k=-n}^n c_k(f) \textrm{e}^{\textrm{i}kx} \] oder eben in der rellen Variante mit zwei Summen, die Kosinus- und Sinus-Terme enthalten. Dabei berechnen sich die Fourier-Koeffizienten über das Integral \[ c_k(f) = \frac{1}{2\pi}\int_{-\pi}^{\pi} f(x)\textrm{e}^{-\textrm{i}kx}\,\textrm{d}x\text{.} \] Die Integration an sich ist jedoch meist kompliziert, auch wenn sich das in den bisherigen zwei Beispielen ausrechnen ließ, ist für die Integration nicht klar, ob sich dafür immer eine Stammfunktion bestimmen lässt. Man kann also im Allgemeinen die Werte \(c_k(f)\) nicht unbedingt explizit ausrechnen. Außerdem sind die Funktionen Sinus und Kosinus – und damit die Funktion \(f(x)\) stetige Funktionen, ein Computer kann jedoch nur einzelne Zahlen speichern. Wie kommt es dann, dass die Fourier-Transformation so wichtig ist, insbesondere bei Algorithmen, die wir Tag für Tag verwenden, wie zum Beispiel in den Datei-Formaten JPEG und MP3? Darum soll es in den nächsten Beiträgen gehen.

In diesem Beitrag soll die Integration im Mittelpunkt stehen. Vorher benötigen wir jedoch noch ein kleines, aber wichtiges Werkzeug, die Modulo-Operation. Dazu stelle man sich wieder vor, was das Intervall \([-\pi,\pi)\) bei Sinus und Kosinus bedeutet: Eine Position auf dem Kreis. Ein Vielfaches von \(2\pi\) entspricht auf dem Kreis also dem Um-den-Kreis-Herumlaufen um ebenso viele Male. Man landet jedoch am gleichen Punkt. Dazu existiert die Modulo-Operation, die hier ein klein wenig modifiziert eingeführt wird. Für eine reelle Zahl \(r\in\mathbb R\) bezeichne \((r)_{2\pi}\in[-\pi,\pi)\) diejenige Zahl (auf dem Kreis), für die ein \(k\in\mathbb Z\) existiert, so dass \(r = (r)_{2\pi} + k\cdot2\pi\) gilt. Oder in anderen Worten: Steht man auf dem Kreis an einer beliebigen Stelle \(r\in\mathbb R\), so kann man von dort aus immer so lange im Kreis laufen (im Uhrzeigersinn für negative, gegen den Uhrzeigersinn für positive Zahlen), dass man damit eine (größere für negative, kleinere für positive) Zahl findet, die ein Vielfaches der Zahl \(2\pi\) von \(r\) entfernt ist und in \([-\pi,\pi)\) liegt. Die Anzahl Umläufe findet sich genau in dem \(k\) wieder. Das funktioniert also fast wie beim Teilen mit Rest, wo wir ebenso an diesem Rest interessiert sind, nur, dass hier durch \(2\pi\) mit Rest geteilt wird und das Ergebnis in dem (zumindest fürs Teilen mit Rest) ungewöhnlichen Intervall \([-\pi,\pi)\) liegt. Die Idee ist aber exakt die gleiche.

Wie schon erwähnt, hat der Computer kaum eine Möglichkeit, alle Funktionen wirklich als Funktionen zu speichern. Eine Funktion \(f(x)\) ist ein Konstrukt, bei dem für einen Wert \(x\) die Funktion eine Zahl zurückgibt, ihren Funktionswert. Dabei kann die Menge an erlaubten Werten begrenzt sein, wie etwa bisher hier das Intervall \([-\pi,\pi)\). Ein Computer ist nur sehr begrenzt in der Lage, dieses Konzept zu speichern und mit ihm Umzugehen. Insbesondere bei der Integration tun sich solche auch Algebra-Systeme genannten Programme schwer. Anstelle der gesamtem Funktion \(f(x)\) kann ein Computer nur endlich viele Werte speichern, etwa für eine bestimmte Anzahl \(N\in\mathbb N\) sich Funktionswerte ausrechnen; für Sinus und Kosinus, aber auch für die Exponentialfunktion, gibt es Implementierungen, die genau das tun. Der Einfachheit halber seien diese Funktionswerte hier äquidistant gewählt, d.h. zwei aufeinanderfolgende Punkte, an denen die Funktion ausgewertet werden soll, haben stets den gleichen Abstand. Im Periodischen sind \(+\pi\) und \(-\pi\) der gleiche Punkt, daher gehört der Erste auch nicht zum üblichen betrachteten Intervall, da sonst dieser Punkt des Kreises zweimal im Intervall vorkäme. Mit diesem Wissen ergeben sich die ersten äquidistanten Punkte — immer von \(x=0\) „loslaufend“ — wie folgt

\(N=1\). Bei genau einem Punkt bleibt mit dem genannten Anfang nur genau dieser, also \[ x_0 = 0\text{.} \]

\(N=2\). Bei Zwei Punkten unterteilt man das Intervall \([-\pi,\pi)\), welches die Länge \(2\pi\) besitzt, in zwei gleich große Teile der Länge \(\pi\) und erhält \[ x_0 = 0,\quad x_1=-\pi\text{.} \] Hier fällt allerdings schon auf, dass die Punkte nicht so ganz geordnet zu sein scheinen, wenn wir im Nullpunkt beginnen. Auf dem Kreis liegen sie aber durchaus in einer Folge, die man nacheinander abläuft.

\(N=3\). Der Abstand zwischen zwei Punkten ist in diesem Fall \(d=\frac{2\pi}{3}\). Vom zweiten Punkt \(x_1 = \frac{2\pi}{3}\), den man genau so erhält, wie im vorigen Fall, ist der nächste Punkt \(x_2 = -\frac{2\pi}{3} = \frac{4\pi}{3}-2\pi = \bigl(\frac{4\pi}{3}\bigr)_{2\pi}\) von beiden Punkten \(x_0=0\) und \(x_1\) eben genau den Abstand \(d\) entfernt. Die Addition (oder Subtraktion) von \(2\pi\) (oder Vielfachen davon) ändert an dem Punkt selbst nichts.

\(N=4\). Mit der gleichen Überlegung wie bei den drei Punkten nur mit \(d=\frac{\pi}{2}\) erhält man \[ x_0 = 0,\quad x_1 = \frac{\pi}{2},\quad x_2 = \bigl(\frac{2\pi}{2}\bigr)_{2\pi} = (\pi)_{2\pi} = -\pi,\quad x_3 = \bigl(\frac{3\pi}{2}\bigr)_{2\pi} = -\frac{\pi}{2}. \]

Erkennt man an dieser Stelle schon das Schema? Der Abstand ergibt sich im allgemeinen Fall, also für eine natürliche Zahl \(N\in\mathbb N\) stets zu \(d = \frac{2\pi}{N}\). Da wir von \(x_0 = 0\) „loslaufen“, ergeben sich die Punkte als Vielfache dieser Strecke. Formell also sind die Punkte \[ x_k = \Bigr(\frac{k2\pi}{N}\Bigl)_{2\pi},\quad k=0,1,\ldots,N-1, \] \(N\) äquidistante Punkte aus \([-\pi,\pi)\).

Mit diesen Punkten erhält man, vom Computer berechnet oder fleißig auf Papier, dann die Funktionswerte \(f(x_k), k=0,\ldots,N-1\). Widmet man sich zunächst der einfacheren Aufgabe, das Integral \[ \int_{-\pi}^{\pi} f(x)\,\text{d}x \] ausrechnen zu wollen, so ist eine Idee, das mit den eben ausgerechneten Funktionswerten an den äquidistanten Stützstellen zumindest Näherungsweise zu tun. Allgemein gelangt man damit zur numerischen Integration, die auch Quadratur genannt wird. Hier soll eine ganz einfache Variante Verwendung finden: Die zusammengesetzte Rechteck- oder Mittelpunktsregel. Wir stellen uns vor, an einem der Punkte \(x_k\) spannen wir nach links und rechts eine Strecke auf der \(x\)-Achse, die gerade so lang ist, wie die Hälfte der Strecke zum rechten plus die Hälfte der Strecke zum linken Nachbarn. Die Länge dieser Linie ist also genau ein solcher Abstand zweier Punkte, also \(\frac{2\pi}{N}\). Nimmt man dazu die Höhe \(f(x_k)\), so erhält man ein Rechteck, das auf dem Funktionswert in der Mitte der Strecke basiert. Summiert man all diese Rechtecke auf, setzt diese also zu einer großen, oben etwas ungleichmäßigen Fläche zusammen, ergibt sich auch schon der Name. Die folgende Abbildung illustriert diese Idee:

Anz. \(n\)1
Funktion \(f(x)\) 
Quadratur mit der Mittelpunktsregel am Beispiel verschiedener Funktionen. Dabei sind die Punkte die gemessenen Daten \(f(x_k)\), die mittig auf ihrem Rechteck liegen. Man beachte, dass das Rechteck, welches für eine gerade Anzahl Punkte zu \(x=-\pi\) gehört, eine Hälfte links und eine rechts besitzt. Dies liegt an der Periodizität.

Der Vorteil dieser Überlegung ist, dass die untere Strecke stets \(\frac{2\pi}{N}\) ist und der Flächeninhalt jedes einzelnen Rechtecks somit \(\frac{2\pi}{N}f(x_k)\). Summiert man diese Rechtecke, erhält man eine Näherung für das Integral, oder als Formel \[ \int_{-\pi}^{\pi} f(x)\,\text{d}x \approx \frac{2\pi}{N}\sum_{k=0}^{N-1}f(x_k). \] Mit größerem \(N\) erhält man eine genauere Darstellung der Fläche, wird also exakter. Man sieht jedoch auch am Sinus, dass selbst für eine große Anzahl \(n\) an Rechtecken stets eine Fläche zwischen diesen und dem Sinus weiß bleibt. Ebenso ist stets bei der Funktion bestehen aus den zwei Rechtecken die linke hälfte des Rechtecks, das zu \(x_0=0\) gehört zuviel Fläche. Diese Fläche wird jedoch auch mit zunehmendem \(n\) kleiner. So lässt sich über die Anzahl Datenpunkte \(N\), also die Anzahl vorhandener Werte \(f(x_k), k=0,\ldots,N-1\), die Genauigkeit steuern. Je mehr Speicher (und Rechenzeit für die Summe) man investiert, desto genauer wird im Allgemeinen die Näherung. Dieses Prinzip der Quadratur bringt die Integration auf den Computer – zumindest näherungsweise.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.