Analysis-WS16-06

Dateiinhalt

5.6 Die komplexe Exponentialfunktion
------------------------------------

Man erweitert die Exponentialfunktion exp(x)=e^x auf die komplexen Zahlen durch die folgende Setzung:


e^(a+bi) = e^a * (cos(b) + i*sin(b))

also insbesondere e^(i*t) = cos(t) + i*sin(t).

Diese Definition ist aus folgenden Gruenden sinnvoll:

* Die Potenzgesetze gelten fort:

   e^(w+z) = e^w*e^z, selbst wenn w,z komplex sind

* Die Reihenentwicklung

   e^z = sum(z^k/k!, k=0..oo)

gilt auch fuer die oben definierte Fortsetzung der e-Funktion auf die
komplexen Zahlen.

NB: Man kann die Exponentialreihe als Definition der komplexen
Exponentialfunktion nehmen und dann die obigen Gleichungen beweisen.

Es gilt sin(t) = Im(e^(it)), cos(t) = Re(e^(it)). Daraus erhaelt man
folgende Reihenentwicklungen fuer die trigonometrischen Funktionen:

sin(x) = sum((-1)^k * x^(2k+1)/(2k+1)!, k=0..oo)
cos(x) = sum((-1)^k * x^(2k)/(2k)!, k=0..oo)

Daraus kann man z.B. ableiten

lim sin(x)/x = lim (x+O(x^2))/x = 1
x->0           x->0
lim (cos(x)-1)/x = lim (O(x^2))/x = 0
x->0               x->0

Fuer den speziellen Wert x=pi ergibt sich aus der Definition der
Exponentialfunktion die beruehmte Eulersche Formel

                     i pi 
                   e       =  -1

und ebenso e^(2*pi*i)=1. 




5.7 Polarkoordinaten
- - - - - - - - - -

Jede komplexe Zahl z=a+bi kann in der Form r*e^(i*phi) geschrieben
werden, wobei r=|z| = sqrt(a^2+b^2) und phi der Winkel des Ortsvektors
(a,b) ist. Es ist phi = arctan(b/a) oder phi = pi-arctan(b/a), je
nachdem, ob a positiv oder negativ ist. In vielen Programmiersprachen
gibt es die Funktion atan2 fuer diesen Zweck.

Man erhaelt als Anwendung eine praktische Darstellung der n-ten
Einheitswurzeln: und zwar definiert man

w_z := e^(2*pi*i / n)

und die Eckpunkte eines regelmaessigen n-Ecks vom Radius Eins in der
Zahlenebene sind dann w_z, w_z^2, ..., w_z^n, wobei w_z^n=1 gilt.

Anwendung: Die Gleichung e^x = z hat fuer alle z:CC eine Loesung,
naemlich ln(r)+i*(phi+2*pi*k), falls z=r*e^(i*phi) und k:ZZ beliebig.

Man findet die Notation Ln(z) fuer diese Loesung im Falle k=0 und
phi:]-pi;pi] und spricht vom Hauptwert des komplexen Logarithmus. Wir
verwenden diese Notation und Sprechweise nicht.

5.8 Komplexe Potenzen
---------------------

Fuer reelles a>0 und komplexes z definiert man

a^z := exp(z * ln(a))

Es gilt dann a^(w+z)=a^w*a^z. 


Potenzen mit komplexen Basen sind ebenso wie solche mit negativen
Basen nach wie vor nur fuer ganzzahlige Exponenten erklaert.

Zwar koennte man z.B. setzen, (-1)^(0.5) = i, aber warum nicht -i? Die
Festlegung auf positive Werte, wie bei den reellen Wurzeln
funktioniert ja im Komplexen nicht.

Bei komplexen Exponenten und negativen Basen ergeben sich weitere
Ungereimtheiten: 

e^(i pi) = -1

(-1)^i =?= e^(-pi)


e^(-2pi) =?= 1^i = 1 ????


5.9 Trigonometrische Funktionen im Komplexen
--------------------------------------------

Fuer reelles x rechnet man leicht nach, dass

cos(x) = (e^(ix)+e^(-ix))/2
sin(x) = (e^(ix)-e^(-ix))/(2i)


Diese Formeln machen nun auch fuer komplexes x Sinn und werden daher
als Definition der trig. Fkt. im Komplexen verwendet.  Die weiter oben
besprochenen Reihenentwicklungen fuer die trig. Fkt. gelten auch fuer
diese komplexen Erweiterungen. 


5.10 Diskrete Fouriertransformation
-----------------------------------

Definition: Seien x_0..x_(N-1) komplexe Zahlen. Die diskrete
Fouriertransformation (DFT) dieser Zahlen ist definiert durch die
Zahlen X_k

X_k = sum_{j=0}^{N-1} x_j * exp(- 2*pi/N * i * j * k)

Bemerkung: Es ist X_{k+tN} = X_k fuer t:ZZ, deshalb betrachtet man die
X_k nur fuer k=0..N-1.

