diff options
Diffstat (limited to 'buch/chapters/70-graphen')
-rw-r--r-- | buch/chapters/70-graphen/images/Makefile | 44 | ||||
-rw-r--r-- | buch/chapters/70-graphen/images/fundamental.tex | 108 | ||||
-rw-r--r-- | buch/chapters/70-graphen/spektral.tex | 396 | ||||
-rw-r--r-- | buch/chapters/70-graphen/wavelets.tex | 250 |
4 files changed, 399 insertions, 399 deletions
diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile index bd77756..c1bc5df 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -1,22 +1,22 @@ -# -# Makefile -- Bilder für Kapitel Graphen -# -# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -# -all: peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf - -peterson.pdf: peterson.tex - pdflatex peterson.tex - -adjazenzu.pdf: adjazenzu.tex - pdflatex adjazenzu.tex - -adjazenzd.pdf: adjazenzd.tex - pdflatex adjazenzd.tex - -kreis.pdf: kreis.tex - pdflatex kreis.tex - -fundamental.pdf: fundamental.tex - pdflatex fundamental.tex - +#
+# Makefile -- Bilder für Kapitel Graphen
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+all: peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf
+
+peterson.pdf: peterson.tex
+ pdflatex peterson.tex
+
+adjazenzu.pdf: adjazenzu.tex
+ pdflatex adjazenzu.tex
+
+adjazenzd.pdf: adjazenzd.tex
+ pdflatex adjazenzd.tex
+
+kreis.pdf: kreis.tex
+ pdflatex kreis.tex
+
+fundamental.pdf: fundamental.tex
+ pdflatex fundamental.tex
+
diff --git a/buch/chapters/70-graphen/images/fundamental.tex b/buch/chapters/70-graphen/images/fundamental.tex index b7fe9c4..388bdf7 100644 --- a/buch/chapters/70-graphen/images/fundamental.tex +++ b/buch/chapters/70-graphen/images/fundamental.tex @@ -1,54 +1,54 @@ -% -% fundamental.tex -- template for standalon tikz images -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\documentclass[tikz]{standalone} -\usepackage{amsmath} -\usepackage{times} -\usepackage{txfonts} -\usepackage{pgfplots} -\usepackage{csvsimple} -\usetikzlibrary{arrows,intersections,math} -\begin{document} -\def\skala{1} -\begin{tikzpicture}[>=latex,thick,scale=\skala] - -\begin{scope}[xshift=-4.6cm] - \draw[color=red,line width=2pt] (1.8,0) -- (1.8,2); - \draw[color=red,line width=2pt] (0,0) -- (4,0); - \node at (1.8,0) [below] {$i$}; - \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}]; - \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}]; - - \node at (2,-2.3) [below] {Standarbasis}; -\end{scope} - -\begin{scope} - \draw[color=red,line width=1.4pt] - plot[domain=0:360,samples=100] ({\x/90},{2*sin(\x)}); - \draw[color=blue,line width=1.4pt] - plot[domain=0:360,samples=100] ({\x/90},{2*cos(\x)}); - \node[color=blue] at (1,-1) {$\Re f_i$}; - \node[color=red] at (2,1) {$\Im f_i$}; - \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}]; - \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}]; - \node at (2,-2.3) [below] {Eigenbasis}; -\end{scope} - -\begin{scope}[xshift=4.6cm] - \foreach \t in {0.02,0.05,0.1,0.2,0.5}{ - \draw[color=red,line width=1.0pt] - plot[domain=-1.8:2.2,samples=100] - ({\x+1.8},{exp(-\x*\x/(4*\t))/(sqrt(4*3.1415*\t))}); - } - \fill[color=red] (1.8,0) circle[radius=0.08]; - \node at (1.8,0) [below] {$\xi$}; - \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}]; - \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}]; - \node at (2,-2.3) [below] {Fundamentallösung}; -\end{scope} - -\end{tikzpicture} -\end{document} - +%
+% fundamental.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\begin{scope}[xshift=-4.6cm]
+ \draw[color=red,line width=2pt] (1.8,0) -- (1.8,2);
+ \draw[color=red,line width=2pt] (0,0) -- (4,0);
+ \node at (1.8,0) [below] {$i$};
+ \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}];
+ \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}];
+
+ \node at (2,-2.3) [below] {Standarbasis};
+\end{scope}
+
+\begin{scope}
+ \draw[color=red,line width=1.4pt]
+ plot[domain=0:360,samples=100] ({\x/90},{2*sin(\x)});
+ \draw[color=blue,line width=1.4pt]
+ plot[domain=0:360,samples=100] ({\x/90},{2*cos(\x)});
+ \node[color=blue] at (1,-1) {$\Re f_i$};
+ \node[color=red] at (2,1) {$\Im f_i$};
+ \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}];
+ \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}];
+ \node at (2,-2.3) [below] {Eigenbasis};
+\end{scope}
+
+\begin{scope}[xshift=4.6cm]
+ \foreach \t in {0.02,0.05,0.1,0.2,0.5}{
+ \draw[color=red,line width=1.0pt]
+ plot[domain=-1.8:2.2,samples=100]
+ ({\x+1.8},{exp(-\x*\x/(4*\t))/(sqrt(4*3.1415*\t))});
+ }
+ \fill[color=red] (1.8,0) circle[radius=0.08];
+ \node at (1.8,0) [below] {$\xi$};
+ \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}];
+ \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}];
+ \node at (2,-2.3) [below] {Fundamentallösung};
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex index f68c814..72e3519 100644 --- a/buch/chapters/70-graphen/spektral.tex +++ b/buch/chapters/70-graphen/spektral.tex @@ -1,198 +1,198 @@ -% -% spektral.tex -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Spektrale Graphentheorie -\label{buch:section:spektrale-graphentheorie}} -\rhead{Spektrale Graphentheorie} -Die Laplace-Matrix codiert alle wesentliche Information eines -ungerichteten Graphen. -Sie operiert auf Vektoren, die für jeden Knoten des Graphen eine -Komponente haben. -Dies eröffnet die Möglichkeit, den Graphen über die linearalgebraischen -Eigenschaften der Laplace-Matrix zu studieren. - -\subsection{Grapheigenschaften und Spektrum von $L$ -\label{buch:subsection:grapheigenschaften-und-spektrum-von-l}} -TODO XXX - -\subsection{Wärmeleitung auf einem Graphen -\label{buch:subsection:waermeleitung-auf-einem-graphen}} -Die Vektoren, auf denen die Laplace-Matrix operiert, können betrachtet -werden als Funktionen, die jedem Knoten einen Wert zuordnen. -Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung -auf dem Graphen. -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 -grösser ist der Wärmefluss und desto schneller ändert sich die Temperatur -der beteiligten Knoten. -Die zeitliche Änderung der Temperatur $T_i$ im Knoten $i$ ist proportional -\[ -\frac{dT_i}{dt} -= -\sum_{\text{$j$ Nachbar von $i$}} \kappa (T_j-T_i) -= -- -\kappa -\biggl( -d_iT_i -- -\sum_{\text{$j$ Nachbar von $i$}} T_j -\biggr) -\] -Der Term auf der rechten Seite ist genau die Wirkung der -Laplace-Matrix auf dem Vektor $T$ der Temperaturen: -\begin{equation} -\frac{dT}{dt} -= --\kappa L T. -\label{buch:graphen:eqn:waermeleitung} -\end{equation} -Der Wärmefluss, der durch die -Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} beschrieben -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 -statt. -Die Lösungen der Wärmeleitungsgleichung liefern also Informationen -über den Graphen. - -\subsection{Eigenwerte und Eigenvektoren -\label{buch:subsection:ein-zyklischer-graph}} -Die Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} -ist eine lineare Differentialgleichung mit konstanten Koeffizienten, -die mit der Matrixexponentialfunktion gelöst werden. -Die Lösung ist -\[ -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 -zugehörigen Eigenwerte mit $\lambda_i$. -Die Funktion $f_i(t)= e^{-\kappa\lambda_it}f_i$ ist dann eine Lösung -der Wärmeleitungsgleichung, denn die beiden Seiten -\begin{align*} -\frac{d}{dt}f_i(t) -&= --\kappa\lambda_ie^{-\kappa\lambda_it}f_i -= --\kappa\lambda_i f_i(t) -\\ --\kappa Lf_i(t) -&= --\kappa e^{-\kappa\lambda_it} Lf_i -= --\kappa e^{-\kappa\lambda_it} \lambda_i f_i -= --\kappa \lambda_i f_i(t) -\end{align*} -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, -die Koeffizienten sind die Skalarprodukte mit den Eigenvektoren: -\[ -f=\sum_{i=1}^n \langle f_i,f\rangle f_i. -\] -Daraus kann man die allgmeine Lösungsformel -\begin{equation} -f(t) -= -\sum_{i=1}^n \langle f_i,f\rangle f_i(t) -= -\sum_{i=1}^n \langle f_i,f\rangle e^{-\kappa\lambda_i t}f_i -\label{buch:graphen:eqn:eigloesung} -\end{equation} -ableiten. - -\subsection{Beispiel: Ein zyklischer Graph} -\begin{figure} -\centering -\includegraphics{chapters/70-graphen/images/kreis.pdf} -\caption{Beispiel Graph 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: -\[ -\left. -\begin{aligned} -s_m(k) -&= -\sin\frac{2\pi mk}{n} -\\ -c_m(k) -&= -\cos\frac{2\pi mk}{n} -\end{aligned} -\; -\right\} -\quad -\Rightarrow -\quad -e_m(k) -= -e^{2\pi imk/n} -= -c_m(k) + is_m(k). -\] -Das Skalarprodukt dieser Funktionen ist -\[ -\langle e_m, e_{m'}\rangle -= -\frac1n -\sum_{k=1}^n -\overline{e^{2\pi i km/n}} -e^{2\pi ikm'/n} -= -\frac1n -\sum_{k=1}^n -e^{\frac{2\pi i}{n}(m'-m)k} -= -\delta_{mm'} -\] -Die Funktionen bilden daher eine Orthonormalbasis des Raums der -Funktionen auf $G$. -Wegen $\overline{e_m} = e_{-m}$ folgt, dass für gerade $n$ -die Funktionen -\[ -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 -kombinieren lassen, ist die Standardbasis. -Sie hat für jeden Knoten $v$ des Graphen eine Basisfunktion mit den Werten -\[ -e_v\colon V\to\mathbb R:v'\mapsto \begin{cases} -1\qquad&v=v'\\ -0\qquad&\text{sonst.} -\end{cases} -\] - - +%
+% spektral.tex
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Spektrale Graphentheorie
+\label{buch:section:spektrale-graphentheorie}}
+\rhead{Spektrale Graphentheorie}
+Die Laplace-Matrix codiert alle wesentliche Information eines
+ungerichteten Graphen.
+Sie operiert auf Vektoren, die für jeden Knoten des Graphen eine
+Komponente haben.
+Dies eröffnet die Möglichkeit, den Graphen über die linearalgebraischen
+Eigenschaften der Laplace-Matrix zu studieren.
+
+\subsection{Grapheigenschaften und Spektrum von $L$
+\label{buch:subsection:grapheigenschaften-und-spektrum-von-l}}
+TODO XXX
+
+\subsection{Wärmeleitung auf einem Graphen
+\label{buch:subsection:waermeleitung-auf-einem-graphen}}
+Die Vektoren, auf denen die Laplace-Matrix operiert, können betrachtet
+werden als Funktionen, die jedem Knoten einen Wert zuordnen.
+Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung
+auf dem Graphen.
+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
+grösser ist der Wärmefluss und desto schneller ändert sich die Temperatur
+der beteiligten Knoten.
+Die zeitliche Änderung der Temperatur $T_i$ im Knoten $i$ ist proportional
+\[
+\frac{dT_i}{dt}
+=
+\sum_{\text{$j$ Nachbar von $i$}} \kappa (T_j-T_i)
+=
+-
+\kappa
+\biggl(
+d_iT_i
+-
+\sum_{\text{$j$ Nachbar von $i$}} T_j
+\biggr)
+\]
+Der Term auf der rechten Seite ist genau die Wirkung der
+Laplace-Matrix auf dem Vektor $T$ der Temperaturen:
+\begin{equation}
+\frac{dT}{dt}
+=
+-\kappa L T.
+\label{buch:graphen:eqn:waermeleitung}
+\end{equation}
+Der Wärmefluss, der durch die
+Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} beschrieben
+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
+statt.
+Die Lösungen der Wärmeleitungsgleichung liefern also Informationen
+über den Graphen.
+
+\subsection{Eigenwerte und Eigenvektoren
+\label{buch:subsection:ein-zyklischer-graph}}
+Die Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung}
+ist eine lineare Differentialgleichung mit konstanten Koeffizienten,
+die mit der Matrixexponentialfunktion gelöst werden.
+Die Lösung ist
+\[
+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
+zugehörigen Eigenwerte mit $\lambda_i$.
+Die Funktion $f_i(t)= e^{-\kappa\lambda_it}f_i$ ist dann eine Lösung
+der Wärmeleitungsgleichung, denn die beiden Seiten
+\begin{align*}
+\frac{d}{dt}f_i(t)
+&=
+-\kappa\lambda_ie^{-\kappa\lambda_it}f_i
+=
+-\kappa\lambda_i f_i(t)
+\\
+-\kappa Lf_i(t)
+&=
+-\kappa e^{-\kappa\lambda_it} Lf_i
+=
+-\kappa e^{-\kappa\lambda_it} \lambda_i f_i
+=
+-\kappa \lambda_i f_i(t)
+\end{align*}
+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,
+die Koeffizienten sind die Skalarprodukte mit den Eigenvektoren:
+\[
+f=\sum_{i=1}^n \langle f_i,f\rangle f_i.
+\]
+Daraus kann man die allgmeine Lösungsformel
+\begin{equation}
+f(t)
+=
+\sum_{i=1}^n \langle f_i,f\rangle f_i(t)
+=
+\sum_{i=1}^n \langle f_i,f\rangle e^{-\kappa\lambda_i t}f_i
+\label{buch:graphen:eqn:eigloesung}
+\end{equation}
+ableiten.
+
+\subsection{Beispiel: Ein zyklischer Graph}
+\begin{figure}
+\centering
+\includegraphics{chapters/70-graphen/images/kreis.pdf}
+\caption{Beispiel Graph 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:
+\[
+\left.
+\begin{aligned}
+s_m(k)
+&=
+\sin\frac{2\pi mk}{n}
+\\
+c_m(k)
+&=
+\cos\frac{2\pi mk}{n}
+\end{aligned}
+\;
+\right\}
+\quad
+\Rightarrow
+\quad
+e_m(k)
+=
+e^{2\pi imk/n}
+=
+c_m(k) + is_m(k).
+\]
+Das Skalarprodukt dieser Funktionen ist
+\[
+\langle e_m, e_{m'}\rangle
+=
+\frac1n
+\sum_{k=1}^n
+\overline{e^{2\pi i km/n}}
+e^{2\pi ikm'/n}
+=
+\frac1n
+\sum_{k=1}^n
+e^{\frac{2\pi i}{n}(m'-m)k}
+=
+\delta_{mm'}
+\]
+Die Funktionen bilden daher eine Orthonormalbasis des Raums der
+Funktionen auf $G$.
+Wegen $\overline{e_m} = e_{-m}$ folgt, dass für gerade $n$
+die Funktionen
+\[
+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
+kombinieren lassen, ist die Standardbasis.
+Sie hat für jeden Knoten $v$ des Graphen eine Basisfunktion mit den Werten
+\[
+e_v\colon V\to\mathbb R:v'\mapsto \begin{cases}
+1\qquad&v=v'\\
+0\qquad&\text{sonst.}
+\end{cases}
+\]
+
+
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index 9c88c08..26a9e42 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -1,125 +1,125 @@ -% -% wavelets.tex -- Wavelets auf Graphen -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Wavelets auf Graphen -\label{buch:section:wavelets-auf-graphen}} -\rhead{Wavelets auf Graphen} -In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} wurde -gezeigt dass die Standardbasis den Zusammenhang zwischen den einzelnen -Teilen des Graphen völlig ignoriert, während die Eigenbasis Wellen -beschreibt, die mit vergleichbarer Amplitude sich über den ganzen -Graphen entsprechen. -Die Eigenbasis unterdrückt also die ``Individualität'' der einzelnen -Knoten fast vollständig. - -Wenn man einen Standardbasisvektor in einem Knoten $i$ -als Anfangstemperaturverteilung verwendet, erwartet man eine Lösung, -die für kleine Zeiten $t$ die Energie immer in der Nähe des Knotens $i$ -konzentriert hat. -Weder die Standardbasis noch die Eigenbasis haben diese Eigenschaft. - -\subsection{Vergleich mit der Wärmeleitung auf $\mathbb{R}$} -Ein ähnliches Phänomen findet man bei der Wärmeausbreitung gemäss -der partiellen Differentialgleichung -\[ -\frac{\partial T}{\partial t} = -\kappa \frac{\partial^2 T}{\partial x^2}. -\] -Die von Fourier erfundene Methode, die Fourier-Theorie, verwendet die -Funktionen $e^{ik x}$, die Eigenvektoren der zweiten Ableitung -$\partial^2/\partial x^2$ sind. -Diese haben das gleiche Problem, der Betrag von $e^{ikx}$ ist $1$, die -Entfernung von einem Punkt spielt überhaupt keine Rolle. -Die Funktion -\[ -F(x,t) -= -\frac{1}{\sqrt{4\pi\kappa t}}e^{-x^2/4\kappa t} -\] -ist eine Lösung der Wärmeleitungsgleichung mit einem Maximum an -der Stelle $0$. -Sie heisst die Fundamentallösung der Wärmeleitungsgleichung. -Durch Überlagerung von Translaten in eine Funktion -\begin{equation} -f(x,t) -= -\int_{-\infty}^\infty f(\xi) F(x-\xi,t)\,d\xi -\label{buch:graphen:eqn:fundamentalueberlagerung} -\end{equation} -kann man die allgemeine Lösung aus Fundamentallösungen zusammensetzen. -Die Fundamentallösungen $f(x-\xi,t)$ sind für kleine Zeiten immer noch -deutlich in einer Umgebung von $\xi$ konzentriert. - -% XXX Ausbreitung der Fundamentallösung illustrieren -\begin{figure} -\centering -\includegraphics{chapters/70-graphen/images/fundamental.pdf} -\caption{Vergleich der verschiedenen Funktionenfamilien, mit denen -Lösungenfunktionen durch Linearkombination erzeugt werden können. -In der Standarbasis (links) ist es am einfachsten, die Funktionswerte -abzulesen, in der Eigenbasis (Mitte) kann die zeitliche Entwicklung -besonders leicht berechnet werden. -Dazuwischen liegen die Fundamentallösungen (rechts), die eine einigermassen -übersichtliche Zeitentwicklung haben, die Berechnung der Temperatur an -einer Stelle $x$ zur Zeit $t$ ist aber erst durch das Integral -\eqref{buch:graphen:eqn:fundamentalueberlagerung} gegeben. -\label{buch:graphen:fig:fundamental}} -\end{figure} - -\subsection{Fundamentallösungen auf einem Graphen} -Die Wärmeleitungsgleichung auf einem Graphen kann für einen -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 -\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 \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, -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 -beim Knoten $i$, die zu kleineren $\lambda_i$ beschreiben die Ausbreitung -über grössere Distanzen. -Die Fundamentallösung interpoliert also in einem gewissen Sinne zwischen -den Extremen der Standardbasis und der Eigenbasis. -Die ``Interpolation'' geht von der Differentialgleichung aus, -sie ist nicht einfach nur ein Filter, der die verschiedenen Frequenzen -auf die gleiche Art bearbeitet. - -Gesucht ist eine Methode, eine Familie von Vektoren zu finden, -aus der sich alle Vektoren linear kombinieren lassen, in der aber -auch auf die für die Anwendung interessante Längenskala angepasste -Funktionen gefunden werden können. - -\subsection{Wavelets und Frequenzspektrum} -Eine Wavelet-Basis der Funktionen auf $\mathbb{R}$ zerlegt - - -\subsection{Frequenzspektrum -\label{buch:subsection:frequenzspektrum}} -Die Fundamentallösung der Wärmeleitunsgleichung haben ein Spektrum, welches -wie $e^{-k^2}$ gegen $0$ geht. - -Die Fundamentallösung entsteht dadurch, dass die hohen Frequenzen -schneller dämpft als die tiefen Frequenzen. - - -\subsection{Wavelet-Basen -\label{buch:subsection:}} - - - - - +%
+% wavelets.tex -- Wavelets auf Graphen
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Wavelets auf Graphen
+\label{buch:section:wavelets-auf-graphen}}
+\rhead{Wavelets auf Graphen}
+In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} wurde
+gezeigt dass die Standardbasis den Zusammenhang zwischen den einzelnen
+Teilen des Graphen völlig ignoriert, während die Eigenbasis Wellen
+beschreibt, die mit vergleichbarer Amplitude sich über den ganzen
+Graphen entsprechen.
+Die Eigenbasis unterdrückt also die ``Individualität'' der einzelnen
+Knoten fast vollständig.
+
+Wenn man einen Standardbasisvektor in einem Knoten $i$
+als Anfangstemperaturverteilung verwendet, erwartet man eine Lösung,
+die für kleine Zeiten $t$ die Energie immer in der Nähe des Knotens $i$
+konzentriert hat.
+Weder die Standardbasis noch die Eigenbasis haben diese Eigenschaft.
+
+\subsection{Vergleich mit der Wärmeleitung auf $\mathbb{R}$}
+Ein ähnliches Phänomen findet man bei der Wärmeausbreitung gemäss
+der partiellen Differentialgleichung
+\[
+\frac{\partial T}{\partial t} = -\kappa \frac{\partial^2 T}{\partial x^2}.
+\]
+Die von Fourier erfundene Methode, die Fourier-Theorie, verwendet die
+Funktionen $e^{ik x}$, die Eigenvektoren der zweiten Ableitung
+$\partial^2/\partial x^2$ sind.
+Diese haben das gleiche Problem, der Betrag von $e^{ikx}$ ist $1$, die
+Entfernung von einem Punkt spielt überhaupt keine Rolle.
+Die Funktion
+\[
+F(x,t)
+=
+\frac{1}{\sqrt{4\pi\kappa t}}e^{-x^2/4\kappa t}
+\]
+ist eine Lösung der Wärmeleitungsgleichung mit einem Maximum an
+der Stelle $0$.
+Sie heisst die Fundamentallösung der Wärmeleitungsgleichung.
+Durch Überlagerung von Translaten in eine Funktion
+\begin{equation}
+f(x,t)
+=
+\int_{-\infty}^\infty f(\xi) F(x-\xi,t)\,d\xi
+\label{buch:graphen:eqn:fundamentalueberlagerung}
+\end{equation}
+kann man die allgemeine Lösung aus Fundamentallösungen zusammensetzen.
+Die Fundamentallösungen $f(x-\xi,t)$ sind für kleine Zeiten immer noch
+deutlich in einer Umgebung von $\xi$ konzentriert.
+
+% XXX Ausbreitung der Fundamentallösung illustrieren
+\begin{figure}
+\centering
+\includegraphics{chapters/70-graphen/images/fundamental.pdf}
+\caption{Vergleich der verschiedenen Funktionenfamilien, mit denen
+Lösungenfunktionen durch Linearkombination erzeugt werden können.
+In der Standarbasis (links) ist es am einfachsten, die Funktionswerte
+abzulesen, in der Eigenbasis (Mitte) kann die zeitliche Entwicklung
+besonders leicht berechnet werden.
+Dazuwischen liegen die Fundamentallösungen (rechts), die eine einigermassen
+übersichtliche Zeitentwicklung haben, die Berechnung der Temperatur an
+einer Stelle $x$ zur Zeit $t$ ist aber erst durch das Integral
+\eqref{buch:graphen:eqn:fundamentalueberlagerung} gegeben.
+\label{buch:graphen:fig:fundamental}}
+\end{figure}
+
+\subsection{Fundamentallösungen auf einem Graphen}
+Die Wärmeleitungsgleichung auf einem Graphen kann für einen
+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
+\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 \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,
+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
+beim Knoten $i$, die zu kleineren $\lambda_i$ beschreiben die Ausbreitung
+über grössere Distanzen.
+Die Fundamentallösung interpoliert also in einem gewissen Sinne zwischen
+den Extremen der Standardbasis und der Eigenbasis.
+Die ``Interpolation'' geht von der Differentialgleichung aus,
+sie ist nicht einfach nur ein Filter, der die verschiedenen Frequenzen
+auf die gleiche Art bearbeitet.
+
+Gesucht ist eine Methode, eine Familie von Vektoren zu finden,
+aus der sich alle Vektoren linear kombinieren lassen, in der aber
+auch auf die für die Anwendung interessante Längenskala angepasste
+Funktionen gefunden werden können.
+
+\subsection{Wavelets und Frequenzspektrum}
+Eine Wavelet-Basis der Funktionen auf $\mathbb{R}$ zerlegt
+
+
+\subsection{Frequenzspektrum
+\label{buch:subsection:frequenzspektrum}}
+Die Fundamentallösung der Wärmeleitunsgleichung haben ein Spektrum, welches
+wie $e^{-k^2}$ gegen $0$ geht.
+
+Die Fundamentallösung entsteht dadurch, dass die hohen Frequenzen
+schneller dämpft als die tiefen Frequenzen.
+
+
+\subsection{Wavelet-Basen
+\label{buch:subsection:}}
+
+
+
+
+
|