From ac5d5a9f18fb6b3ef494ae51734feabed701a1f3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sat, 11 Sep 2021 13:35:10 +0200 Subject: chapter 9 --- buch/chapters/70-graphen/beschreibung.tex | 2 +- buch/chapters/70-graphen/waerme.tex | 179 ++++++++++++++++++++---------- buch/chapters/70-graphen/wavelets.tex | 53 +++++---- 3 files changed, 153 insertions(+), 81 deletions(-) (limited to 'buch/chapters/70-graphen') 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. -- cgit v1.2.1