Sind umgekehrt X_0..X_(N-1) gegeben, so koennen die x_j nach folgender
Formel ("inverse DFT") zurueckgewonnen werden.

x_j = 1/N * sum_{k=0}^{N-1} X_j * exp(2*pi/N * i * j * k)

Zum Beweis beachtet man, dass man sich wegen der Linearitaet des Uebergangs von (x_j)_j nach (X_k)_k auf den Spezialfall

                                 /  1, falls j=j0
                         x_j = <
			         \ 0, falls j=/=j0

fuer j0:0,..,N-1 beschraenken kann. Hier aber gilt X_k = exp(-2 pi i
 j0 k), also 1/N sum_{k=0}^{N-1} X_k exp(2pi i j k) = 1/N
 sum_{k=0}^{N-1} exp(2pi i (j-j0) k) = 1/N*N = 1, falls j=j0 und 0
 sonst.

Die DFT hat zahlreiche Anwendungen in der Signalverarbeitung, so etwa
im Mobilfunk und bei der MRT ("Kernspin"). Bei letzterem ist es so,
dass die empfangenen Antennensignale gerade der DFT der als Vektor
zusammengefassten Pixelwerte entsprechen. Es muss also im Rechner die
inverse DFT bestimmt werden. Aus Effizienzgruenden verwendet man
hierzu nicht direkt die obige Formel, sondern ein rekursives
Verfahren, welches als "Fast Fourier Transform" (FFT) bekannt ist.

Die FFT beruht darauf, dass man die DFT eines Vektors der Laenge N
berechnen, indem man zunaechst rekursiv die DFT der Eintraege an den
geraden und den ungeraden Positionen ausrechnet (jeweils Vektoren der
Laenge N/2) und die Ergebnisse dann nach einem bestimmten Schema zur
gesuchten DFT des Vektors der Laenge N zusammensetzt.


Man nutzt dabei aus, dass die Koeffizienten exp(- 2*pi/N * i * j * k)
in der Form w_N^(-jk) geschrieben werden koennen, wobei w_N eine
primitive N-te Einheitswurzel ist, und dass gilt

 w_N^(-2jk) = w_(N/2)^(-jk)           w_N^(-(2j+1)k) = w_N^(-k)*w_(N/2)^(-jk)

wobei N als gerade, oder besser gleich als Zweierpotenz vorausgesetzt sei. 


Setzt man naemlich x_(2l)=y_l und z_(2l+1)=z_l fuer l=0..N/2-1 und schreibt
Y_k, Z_k fuer die DFT (halber Groesse) der y_l bzw der z_l, so erhaelt man: 

X_k = sum_(l=0)^(N/2-1) y_l exp(-2pi i l k/(N/2)) +
      sum_(l=0)^(N/2-1) z_l exp(-2pi i l k/(N/2)) * exp(-2 pi i k / N)
    = Y_(k mod N/2) + Z_(k mod N/2) * exp(-2 pi i k /(N/2))

Fuer den letzten Schritt benutzt man, dass exp(-2 pi i k / (N/2)) =
exp(-2 pi i (k mod N/2) / (N/2)). 

Hat man also die Y_k, Z_k fuer k=0..N/2-1 bereits vorliegen
(ueblicherweise durch rekursive Anwendung dessselben Verfahrens), so
erhaelt man die gesuchten Werte X_k durch die Setzungen

X_k = Y_k + Z_k * w_N^(-k), falls k<N/2
X_k = Y_(k-N/2) + Z_(k-N/2) * w_N^(-k), falls k>=N/2

deren Auswertung linearen (in N) Aufwand macht.

Ist also T(N) der Aufwand fuer die Berechnung einer DFT der Groesse N,
so ergibt sich

                              T(N) = 2*T(N/2) + O(N)

Diese Gleichung hat die Loesung T(N) = O(N * log(N)), was einem fast
linearen Anwachsen des Aufwands mit N bedeutet anstelle des
quadratischen Wachstums bei direkter Verwendung der Definition.


Beispiel: Es sei N=8 und x0 .. x7 gegeben.

Zunaechst teilt man in y0..y3 und z0..z3 auf. Z.B. y3=x6 und z2=y5.

Liegen Y0..Y3 und Z0..Z3 aus (rekursiven) Nebenrechnungen vor, so bildet man

X0 = Y0 + Z0
X1 = Y1 + Z1 * (1/sqrt(2)-1/sqrt(2) i)
X2 = Y2 + Z2 * (-i)
X3 = Y3 + Z3 * (-1/sqrt(2)-1/sqrt(2) i)
X4 = Y0 + Z0 * (-1)
X5 = Y1 + Z1 * (-1/sqrt(2)+1/sqrt(2) i)
X6 = Y2 + Z2 * i
X7 = Y3 + Z3 * (1/sqrt(2)+1/sqrt(2) i)

Denn exp(2pi i/8) = 1/sqrt(2)+i * sqrt(2)