Teaching


In my previous post I illustrated why it is not possible to compute the Jordan canonical form numerically (i.e. in floating point numbers). The simple reason: For every matrix {A} and every {\epsilon>0} there is a matrix {A_{\epsilon}} which differs from {A} by at most {\epsilon} (e.g. in every entry – but all norms for matrices are equivalent, so this does not really play a role) such that {A_{\epsilon}} is diagonalizable. So why should you bother about computing the Jordan canonical form anyway? Or even learning or teaching it? Well, the prime application of the Jordan canonical form is to calculate solutions of linear systems of ODEs. The equation

\displaystyle y'(t) = Ay(t),\quad y(0) = y_{0}

with matrix {A\in {\mathbb R}^{n\times n}} and initial value {y_{0}\in{\mathbb R}^{n}} (both could also be complex). This system has a unique solution which can be given explicitly with the help of the matrix exponential as

\displaystyle y(t) = \exp(At)y_{0}

where the matrix exponential is

\displaystyle \exp(At) = \sum_{k=0}^{\infty}\frac{A^{k}t^{k}}{k!}.

It is not always simple to work out the matrix exponential by hand. The straightforward way would be to calculate all the powers of {A}, weight them by {1/k!} and sum the series. This may be a challenge, even for simple matrices. My favorite example is the matrix

\displaystyle A = \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix}.

Its first powers are

\displaystyle A^{2} = \begin{bmatrix} 1 & 1\\ 1 & 2 \end{bmatrix},\quad A^{3} = \begin{bmatrix} 1 & 2\\ 2 & 3 \end{bmatrix}

\displaystyle A^{4} = \begin{bmatrix} 2 & 3\\ 3 & 5 \end{bmatrix},\quad A^{5} = \begin{bmatrix} 3 & 5\\ 5 & 8 \end{bmatrix}.

You may notice that the Fibonicci numbers appear (and this is pretty clear on a second thought). So, finding a explicit form for {\exp(A)} leads us to finding an explicit form for the {k}-th Fibonacci number (which is possible, but I will not treat this here).

Another way is diagonalization: If {A} is diagonalizable, i.e. there is an invertible matrix {S} and a diagonal matrix {D} such that

\displaystyle S^{-1}AS = D\quad\text{or, equivalently}\quad A = SDS^{-1},

you see that

\displaystyle \exp(At) = S\exp(Dt)S^{-1}

and the matrix exponential of a diagonal matrix is simply the exponential function applied to the diagonal entries.

But not all matrices are diagonalizable! The solution that is usually presented in the classroom is to use the Jordan canonical form instead and to compute the matrix exponential of Jordan blocks (using that you can split a Jordan block {J = D+N} into the sum of a diagonal matrix {D} and a nil-potent matrix {N} and since {D} and {N} commute one can calculate {\exp(J) = \exp(D)\exp(N)} and both matrix exponentials are quite easy to compute).

But in light of the fact that there are a diagonalizable matrices arbitrarily close to any matrix, on may ask: What about replacing a non-diagonalizable matrix {A} with a diagonalizable one (with a small error) and then use this one?

Let’s try this on a simple example:

We consider

\displaystyle A = \begin{bmatrix} -1 & 1\\ 0 & -1 \end{bmatrix}

which is not diagonalizable. The linear initial value problem

\displaystyle y' = Ay,\quad y(0) = y_{0}

has the solution

\displaystyle y(t) = \exp( \begin{bmatrix} -t & t\\ 0 & -t \end{bmatrix}) y_{0}

and the matrix exponential is

\displaystyle \begin{array}{rcl} \exp( \begin{bmatrix} -t & t\\ 0 & -t \end{bmatrix}) & = &\exp(\begin{bmatrix} -t & 0\\ 0 & -t \end{bmatrix})\exp(\begin{bmatrix} 0 & t\\ 0 & 0 \end{bmatrix})\\& = &\begin{bmatrix} \exp(-t) & 0\\ 0 & \exp(-t) \end{bmatrix}\begin{bmatrix} 1 & t\\ 0 & 1 \end{bmatrix}\\ &=& \begin{bmatrix} \exp(-t) & t\exp(-t)\\ 0 & \exp(-t) \end{bmatrix}. \end{array}

So we get the solution

\displaystyle y(t) = \begin{bmatrix} e^{-t}(y^{0}_{1} + ty^{0}_{2})\\ e^{-t}y^{0}_{2} \end{bmatrix}.

Let us take a close-by matrix which is diagonalizable. For some small {\epsilon} we choose

\displaystyle A_{\epsilon} = \begin{bmatrix} -1 & 1\\ 0 & -1+\epsilon \end{bmatrix}.

Since {A_{\epsilon}} is upper triangular, it has its eigenvalues on the diagonal. Since {\epsilon\neq 0}, there are two distinct eigenvalues and hence, {A_{\epsilon}} is diagonalizable. Indeed, with

\displaystyle S = \begin{bmatrix} 1 & 1\\ 0 & \epsilon \end{bmatrix},\quad S^{-1}= \begin{bmatrix} 1 & -\tfrac1\epsilon\\ 0 & \tfrac1\epsilon \end{bmatrix}

we get

\displaystyle A = S \begin{bmatrix} -1 & 0 \\ 0 & -1+\epsilon \end{bmatrix}S^{-1}.

The matrix exponential of {A_{\epsilon}t} is

\displaystyle \begin{array}{rcl} \exp(A_{\epsilon}t) &=& S\exp( \begin{bmatrix} -t & 0\\ 0 & -t(1-\epsilon) \end{bmatrix} )S^{-1}\\ &=& \begin{bmatrix} e^{-t} & \tfrac{e^{-(1-\epsilon)t} - e^{-t}}{\epsilon}\\ 0 & e^{-(1-\epsilon)t} \end{bmatrix}. \end{array}

Hence, the solution of {y' = Ay}, {y(0) = y_{0}} is

\displaystyle y(t) = \begin{bmatrix} e^{-t}y^{0}_{1} + \tfrac{e^{-(1-\epsilon)t} - e^{-t}}{\epsilon}y^{0}_{2}\\ e^{-(1-\epsilon)t}y^{0}_{2} \end{bmatrix}.

How is this related to the solution of {y'=Ay}? How far is it away?

Of course, the lower right entry of {\exp(A_{\epsilon}t)} converges to {e^{-t}} for {\epsilon \rightarrow 0}, but what about the upper right entry? Note that the entry

\displaystyle \tfrac{e^{-(1-\epsilon)t} - e^{-t}}{\epsilon}

is nothing else that the (negative) difference quotient for the derivative of the function {f(a) = e^{-at}} at {a=1}. Hence

\displaystyle \tfrac{e^{-(1-\epsilon)t} - e^{-t}}{\epsilon} \stackrel{\epsilon\rightarrow 0}{\longrightarrow} -f'(1) = te^{-t}

and we get

\displaystyle \exp(A_{\epsilon}t) \stackrel{\epsilon\rightarrow 0}{\longrightarrow} \begin{bmatrix} e^{-t} & te^{-t}\\ 0 & e^{-t} \end{bmatrix} = \exp(At)

as expected.

It turns out that a fairly big \epsilon is already enough to get a quite good approximation and even the correct asymptotics: The blue curve it first component of the exact solution (initialized with the second standard basis vector), the red one corresponds \epsilon = 0.1 and the yellow on (pretty close to the blue on) is for \epsilon = 0.01.

 

 

to  $\e102_jordan_ode

 

Advertisements

I remember from my introductory class in linear algebra that my instructor said

It is impossible to calculate the Jordan canonical form of a matrix numerically.

Another quote I remember is

The Jordan canonical form does not depend continuously on the matrix.

For both quotes I did not remember the underlying reasons and since I do teach an introductory class on linear algebra this year, I got thinking about these issues again.

Here is a very simple example for the fact in the second quote:

Consider the matrix

\displaystyle A_{\varepsilon} = \begin{pmatrix}1 & \varepsilon\\ 0 & 1\end{pmatrix}

for {\varepsilon>0}. This matrix has {1} as a double eigenvalue, but the corresponding eigenspace is one-dimensional and spanned by {v_{1} = e_{1}}. To extend this vector to a basis we calculate a principle vector by solving

\displaystyle (A_{\varepsilon}-I)v_{2} = v_{1}

which leads to

\displaystyle v_{2} = \begin{pmatrix} 0\\\varepsilon^{-1} \end{pmatrix}.

Defining {S = [v_{1}\, v_{2}]} we get the Jordan canonical form of {A_{\varepsilon}} as

\displaystyle J_{\varepsilon} = S^{-1}A_{\varepsilon}S = \begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}

So we have

\displaystyle A_{\varepsilon}\rightarrow A = I\quad\text{and}\quad J_{\varepsilon} \rightarrow J = \begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix},

