Wellenbaukasten

~ X: Das Gibbs-Phänomen

Josiah Willard Gibbs(1839-1903) Quelle: Wikimedia Eine der wesentlichen Fragen aus dem Beginn der Fourier-Analysis trat gegen Ende eines vorigen Beitrages schon einmal auf: Was haben die Fourier-Koeffizienten \(c_k(f)\) einer periodischen Funktion \(f\) mit \(f\) selbst zu tun? Die Beschäftigung mit dieser Frage hat zu Beginn des letzten Jahrhunderts viele Wissenschaftler beschäftigt und einige Gebiete der […] »

~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 […] »

~XII: Die diskrete Fourier-Transformation

Die Quadratur oder numerische Integration aus dem letzten Beitrag liefert einen wichtigen Baustein, um die eine diskrete Variante der Berechnung der Fourier-Koeffizienten anzugeben: die diskrete Fourier-Transformation, eine näherungsweise Berechnung der Fourier-Koeffizienten, die sich am Computer durchführen lässt. Mit der Quadratur basiert die Berechnung lediglich auf einer gegebenen endlichen Folge von Zahlen, den Abtastwerten \(f\bigl(\frac{2\pi k}{N}\bigr),\ […] »

~XIII: Die inverse diskrete Fourier-Transformation

Im letzten Beitrag wurde die diskrete Fourier-Transformation eingeführt. Eigentlich sind die Fourier-Koeffizienten als eine Art Baukasten eingeführt worden, denn sie sind Gewichte von gestauchten Sinus- und Kosinus-Funktionen, beispielsweise die Koeffizienten \(a_j\) für \(\cos(jx)\) oder die Koeffizienten \(c_k\) der komplexen Funktion \(\textrm{e}^{\textrm{i}kx}\). Diese Baukasten-Idee ist allerdings in gewissem Sinne die entgegengesetzte Richtung zur diskreten Fourier-Transformation. Während […] »

~XIV: Die Laufzeit der diskreten Fourier-Transformation

Eine zentrale Frage der Informatik ist, wie effizient ein Algorithmus ist. Beispielsweise, um zu überlegen, ob man eine gewisse Berechnung auch effizienter durchfphren kann. Stellt man sich einen Algorithmus wie eine Schulaufgabe vor, so ist Effizienz der Verbrauch an Papier und Bleistift, aber auch an Denk/Rechenzeit. Es ist schließlich unpraktikabel, wenn ein entworfener Algorithmus, also […] »

~ XV: Die schnelle Fourier-Transformation

John W. Tukey (1915-2000), Quelle: Wikimedia Die schnelle Fourier-Transformation ist die Grundlage dafür, dass, neben der Eleganz der Formeln selbst, sich die Fourier-Transformation am Computer so häufig wiederfindet und von einigen sogar als einer der wichtigsten Algorithmen des 20. Jahrhunderts angesehen wird. Wie der Name schon verrät, ist die schnelle Fourier-Transformation eine Berechnung der diskreten […] »

~ XVI: The Harmonic Analyzer

Abraham A. Michelson (1852–1931), Quelle: Wikimedia Bereits lange vor der schnellen Fourier-Transformation aus dem letzten Beitrag gab es viele Anwendungen der Fourier-Transformation, so auch in einigen mechanischen Vorgängern des Computers. Beispielsweise die Gezeitenberechenmaschine von Wiliam Thomson, 1. Baron Kelvin, (1824–1907) von 1973. Eine spezielle Maschine, die sich direkt dem widmet, was im dritten Beitrag als […]

»