aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/70-graphen
diff options
context:
space:
mode:
authorRoy Seitz <roy.seitz@ost.ch>2021-09-11 14:04:07 +0200
committerRoy Seitz <roy.seitz@ost.ch>2021-09-11 14:04:07 +0200
commitf6f7b194411c8fdda2ba6777a3d5fac69d043ad2 (patch)
treef151914b6af8736451e8d5f87ff09aaef773bc65 /buch/chapters/70-graphen
parentReferenz auf WrStatt-Skript. (diff)
parenttypos, index (diff)
downloadSeminarMatrizen-f6f7b194411c8fdda2ba6777a3d5fac69d043ad2.tar.gz
SeminarMatrizen-f6f7b194411c8fdda2ba6777a3d5fac69d043ad2.zip
Merge branch 'master' of github.com:AndreasFMueller/SeminarMatrizen
Diffstat (limited to 'buch/chapters/70-graphen')
-rw-r--r--buch/chapters/70-graphen/beschreibung.tex2
-rw-r--r--buch/chapters/70-graphen/waerme.tex179
-rw-r--r--buch/chapters/70-graphen/wavelets.tex53
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.