but {J} is not the Jordan canonical form of {A}. So, in short: The Jordan canonical form of the limit of {A_{\varepsilon}} is not the limit of the Jordan canonical form of {A_{\varepsilon}}. In other words: Taking limits does not commute with forming the Jordan canonical form.

A side note: Of course, the Jordan canonical form is not even unique in general, so speaking of “dependence on the matrix” is an issue. What we have shown is, that there is no way to get continuous dependence on the matrix even if non-uniqueness is not an issue (like in the example above).

What about the first quote? Why is it impossible to compute the Jordan canonical form numerically? Let’s just try! We start with the simplest non-diagonalizable matrix

\displaystyle A = \begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}

If we ask MATLAB or Octave to do the eigenvalue decomposition we get

>> [V,D] = diag(A)
V =

1.00000 -1.00000
0.00000  0.00000

D =

1 0
0 1

We see that {V} does not seem to be invertible and indeed we get

>> rank(V)
ans = 1

What is happening? MATLAB did not promise the produce an invertible {V} and it does not promise that the putcome would fulfill {V^{-1}AV = D} (which is my definition of diagonalizability). It does promise that {AV = VD} and in fact

>> A*V
ans =

1.00000  1.00000
0.00000 -0.00000

>> V*D
ans =

1.00000 -1.00000
0.00000  0.00000

>> A*V-V*D
ans =

0.0000e+00 2.2204e-16
0.0000e+00 0.0000e+00

so the promised identity is fulfilled up to machine precision (which is actually equal \texttt{2.2204e-16} and we denote it by {\epsilon} from here on).

How did MATLAB diagonalize this matrix? Here is the thing: The diagonalizable matrices are dense in {{\mathbb C}^{n\times n}}! (You probably have heard that before…) What does that mean numerically? Any matrix that you represent in floating point numbers is actually a representative of a whole bunch of matrices. Each entry is only known up to a certain precision. But this bunch of matrices does contain some matrix which is diagonalizable! This is exactly, what it means to be a dense set! So it is impossible to say if a matrix given in floating point numbers is actually diagonalizable or not. So, what matrix was diagonalized by MATLAB? Let us have closer look at the matrix {V}: The entries in the first row are in fact {1} and {-1}:

>> V(1,:)
ans =
1 -1

In the second row we have

>> V(2,1)
ans =
0
>> V(2,2)
ans = 2.2204e-16

and there we have it. The inverse of {V} does exist (although the matrix has numerical rank {1}) and it is

>> inv(V) warning: matrix singular to machine precision, rcond = 1.11022e-16
ans =

1.0000e+00 4.5036e+15
0.0000e+00 4.5036e+15

and note that \texttt{4.5036e+15} is indeed just the inverse of the machine precision, so this inverse is actually 100% accurate. Recombining gives

>> inv(V)*D*V warning: matrix singular to machine precision, rcond = 1.11022e-16
ans =

1 0
0 1

which is not even close to our original {A}.
How is that? Here is a solution. The matrix

\displaystyle \tilde A = \begin{pmatrix} 1 & 1\\ 0 & 1+\epsilon^{-2} \end{pmatrix}

is indistinguishable from {A} numerically. However, it has two distinct eigenvalues, so it is diagonalizable. Indeed, a basis of eigenvectors is

\displaystyle \tilde V = \begin{pmatrix} 1 & -1\\ 0 & \epsilon^{-2} \end{pmatrix}

which is indistinguishable from {V} above and it holds that

\displaystyle \tilde V^{-1}\tilde A\tilde V = \begin{pmatrix} 1 & 0\\ 0 & 1+\epsilon^{-2}. \end{pmatrix}

which is indistinguishable from D.

Im Wintersemster 2018/19 habe ich die Vorlesung “Lineare Algebra 1” gehalten. Hier die lecture notes dazu:

Im Wintersemester 2015/2016 habe ich die Vorlesung “Analysis 3” gehalten und dazu dieses Skript verfasst:

Diese Seite dient dazu, in den Kommentaren gefundene Fehler zu sammlen und hier zu dokumentieren.

Errata zur gedruckten Version:

  • Seite 16: “|\det(U)| und \int_{\mathbb{R}} statt \int_{\mathbb{-R}}
  • Seite 17, zweiter Absatz: “wobei G eine Teilmenge des \mathbb{R}^{n+1} ist”
  • Seite 34 Beispiel 18.5 ii) Argument leicht umformuliert da vorher nicht ganz korrekt
  • Seite 45: \varphi_2 = \dots = \varphi''
  • Seite 58 Satz 19.3 Schritt2. die letzte Zeile. ” Dies heißt aber, dass \varphi^1,\dots,\varphi^n linear abhängig sind. Widerspruch!”
    Korrektur: “Dies heißt aber, dass \psi^1,\dots,\psi^n linear abhängig sind. Widerspruch!”
  • Seite 59 die erste Bemerkung (zweite Zeile): Lösungen \varphi^k statt \psi^k;
  • Seite 61 Korollar 19.7 “Fundamentalmatrix zu y'=A(x)y” statt “y'=A(x)“.
  • Seite 70, Beweis von Satz 19.17: +b(x) statt -b(x).
  • Seite 80, Beipsiel 19.29, 2.: \mathrm{i}\omega ist eine Nullstelle.
  • Seite 107, Satz 21.4: \tilde\phi:\tilde T\to M.
  • Seite 116: \omega_5 = \tfrac{8\pi^2}{3}.
  • Seite 137 unten: “aus f_\nu\to f glm. folgt…”
  • Seite 140, Beweis von Lemma 23.11: \partial^\alpha\phi_\nu\stackrel{\mathcal{D}}{\to}\partial^\alpha\phi .
  • Seite 141: [x\phi(x)]_{-\infty}^0
  • Seite 152: (LE)*\rho = \delta_0*\rho

Das Skript zur zugehörigen Vorlesung “Analysis 2” ist hier zu finden.

Im Sommersemester 2015 habe ich die Vorlesung “Analysis 2” gehalten und dazu dieses Skript verfasst:

Diese Seite dient dazu, in den Kommentaren gefundene Fehler zu sammlen und hier zu dokumentieren.

Errata zur gedruckten Version:

  • p. 54, Beweis zu Satz 13.32: In der letzten Zeile müsste D_i f(x) statt D_if(0) stehen.
  • p. 61, Beweis zu Satz 14.8: Nach dem ersten Absatz müsste es heißen v-y=A(g(v))(g(v)-g(y)).
  • p. 63, Beweis zu Satz14.11: In der Zeile unter (*) ist ein „gilt“ zu viel.
  • p. 66, Beweis zu Satz14.13: In der vorletzten Zeile fehlt das „d“ von „passend“.
  • p. 82. Lemma 15.16: In der ersten Zeile muss es  j\neq k heißen.
  • p. 93, Zeile über Beispiel 16.1: Es muss heißen „..allerdings keine brauchbaren Sätze”.
  • p. 106, Beweis zu Satz 16.24: Im ersten Absatz, dritte Zeile: „Somit ist x\mapsto D_t f(x,t)…“
  • p. 108, Beispiel 16.26: dritte Gleichung, zweites Integral muss heißen
    \int_0^\infty x^3\exp(-tx)\mathrm{d}x = \tfrac{6}{t^4}.
  • p. 108, Beispiel 16.26: vorletztes Integral muss heißen \int_0^\infty x^n\exp(-x)\mathrm{d}x = n!.
  • p. 109,  zweiter Absatz muss lauten “… bei jedem Integral um einen Grenzwert…”.
  • p. 109 letzter Satz muss lauten “…und den Größen…”.
  • p. 110, Satz 16.27: Letzter Satz muss lauten “Ist \lambda(M)<\infty, so ist f\in L^1(\mathbb{R}).

