Robert Sedgewick: Algorithmen

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


41. Die schnelle Fourier-Transformation



Berechnen, Multiplizieren, Interpolieren

Die allgemeine Strategie der verbesserten Methode für die Polynom-Multiplikation, die wir betrachten werden, nutzt die Tatsache aus, daß ein Polynom vom Grad N - 1 durch seine Werte in N verschiedenen Punkten vollständig bestimmt ist. Wenn wir zwei Polynome vom Grad N - 1 miteinander multiplizieren, erhalten wir ein Polynom vom Grad 2N - 2; wenn wir die Werte dieses Polynoms in 2N - 1 Punkten ermitteln können, ist es vollständig bestimmt. Wir können jedoch den Wert des resultierenden Polynoms in einem beliebigen Punkt bestimmen, indem wir einfach die Werte der beiden zu multiplizierenden Polynome in diesem Punkt berechnen und dann diese Zahlen multiplizieren.

Dies führt zu dem folgenden allgemeinen Schema für die Multiplikation zweier Polynome vom Grad N - 1:

Um zum Beispiel r(x) = p(x)q(x) mit p(x) = 1 + x + x2 und q(x) = 2 - x + x2 zu berechnen, können wir p(x) und q(x) in fünf beliebigen Punkten berechnen, etwa in -2, -1, 0, 1, 2, wobei wir die Werte

[p(-2), p(-1), p(0), p(1), p(2)] = [3, 1, 1, 3, 7],
[q(-2), q(-1), q(0), q(1), q(2)] = [8, 4, 2, 2, 4]

erhalten. Indem wir diese Werte paarweise miteinander multiplizieren, erhalten wir genügend viele Werte des sich als Produkt ergebenden Polynoms

[r(-2), r(-1), r(0), r(1), r(2)] = [24, 4, 2, 6, 28],

so daß dessen Koeffizienten mittels Interpolation bestimmt werden können. Mit Hilfe der Lagrangeschen Formel ergibt sich

Formel

was sich zu dem Ergebnis vereinfachen läßt:

r(x) = 2 + x + 2x2 + x4.

In der oben beschriebenen Form ist dieses Verfahren kein vorteilhafter Algorithmus für die Multiplikation von Polynomen, da die besten Algorithmen, die wir bisher sowohl für die Berechnung (wiederholte Anwendung des Horner-Schemas) als auch für die Interpolation (Lagrangesche Formel) kennengelernt haben, N2 Operationen erfordern. Es besteht jedoch eine gewisse Hoffnung, einen besseren Algorithmus zu finden, da das Verfahren für jede beliebige Wahl von 2N - 1 verschiedenen Punkten zum Ziel führt und man mit Recht davon ausgehen kann, daß Berechnung und Interpolation für bestimmte Punktmengen einfacher sein werden als für andere.


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