Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


41. Die schnelle Fourier-Transformation



Interpolation mit Hilfe der Einheitswurzeln

Nachdem wir nun über ein schnelles Verfahren zur Berechnung von Polynomen in einer spezifischen Menge von Punkten verfügen, benötigen wir nur noch eine schnelle Methode zur Interpolation von Polynomen mit Hilfe der gleichen Punkte, um ein schnelles Verfahren zur Multiplikation von Polynomen zu erhalten. Erstaunlicherweise zeigt es sich, daß die Interpolation für die komplexen Einheitswurzeln durch Ausführung des Programms für eine spezielle Menge von Punkten realisiert werden kann! Dies ist ein spezielles Beispiel einer grundlegenden »Inversionseigenschaft« der Fourier-Transformation, aus der viele wichtige mathematische Ergebnisse hergeleitet werden können.

Für unser Beispiel mit N = 8 besteht das Problem der Interpolation darin, das Polynom

r(x) = r0 + r1x + r2x2 + r3x3 + r4x4 + r5x5 + r6x6 + r7x7

zu bestimmen, das die Werte

r(w80) = r0,       r(w81) = r1,       r(w82) = r2,       r(w83) = r3,
r(w84) = r4,       r(w85) = r5,       r(w86) = r6,       r(w87) = r7.

besitzt. Wenn die betreffenden Punkte die komplexen Einheitswurzeln sind, ist das Problem der Interpolation exakt das zu dem der Berechnung »inverse« Problem. Wenn wir

s(x) = s0 + s1x + s2x2 + s3x3 + s4x4 + s5x5 + s6x6 + s7x7

setzen, können wir die Koeffizienten

r0, r1, r2, r3, r4, r5, r6, r7

erhalten, indem wir einfach das Polynom s(x) für die reziproken Werte der komplexen Einheitswurzeln

W8-1: w80, w8-1, w8-2, w8-3, w8-4, w8-5, w8-6, w8-7.

berechnen. Doch das ist die gleiche Folge der komplexen Einheitswurzeln, nur in einer anderen Reihenfolge:

W8-1: w80, w87, w86, w85, w84, w83, w82, w81.

Mit anderen Worten, wir können für die Interpolation das gleiche Programm verwenden wie für die Berechnung; es ist lediglich eine einfache Umordnung der Punkte, für die die Berechnung erfolgt, erforderlich.

Der Beweis dieser Tatsache erfordert einige elementare Operationen mit endlichen Summen; mit solchen Operationen nicht vertraute Leser können das Folgende überspringen und am Ende dieses Abschnitts weiterlesen. Wenn man s(x) für den reziproken Wert der t-ten N-ten Einheitswurzel (wN-i) berechnet, erhält man

Formel

Im letzten Ausdruck verschwindet beinahe alles, da die innere Summe trivialerweise N ergibt, falls i = t gilt. Falls i <> t ist, hat sie den Wert

Formel

Beachten Sie, daß ein zusätzlicher Faktor N auftritt. Dies ist der »Inversionssatz« für die diskrete Fourier-Transformation, der aussagt, daß ein Polynom mit der gleichen Methode in beiden Richtungen umgewandelt werden kann: aus seiner Koeffizientendarstellung in seine Darstellung mit Hilfe der komplexen Einheitswurzeln und umgekehrt.

Eigenschaft 41.2 Ein Polynom vom Grad N - 1 kann mit Hilfe der N-ten Einheitswurzeln mit ungefähr N lg N Multiplikationen interpoliert werden.

Auch wenn die oben dargelegten mathematischen Zusammenhänge kompliziert erscheinen mögen, lassen sich die Ergebnisse sehr leicht anwenden: Um ein Polynom mit Hilfe der N-ten Einheitswurzeln zu interpolieren, verwende man die gleiche Prozedur wie für die Berechnung, verwende dabei jedoch die für die Interpolation vorgesehenen Werte als Koeffizienten des Polynoms, ordne dann die Lösungen um und dividiere sie durch N. w.z.b.w.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]