Zur ergänzenden Vorlesung zur Analysis 2 für Physiker mit der knappen “Hands-on” Einführung in die Vektoranalysis gibt es hier ebenfalls das Skript:

Errata:

In my Analysis class today I defined the trigonometric functions {\sin} and {\cos} by means of the complex exponential. As usual I noted that for real {x} we have {|\mathrm{e}^{\mathrm{i} x}| = 1}, i.e. {\mathrm{e}^{\mathrm{i} x}} lies on the complex unit circle. Then I drew the following picture:

 

075_exp

This was meant to show that the real part and the imaginary part of {\mathrm{e}^{\mathrm{i} x}} are what is known as {\cos(x)} and {\sin(x)}, respectively.

After the lecture a student came to me and noted that we could have started with {a>1} and note that {|a^{\mathrm{i} x}|=1} and could do the same thing. The question is: Does this work out? My initial reaction was: Yeah, that works, but you’ll get a different {\pi}

But then I wondered, if this would lead to something useful. At least for the logarithm one does a similar thing. We define {a^x} for {a>0} and real {x} as {a^x = \exp_a(x) = \exp(x\ln(a))}, notes that this gives a bijection between {{\mathbb R}} and {]0,\infty[} and defines the inverse function as

\displaystyle  \log_a = \exp_a^{-1}.

So, nothing stops us from defining

\displaystyle  \cos_a(x) = \Re(a^{\mathrm{i} x}),\qquad \sin_a(x) = \Im(a^{\mathrm{i} x}).

Many identities are still valid, e.g.

\displaystyle  \sin_a(x)^2 + \cos_a(x)^2 = 1

or

\displaystyle  \cos_a(x)^2 = \tfrac12(1 + \cos_a(2x)).

For the derivative one has to be a bit more careful as it holds

\displaystyle  \sin_a'(x) = \ln(a)\cos_a(x),\qquad \cos_a'(x) = -\ln(a)\sin_a(x).

Coming back to “you’ll get a different {\pi}”: In the next lecture I am going to define {\pi} by saying that {\pi/2} is the smallest positive root of the functions {\cos}. Naturally this leads to a definition of “{\pi} in base {a}” as follows:

Definition 1 {\pi_a/2} is the smallest positive root of {\cos_a}.

How is this related to the area of the unit circle (which is another definition for {\pi})?

The usual analysis proof goes by calculating the area of a quarter the unit circle by integral {\int_0^1 \sqrt{1-x^2} dx}.

Doing this in base {a} goes by substituting {x = \sin_a(\theta)}:

