chapter 9

3 files changed, 153 insertions, 81 deletions

diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex
index 918594d..af934e4 100644
--- a/buch/chapters/70-graphen/beschreibung.tex
+++ b/buch/chapters/70-graphen/beschreibung.tex
@@ -193,7 +193,7 @@ a_{i\!j}
 1&\qquad  (j,i) \in E\\
 0&\qquad  \text{sonst.}
 \end{cases}
-\label{buch:graphen:eqn:adjazenzmatrix}
+\label{buch:graphen:eqn:adjazenzmatrixgerichtet}
 \end{equation}
 Die Matrix $A(G)$ hat also genau dann einen nicht verschwindenden
 Matrixeintrag in Zeile $i$ und Spalte $j$, wenn es eine Verbindung
diff --git a/buch/chapters/70-graphen/waerme.tex b/buch/chapters/70-graphen/waerme.tex
index e7fc023..bfeff74 100644
--- a/buch/chapters/70-graphen/waerme.tex
+++ b/buch/chapters/70-graphen/waerme.tex
@@ -5,10 +5,11 @@
 %
 \section{Wärmeleitung auf einem Graphen
 \label{buch:section:waermeleitung-auf-einem-graphen}}
-Die Vektoren, auf denen die Laplace-Matrix operiert, können betrachtet
-werden als Funktionen, die jedem Knoten einen Wert zuordnen.
+Die Vektoren, auf denen die Laplace-Matrix operiert, können
+als Funktionen betrachtet werden, die jedem Knoten einen Wert zuordnen.
 Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung
 auf dem Graphen.
+\index{Temperaturverteilung}%
 Die Kanten zwischen den Knoten erlauben der Wärmeenergie, von einem Knoten
 zu einem anderen zu fliessen.
 Je grösser die Temperaturdifferenz zwischen zwei Knoten ist, desto
@@ -29,7 +30,7 @@ d_iT_i
 \biggr)
 \]
 Der Term auf der rechten Seite ist genau die Wirkung der 
-Laplace-Matrix auf dem Vektor $T$ der Temperaturen:
+Laplace-Matrix $L=L(G)$ auf dem Vektor $T$ der Temperaturen:
 \begin{equation}
 \frac{dT}{dt}
 =
@@ -38,6 +39,7 @@ Laplace-Matrix auf dem Vektor $T$ der Temperaturen:
 \end{equation}
 Der Wärmefluss, der durch die
 Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} beschrieben
+\index{Wärmeleitungsgleichung}%
 wird, codiert ebenfalls wesentliche Informationen über den Graphen.
 Je mehr Kanten es zwischen verschiedenen Teilen eines Graphen gibt,
 desto schneller findet der Wärmeaustausch zwischen diesen Teilen
@@ -50,6 +52,7 @@ Die Lösungen der Wärmeleitungsgleichung liefern also Informationen
 Die Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} 
 ist eine lineare Differentialgleichung mit konstanten Koeffizienten,
 die mit der Matrixexponentialfunktion gelöst werden.
