Robert Sedgewick: Algorithmen

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


41. Die schnelle Fourier-Transformation



Komplexe Einheitswurzeln

Es zeigt sich, daß die für die Interpolation und Berechnung des Polynoms am besten geeigneten Punkte komplexe Zahlen sind, und zwar eine spezielle Menge komplexer Zahlen, die komplexe Einheitswurzeln genannt werden.

An dieser Stelle ist es erforderlich, an einige Tatsachen aus der komplexen Analysis zu erinnern. Die Zahl i = sqrt-1 ist eine imaginäre Zahl; obwohl sqrt-1 als reelle Zahl nicht definiert ist, ist es zweckmäßig, ihr einen Namen zu geben, i, und algebraische Operationen mit ihr auszuführen, wobei i2 durch -1 ersetzt wird. Eine komplexe Zahl besteht aus zwei Teilen, dem Realteil und dem Imaginärteil; man schreibt sie gewöhnlich in der Form a + bi, wobei a und b reelle Zahlen sind. Für die Multiplikation komplexer Zahlen gelten die üblichen Regeln, wobei jedoch i2 durch -1 zu ersetzen ist. Zum Beispiel ist

(a + bi)(c + di) = (ac - bd) + (ad + bc)i.

Manchmal kann bei der Ausführung einer komplexen Multiplikation der Realteil oder der Imaginärteil verschwinden. Zum Beispiel erhält man

(1 - i)(1 - i) = -2i,
(1 + i)4 = -4,
(1 + i)8 = 16.

Wenn wir die letzte Gleichung normieren, indem wir sie durch 16 = (sqrt2)8 dividieren, finden wir, daß

Formel

gilt.

Es gibt sogar viele komplexe Zahlen, die beim Potenzieren 1 ergeben. Dies sind die sogenannten komplexen Einheitswurzeln. Tatsächlich zeigt es sich, daß für jedes N genau N komplexe Zahlen z mit zN = 1 existieren. Eine von ihnen, die mit wN bezeichnet wird, wird die N-te Haupteinheitswurzel genannt; die anderen erhält man, indem man wN in die k-te Potenz erhebt, für k = 0, 1, 2, ..., N - 1. Zum Beispiel können wir die achten Einheitswurzeln wie folgt aufzählen:

w80, w81, w82, w83, w84, w85, w86, w87.

Die erste Wurzel, wN0 , hat den Wert 1, und die zweite, wN1 , ist die Hauptwurzel. Weiterhin hat für gerades N die Wurzel wNN/2 den Wert -1 (da (wNN/2)2 = 1). Die genauen Werte der Wurzeln sind einstweilen nicht von Bedeutung. Wir werden nur einfache Eigenschaften benutzen, die leicht aus der grundlegenden Tatsache hergeleitet werden können, daß die N-te Potenz jeder N-ten Einheitswurzel den Wert 1 haben muß.


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