\displaystyle  \begin{array}{rcl}  \int\limits_0^1\sqrt{1-x^2}\, dx & = & \int\limits_0^{\pi_a/2}\sqrt{1-\sin_a(\theta)^2}\, \ln(a)\cos_a(\theta)\, d\theta\\ & = & \ln(a) \int\limits_0^{\pi_a/2} \cos_a(\theta)^2\, d\theta\\ & = & \ln(a) \frac12 \int\limits_0^{\pi_a/2}(1 + \cos_a(2\theta))\, d\theta\\ & = & \frac{\ln(a)}{2} \Big( \frac{\pi_a}{2} + \int\limits_0^{\pi_a/2}\cos_a(2\theta)\, d\theta\\ & = & \frac{\ln(a)\pi_a}{4} + 0. \end{array}

Thus, the area of the unit circle is now {\ln(a)\pi_a}

Oh, and by the way, you’ll get the nice identity

\displaystyle  \pi_{\mathrm{e}^\pi} = 1

(and hence, the area of the unit circle is indeed {\ln(\mathrm{e}^\pi)\pi_{\mathrm{e}^\pi} = \pi})…

This is the last part of the lecture notes for the course in integral transforms.

1. Fourierreihen und das Abtasttheorem

Neben der Fourier-Transformation auf { L^1({\mathbb R}^d)}, { L^2({\mathbb R}^d)}, {\mathcal{S}{{\mathbb R}^d}} und {\mathcal{S}({\mathbb R}^d)'} sind auch analoge Transformationen für Funktionen {f} auf Rechtecken {\prod_{k=1}^d[a_k,b_k]\subset{\mathbb R}^d} interessant. Dies führt auf die sogenannten Fourierreihen. Mit ihrer Hilfe werden wir das Abtasttheorem beweisen

1.1. Fourierreihen in {L^2}

Wir betrachten vorerst eindimensionale Signale {u:[-\pi,\pi]\rightarrow {\mathbb C}}. Signale auf allgemeinen beschränkten Intervallen erhalten wir durch Skalierung und höherdimensionale Abbildungen werden wir durch “Tensorproduktbildung” behandeln können. In diesem Abschnitt werden wir uns alle Funktionen auf einem beschränkten Intervall (wie z.B. {[-\pi,\pi]}) als periodisch auf ganz {{\mathbb R}} fortgesetzt denken. Z.B. hat die Funktion {u(x) = x} (auf {[-\pi,\pi]}) für uns hier eine Sprungstelle bei {x=\pi}. Als Nebeneffekt können wir Integrale von periodischen Funktionen auch über verschobene Intervalle ausrechnen, wenn es sich anbietet, d.h. für {2\pi}-periodisches {u} und jedes {a\in{\mathbb R}} gilt

\displaystyle  \int_{-\pi}^\pi u(x){\mathrm d}{x} = \int_{a}^{2\pi+a}u(x){\mathrm d}{x}.

Im Falle von Fourierreihen können wir, anders als im Fall der Fourier-Transformation, gleich im Hilbert-Raum {L^2([-\pi,\pi])} beginnen. Wir statten ihn mit dem normalisierten Skalarprodukt

\displaystyle  \langle u,v\rangle_{[-\pi,\pi]} = \frac{1}{2\pi}\int_{-\pi}^\pi u(x)\overline{v}(x){\mathrm d}{x}

aus, welches die Norm

\displaystyle  \|u\|_{[-\pi,\pi]} = \frac{1}{\sqrt{2\pi}}\Big(\int_{-\pi}^\pi |u(x)|^2{\mathrm d}{x}\Big)^{1/2}

nach sich zieht.

Bei komplexen Fourier-Reihen wird eine Funktion {u:[-\pi,\pi]\rightarrow{\mathbb C}} als Reihe in den komplexen Exponentialfunktionen

\displaystyle  e_k(x) = \mathrm{e}^{\mathrm{i} kx}\quad (k\in{\mathbb Z})

geschrieben. Die Zahlen

\displaystyle  c_k = \frac{1}{2\pi}\int_{-\pi}^\pi u(x)\mathrm{e}^{-\mathrm{i} kx}{\mathrm d}{x} = \frac{1}{2\pi}\int_{-\pi}^\pi u(x)\overline{e_k(x)}{\mathrm d}{x}

heißen (komplexe) Fourier-Koeffizienten von {u}.

Satz 1 Die Funktionen {(e_k)_{k\in{\mathbb Z}}} bilden eine Orthonormalbasis von {L^2([-\pi,\pi])}. Insbesondere lässt sich jede Funktion {u\in L^2([-\pi,\pi])} als Fourierreihe

\displaystyle  u = \sum_{k\in{\mathbb Z}}c_k e_k

schreiben, wobei die Reihe im {L^2}-Sinn konvergiert. Insbesondere gilt

\displaystyle  \|u\|_{[-\pi,\pi]}^2 = \sum_{k\in{\mathbb Z}} |c_k|^2 \qquad \text{(Parseval Identit\"at)}.

Beweis: Die Orthonormalität der {e_k} lässt sich elementar nachrechnen. Um zu zeigen, dass die {e_k} eine Basis bilden, zeigen wir, dass die lineare Hülle der {e_k} dicht in {L^2([-\pi,\pi])} liegt. Nach dem Weierstraßschen Approximationssatz für trigonometrische Polynome existiert für jede stetige Funktion {u:[-\pi,\pi]\rightarrow{\mathbb C}} und jedes {\varepsilon>0} ein trigonometrisches Polynom {P_k(x) = \sum_{n=-k}^k a_ne_n(x)}, so dass {|u(x) - P_k(x)|\leq \varepsilon}. Es folgt

\displaystyle  \|u-P_k\|_{[-\pi,\pi]}^2 = \frac{1}{2\pi}\int_{-\pi}^\pi |u(x)-P_k(x)|^2{\mathrm d}{x} \leq \varepsilon^2.

Da die stetigen Funktionen in {L^2([-\pi,\pi])} dicht liegen, lässt sich auch jede {L^2}-Funktion beliebig gut durch trigonometrische Polynome approximieren und wir sehen, dass die {(e_k)} eine Basis bilden. Die Reihendarstellung und die Parseval Identität sind eine direkt Konsequenz aus allgemeinen Aussagen über Orthonormalbasen in Hilbert-Räumen. \Box

Mit Hilfe des oben definierten Skalarproduktes kann man die Fourier-Entwicklung auch schreiben als

\displaystyle  u = \sum_{k\in{\mathbb Z}}\langle u,e_k\rangle_{[-\pi,\pi]} e_k

was noch einmal deutlicher herausstellt, dass es sich bei den {(e_k)} um eine Orthonormalbasis handelt.

Das summierbare Folgen Nullfolgen sind, ist folgt aus der Parseval-Identität:

Korollar 2 (Riemann-Lebesgue-Lemma für Fourier-Reihen) Für die Fourier-Koeffizienten {c_k} einer Funktion {u\in L^2([-\pi,\pi])} gilt

\displaystyle  c_k\rightarrow 0,\ \text{f\"ur}\ |k|\rightarrow\infty.

Bemerkung 3 (Reelle Fourier-Koeffizienten) Über die Eulersche Formel lassen sich auch “reelle” Fourier-Koeffizienten bestimmen. Diese sind

\displaystyle  a_k = \frac{1}{\pi}\int_{-\pi}^\pi u(x)\cos(kx){\mathrm d}{x},\quad k=0,1,2,\dots

und

\displaystyle  b_k =\frac{1}{\pi}\int_{-\pi}^\pi u(x)\sin(kx){\mathrm d}{x},\quad k=1,2,\dots

Für reellwertige Funktionen sind die {a_k} und {b_k} reellwertig. Ist {u} gerade (d.h. {u(-x)=u(x)}) gilt {b_k=0}, ist {u} ungerade ({u(-x) = -u(x)}), so gilt {a_k=0}.

Bemerkung 4 Für Funktionen in {L^2([-B,B])} definieren wir das Skalarprodukt

\displaystyle  \langle u,v\rangle_{[-B,B]} = \frac{1}{2B}\int_{-B}^Bu(x)\overline{v}(x){\mathrm d}{x}.

Die Funktionen {e_k(x) = \mathrm{e}^{\mathrm{i} k\tfrac{\pi}{B} x}} bilden hier eine Orthonormalbasis und mit den Fourier-Koeffizienten von {u}

\displaystyle  \langle u,e_k\rangle_{[-B,B]} = \frac{1}{2B}\int_{-B}^B u(x) \mathrm{e}^{-\mathrm{i} k\tfrac{\pi}{B}x}{\mathrm d}{x}

gilt

\displaystyle  u = \sum_{k\in{\mathbb Z}}\langle u,e_k\rangle_{[-B,B]}e_k.

Auf einem {d}-dimensionalen Rechteck {\Omega = \prod_{l=1}^d [-B_l,B_l]} definieren wir die Funktion {(e_{\vec k})_{\vec k\in {\mathbb Z}^d}} durch

\displaystyle  e_{\vec k}(x) = \prod_{l=1}^d\mathrm{e}^{\mathrm{i} k_l \tfrac{\pi}{B_l}x_l}

und erhalten eine Orthonormalbasis in {L^2(\Omega)} bezüglich des Skalarproduktes

\displaystyle  \langle u,v\rangle_\Omega = \frac{1}{2^d\prod_{l=1}^dB_l }\int_\Omega u(x)\overline{v}(x){\mathrm d}{x}.

1.2. Punktweise Konvergenz von Fourier-Reihen

Die Konvergenz der Fourier-Reihe einer {L^2}-Funktion in {L^2}-Sinne ist (mit Hilfe des Weierstraßschen Approximationssatzes) nicht sehr schwierig zu zeigen. Im Allgemeinen kann die Konvergenz von Fourier-Reihen sehr schwierig sein. Wir gehen in diese Richtung nicht allzu sehr in die Tiefe. Wir wollen die Partialsummen der Fourier-Reihen betrachten, d.h. zu {N\in{\mathbb N}} die Funktion

\displaystyle  S_N(x) = \sum_{k=-N}^N \langle u,e_k\rangle_{[-\pi,\pi]}\mathrm{e}^{\mathrm{i} kx}.

Wir beginnen mit dem Faltungsatz für Fourier-Reihen:

Lemma 5 (Fourier-Koeffizienten der periodischen Faltung) Es seien {f,g\in L^1([-\pi,\pi])} ({2\pi}-periodisch auf {{\mathbb R}} fortgesetzt). Die periodische Faltung von {f} und {g} ist

\displaystyle  f*g(x) = \int_{-\pi}^\pi f(y)g(x-y){\mathrm d}{y}

und es gilt:

\displaystyle  \langle f*g,e_k\rangle_{[-\pi,\pi]} = 2\pi\langle f,e_k\rangle_{[-\pi,\pi]}\langle g,e_k\rangle_{[-\pi,\pi]},

d.h. die Fourier-Koeffizienten der Funktion {f*g} sind (bis auf den Vorfaktor) die Produkte der Fourier-Koeffizienten von {f} und {g}.

Beweis: Mit dem Satz von Fubini folgt

\displaystyle  \begin{array}{rcl}  \langle f*g,e_k\rangle_{[-\pi,\pi]} &= & \frac{1}{2\pi}\int_{-\pi}^\pi \int_{-\pi}^\pi f(y)g(x-y){\mathrm d}{y}\mathrm{e}^{-\mathrm{i} kx}{\mathrm d}{x}\\ &=& \frac{1}{2\pi}\int_{-\pi}^\pi f(y) \mathrm{e}^{-\mathrm{i} ky}\int_{-\pi}^\pi g(x-y){\mathrm d}{y}\mathrm{e}^{-\mathrm{i} k(x-y)}{\mathrm d}{x}\\ &=& 2\pi \langle f,e_k\rangle_{[-\pi,\pi]} \langle g,e_k\rangle_{[-\pi,\pi]} . \end{array}

\Box

Die Partialsummen {S_N} lassen sich als Faltung schreiben:

Satz 6 Es sei {u\in L^1([-\pi,\pi])} und zu {N\in{\mathbb N}} definieren wir

\displaystyle  S_N(x) = \sum_{k=-N}^N \langle u,e_k\rangle_{[-\pi,\pi]}\mathrm{e}^{\mathrm{i} kx}.

Dann gilt mit dem Dirichlet-Kern

\displaystyle  D_N(x) = \frac{\sin\big((N+\tfrac{1}{2})x\big)}{2\pi\sin(\tfrac{x}{2})},

dass

\displaystyle  S_N(x) = u*D_N(x) = \int_{-\pi}^\pi u(y)D_N(x-y){\mathrm d}{y}.

Beweis: Das Ergebnis lässt wie folgt erahnen: Sind {c_k} die Fourier-Koeffizienten von {u} und ist {b_k = 1} ({|k|\leq N}), {b_k = 0} ({|k|>N}), so ist

\displaystyle  S_N(x) = \sum_{k\in{\mathbb Z}} c_k b_k \mathrm{e}^{\mathrm{i} kx}.

Auf Grund der vorigen Lemmas vermuten wir also, dass es sich bei {D_N} um die Funktion {\tfrac{1}{2\pi}\sum_{|k|\leq N}\mathrm{e}^{\mathrm{i} kx}} handelt. Das stimmt in der Tat: Mit Hilfe der geometrischen Summe folgt für {r\in {\mathbb C}}

\displaystyle  \begin{array}{rcl}  \sum_{k=-N}^N r^k &=& r^{-N}\sum_{k=0}^{2N} r^k\\ &=& r^{-N}\frac{1-r^{2N+1}}{1-r}\\ &=& \frac{r^{-N-1/2}}{r^{-1/2}}\frac{1-r^{2N+1}}{1-r}\\ &=& \frac{r^{-N-1/2} - r^{N+1/2}}{r^{-1/2} - r^{1/2}}. \end{array}

Mit {r=\mathrm{e}^{\mathrm{i} x}} folgt

\displaystyle  \begin{array}{rcl}  \sum_{|k|\leq N}\mathrm{e}^{\mathrm{i} kx}&=& \frac{\mathrm{e}^{-\mathrm{i} x(N+1/2)} - \mathrm{e}^{\mathrm{i} x(N+1/2)}}{\mathrm{e}^{-\mathrm{i} x/2} - \mathrm{e}^{\mathrm{i} x/2}}\\ &=& \frac{2\mathrm{i} \sin\big((N+\tfrac{1}{2})x\big)}{2\mathrm{i} \sin(\tfrac{x}{2})}=2\pi D_N(x). \end{array}

Nun rechnen wir

\displaystyle  \begin{array}{rcl}  u*D_N(x) &=& \int_{-\pi}^\pi u(y)D_N(x-y){\mathrm d}{y}\\ &=& \sum_{k=-N}^N\frac{1}{2\pi}\int_{-\pi}^\pi u(y)\mathrm{e}^{\mathrm{i} k(x-y)}{\mathrm d}{y}\\ &=& \sum_{k=-N}^N\mathrm{e}^{\mathrm{i} kx}\frac{1}{2\pi}\int_{-\pi}^\pi u(y)\mathrm{e}^{-\mathrm{i} ky}{\mathrm d}{y} =S_N(x). \end{array}

\Box

Satz 7 (Punktweise Konvergenz der Fourier-Reihe von differenzierbaren Funktionen) Es sei {f:[-\pi,\pi]\rightarrow {\mathbb C}} differenzierbar (periodisch fortgesetzt auf {{\mathbb R}} und dabei in {\pm\pi} ebenfalls differenzierbar). Dann gilt für jedes {x\in[-\pi,\pi]}

\displaystyle  S_N(x) \rightarrow f(x),\quad N\rightarrow\infty.

Beweis: Aus der Darstellung {D_N(x) = \tfrac{1}{2\pi}\sum_{k=-N}^N \mathrm{e}^{ikx}} folgt direkt, dass

\displaystyle  \int_{-\pi}^\pi D_N(x){\mathrm d}{x} = 1.

Es gilt

\displaystyle  \begin{array}{rcl}  S_N(x) - f(x) &=& f*D_N(x) - f(x)\\ &=& \int_{-\pi}^\pi (f(x-y) - f(x))D_N(y){\mathrm d}{y}\\ &=& \frac{1}{2\pi}\int_{-\pi}^\pi \frac{f(y-x) - f(x)}{\sin(y/2)}\sin\big((N+1/2) y\big){\mathrm d}{y}. \end{array}

Die Funktion {g_x(y) = \frac{f(x-y) - f(x)}{\sin(y/2)}} ist in jedem {y\neq 0} stetig, und lässt sich nach {y=0} durch {-2f'(x)} stetig fortsetzen, insbesondere ist {g_x} eine {L^2}-Funktion. Es gilt also

\displaystyle  \begin{array}{rcl}  S_N(x) - f(x) &=& \frac{1}{2\pi}\int_{-\pi}^\pi g_x(y)\frac{\mathrm{e}^{\mathrm{i}(N+1/2)y}-\mathrm{e}^{-\mathrm{i}(N+1/2) y}}{2\mathrm{i}}{\mathrm d}{y}\\ &=& \frac{\langle g_x(y) \mathrm{e}^{\mathrm{i} y/2},e_{-N}\rangle - \langle g_x(y) \mathrm{e}^{-\mathrm{i} y/2},e_N\rangle}{2\mathrm{i}}. \end{array}

Nach dem Riemann-Lebesgue-Lemma (Korollar 2) geht die rechte Seite für {N\rightarrow\infty} gegen Null und es folgt die Behauptung. \Box

Bemerkung 8 Ein genauer Blick auf den Beweis offenbart, dass sich die Voraussetzungen in obigem Satz abschwächen lassen: ist die Funktion

\displaystyle  g_x(y) = \frac{f(x-y) - f(x)}{\sin(y/2)}

eine Funktion für die das Riemann-Lebesgue-Lemma gilt (d.h. die Fourier-Koeffizienten gehen gegen Null), so konvergiert die Fourier-Reihe von {f} im Punkt {x}. Das Riemann-Lebesgue-Lemma gilt nicht nur für {L^2}-Funktionen, sondern auch für integrierbare (d.h. {L^1}) Funktionen. Dies folgt zum Beispiel aus Aufgabe 25: Eine Funktion {f\in L^1([-\pi,\pi])} lässt sich durch Null-Fortsetzung zu einer Funktion {\tilde f\in L^1({\mathbb R})} machen. Dann gilt

\displaystyle  \langle f,e_k\rangle_{[-\pi,\pi]} = \frac{1}{2\pi}\int_{\mathbb R} \tilde f(x)\mathrm{e}^{-\mathrm{i} k x}{\mathrm d}{x} = \frac{1}{\sqrt{2\pi}}\widehat{\tilde f}(k)\rightarrow 0\quad |k|\rightarrow\infty.

Die Stetigkeit von {f} in {x} ist allerdings nicht genug, um die Konvergenz der Fourier-Reihe in {x} zu garantieren; es gibt mehr oder minder explizite Gegenbeispiele, siehe z.B. Kapitel II, Abschnitt 2 in “An Introduction to Harmonic Analysis” von Yitzhak Katznelson. In eben diesem Buch ist auch das Ergebnis von Kolmogorov zu finden, dass es eine {L^1}-Funktion gibt, deren Fourier-Reihe überall divergiert. Dass der Raum {L^1} hier speziell ist, zeigt das Carleson-Hunt-Theorem, dass die Fourier-Reihe einer {L^p}-Funktion (mit {2\geq p>1}) fast überall konvergiert.

1.3. Das Abtasttheorem

Zur Diskretisierung werden kontinuierliche eindimensionale Signale {u:{\mathbb R}\rightarrow{\mathbb C}} üblicherweise mit einer konstanten Abtastrate {T>0} abgetastet, das heißt, es werden die Werte {(u(nT))_{n\in{\mathbb Z}}} gespeichert.

Unter welchen Umständen die Abtastwerte die gesamte Information des Signals beinhalten, zeigt der nächste Satz:

Satz 9 (Abtasttheorem nach Shannon-Whitakker) Es seien {B>0} und {u\in L^2({\mathbb R})} so, dass {\widehat{u}(\xi) = 0} für {|\xi|>B}. Dann ist {u} durch die Werte {(u(k\pi/B))_{k\in{\mathbb Z}}} bestimmt und es gilt mit

\displaystyle  \mathrm{sinc}(x) = \frac{\sin(x)}{x}

für alle {x} die Rekonstruktionsformel

\displaystyle  u(x) = \sum_{k\in{\mathbb Z}} u(\tfrac{k\pi}{B}) \mathrm{sinc}\bigl(B(x - \tfrac{k\pi}{B})\bigr).

Beweis: Der Trick in diesem Beweis besteht darin, dass sich {\widehat{u}} sowohl als Element in {L^2({\mathbb R})} als auch in {L^2([-B,B])} auffassen lässt. Wir können also sowohl die Fourier-Transformation als auch die Fourierreihe von {\widehat{u}} betrachten. Da {\widehat{u}} in {L^2([-B,B])} liegt, liegt es ebenfalls in {L^1([-B,B])}. Damit ist {u} stetig und die Punktauswertung von {u} ist wohldefiniert. Wir benutzen die Rekonstruktionsformel der Fourier-Transformation und erhalten

\displaystyle  u(\tfrac{k\pi}{B}) = \frac{1}{\sqrt{2\pi}}\int_{-B}^B \widehat{u}(\xi)\mathrm{e}^{\mathrm{i} \xi \tfrac{k\pi}{B}}{\mathrm d}{\xi} = \sqrt{\tfrac{2}{\pi}}B\,\langle\widehat{u},e_{-k}\rangle_{[-B,B]}

(beachte {e_k(x) = \mathrm{e}^{\mathrm{i} k \tfrac{\pi}{B}x}}). Die Werte {u(\tfrac{k\pi}{B})} bestimmen also die Werte {\langle \widehat{u},e_{-k}\rangle_{[-B,B]}} und da {\widehat{u}\in L^2([-B,B])} ist, auch die ganze Funktion {\widehat{u}}. Damit ist gezeigt, dass {u} durch die Werte {(u(\tfrac{k\pi}{B}))_{k\in{\mathbb Z}}} bestimmt ist. Um die Rekonstruktionsformel zu zeigen, entwickeln wir {\widehat{u}} in seine Fourierreihe und beachten dabei, dass wir für {\xi\in{\mathbb R}} mit der charakteristischen Funktion {\chi_{[-B,B]}} einschränken müssen:

\displaystyle  \widehat{u}(\xi) = \sum_{k\in{\mathbb Z}} \langle \widehat{u},e_k\rangle_{[-B,B]}e_k(\xi)\chi_{[-B,B]}(\xi) =\sqrt{\frac{\pi}{2}}\frac{1}{B}\sum_{k\in{\mathbb Z}} u(-\tfrac{k\pi}{B}) e_k(\xi)\chi_{[-B,B]}(\xi).

Da die inverse Fourier-Transformation stetig ist, können wir sie an der Reihe vorbeiziehen und bekommen

\displaystyle  u = \sqrt{\frac{\pi}{2}}\frac{1}{B}\sum_{k\in{\mathbb Z}} u(-\tfrac{k\pi}{B}) \mathcal{F}^{-1}(e_k\chi_{[-B,B]}).

Mit Hilfe der Rechenregeln für die Fouriertransformation und der bekannten Transformierten der charakteristischen Funktion ergibt sich

\displaystyle  \begin{array}{rcl}  \mathcal{F}^{-1}(e_k\chi_{[-B,B]})(x) & =& \overline{\mathcal{F}(\overline{M_{k\tfrac{\pi}{B}}\chi_{[-B,B]}})(x)}\\ & = &D_{-1}V_{-k\tfrac{\pi}{B}}\mathcal{F}(\chi_{[-B,B]})(x) = \sqrt{\tfrac{2}{\pi}}B\mathrm{sinc}\bigl(B(-x-\tfrac{k\pi}{B})\bigr)\\ & =& \sqrt{\tfrac{2}{\pi}}B\mathrm{sinc}\bigl(B(x+\tfrac{k\pi}{B})\bigr). \end{array}

Die Kombination mit der vorhergehenden Formel zeigt die Behauptung. \Box

Bemerkung 10 Im obigen Fall nennen wir {B} die Bandbreite des Signals. Die Bandbreite gibt an, welches die höchste Frequenz in dem Signal ist. In Worten gesprochen sagt das Abtasttheorem das Folgende: Hat ein Signal Bandbreite {B}, so muss es mit der Abtastrate {\tfrac{\pi}{B}} abgetastet werden, um alle Informationen des Signals zu speichern.

Wir benutzen hier das Wort “Frequenz” nicht in dem Sinne, in dem es in den Ingenieurwissenschaften häufig benutzt wird. Dort wird typischerweise die Kreisfrequenz {f = 2\pi B} benutzt. Ebenso ist dort die Variante der Fourier-Transformation mit dem Term {\mathrm{e}^{-2\pi\mathrm{i} x\cdot \xi}} verbreitet. Damit liest sich die Aussage des Abtasttheorems: Hat ein Signal Frequenzen bis zu einer maximalen Kreisfrequenz {f}, so muss es mit der Abtastrate {\tfrac{1}{2f}} abgetastet werden, um alle Informationen des Signals zu speichern. In anderen Worten: Man muss doppelt so schnell wie die höchste Kreisfrequenz abtasten. Man nennt die Abtastrate {\tfrac{1}{2f}} auch Nyquist-Rate.

1.4. Der Alias-Effekt

Der Alias-Effekt ist das, was in diesem Bild oder auch bei Aufrufen von “plot(sin(1:5000),’.’)” in MATLAB zu sehen ist. Das diskrete Bild, beziehungsweise Signal, entspricht nicht dem Originalsignal. Es tauchen Frequenzen in der diskreten Version auf, die im Original nicht enthalten sind. Sie stehen als “Alias” für die richtigen Frequenzen.

Im vorhergehenden Abschnitt haben wir gesehen, dass dieser Effekt nicht auftreten kann, wenn das Signal hoch genug abgetastet wurde. Wie genau der Alias-Effekt entsteht und wie man ihn beheben kann, wollen wir in diesem Abschnitt verstehen.

Wir benötigen ein weiteres Hilfsmittel:

Lemma 11 (Poisson-Formel) Es sei {u\in L^2({\mathbb R})} und {B>0} so, dass entweder die Funktion {\sum_{k\in{\mathbb Z}} \widehat{u}(\cdot + 2Bk) \in L^2([-B,B])} oder die Reihe {\sum_{k\in{\mathbb Z}} |u(\tfrac{k\pi}{B})|^2} konvergiert. Dann gilt für fast alle {\xi}

\displaystyle  \sum_{k\in{\mathbb Z}} \widehat{u}(\xi+2Bk) = \frac{\sqrt{2\pi}}{2B}\sum_{k\in{\mathbb Z}} u(\tfrac{k\pi}{B}) \mathrm{e}^{-\mathrm{i}\tfrac{k\pi}{B}\xi}.

Beweis: Wir definieren die Periodisierung von {\widehat{u}} als

\displaystyle  \phi(\xi) = \sum_{k\in{\mathbb Z}} \widehat{u}(\xi+2Bk).

Ist {\phi\in L^2([-B,B])}, können wir die Funktion durch ihre Fourierreihe darstellen. Die Fourier-Koeffizienten sind

\displaystyle  \begin{array}{rcl}  \langle \phi ,e_k\rangle_{[-B,B]} & =& \frac{1}{2B} \int_{-B}^B \phi(\xi)\mathrm{e}^{-\mathrm{i} \tfrac{k\pi}{B}\xi}{\mathrm d}{\xi}\\ & = &\frac{1}{2B} \int_{-B}^B \sum_{l\in{\mathbb Z}} \widehat{u}(\xi+2Bl)\mathrm{e}^{-\mathrm{i}\tfrac{k\pi}{B}\xi}{\mathrm d}{\xi}\\ & = &\frac{1}{2B} \int_{-B}^B \sum_{l\in{\mathbb Z}} \widehat{u}(\xi+2Bl)\mathrm{e}^{-\mathrm{i} \tfrac{k\pi}{B}(\xi+2Bl)}{\mathrm d}{\xi}\\ & = &\frac{1}{2B} \int_{\mathbb R} \widehat{u}(\xi)\mathrm{e}^{-\mathrm{i}\tfrac{k\pi}{B}\xi}{\mathrm d}{\xi}\\ & = &\frac{\sqrt{2\pi}}{2B} u(-\tfrac{k\pi}{B}). \end{array}

Also ist die Fourierreihe

\displaystyle  \begin{array}{rcl}  \phi(\xi) & = &\sum_{k\in{\mathbb Z}}\langle \phi ,e_k\rangle_{[-B,B]}e_k(\xi)\\ & = &\frac{\sqrt{2\pi}}{2B} \sum_{k\in{\mathbb Z}}u(-\tfrac{k\pi}{B}) \mathrm{e}^{\mathrm{i}\tfrac{k\pi}{B}\xi} \end{array}

im {L^2}-Sinn konvergent, woraus die Behauptung folgt. Andersherum konvergiert obige Fourierreihe, wenn die Koeffizienten {(u(\frac{k\pi}{B}))_k} quadratsummierbar sind und die Behauptung folgt ebenfalls. \Box

Bemerkung 12 Im Spezialfall {\xi=0} erhalten wir die bemerkenswerte Formel

\displaystyle   \sum_{k\in{\mathbb Z}}\widehat{u}(2Bk) = \frac{\sqrt{2\pi}}{2B}\sum_{k\in{\mathbb Z}}u(\tfrac{\pi}{B}k), \ \ \ \ \ (1)

die die Werte von {u} und {\widehat{u}} in Beziehung setzt. Diese lässt sich auch als Aussage über die Fourier-Transformierte des sogenannten Dirac-Kamms auffassen: Der Dirac-Kamm zu {T>0} ist eine (temperierte) Distribution, definiert durch

\displaystyle  \Delta_T(\phi) = \sum_{k\in{\mathbb Z}}\phi(kT)

(vgl. Aufgabe 16). Die Poisson-Formel gilt insbesondere für Schwartz-Funktionen {\phi}, und daher können wir (1) schreiben als

\displaystyle  \Delta_{2B}(\hat\phi) = \frac{\sqrt{2\pi}}{2B}\Delta_{\tfrac{\pi}{B}}(\phi).

Aus der Definition der Fourier-Transformation für temperierte Distributionen folgt also

\displaystyle  \widehat{\Delta_{2B}} = \frac{\sqrt{2\pi}}{2B}\Delta_{\tfrac{\pi}{B}}.

Die Fourier-Transformierte eines Dirac-Kamms ist also wieder ein Dirac-Kamm. Insbesondere ist {\Delta_{\sqrt{2\pi}}} ein weiterer Fixpunkt der Fourier-Transformation (neben der Gauß-Funktion).

Nun wenden wir uns genauer dem Abtasten zu. Mit Hilfe von Distributionen formuliert, können wir das diskret mit der Rate {\tfrac{\pi}{B}} abgetastete Signal mit Hilfe eines Dirac-Kamms darstellen:

\displaystyle  u_d = \sum_{k\in{\mathbb Z}} u(\tfrac{k\pi}{B})\delta_{k\tfrac{\pi}{B}}.

Ist {u} unendlich oft differenzierbar (und nicht zu schnell wachsend), so ist der Ausdruck für {u_d} genau das Produkt von {u} mit einem Dirac-Kamm:

\displaystyle  u_d = u\Delta_{\tfrac{\pi}{B}}.

Der Zusammenhang von {u} und {u_d} erschließt sich über die Fourier-Transformation.

Lemma 13 Es gilt für fast alle {\xi}

\displaystyle \widehat{u_d}(\xi) = \frac{B}{\pi} \sum_{k\in{\mathbb Z}} \widehat{u}(\xi+2Bk).

Beweis: Die Fourier-Transformation von {\delta_{k\tfrac{\pi}{B}}} ist uns schon bekannt

\displaystyle  \widehat{\delta_{k\tfrac{\pi}{B}}}(\xi) = \frac{1}{\sqrt{2\pi}}\mathrm{e}^{-\mathrm{i} \tfrac{k\pi}{B}\xi}.

Deshalb ist aufgrund der Poisson-Formel (Lemma~11)

\displaystyle  \begin{array}{rcl}  \widehat{u_d}(\xi) & = &\frac{1}{\sqrt{2\pi}}\sum_{k\in{\mathbb Z}}u(\tfrac{k\pi}{B})\mathrm{e}^{-\mathrm{i}\tfrac{k\pi}{B}\xi}\\ & = &\frac{B}{\pi} \sum_{n\in{\mathbb Z}} \widehat{u}(\xi+2Bn). \end{array}

\Box

In Worten sagt das Lemma, dass die Fourier-Transformation des abgetasteten Signals einer Periodisierung mit Periode {2B} der Fourier-Transformation des Original-Signals entspricht.

In dieser Sprechweise können wir die Rekonstruktionsformel aus dem Abtasttheorem~9 auch als Faltung interpretieren:

\displaystyle  u(x) = \sum_{k\in{\mathbb Z}} u(\tfrac{k\pi}{B})\mathrm{sinc}(B(x-\tfrac{k\pi}{B})) = u_d*\mathrm{sinc}(B\cdot)(x).

Auf der Fourier-Seite heißt das formal

\displaystyle  \widehat{u}(\xi) = \widehat{u_d}(\xi) \tfrac{B}{\pi}\chi_{[-B,B]}(\xi).

Hat {\widehat{u}} seinen Träger im Intervall {[-B,B]}, entsteht bei der Periodisierung kein Überlapp und {\widehat{u_d}\tfrac{B}{\pi} \chi_{[-B,B]}} entspricht genau {\widehat{u}}.

Hat allerdings {\widehat{u}} einen größeren Träger, so hat der Träger von {\widehat{u}(\cdot + 2Bk)} für mehrere {k} einen Schnitt mit {[-B,B]}. Dieses “Zurückklappen” im Frequenzbereich ist für den Alias-Effekt verantwortlich.

Beispiel 14 (Abtasten von harmonischen Schwingungen) \index{index}{Abtasten} Wir betrachten eine harmonische Schwingung

\displaystyle  u(x) = \cos(\xi_0 x) = \frac{\mathrm{e}^{\mathrm{i}\xi_0 x} + \mathrm{e}^{-\mathrm{i}\xi_0 x}}{2}.

Die Fourier-Transformation ist

\displaystyle  \widehat{u} = \sqrt{\tfrac{\pi}{2}} (\delta_{\xi_0} + \delta_{-\xi_0}).

Das Signal hat also formal die Bandbreite {\xi_0}. Wenn wir eine andere Bandbreite {B} annehmen und das Signal entsprechend mit der Rate {\pi/B} abtasten, erhalten wir auf der Fourier-Seite \begin{equation*} \widehat{u_d} = \tfrac{\pi}{B}\sqrt{\tfrac{\pi}{2}} \sum_{k\in{\mathbb Z}} (\delta_{\xi_0-2kB} + \delta_{-\xi_0-2kB}) \end{equation*} Das Rekonstruieren nach dem Abtasttheorem~9 bedeutet, den Träger von {\widehat{u_d}} auf das Intervall {[-B,B]} einzuschränken. Um zu verstehen, was das für das Signal bedeutet, müssen wir untersuchen, wie sich dieses Einschränken auf die Reihe auswirkt.

  • Überabtasten: Nehmen wir eine zu große Bandbreite {B>\xi_0} an, tasten wir das Signal zu schnell ab. Von den Termen in der Reihe für {\widehat{u_d}} liegen genau diejenigen mit {k=0} im Intervall {[-B,B]}. Es gilt

    \displaystyle  \begin{array}{rcl}  \widehat{u_d} & = &\tfrac{\pi}{B}\sqrt{\tfrac{\pi}{2}} \sum_{k\in{\mathbb Z}} (\delta_{\xi_0-2kB} + \delta_{-\xi_0-2kB}) \tfrac{B}{\pi}\chi_{[-B,B]}\\ & = &\sqrt{\tfrac{\pi}{2}} (\delta_{\xi_0} + \delta_{-\xi_0}) = \widehat{u}. \end{array}

    Das heißt, {u_d= u} und wir rekonstruieren das Signal perfekt.

  • Unterabtasten: Nehmen wir eine zu kleine Bandbreite {B<\xi_0<3B} an, so tasten wir das Signal zu langsam ab. Von den Termen der Reihe liegen wieder genau zwei im Intervall {[-B,B]}, nämlich {\delta_{\xi_0-2B}} und {\delta_{-\xi_0+2B}}. Das heißt, es gilt

    \displaystyle  \widehat{u_d}\,\tfrac{B}{\pi}\chi_{[-B,B]} = \sqrt{\tfrac{\pi}{2}}(\delta_{\xi_0-2B} + \delta_{-(\xi_0-2B)}).

    Wir rekonstruieren also das Signal

    \displaystyle  u_{\text{rek}}(x) = \cos((\xi_0-2B) x).

    Die Rekonstruktion ist wieder eine harmonische Schwingung, aber mit einer anderen Frequenz. Durch Unterabtasten werden hohe Frequenzen {\xi_0} durch niedrige Frequenzen in {[-B,B]} dargestellt.

  • Bemerkung 15 (Abtasten in 2D) Eine einfache Verallgemeinerung des Abtasttheorems und der Erklärung des Alias-Effekts in zwei Dimensionen erhalten wir durch Bildung des Tensorproduktes: Es sei {u:{\mathbb R}^2\rightarrow{\mathbb C}} so, dass die Fourier-Transformation {\widehat{u}} ihren Träger in Rechteck {[-B_1,B_1]\times[-B_2,B_2]} hat. In diesem Fall ist {u} durch die Werte {u(k_1\pi/B_1,k_2\pi/B_2)} bestimmt und es gilt die Formel

    \displaystyle  u(x_1,x_2) = \sum_{k\in{\mathbb Z}^2}u\bigl(\tfrac{k_1\pi}{B_1},\tfrac{k_2\pi}{B_2}\bigr)\mathrm{sinc}\bigl(B_1(x_1-\tfrac{k_1\pi}{B_1})\bigr)\mathrm{sinc}\bigl(B_2(x_2-\tfrac{k_2\pi}{B_2})\bigr).

    Ein diskret auf einem Rechteckgitter mit den Abtastraten {T_1} und {T_2} abgetastetes Bild schreiben wir als

    \displaystyle  u_d = \sum_{k\in{\mathbb Z}^2} u(k_1T_1,k_2T_2)\delta_{(k_1T_1,k_2T_2)}.

    Der Zusammenhang mit dem kontinuierlichen Bild {u} schreibt sich mit der Fourier-Transformation

    \displaystyle  \widehat{u_d}(\xi) = \frac{B_1B_2}{\pi^2}\sum_{k\in{\mathbb Z}^2}\widehat{u}(\xi_1+2B_1k_1,\xi_2+2B_2k_2).

    Auch hier tritt der Alias-Effekt auf, falls das Bild nicht bandbeschränkt ist oder zu niedrig abgetastet wurde. Zusätzlich zur Änderung der Frequenz tritt hier auch eine Änderung der Richtung auf.

    Beispiel 16 (Unterabtasten, Verhindern des Alias-Effektes) Haben wir ein diskretes Bild {u_d = \sum_{k\in{\mathbb Z}^2}u_k\delta_k} gegeben und wollen die Größe um den Faktor {l\in{\mathbb N}} verringern, so liefert das {u_d^l = \sum_{k\in{\mathbb Z}}u_{lk}\delta_{lk}}. Auch bei dieser Unterabtastung erhalten wir wieder einen Alias-Effekt. Um diesen zu verhindern, sollte vor der Unterabtastung ein Tiefpassfilter {h} angewendet werden, um die Frequenzen zu eliminieren, die durch den Alias-Effekt als falsche Frequenzen rekonstruiert werden. Es bietet sich an, diesen Filter als perfekten Tiefpass mit der Breite {\pi/l} zu wählen, d.h.~{\widehat{h} = \chi_{[-\pi/l,\pi/l]^2}}.

    2. Abschließende Bemerkungen

    Jetzt, wo wir den Vorlesungsstoff hinter uns haben, blicken wir noch einmal auf die vier Transformationen zurück. Es stellt sich heraus, dass sowohl {\mathcal{Z}}-Transformation und Fourier-Reihen, als auch bei Laplace-Transformation und Fourier-Transformation jeweils eng zusammenhängen:

  • {\mathcal{Z}}-Transformation: {f_n:{\mathbb Z}\rightarrow{\mathbb C}} mit “exponentiellem Abfallverhalten bei {\pm\infty}”:

    \displaystyle  \mathcal{Z}(f)(z) = \sum_{k\in{\mathbb Z}} f_n z^{-n}

    Konvergent im Kreisring {r<|z|<R}.

    Inversion: {r<\rho<R}:

    \displaystyle  f_n = \frac{1}{2\pi\mathrm{i}}\int_{|z|=\rho}\mathcal{Z}(f)(z)z^{n-1}{\mathrm d}{z} = \frac{1}{2\pi}\int_{-\pi}^\pi \mathcal{Z}(f)(\rho\mathrm{e}^{\mathrm{i} t})\rho^n\mathrm{e}^{\mathrm{i} nt}{\mathrm d}{t}.

  • Fourier-Reihe: {f:[-\pi,\pi]\rightarrow{\mathbb C}}

    \displaystyle  c_k = \frac{1}{2\pi}\int_{-\pi}^\pi f(t)\mathrm{e}^{-\mathrm{i} kt}{\mathrm d}{t}.

    “Inversion”:

    \displaystyle  f(t) = \sum_{k\in{\mathbb Z}} c_k \mathrm{e}^{\mathrm{i} k t}

    Ist also {r<1<R}, dann gilt

    \displaystyle  \mathcal{Z}(c_k)(\mathrm{e}^{-\mathrm{i} t}) = f(t),

    mit anderen Worten: Die {\mathcal{Z}}-Transformation entlang des Einheitskreises entspricht der Fourier-Reihe.

    Anstelle des Abfallverhaltens der Folge {f_n} bei der {\mathcal{Z}}-Transformation tritt bei den Fourier-Reihen eine “Summierbarkeitsbedingung” an die Fourier-Koeffizienten. Als Konsequenz erhält man nicht immer eine Funktion, die sich komplex-differenzierbar über den Einheitskreis hinaus fortsetzen lässt, dafür ist die Konvergenz auf dem Einheitskreis auf verschiedene Arten nachweisbar (z.B. punktweise oder in {L^2}).

  • Laplace-Transformation: {f:[0,\infty[\rightarrow{\mathbb C}} “Original”, exponentiell beschränkt.

    \displaystyle  \mathcal{L}(f)(s) = \int_0^\infty f(t)\exp(-st){\mathrm d}{t},

    gültig für {\mathrm{Re}(s)>\sigma_0(f)}.

  • Fourier-Transformation: {f:{\mathbb R}\rightarrow{\mathbb C}} integrierbar (z.B. in {L^1({\mathbb R})}).

    \displaystyle  \mathcal{F}(f)(\xi) = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^\infty f(x)\exp(-\mathrm{i} x\xi){\mathrm d}{x}.

    Ist {\sigma_0(f)<0}, so gilt (mit {f(t)=0} für {t<0})

    \displaystyle  \mathcal{F}(f)(\xi) = \frac{1}{\sqrt{2\pi}}\mathcal{L}(f)(\mathrm{i}\xi).

    Mit anderen Worten: Die Laplace-Transformation entlang der imaginären Achse ist die Fourier-Transformation.

    Ebenso wie beim Zusammenhang von {\mathcal{Z}}-Transformation und Fourier-Reihen ist wird “Abfallverhalten bei {\infty}” für die Laplace-Transformation durch Integrierbarkeitsanforderungen bei der Fourier-Transformation ersetzt. Es handelt sich auch hier (ebenso wie oben) um zwei verschiedenen Zugänge zu fast identischen Transformationen. Im Fall der Laplace-Transformation ermöglicht die exponentielle Beschränkung, dass es sich bei der Transformierten um eine komplex differenzierbare Funktion handelt. Im Fall der Fourier-Transformation erhält man kaum Regularität der Transformierten, aber dafür (im {L^2}-Fall) die gleiche Art der Integrierbarkeit und damit eine praktische Symmetrie von Hin- und Rücktransformation.

  • Next Page »