+\index{Matrixexponentialfunktion}%
 Die Lösung ist
 \[
 f(t) = e^{-\kappa Lt}f(0).
@@ -58,93 +61,131 @@ f(t) = e^{-\kappa Lt}f(0).
 Die Berechnung der Lösung mit der Matrixexponentialreihe ist ziemlich
 ineffizient, da grosse Matrizenprodukte berechnet werden müssen.
 Da die Matrix $L$ symmetrisch ist, gibt es eine Basis aus 
-orthonormierten Eigenvektoren und die Eigenwerte sind reell.
-Wir bezeichnen die Eigenvektoren mit $f_1,\dots,f_n$  und die
+orthonormierten Eigenvektoren und die zugehörigen Eigenwerte sind reell.
+Wir bezeichnen die Eigenvektoren mit $\chi_1,\dots,\chi_n$  und die
 zugehörigen Eigenwerte mit $\lambda_i$.
-Die Funktion $f_i(t)= e^{-\kappa\lambda_it}f_i$ ist dann eine Lösung
+Die Funktion $\chi_i(t)= e^{-\kappa\lambda_it}\chi_i$ ist dann eine Lösung
 der Wärmeleitungsgleichung, denn die beiden Seiten
-\begin{align*}
-\frac{d}{dt}f_i(t)
+\begin{equation}
+\begin{aligned}
+\text{linke Seite:}&&
+\frac{d}{dt}\chi_i(t)
 &=
--\kappa\lambda_ie^{-\kappa\lambda_it}f_i
+-\kappa\lambda_ie^{-\kappa\lambda_it}\chi_i
 =
--\kappa\lambda_i f_i(t)
+-\kappa\lambda_i \chi_i(t)
 \\
--\kappa Lf_i(t)
+\text{rechte Seite:}&&
+-\kappa L\chi_i(t)
 &=
--\kappa e^{-\kappa\lambda_it} Lf_i
+-\kappa e^{-\kappa\lambda_it} L\chi_i
 =
--\kappa e^{-\kappa\lambda_it} \lambda_i f_i
+-\kappa e^{-\kappa\lambda_it} \lambda_i \chi_i
 =
--\kappa \lambda_i f_i(t)
-\end{align*}
+-\kappa \lambda_i \chi_i(t)
+\end{aligned}
+\end{equation}
 von \eqref{buch:graphen:eqn:waermeleitung} stimmen überein.
 
 Eine Lösung der Wärmeleitungsgleichung zu einer beliebigen
 Anfangstemperaturverteilung $f$ kann durch Linearkombination aus 
-den Lösungen $f_i(t)$ zusammengesetzt werden.
-Dazu ist nötig, $f$ aus den Vektoren $f_i$ linear zu kombinieren.
-Da aber die $f_i$ orthonormiert sind, ist dies besonders einfach,
+den Lösungen $\chi_i(t)$ zusammengesetzt werden.
+Dazu ist nötig, $f$ aus den Vektoren $\chi_i$ linear zu kombinieren.
+Da aber die $\chi_i$ orthonormiert sind, ist dies besonders einfach,
 die Koeffizienten sind die Skalarprodukte mit den Eigenvektoren:
 \[
-f=\sum_{i=1}^n \langle f_i,f\rangle f_i.
+f=\sum_{i=1}^n \langle \chi_i,f\rangle \chi_i.
 \]
-Daraus kann man die allgmeine Lösungsformel
+Daraus kann man die allgemeine Lösungsformel
 \begin{equation}
 f(t)
 =
-\sum_{i=1}^n \langle f_i,f\rangle f_i(t)
+\sum_{i=1}^n \langle \chi_i,f\rangle \chi_i(t)
 =
-\sum_{i=1}^n \langle f_i,f\rangle e^{-\kappa\lambda_i t}f_i
+\sum_{i=1}^n \langle \chi_i,f\rangle e^{-\kappa\lambda_i t}\chi_i
 \label{buch:graphen:eqn:eigloesung}
 \end{equation}
 ableiten.
 
-\subsection{Beispiel: Ein zyklischer Graph}
+\subsection{Beispiel: Ein zyklischer Graph
+\label{buch:graphen:subsection:zyklischer-graph}}
 \begin{figure}
 \centering
 \includegraphics{chapters/70-graphen/images/kreis.pdf}
-\caption{Beispiel Graph zur Illustration der verschiedenen Basen auf einem
+\caption{Beispielgraph zur Illustration der verschiedenen Basen auf einem
 Graphen.
 \label{buch:graphen:fig:kreis}}
 \end{figure}
 Wir illustrieren die im folgenden entwickelte Theorie an dem Beispielgraphen
 von Abbildung~\ref{buch:graphen:fig:kreis}.
-Besonders interessant sind die folgenden Funktionen:
+Für jedes $k=0,\dots,n-1$ ist der Vektor mit den Komponenten
 \[
-\left.
-\begin{aligned}
-s_m(k)
+\chi_k(l) = e^{2\pi ikl/n}, \quad l=1,\dots,n
+\]
+ein Eigenvektor der Laplace-Matrix zum Eigenwert
+$\lambda_k=4\sin^2\frac{\pi k}{n}$.
+Tatsächlich ist
+\begin{align*}
+(L\chi_k)(l)
 &=
-\sin\frac{2\pi mk}{n}
+-\chi_k(l-1)
++
+2\chi_k(l)
+-
+\chi_k(l+1)
 \\
-c_m(k)
 &=
-\cos\frac{2\pi mk}{n}
-\end{aligned}
-\;
-\right\}
-\quad
-\Rightarrow
-\quad
-e_m(k)
+-e^{2\pi ik(l-1)/n}
++
+2e^{2\pi ikl/n}
+-
+e^{2\pi ik(l+1)/n}
+\\
+&=
+(-e^{-2\pi ik/n}+2-e^{2\pi ik/n})e^{2\pi ikl/n}
+\\
+&=
+-(e^{2\pi ik/2n}-e^{-2\pi ik/2n})^2 \chi_k(l)
+\\
+&=
+-
+\biggl(
+\frac{e^{2\pi ik/2n}-e^{-2\pi ik/2n}}{2i}
+\biggr)^2
+(2i)^2 \chi_k(l)
+\\
+&=
+4\sin^2\frac{\pi k}n \chi_k(l)
+\end{align*}
+
+Natürlich sind auch Real- und Imaginärteil Eigenvektoren:
+\[
+\begin{aligned}
+s_k(l)
+&=
+\sin\frac{2\pi kl}{n}
 =
-e^{2\pi imk/n}
+\Im \chi_k(l)
+\\
+c_k(l)
+&=
+\cos\frac{2\pi kl}{n}
 =
-c_m(k) + is_m(k).
+\Re\chi_k(l)
+\end{aligned}
 \]
 Das Skalarprodukt dieser Funktionen ist
 \[
-\langle e_m, e_{m'}\rangle
+\langle \chi_m, \chi_{m'}\rangle
 =
 \frac1n
-\sum_{k=1}^n
-\overline{e^{2\pi i km/n}}
-e^{2\pi ikm'/n}
+\sum_{l=1}^n
+\overline{e^{2\pi i ml/n}}
+e^{2\pi im'l/n}
 =
 \frac1n
-\sum_{k=1}^n
-e^{\frac{2\pi i}{n}(m'-m)k}
+\sum_{l=1}^n
+e^{\frac{2\pi i}{n}(m'-m)l}
 =
 \delta_{mm'}
 \]
@@ -157,21 +198,9 @@ c_0, c_1,s_1,c_2,s_2,\dots c_{\frac{n}2-1},c_{\frac{n}2-1},c_{\frac{n}2}
 \]
 eine orthonormierte Basis.
 
-
-Die Laplace-Matrix kann mit der folgenden Definition zu einer linearen
-Abbildung auf Funktionen auf dem Graphen gemacht werden.
-Sei $f\colon V\to \mathbb{R}$ und $L$ die Laplace-Matrix mit
-Matrixelementen $l_{vv'}$ wobei $v,v'\in V$ ist.
-Dann definieren wir die Funktion $Lf$ durch
-\[
-(Lf)(v)
-=
-\sum_{v'\in V} l_{vv'}f(v').
-\]
-
 \subsection{Standardbasis und Eigenbasis
 \label{buch:subsection:standardbasis-und-eigenbasis}}
-Die einfachste Basis, aus der siche Funktionen auf dem Graphen linear
+Die einfachste Basis, aus der sich Funktionen auf dem Graphen linear
 kombinieren lassen, ist die Standardbasis.
 Sie hat für jeden Knoten $v$ des Graphen eine Basisfunktion mit den Werten
 \[
@@ -180,5 +209,37 @@ e_v\colon V\to\mathbb R:v'\mapsto \begin{cases}
 0\qquad&\text{sonst.}
 \end{cases}
 \]
+Sie zeichnet sich dadurch aus, dass sie perfekt lokalisiert ist.
+Im Gegensatz dazu zeigt das Beispiel von
+Abschnitt~\ref{buch:graphen:subsection:zyklischer-graph}, dass
+die Eigenfunktionen von $L(G)$ typischerweise delokalisiert sind.
+Im Beispiel hat $\chi_k(l)$ überall auf dem Graphen den gleichen
+Betrag.
+Die ``Frequenz'' einer Eigenfunktion dagegen ist exakt bestimmt.
+
+\subsection{Fourier-Theorie auf einem Graphen}
+Die Eigenfunktionen der Laplace-Matrix auf einem Graphen erlauben
+also, das Wärmeleitungsproblem auf dem Graphen auf ganz ähnliche
+Art zu lösen, wie die Fourier-Theorie das Wärmeleitungsproblem auf
+$\mathbb{R}$ oder auf einem Intervall löst.
+Es ist daher angemessen, die Entwicklung einer Funktion
+$f\colon G\to\mathbb{C}$ nach den Eigenvektoren $\chi_k$
+als Fourier-Transformation zu bezeichnen und die Koeffizienten
+\(
+c_k = \langle \chi_k, f\rangle
+\)
+als die Fourier-Koeffizienten.
+Grundlegende Eigenschaften der Fourier-Transformation stehen damit
+auch für die Analyse von Funktionen auf einem Graphen zur Verfügung.
 
+Es fehlen allerdings Eigenschaften, die mit zusätzlicher Struktur
+auf dem Definitionsbereich zusammenhängen.
+Die Faltung zum Beispiel setzt eine Rechenoperation auf dem
+Definitionsbereich voraus, welche natürlich in einem Graphen nicht erwartet
+werden kann.
+Im Beispiel von Abschnitt~\ref{buch:graphen:subsection:zyklischer-graph}
+lässt sich eine solche Struktur finden, die Knoten des Graphen können
+als die Elemente einer zyklischen Gruppe betrachtet werden.
+Daraus lassen sich die bekannten Faltungsformeln der diskreten
+Fourier-Transformation ableiten.
 
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex
index 2b9f29b..b11af3f 100644
--- a/buch/chapters/70-graphen/wavelets.tex
+++ b/buch/chapters/70-graphen/wavelets.tex
@@ -73,20 +73,21 @@ Standardbasisvektor mit Hilfe der
 Lösungsformel~\eqref{buch:graphen:eqn:eigloesung}
 gefunden werden.
 Aus physikalischen Gründen ist aber offensichtlich, dass die
-Wärmeenergie Fundamentallösungen $F_i(t)$ für kurze Zeiten $t$
-in der Nähe des Knoten $i$ konzentriert ist.
-Dies ist aber aus der expliziten Formel
+Wärmeenergie der Fundamentallösungen $F_i(t)$ für kurze Zeiten $t$
+in der Nähe des Knotens $i$ konzentriert ist.
+Dies ist aber aus der Fourier-Entwicklung
 \begin{equation}
 F_i(t)
 =
-\sum_{j=1}^n \langle f_j,e_i\rangle e^{-\kappa \lambda_i t} f_j
+\sum_{j=1}^n \langle \chi_j,e_i\rangle e^{-\kappa \lambda_i t} \chi_j
 =
 \sum_{j=1}^n \overline{f}_{ji} e^{-\kappa \lambda_i t},
 \label{buch:graphen:eqn:fundamentalgraph}
 \end{equation}
 nicht unmittelbar erkennbar.
 
-Man kann aber aus~\eqref{buch:graphen:eqn:fundamentalgraph} ablesen,
+Man kann aber aus~\eqref{buch:graphen:eqn:fundamentalgraph}
+wenigstens ablesen,
 dass für zunehmende Zeit die hohen Frequenzen sehr schnell gedämpft
 werden.
 Die hohen Frequenzen erzeugen also den scharfen Peak für Zeiten nahe
@@ -115,7 +116,7 @@ Die Darstellung im Frequenzraum und in der Zeit sind also extreme
 Darstellungen, entweder Frequenzlokalisierung oder zeitliche Lokalisierung
 ermöglichen, sich aber gegenseitig ausschliessen.
 
-\subsubsection{Dilatation}
+\subsubsection{Dilatation im Frequenzraum, spektrale Dilatation}
 Eine Wavelet-Basis für die $L^2$-Funktionen auf $\mathbb{R}$ erlaubt
 eine Funktion auf $\mathbb{R}$ auf eine Art zu analysieren, die eine
 ungenaue zeitliche Lokalisierung bei entsprechend ungenauer
@@ -140,7 +141,7 @@ Graphen gibt es keine Rechtfertigung für diese spezielle Wahl von
 Streckungsfaktoren mehr.
 Es stellt sich daher die Frage, ob man für eine beliebige Menge
 \(
-T= \{ t_1,t_2,\dots\} \}
+T= \{ t_1,t_2,\dots\}
 \)
 von Streckungsfaktoren eine Familie von Funktionen $\chi_j$ zu finden
 derart, dass man sich die $\chi_j$ in einem gewissen Sinn als aus
@@ -164,14 +165,14 @@ Menge von reellen Zahlen ohne innere algebraische Struktur ist.
 \centering
 \includegraphics{chapters/70-graphen/images/gh.pdf}
 \caption{Lokalisierungsfunktion $g(\lambda)$ für die Dilatation (links).
-Die Dilatierten Funktionen $g_i=\tilde{D}_{1/a_i}g$ lokalisieren
+Die dilatierten Funktionen $g_i=\tilde{D}_{1/a_i}g$ lokalisieren
 die Frequenzen jeweils um die Frequenzen $a_i$ im Frequenzraum.
 Der Konstante Vektor ist vollständig delokalisiert, die Funktion $h$
 in der rechten Abbildung entfernt die hohen Frequenzen und liefert Funktionen,
-die in der Umgebung eines Knotens wie die Konstante Funktion aussehen.
+die in der Umgebung eines Knotens wie die konstante Funktion aussehen.
 \label{buch:graphs:fig:lokalisierung}}
 \end{figure}
-Das Mutter-Wavelet einer Wavelet-Analyse zeichnet definiert, in welchem Mass
+Das Mutter-Wavelet einer Wavelet-Analyse definiert, in welchem Mass
 sich Funktionen im Orts- und im Frequenzraum lokalisieren lassen.
 Die Standardbasis der Funktionen auf einem Graphen repräsentieren die
 perfekte örtliche Lokalisierung, Eigenbasis der Laplace-Matrix $L$ repräsentiert
@@ -181,8 +182,8 @@ $\lambda\to\infty$ rasch abfällt mit einem Maximum irgendwo dazwischen
 (Abbildung~\ref{buch:graphs:fig:lokalisierung}).
 Sie kann als eine Lokalisierungsfunktion im Frequenzraum betrachtet werden.
 
-Die Matrix $g(L)$ bildet entfernt aus einer Funktion die ganz hohen und 
-die ganz tiefen Frequenz, lokalisiert also die Funktionen im Frequenzraum.
+Die Matrix $g(L)$ entfernt die ganz hohen und die ganz tiefen Frequenz
+aus einer Funktion, lokalisiert also die Funktionen im Frequenzraum.
 Die Standardbasisvektoren werden dabei zu Funktionen, die nicht mehr nur
 auf einem Knoten von $0$ verschieden sind, aber immer noch einigermassen
 auf dem Graphen lokalisiert sind.
@@ -191,7 +192,7 @@ $\lambda_0 < \lambda_1\le \dots\le \lambda_n$ der Laplace-Matrix
 von Interesse.
 
 Die Matrix $g(L)$ kann mit Hilfe der Spektraltheorie berechnet werden,
-was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren von
+was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren 
 der Laplace-Matrix bereits bekannt sind.
 Die Matrix $\chi^t$ bildet die Standardbasisvektoren in die
 Eigenbasis-Vektoren ab, also in eine Zerlegung im Frequenzraum ab,
@@ -211,7 +212,7 @@ g(\lambda_0)&0&\dots&0\\
 \label{buch:graphen:eqn:mutterwavelet}
 \end{equation}
 
-\subsubsection{Dilatation}
+\subsubsection{Spektrale Dilatation der Mutterwavelets}
 Die Dilatation um $a$ im Ortsraum wird zu einer Dilatation um $1/a$ im
 Frequenzraum.
 Statt also nach einer echten Dilatation der Spaltenvektoren in $g(L)$
@@ -266,12 +267,20 @@ h(L) + \sum_{i}g_i(L)=I
 gelten würde.
 Nach der Spektraltheorie gilt das nur, wenn für alle Eigenwerte
 $\lambda_k$, $k=1,\dots,n$
-\[
+\begin{equation}
 h(\lambda_k) + \sum_ig(a_i\lambda_k)=1
-\]
+\label{buch:graphen:eqn:summegh}
+\end{equation}
 gilt.
-Für beliebige Funktionen $g$ und $h$ kann man nicht davon ausgehen,
-aber man kann erwarten.
+
+Allerdings kann man im Allgemeinen nicht erwarten,
+dass \ref{buch:graphen:eqn:summegh} für
+beliebige Funktionen $g$ und $h$ gilt.
+Da es aber nur auf die Werte auf den Eigenwerten ankommt,
+muss nur sichergestellt sein, dass 
+die linke Seite von \eqref{buch:graphen:eqn:summegh}
+nicht verschwindet.
+Dies garantiert, dass die Wavelet-Entwicklung umkehrbar ist.
 Man muss daher zusätzlich verlangen, dass
 \[
 h(\lambda_k) + \sum_{i} g(a_i\lambda_k) > 0
@@ -301,7 +310,7 @@ B\|v\|^2
 Die Zahlen $A$  und $B$ heissen die {\em Frame-Konstanten} des Frames.
 \end{definition}
 
-Die oben gefundenen Vektoren, die Spalten Vektoren von $h(L)$ und $g_i(L)$
+Die oben gefundenen Vektoren, die Spaltenvektoren von $h(L)$ und $g_i(L)$,
 bilden daher ein Frame.
 Die Frame-Konstanten kann man unmittelbar ausrechnen.
 Der mittlere Term von \eqref{buch:graphen:eqn:frame} ist 
@@ -318,12 +327,14 @@ h(\lambda)^2 + \sum_i g_i(\lambda)^2
 \]
 abgeschätzt werden kann.
 Die Frame-Konstanten sind daher
-\begin{align*}
+\[
+\begin{aligned}
 A&=\min_{k} f(\lambda_k)
 &
 &\text{und}&
 B&=\max_{k} f(\lambda_k).
-\end{align*}
+\end{aligned}
+\]
 Die Konstruktion hat also ein Frame für die Funktionen auf dem Graphen
 etabliert, die viele Eigenschaften einer Multiskalenanalyse in diese
 wesentlich weniger symmetrische Situation rettet.