May 2012


1. Die Laplace-Transformation

Etwas grob kann man sagen, dass die Laplace-Transformation die Anpassung der {z}-Transformation an kontinuierliche Funktionen {f:{\mathbb R}_{\geq 0}\rightarrow{\mathbb C}} ist.

Aus einer Folge {(f_n)_{n\in{\mathbb N}}} können wir durch stückweise konstante Interpolation eine Funktion {f:{\mathbb R}_{\geq 0}\rightarrow{\mathbb C}} machen:

\displaystyle  f(t) = f_n,\quad\text{falls}\ n\leq t<n+1.

Wollen wir aus der Reihe in der {z}-Transformierten der Folge {(f_n)} (also aus {\mathcal{Z}(f)(z) = \sum_{n\in{\mathbb N}} f_n z^{-n}}) ein Integral über {f} machen, so wird aus {n\in{\mathbb N}} ein {t\in{\mathbb R}_{\geq 0}} und der naive Weg würde einen Ausdruck {z^{-t}} ergeben. Reelle Potenzen komplexer Zahlen sind mit Hilfe des Logarithmus definiert als {z^{-t} = \exp(-t\log(z))}, wobei man sich jedoch auf einen “Zweig des komplexen Logarithmus” festlegen muss. Man nimmt hier {z = \exp(s)} (mit {s\in{\mathbb C}}) und bekommt den wohldefinierten Ausdruck {\exp(-ts)}. Aus der Reihe wird also

\displaystyle  \sum_{n\in{\mathbb N}} f_n z^{-n}\quad\leadsto \int_0^\infty f(t)\exp(-ts){\mathrm d}{t}.

1.1. Definition und Eigenschaften

Definition 1 (Original) Eine Funktion {f:{\mathbb R}_{\geq0}\rightarrow{\mathbb C}} nennen wir ein (zulässiges) Original, falls {f} über jede kompakte Menge integrierbar ist und von höchstens exponentiellem Wachstum ist, d.h. es existieren {K\geq 0}, {\sigma\in{\mathbb R}} und {t_0\geq 0}, so dass für {t\geq t_0} gilt

\displaystyle  |f(t)|\leq K\exp(\sigma t).

Das Infimum über die möglichen {\sigma} heißt der Wachstumsindex. Wir bezeichnen ihn auch mit

\displaystyle  \sigma_0(f) =\inf\{\sigma\in{\mathbb R}\ :\  \exists K,t_0:|f(t)|\leq K\exp(\sigma t), t\geq t_0\}.

Bemerkung 2 Die Funktionen, die über kompakte Mengen integrierbar sind heißen auch “lokal integrierbar”. Sprechen wir von Integrierbarkeit im Lebesgueschen Sinne, so fassen wir diese Funktionen im Raum

\displaystyle  L^1_{\text{loc}}(\Omega) = \{f:\Omega\rightarrow{\mathbb C}\ :\  \forall K\subset\Omega\ \text{kompakt}:\ \int_K|f(t)|{\mathrm d}{t}<\infty\}

zusammen.

Ähnlich wie bei der {z}-Transformation benutzen wir auch bei {\sigma_0} (und der weiter unter definierten Laplace-Transformation {\mathcal{L}}) die Schreibweise {\sigma_0(f(t))} wenn es sich anbietet.

Beispiel 3

  • Für {-1<\alpha<\infty} gilt {\sigma_0(t^\alpha) = 0}, da {t^m\leq K_\epsilon \exp(\epsilon t)} für jedes {\epsilon>0}. (Ist {\alpha\leq -1}, so ist {t^\alpha} nicht lokal integrierbar.)
  • Für {\lambda\in{\mathbb C}} gilt {\sigma_0(\exp(\lambda t)) = \mathrm{Re}(\lambda)}.
  • Ist {f} beschränkt, so gilt {\sigma_0(f) \leq 0}.
  • Für {c\neq 0} gilt {\sigma_0(cf) = \sigma_0(f)}.

Definition 4 (Laplace-Transformation) Für ein Original {f} definieren wir die Laplace-Transformierte

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

Oftmals schreiben wir auch {F(s) =\mathcal{L}(f)(s)}.

Der Wachstumsindex gibt an für welche {s\in{\mathbb C}} das Integral in der Laplace-Transformation konvergiert: Ist {f} ein Original, und {x =\mathrm{Re}(s) >\sigma> \sigma_0(f)}, so gilt

\displaystyle  |f(t)\exp(-st)| = |f(t)|\exp(-\mathrm{Re}(s) t) \leq K\exp(\sigma t - xt) = K\exp(-(x-\sigma)t)

und daher existiert das Integral {\int_0^\infty f(t)\exp(-st){\mathrm d}{t}} für {\mathrm{Re}(s)>\sigma_0(f)}.

Die erste Funktion, zu der wir die Laplace-Transformierte ausrechnen ist die Heaviside-Funktion, die das kontinuierliche Gegenstück zum Einheitssprung ist:

\displaystyle  H(t) = \begin{cases} 0 & \text{für } t<0\\ 1 & \text{für } t\geq 0. \end{cases}

Es ist für {\mathrm{Re}(s)\geq\sigma_0(H) = 0}

\displaystyle  \mathcal{L}(H)(s) = \int_0^\infty \exp(-st){\mathrm d}{t} = \Big[-\frac1s\exp(-st)\Big|_{t=0}^\infty = \frac1s.

Satz 5 Für {F = \mathcal{L}(f)} gilt

  1. {F} ist für {\mathrm{Re}(s)>\sigma_0(f)} komplex differenzierbar.
  2. Für {\mathrm{Re}(s)\rightarrow\infty} gilt {F(s)\rightarrow 0}

Beweis:

  • Folgt aus den üblichen Regeln zur Vertauschung von Differentiation und Integration.
  • Für {x>\sigma>\sigma_0(f)} gilt

    \displaystyle  |F(s)|\leq \int_0^\infty K\exp(-(x-\sigma)t){\mathrm d}{t} \leq \frac{K}{x-\sigma}\rightarrow 0\quad\text{für }\ x\rightarrow\infty.

\Box

Bemerkung 6

  1. Führen wir die Differentiation unter dem Integral im ersten Punkt des Satzes durch, so sehen wir:

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

    und allgemeiner

    \displaystyle  F^{(n)}(s) = (-1)^n\mathcal{L}(t^n f(t))(s).

  2. Originale sind nur auf {[0,\infty{[}} definiert, wir denken sie uns allerdings üblicherweise durch Null auf ganz {{\mathbb R}} fortgesetzt. D.h. die Heaviside-Funktion “ist das gleiche” wie {1:{\mathbb R}_{\geq 0}\rightarrow{\mathbb C}} und {\cos(t)} entspricht dem Original {H(t)\cos(t)}. Die Ableitung eines Originals im Punkt {t=0} ist durch den rechtsseitigen Grenzwert gegeben:

    \displaystyle  f'(0) = \lim_{h\searrow 0}\frac{f(h) - f(0)}{h}

    und entsprechend für höhere Ableitungen.

1.2. Rechenregeln

Satz 7 Es sei {f} ein Original. Dann gelten folgenden Regeln:

  • Dämpfungsregel: Für {\alpha\in{\mathbb C}}:

    \displaystyle  \mathcal{L}(\exp(\alpha t)f(t))(s) = \mathcal{L}(f)(s-\alpha).

  • Skalierung: Für {a>0}:

    \displaystyle  \mathcal{L}(f(at))(s) = \tfrac{1}{a}\mathcal{L}(f)\big(\tfrac{s}{a}\big).

  • Zeitverschiebung: Für {a>0}:

    \displaystyle  \mathcal{L}(H(t-a)f(t-a))(s) = \exp(-as)\mathcal{L}(f)(s).

  • Differentiation: Ist {f} {n-1}-mal stetig differenzierbar und {f^{(n-1)}} habe stückweise stetiger Ableitung {f^{(n)}} und ist {f^{(n)}} ein Original, dann ist auch {f} ein Original und es gilt

    \displaystyle  \mathcal{L}(f^{(n)})(s) = s^n\mathcal{L}(f)(s) - f(0)s^{n-1} - f'(0)s^{n-2} - \cdots - f^{(n-1)}(0).

  • Integration: Für {\mathrm{Re}(s)>\max(0,\sigma_0(f))} gilt:

    \displaystyle  \mathcal{L}(\int_0^tf(\tau){\mathrm d}{\tau})(s) = \frac{1}{s}\mathcal{L}(f)(s)

  • Differentiation im Bildbereich: Für {n\in{\mathbb N}} gilt

    \displaystyle  \frac{{\mathrm d}{}^n}{{\mathrm d}{s}^n}\mathcal{L}(f)(s) = (-1)^n\mathcal{L}(t^nf(t))(s).

  • Beweis:

  • Dämpfungsregel, Skalierung und Zeitverschiebung folgen direkt nach entsprechender Substitution im Integral.
  • Differentiation: Wir zeigen die Behauptung für {n=1}: Es ist {f(t) = \int_0^t f'(\tau){\mathrm d}{\tau} - f(0)} und mit {|f'(t)|\leq K\exp(\sigma t)} ({\sigma>0}, sonst klar) folgt

    \displaystyle  |f(t)|\leq \int_0^t K\exp(\sigma \tau){\mathrm d}{\tau} + |f(0)| \leq \frac{K}{\sigma}(\exp(\sigma t) - 1) + |f(0)|

    und also ist auch {f} ein Original. Mit partieller Integration ergibt sich zu {b>0}

    \displaystyle  \int_0^b f'(t)\exp(-st){\mathrm d}{t} = \Big[ f(t)\exp(-st)\Big|_{t=0}^b + s\int_0^b f(t)\exp(-st){\mathrm d}{t}.

    Wir lassen nun {b} gegen unendlich streben und bekommen

    \displaystyle  \mathcal{L}(f')(s) = -f(0) + s\mathcal{L}(f)(s).

    Für {n>1} folgt die Behauptung per Induktion.

  • Integration folgt aus der Differentiation: Wir setzen {\Phi(t) = \int_0^t f(\tau){\mathrm d}{\tau}}. Das für ein Original {f} auch {\Phi(t)} ein Original ist, haben wir schon gesehen. Ist {\sigma_0(f) \geq 0}, so ist {\sigma_0(\Phi)=\sigma_0(f)}, ist {\sigma_0(f)<0} so ist {\sigma_0(\Phi) = 0}. Setzen wir {\Phi} in die Differentiationsregel ein, folgt die Behauptung.
  • Differentiation im Bildbereich Haben wir schon in Bemerkung 6 gesehen. \Box

    Zusätzlich zu diesen Rechenregeln gilt auch für die Laplace-Transformation ein Faltungssatz. Dafür definieren wir die Faltung von zwei Funktionen:

    Definition 8 Es seien {f,g\in L^1({\mathbb R})} (d.h. {f} und {g} sind absolut integrierbar im Lebesgueschen Sinne). Dann ist die Faltung von {f} und {g} definiert durch

    \displaystyle  (f*g)(t) = \int_{\mathbb R} f(\tau)g(t-\tau){\mathrm d}{\tau}.

    Bemerkung 9

    1. Gilt {f(t)=g(t)=0} für {t<0} so ist

      \displaystyle  (f*g)(t) = \begin{cases} \int_0^t f(\tau)g(t-\tau){\mathrm d}{\tau} & t\geq 0\\ 0 & t<0 \end{cases}.

      Diese Definition ist auch in Ordnung, wenn {f} und {g} nur lokal integrierbar sind. In diesem Fall ist auch {f*g\in L^1_{\textup{loc}}({\mathbb R}_{\geq 0})}.

    2. Sind {f} und {g} Originale, so ist auch {f*g} ein Original: Für {\sigma>\max(\sigma_0(f),\sigma_0(g))} gilt {|f(t)|\leq K_1\exp(\sigma t)} und {|g(t)|\leq K_2 \exp(\sigma t)} und es folgt

      \displaystyle  \begin{array}{rcl}  |(f*g)(t)| & \leq & \int_0^t K_1K_2 \exp(\sigma \tau)\exp(\sigma(t-\tau)){\mathrm d}{\tau}\\ & = & K_1K_2 t\exp(\sigma t)\\ & \leq & \tilde K\exp((\sigma+\epsilon)t). \end{array}

      für jedes {\epsilon>0} (mit passendem {\tilde K}). Es folgt

      \displaystyle  \sigma_0(f*g)\leq\max(\sigma_0(f),\sigma_0(g)).

    Satz 10 (Faltungssatz für die Laplace-Transformation) Für Originale {f} und {g} gilt

    \displaystyle  \mathcal{L}(f*g) = \mathcal{L}(f)\,\mathcal{L}(g).

    Beweis: Der Satz von Fubini erlaubt das Vertauschen der Integrationsreihenfolge. Beachte dabei das Integrationsgebiet {\{(t,\tau)\ :\  t\geq 0,\quad 0\leq\tau\leq t\} = \{(t,\tau)\ :\  \tau\geq 0,\quad \tau\leq t\}}.

    \displaystyle  \begin{array}{rcl}  &&\int_0^\infty \Big(\int_0^t f(\tau)g(t-\tau){\mathrm d}{\tau}\Big)\exp(-st){\mathrm d}{t}\\ &&= \int_0^\infty\int_0^t f(\tau)\exp(-s\tau)g(t-\tau)\exp(-s(t-\tau)){\mathrm d}{\tau}{\mathrm d}{t}\\ &&= \int_0^\infty f(\tau)\exp(-s\tau)\int_\tau^\infty g(t-\tau)\exp(-s(t-\tau)){\mathrm d}{t}{\mathrm d}{\tau}\\ && =\mathcal{L}(f)(s)\mathcal{L}(g)(s). \end{array}

    \Box

    1.3. Beispiele

    Beispiel 11 (Heavisidefunktion und einseitige Monome) Uns ist schon {\mathcal{L}(H)(s) = 1/s} für die Heavisidefunktion {H} bekannt. Differentiation im Bildbereich zeigt für {n\in{\mathbb N}}:

    \displaystyle  \mathcal{L}(t^n)(s) = \frac{n!}{s^{n+1}}.

    Beispiel 12 (Exponentialfunktion, Sinus und Kosinus) Mit der Dämpfungsregel und der Linearität folgt für {\lambda\in{\mathbb C}}

    \displaystyle  \mathcal{L}(\exp(\lambda t))(s) = \frac{1}{s-\lambda}

    Mit {\cos(\lambda t) = (\exp(\mathrm{i}\lambda t) + \exp(-\mathrm{i}\lambda t))/2} folgt daraus

    \displaystyle  \mathcal{L}(\cos(\lambda t))(s) = \frac12\Big(\frac{1}{s-\mathrm{i}\lambda} + \frac{1}{s+\mathrm{i}\lambda}\Big) = \frac{s}{s^2+\lambda^2}.

    und ebenso

    \displaystyle  \mathcal{L}(\sin(\lambda t))(s) = \frac1{2\mathrm{i}}\Big(\frac{1}{s-\mathrm{i}\lambda} - \frac{1}{s+\mathrm{i}\lambda}\Big) = \frac{\lambda}{s^2+\lambda^2}.

    Anwendung der Dämpfungsregel gibt für {\lambda,\omega\in{\mathbb C}}

    \displaystyle  \mathcal{L}(\exp(\lambda t)\cos(\omega t))(s) = \frac{(s-\lambda)}{(s-\lambda)^2 + \omega^2}

    und

    \displaystyle  \mathcal{L}(\exp(\lambda t)\sin(\omega t))(s) = \frac{\omega}{(s-\lambda)^2 + \omega^2}.

    Durch Differentiation im Bildbereich erhalten wir noch

    \displaystyle  \mathcal{L}(t\exp(\lambda t)\cos(\omega t))(s) = \frac{(s-\lambda)^2 - \omega^2}{\big((s-\lambda)^2+\omega^2\big)^2}

    und

    \displaystyle  \mathcal{L}(t\exp(\lambda t)\sin(\omega t))(s) = \frac{2(s-\lambda)\omega}{\big((s-\lambda)^2+\omega^2\big)^2}.

    Beispiel 13 (Charakteristische Funktionen von Intervallen) Wir betrachten ein Plateau der Höhe {c} von {a_1} bis {a_2}, d.h.

    \displaystyle  c\chi_{[a_1,a_2]}f(t) = \begin{cases} c & 0\leq a_1\leq t\leq a_2\\ 0 & \text{sonst}. \end{cases}

    Wegen {c\chi_{[a_1,a_2]}(t) = c(H(t-a_1) - H(t-a_2))} folgt

    \displaystyle  \mathcal{L}(c\chi_{[a_1,a_2]})(s) = \frac{c}{s}(\exp(-a_1 s) - \exp(-a_2 s))

    mit dem Spezialfall {c=1}, {a_1=0}, {a_2=1}

    \displaystyle  \mathcal{L}(\chi_{[0,1]})(s) = \frac{1-\exp(-s)}{s}.

    Beispiel 14 (Hut-Funktion) Wir betrachten

    \displaystyle  f(t) = \begin{cases} t & 0\leq t\leq 1\\ 2-t & 1\leq t\leq 2\\ 0 & \text{sonst}. \end{cases}

    Die Laplace-Transformierte erhalten wir einerseits aus dem Faltungssatz, denn es gilt {f = \chi_{[0,1]}*\chi_{[0,1]}} und daher

    \displaystyle  \mathcal{L}(f)(s) = (\mathcal{L}(\chi_{[0,1]})(s))^2 = \frac{(1-\exp(-s))^2}{s^2}.

    Andererseits gilt (fast überall)

    \displaystyle  f'(t) = H(t) - 2H(t-1) + H(t-2)

    und wegen

    \displaystyle  \mathcal{L}(f')(s) = \frac{1}{s}(1 - 2\exp(-s) + \exp(-2s))

    erhalten wir das gleiche Ergebnis mit Hilfe der Integrationsregel.

    Beispiel 15 (Rechteckschwingung) Die Rechteckschwingung ist

    \displaystyle  \begin{array}{rcl}  f(t) & =& \begin{cases} 1 & 2n\leq t<2n+1\\ -1 & 2n+1\leq t\leq 2n+2 \end{cases}\\ & =& H(t) - 2H(t-1) + 2H(t-2) - 2H(t-3) \pm\cdots \end{array}

    Dies gibt die Transformierte

    \displaystyle  \begin{array}{rcl}  \mathcal{L}(f)(s) & = & \frac{1}{s} - \frac{2}{s}\exp(-s) + \frac{2}{s}\exp(-2s) - \cdots\\ & = & \frac{2}{s}\Big(1 - \exp(-s) + \exp(-2s)-\cdots\Big) - \frac{1}{s}\\ & = & \frac{2}{s}\frac{1}{1 + \exp(-s)} - \frac{1}{s}\\ & = & \frac{1}{s}\,\frac{1-\exp(-s)}{1+\exp(-s)}. \end{array}

    Beispiel 16 (Dreieckschwingung) Wir setzen die Hut-Funktion periodisch fort und erhalten eine Dreiecksschwingung: Mit der Funktion {f} aus Beispiel 14 definieren wir

    \displaystyle  g(t) = f(t) + f(t-2) + f(t-4)+\cdots

    Es ergibt sich mit der Verschiebungsregel

    \displaystyle  \begin{array}{rcl}  \mathcal{L}(g)(s) & = & \frac{(1-\exp(-s))^2}{s^2}(1 + \exp(-2s) + \exp(-4s) + \cdots)\\ & = & \frac{(1-\exp(-s))^2}{s^2}\frac{1}{1 - \exp(-2s)}\\ & = & \frac{(1-\exp(-s))^2}{s^2(1 - \exp(-s))(1+\exp(-s))}\\ & = & \frac{1-\exp(-s)}{s^2(1+\exp(-s))}. \end{array}

    Das vorherige Beispiel motiviert die Betrachtung von periodischen Funktionen:

    Beispiel 17 (Periodische Funktionen) {f} habe die Periode {T}, d.h. {f(t+T) = f(t)}. Dann gilt

    \displaystyle  \begin{array}{rcl}  \mathcal{L}(f)(s) & = & \sum_{k=0}^\infty \int_{kT}^{(k+1)T} f(t) \exp(-st){\mathrm d}{t}\\ & = & \sum_k\int_0^T f(\tau)\exp(-s(\tau +kT)){\mathrm d}{\tau}\\ & = &\int_0^T f(\tau)\exp(-s\tau){\mathrm d}{\tau}\sum_k \exp(-skT)\\ & = & \frac{1}{1-\exp(-sT)}\int_0^T f(\tau)\exp(-s\tau){\mathrm d}{\tau}. \end{array}

    Die Laplace-Transformierte lässt sich also durch ein Integral über eine Periode der Funktion berechnen.

    Auch Potenzreihen lassen sich Laplace-transformieren:

    Lemma 18 Es sei {f(t) = \sum_{n=0}^\infty a_nt^n} für {t\geq 0}. Ist {\sum_{n=0}^\infty |a_n|n!\beta^{-n}<\infty} für ein {\beta>0}, so ist {f} ein Original und die Reihe

    \displaystyle  F(s) = \sum_{n=0}^\infty a_n n! s^{-n-1}

    konvergiert für {\mathrm{Re}(s)>\beta} und stimmt dort mit {\mathcal{L}(f)} überein.

    Beweis: Konvergenz für {\mathrm{Re}(s)>\beta} folgt aus dem Majoranten-Kriterium. Insbesondere ist {a_n n! s^{-n-1}} beschränkt, d.h. es gibt ein {c>0}, so dass

    \displaystyle  |a_n|\leq c\frac{\beta^n}{n!}

    und daher gilt

    \displaystyle  |f(t)|\leq c\sum (\beta t)^n/n! = c\exp(\beta t).

    Also ist {f} ein Original mit {\sigma_0(f) \leq \beta}. Für {\mathrm{Re}(s) \geq \beta + \epsilon} gilt

    \displaystyle  \Big|\sum_{n=0}^N a_n t^n \exp(-st)\Big|\leq c\sum_{n=0}^N \frac{(\beta t)^n}{n!}\exp(-(\beta+\epsilon)) \leq C\exp(-\epsilon t)

    Die rechte Seite ist (unabhängig von {N}) über {{\mathbb R}_{\geq 0}} absolut integrierbar. Der Satz von dominierten Konvergenz erlaubt also das gliedweise Integrieren. \Box

    Beispiel 19 (Besselfunktion) Die Besselfunktion nullter Ordnung ist

    \displaystyle  J_0(t) = \sum_{n=0}^\infty \frac{(-1)^n t^{2n}}{2^{2n}(n!)^2}.

    Als Laplace-Transformierte erhalten wir

    \displaystyle  \mathcal{L}(J_0)(s) = \sum_{n=0}^\infty \frac{(-1)^n (2n)!}{2^{2n}(n!)^2} s^{-2n-1}

    was nach dem Quotientenkriterium für {|s|>1} konvergiert. Es gilt allerdings (ebenfalls für {|s|>1}) für den Hauptzweig der komplexen Wurzel

    \displaystyle  \frac{1}{\sqrt{1+s^2}} = \frac{1}{s}\frac{1}{\sqrt{1 + \frac{1}{s^2}}} = \sum_{n=0}^\infty \binom{-\tfrac{1}{2}}{n} s^{-2n}

    mit dem verallgemeinerten Binomialkoeffizienten

    \displaystyle  \begin{array}{rcl}  \binom{-\tfrac{1}{2}}{n} & = & \frac{(-1/2)(-3/2)\cdots(-(2n-1)/2)}{n!}\\ & = & (-1)^n\frac{1\cdot 3\cdot 5\cdots (2n-1)}{2^n n!}\\ & = & (-1)^n\frac{(2n)!}{2^{2n}(n!)^2}. \end{array}

    und daher

    \displaystyle  \mathcal{L}(J_0)(s) = \frac{1}{\sqrt{1+s^2}}.

    1.4. Elektrische Netzwerke

    Die Laplace-Transformation lässt sich einsetzen, um elektrische Netzwerke zu analysieren. Ein elektrisches Netzwerk besteht aus drei verschiedenen Bauteilen: Widerständen, Spulen und Kondensatoren. Die Bauteile sind durch Leitungen miteinander verbunden, so dass Strom fließen kann. Legen wir nun an einer Stelle im Netzwerk eine Spannung {u(t)} an, so fließt ein Strom {i(t)}. Die Berechnung des fließenden Stroms wird durch folgende Regeln berechnet:

    Die Laplace-Transformation dieser Identitäten ergibt (Bezeichnung: {\mathcal{L}(u) = U} und {\mathcal{L}(i) = I})

    • \displaystyle U(s) = RI(s)

    • \displaystyle U(s) = Ls I(s)\quad\text{bei }\ i(0)=0

    • \displaystyle U(s) = \frac{1}{Cs}I(s)

    In jedem Fall läuft ein Bauteil auf eine Multiplikation von {I} mit einer rationalen Funktion hinaus. Diese Funktion bezeichnet man auch als “komplexen Widerstand” oder Impedanz und bezeichnet Ihn mit {Z(s)}, also

    \displaystyle  U(s) = Z(s)I(s).

    Die Impedanz eines Netzwerkes berechnet sich nach den Kirchhoffschen Regeln:

    • Sind Bauteile hintereinander geschaltet (“in Reihe”), so addieren sich die Impedanzen. Das heißt: Liegt an hintereinderliegenden Bauteilen mit Impedanzen {Z_1,\dots,Z_n} je eine Spannung {u_1,\dots,u_n} an, dann haben sie gemeinsam die Impedanz {Z = \sum Z_k} und die die Laplace-transformierte Spannung am {k}-ten Bauteil ist {U_k = Z_k I} und die Spannung über das zusammengefasste Bauteil {U = \sum Z_k I}.
    • Sind Bauteile parallel geschaltet, so ist die Impedanz der Kehrwerte der Summe der Kehrwerte. Das heißt: Fließt durch die Bauteile mit Impedanzen {Z_1,\dots, Z_n} je ein Strom {i_1,\dots, i_n}, dann hat das zusammenfasste Bauteil die Impedanz {Z = (\sum_k \tfrac1{Z_k})^{-1}} und der Laplace-transformierte Strom im {k}-ten Bauteil ist {I_k = \tfrac{U}{Z_k}}.

    Anschalten eines LCR-Gliedes/\href{Schwingkreises}} Für ein einfaches Beispiel in dem eine Spule {L} hinter eine Parallelschaltung von einem Widerstand und einem Kondensator {C} geschaltet wird ergibt sich die Gesamtimpedanz als

    \displaystyle  Z(s) = Ls + \frac{1}{Cs + \tfrac1R} = \frac{LCRs^2 + Ls + R}{RCs + 1}.

    Wir wollen nun zum Zeitpunkt {t=0} eine Gleichspannung {u_0} anlegen, das heißt, die Spannung ist {u(t) = H(t)u_0}. Die Laplace-Transformierte ist {U(s) = \frac{u_0}{s}} und die Laplace-Transformierte des Stromes durch das gesamte Glied ist

    \displaystyle  I(s) = \frac{U(s)}{Z(s)} = \frac{u_0(RCs + 1)}{(LCRs^2 + Ls + R)s}.

    Unter der Annahme {L<4RC^2} hat der Nenner die Nullstellen {s_0=0}, {s_{1/2} = -\sigma \pm \mathrm{i} \omega} mit {\sigma = \tfrac{1}{2RC}}, {\omega = \sqrt{\frac{1}{LC} - \frac{1}{4C^2R^2}}}. Um einen Eindruck der Rücktransformierten zu bekommen, Zerlegen wir {I(s)} in Partialbrüche und erhalten etwas von der Form

    \displaystyle  I(s) = \frac{A}{s-(-\sigma-\mathrm{i}\omega)} + \frac{B}{s-(-\sigma+\mathrm{i}\omega) } +\frac{C}{s}.

    Rücktransformation gibt

    \displaystyle  \begin{array}{rcl}  i(t) &=& A\exp((-\sigma-\mathrm{i}\omega)t) + A\exp((-\sigma+\mathrm{i}\omega)t) + C\\ &=& \exp(-\sigma t)\Big( (A+B)\cos(\omega t) +\mathrm{i}(A-B)\sin(\omega t)\Big) + C \end{array}

    Qualitativ lässt sich über den fließenden Strom folgendes sagen: Für {t\rightarrow\infty} geht dieser gegen eine Konstante {C} (da {\sigma>0}), Anfangs wird die Konstante durch eine Schwingung der Frequenz {\omega} überlagert und der Wert {\sigma} bestimmt die Geschwindigkeit des Abklingverhaltens die Überlagerung.

    Der unstetige Vorgang des Anschaltens lässt sich also mit Hilfe der Laplace-Transformation einfach beschreiben. Ebenso könnte man eine Wechselspannung anschalten, indem man {u(t) = H(t) u_0\exp(i\omega t)} anlegt. Man ist darüberhinaus auch daran interessiert, wie sich der Schaltkreis unter einem “Einheitsimpuls” verhält, d.h. wir legen zum Zeitpunkt {t=0} (für eine “unendlich kurze Zeit”) eine Spannung 1 an. Um dies zu realisieren bräuchte man eine Funktion {u} mit “unendlich kleinem Träger”, welche trotzdem eine Auswirkung in der Gleichung hat. Dies lässt sich mathematisch mit Hilfe von Distributionen formulieren.

    1.5. Laplace-Transformation von Distributionen

    Distributionen sind auch unter dem Namen “verallgemeinerte Funktionen” bekannt, was ihre Natur ganz gut beschreibt. Fundamental für das Konzept einer Distribution ist die Tatsache, dass eine lokal integrierbare Funktion {f:\Omega\rightarrow{\mathbb C}} fast überall durch die Integrale der Form

    \displaystyle  \int_\Omega f(x)\phi(x){\mathrm d}{x}

    bestimmt ist. Es reicht hier, wenn {\phi} alle unendlich oft differenzierbaren Funktionen mit kompaktem Träger durchläuft. Diese Tatsache ist auch als Fundamentallemma der Variationsrechnung oder als “Lemma von du Bois-Reymond” bekannt:

    Lemma 20 (Fundamentallemma der Variationsrechnung) Es sei {\Omega\subset{\mathbb R}^n} und {f\in L^1_{\textup{loc}}(\Omega)}. Gilt dann für alle {\phi\in C^\infty(\Omega)} mit kompaktem Träger

    \displaystyle  \int_\Omega f(x)\phi(x){\mathrm d}{x} = 0

    so ist {f=0} fast überall.

    Das heißt, die Werte {\int_\Omega f\,\phi} beschreiben die Funktion {f} (fast) vollständig. Wir können also statt {f} auch seine Wirkung auf dem Raum der sogenannten “Testfunktionen” (also den {C^\infty}-Funktionen mit kompaktem Träger) vermittels der Abbildung {T_f(\phi) =\int_\Omega f\,\phi} betrachten. Diese Idee lässt sich verallgemeinern: lineare Abbildungen, die jeder Testfunktion eine komplexe Zahl zuordnen, werden unsere verallgemeinerten Funktionen. Um für die Abbildungen noch einen Begriff der Stetigkeit formulieren können, definieren wir:

    Definition 21 (Testfunktionen und Konvergenz) Es sei {\Omega\subset{\mathbb R}}. Eine Funktion {f:\Omega\rightarrow{\mathbb C}} heißt Testfunktion, falls sie kompakten Träger hat und unendlich oft differenzierbar ist, den Vektorraum der Testfunktionen bezeichnen wir mit {\mathcal{D}(\Omega)}. Wir sagen, dass eine Folge {(f_n)} von Testfunktionen in {\mathcal{D}(\Omega)} gegen {f} konvergiert, falls

    1. es eine kompakte Menge {K} gibt, so dass die Träger aller {f_n} in {K} liegt, und
    2. alle Ableitungen {f^{(k)}_n} gleichmäßig gegen {f^{(k)}} konvergieren.

    Wir schreiben dafür {f_n\rightarrow f} in {\mathcal{D}(\Omega)}.

    Definition 22 (Distribution) Eine Abbildung {T:\mathcal{D}(\Omega)\rightarrow{\mathbb C}} heißt Distribution, falls sie linear und stetig ist, d.h. {T(\phi + \lambda\psi) = T(\phi) + \lambda T(\psi)} und für {\phi_n\rightarrow \phi} in {\mathcal{D}(\Omega)} folgt {T(\phi_n)\rightarrow T(\phi)}.

    Die Distributionen bilden einen Vektorraum, der mit {\mathcal{D}(\Omega)'} bezeichnet wird (in Analogie zur Bezeichnung des Dualraums in der Funktionalanalysis).

    Beispiel 23 (Reguläre und {\delta}-Distribution)

    • Jede Funktion {f\in L^1_{\textup{loc}}(\Omega)} induziert eine Distribution via

      \displaystyle  T_f(\phi) = \int_\Omega f(x)\phi(x){\mathrm d}{x}.

      Linearität ist klar und für die Konvergenz {T_f(\phi_n)\rightarrow T_f(\phi)} reicht sogar schon die gleichmäßige Konvergenz von einer kompakten Menge (Konvergenz der Ableitungen wird nicht benötigt). Distributionen, die von einer lokal integrierbaren Funktion induziert werden heißen reguläre Distributionen.

    • Eine bekannte (nicht-reguläre) Distribution ist die {\delta}-Distribution (auch Deltafunktion oder Dirac-Distribution): Sie ist definiert durch

      \displaystyle  \delta(\phi) = \phi(0).

      In Analogie zu regulären Distributionen schreibt man formal manchmal {\int \delta(x)\phi(x){\mathrm d}{x} = \phi(0)}.

    Um die Laplace-Transformation für eine Distribution {T} zu definieren, bietet es sich an, {\mathcal{L}(T)(s) = T(\exp(-st))} zu definieren; leider handelt es sich bei {\exp(-st)} nicht um eine Testfunktion (der Träger ist nicht kompakt). Es gibt jedoch einen etwas größeren Raum von geeigneten Funktionen:

    Definition 24 (Schwartz-Raum) Der Schwartz-Raum auf {{\mathbb R}} ist definiert durch

    \displaystyle  \mathcal{S}({\mathbb R}) = \{f\in C^\infty({\mathbb R})\ :\  \forall n,m\in{\mathbb N}\exists C_{n,m}: |t^n f^{(m)}(t)|\leq C_{n,m}\},

    seine Elemente nennen wir Schwartz-Funktionen oder auch “schnell fallende Funktionen”. Eine Folge {f_k} von Schwartz-Funktionen konvergiert in {\mathcal{S}({\mathbb R})} gegen {f}, falls für alle {n,m\in{\mathbb N}} gilt, dass {t^n(f_k^{(m)}(t) - f^{(m)}(t))} für {k\rightarrow\infty} gleichmäßig gegen Null konvergiert. Schwartz-Funktionen auf {{\mathbb R}_{\geq 0}} sind analog definiert, d.h. es wird keine Abfallverhalten für {t\rightarrow 0} vorgeschrieben.

    In Worten: {f} ist eine Schwartz-Funktion, wenn sie und ihre Ableitungen multipliziert mit allen Polynomen beschränkt ist. Beachte, dass der Schwartz-Raum vorerst nur auf {{\mathbb R}} und {{\mathbb R}_{\geq 0}} definiert wurde (bei Testfunktionen haben wir Teilmengen von {{\mathbb R}^n} zugelassen). Der Grund ist, dass Schwartz-Funktionen “gegen den Rand hin schnell genug abfallen müssen”, was bei Mengen mit kompliziertem Rand schwierig zu formulieren sein kann. Testfunktionen hingegen müssen (im Fall einer offenen Menge {\Omega}) einfach schon “vor dem Rand Null sein”.

    Offensichtlich gilt {\mathcal{D}({\mathbb R})\subset\mathcal{S}({\mathbb R})} (und {\mathcal{D}({\mathbb R}_{\geq 0})\subset \mathcal{S}({\mathbb R}_{\geq 0})}) und {\phi_n\rightarrow\phi} in {\mathcal{D}({\mathbb R})} impliziert {\phi_n\rightarrow\phi} in {\mathcal{S}({\mathbb R})}. Im

    Definition 25 (Temperierte Distribution) Eine lineare und stetige Abbildung {T:\mathcal{S}({\mathbb R})\rightarrow{\mathbb C}} (bzw. {T:\mathcal{S}({\mathbb R}_{\geq 0})\rightarrow{\mathbb C}}) heißt temperierte Distribution. Der Vektorraum der temperierten Distributionen wird mit {\mathcal{S}({\mathbb R})'} (bzw. {\mathcal{S}({\mathbb R}_{\geq 0})'}) bezeichnet.

    Bemerkung 26

    • Jede temperierte Distribution ist eine Distribution.
    • Die {\delta}-Distribution ist temperiert.
    • Nicht jede Distribution ist temperiert, insbesondere ist schon nicht jede reguläre Distribution temperiert: Für {f(x) = \exp(x^2)} gilt zwar {T_f\in\mathcal{D}({\mathbb R})'}, aber {\notin \mathcal{S}({\mathbb R})'} (da {\phi(x)=\exp(-x^2)} eine Schwartz-Funktion ist, für die {\int f(x)\phi(x){\mathrm d}{x}} nicht existiert).

    Bemerkung 27 (Operationen auf Distributionen) Mit Distributionen kann man zahlreiche Sachen machen, die man auch mit Funktionen machen kann.

  • Ableitung: Zum Beispiel kann man Distributionen ableiten: Ist {f:{\mathbb R}\rightarrow{\mathbb C}} lokal integrierbar und (stückweise) differenzierbar mit lokal integriertbarer Ableitung {f}, dann gilt nach der Regel der partiellen Integration

    \displaystyle  T_{f'}(\phi) = \int_{{\mathbb R}} f'(x)\phi(x){\mathrm d}{x} = -\int_{\mathbb R} f(x)\phi'(x){\mathrm d}{x} = -T_f(\phi').

    Der letzte Ausdruck ist jedoch schon ohne Differenzierbarkeit von {f} erklärt! Man nimmt dies zum Anlass und definiert die Ableitung einer Distribution {T} als

    \displaystyle  T'(\phi) = -T(\phi').

    Distributionen sind also unendlich oft differenzierbar!

  • Multiplikation mit einer {C^\infty}-Funktion: Analog lässt sich die Multiplikation einer Distribution mit einer {C^\infty}-Funktion definieren: Ist {g:{\mathbb R}\rightarrow{\mathbb C}} unendlich oft differenzierbar, so ist für eine Testfunktion {\phi} auch {g\phi} eine Testfunktion. Es gilt

    \displaystyle  T_{gf}(\phi) = \int_{\mathbb R} f(x)g(x)\phi(x){\mathrm d}{x} = T_f(g\phi)

    und daher definiert man für eine beliebige Distribution {T}

    \displaystyle   (gT)(\phi) = T(g\phi). \ \ \ \ \ (1)

  • Verschiebung: Um die Verschiebung einer Distribution zu formulieren, gehen wir wie folgt vor: Wie definieren zu {\tau\in{\mathbb R}} die Funktion {v_\tau(t) = t-\tau} und damit den Verschiebungsoperator {V_\tau f = f\circ v_\tau} (d.h. {V_\tau f(t) = f(t-\tau)}. In den Übungen sollen Sie sich überlegen, dass die Verschiebung einer Distribution {T} sinnvollerweise durch

    \displaystyle  (V_\tau T)(\phi) = T(V_{-\tau}\phi)

    definiert wird. Die Skalierung von Distributionen wird ebenfalls in den Übungen behandelt.

  • Bemerkung 28 (Sprechweise “im Distributionensinn”) Operationen, die wir wie in der vorigen Bemerkung von Funktionen auf Distributionen fortgesetzt haben, lassen sich natürlich auch auf reguläre Distributionen anwenden und damit in gewissem Sinne auch auf lokal integrierbare Funktionen. Bildet man zum Beispiel die Ableitung der regulären Distribution {T_f} so spricht man auch von “der Ableitung von {f} im Distributionensinn” oder von “der distributiven Ableitung von {f}”. Algemein sagt man das eine Funktion {f} eine Eigenschaft “im Distributionensinn” hat, wenn die zugehörige reguläre Distribution diese Eigenschaft hat. Zum Beispiel bedeutet “{f=g} im Distributionensinn”, dass {T_f=T_g} ist, was wiederum bedeutet dass {T_f(\phi) = T_g(\phi)} für alle Testfunktionen {\phi}, also {\int f\phi = \int g\phi} für all diese. Nach dem Fundamentallemma der Variationsrechnung also {f=g} fast überall.

    Beispiel 29

    1. Es sei {f(x) = \max(0,x)}. Dann ist die distributionelle Ableitung wieder eine reguläre Distribution, nämlich die, die zur Heaviside-Funktion gehört. Wie schreiben also

      \displaystyle  f'(x) = H(x)

      (und diese Gleichung gilt im Distributionensinn.)

    2. Auch {H} können wir distributionell ableiten. Diesmal ergibt sich allerdings keine Funktion mehr, sondern es gilt

      \displaystyle  H' = \delta

      (im Distributionensinne), oder präziser aber umständlicher {T_H' = \delta}.

    3. Die Ableitung der {\delta}-Distribution ist

      \displaystyle  \delta'(\phi) = -\delta(\phi') = -\phi'(0).

      Außerdem gilt

      \displaystyle  (g\delta)(\phi) = \delta(g\phi) = g(0)\phi(0).

    Beispiel 30 (Multiplikation, Differentiation und Produktregel) Es sei {g:{\mathbb R}\rightarrow{\mathbb C}} unendlich oft differenzierbar.

    1. Was ist {g\cdot\delta}? Wir berechnen die Wirkung auf eine Testfunktion {\phi}:

      \displaystyle  (g\cdot\delta)(\phi) = \delta(g\phi) = g(0)\phi(0).

      Mit anderen Worten: {(g\cdot \delta)(\phi) = g(0)\delta(\phi)}. Nun können wir auch das Argument {\phi} weglassen und erhalten die amüsante Beziehung

      \displaystyle  g\cdot\delta = g(0)\delta,

      (beachte hierbei: Auf der linken Seite steht das Produkt von {C^\infty}-Funktion mit einer Distribution (definiert in~(1); auf der rechten Seite steht das Produkt einer der komplexen Zahl mit einer Distribution).

    2. Was ist {g\cdot\delta'}? Auch hier berechnen wir die Wirkung auf eine Testfunktion und müssen hierbei beachten, dass wir zuerst die Multiplikation mit {g} und dann die Ableitung “in das Argument ziehen” müssen, was die Benutzung der Produktregel der Ableitung nach sich zieht:

      \displaystyle  \begin{array}{rcl}  (g\cdot\delta')(\phi) &=& \delta'(g\phi) = -\delta( (g\phi)') = -\delta(g'\phi + g\phi')\\ & = & -g'(0)\phi(0) - g(0)\phi'(0) \end{array}

      Mit anderen Worten: {(g\cdot\delta')(\phi) = -g(0)\delta(\phi) + g(0)\delta'(\phi)}. Wieder können wir das Argument {\phi} weglassen und bekommen die (eventuell komplizierter als erwartete) Gleichung

      \displaystyle  g\cdot\delta' = -g'(0)\delta + g(0)\delta'.

    3. Was ist {(g\cdot\delta)'}? Wir gehen vor wie oben:

      \displaystyle  (g\cdot\delta)'(\phi) = -(g\cdot\delta)(\phi') = \delta(g\phi') =- g(0)\phi'(0),

      mit anderen Worten {(g\cdot\delta)'(\phi) = g(0)\delta'(\phi)} bzw.

      \displaystyle  (g\cdot\delta)' = g(0)\delta'.

    4. Es gilt auch eine Produktregel für die Ableitung des Produkten von {C^\infty}-Funktion und Distribution:

      \displaystyle  (g\cdot T)'(\phi) = -(g\cdot T)(\phi') = -T(g\cdot \phi').

      Wir benutzen die “Produktregel für die Ableitung des Produktes von Funktionen rückwärts”, d.h. {g\cdot\phi' = (g\cdot\phi)' - g'\cdot\phi} und bekommen

      \displaystyle  \begin{array}{rcl}  (g\cdot T)'(\phi) &=& -T((g\cdot\phi)' - g'\cdot\phi)\\ &=& -T((g\cdot\phi)') + T(g'\cdot\phi)\\ &=& T'(g\cdot\phi) + (g'\cdot T)(\phi)\\ &=& (g\cdot T')(\phi) + (g'\cdot T)(\phi), \end{array}

      d.h.

      \displaystyle  (g\cdot T)' = g\cdot T' + g'\cdot T.

    Zu guter Letzt kann man sich davon überzeugen, dass unsere Überlegungen alle konsistent sind, in dem man sich {(g\cdot\delta)'} noch einmal mit Hilfe der allgemeinen Produktregel berechnet.

    Zurück zur Laplace-Transformation von Distributionen: Wir können zum Beispiel schon formal die {\delta}-Distribution mit unser ursprünglichen Idee transformieren: {\mathcal{L}(\delta)(s) =\delta(\exp(-st)) = \exp(-s0) = 1}.

    Konzeptionell beobachten wir: Wir können die Laplace-Transformierte einer Distribution {T} definieren, wenn es ein {x_0} gibt, so dass {\exp(-x_0 t)T} eine temperierte Distribution ist, denn dann ist für {\mathrm{Re}(s)>x_0} die Funktion {\exp(-(s-x_0)t)} eine Schwartz-Funktion auf {{\mathbb R}_{\geq 0}} und der Ausdruck

    \displaystyle  T(\exp(-st)) = (\exp(-x_0 t)T)(\exp(-(s-x_0)t)

    ist wohldefiniert. Wir halten fest:

    Definition 31 (Laplace-Transformation von Distributionen) Es sei {T\in\mathcal{D}({\mathbb R}_{\geq 0})'} eine Distribution. Gibt es {x_0\in{\mathbb R}}, so dass {\exp(-x_0 t)T} eine temperierte Distribution ist, so definieren wir die Laplace-Transformation von {T} als

    \displaystyle  \mathcal{L}(T)(s) = T(\exp(-st)).

    Die bekannten Rechenregeln für die Laplace-Transformation gelten auch in diesem Fall (falls sie denn sinnvoll erklärt werden können).

    Beispiel 32 (Ableitungsregel) Es gilt

    \displaystyle  \begin{array}{rcl}  \mathcal{L}(\delta')(s) &=& \delta'(\exp(-st)) = -\delta(-s\exp(-st)) = s. \end{array}

    und ebenso

    \displaystyle  L(\delta^{(k)})(s) = s^k.

    Wir können nun schon einige Sachen mit Distributionen machen: Die Vektorraumoperationen Addition und skalare Multiplikation, sie mit {C^\infty}-Funktionen multiplizieren, Ableiten, Verschieben und Skalieren. Nun wollen wir uns daran machen und versuchen, Distributionen zu falten. Das wird nicht in allen Fällen funktionieren. Wieder überlegen wir uns zu erst, wie die Faltung von zwei regulären Distributionen aussieht. Sind {f,g:{\mathbb R}\rightarrow{\mathbb C}} “faltbare Funktionen”, so gilt

    \displaystyle  \begin{array}{rcl}  T_{f*g}(\phi) &=& \int_{\mathbb R} (f*g)(t)\phi(t){\mathrm d}{t}\\ &=& \int_{\mathbb R}\int_{\mathbb R} f(\tau) g(t-\tau){\mathrm d}{\tau}\phi(t){\mathrm d}{t}\\ &=& \int_{\mathbb R} f(\tau)\int_{\mathbb R} g(t)\phi(t+\tau){\mathrm d}{t}{\mathrm d}{\tau}\\ &=& \int_{\mathbb R} f(\tau) T_g(V_{-\tau}\phi){\mathrm d}{\tau}\\ &=& T_f(T_g(V_{-\tau}\phi). \end{array}

    Schauen wir uns diese Herleitung noch einmal kritisch an: Wir müssen die Integrationsreihen vertauschen dürfen, d.h. die Integrierbarkeit der Funktion {(t,\tau)\mapsto f(\tau)g(t-\tau)\phi(t)} muss “gut genug” sein. Der kompakte Träger von {\phi} allein reicht dafür nicht aus. Fordert man zusätzlich noch kompakten Träger von {f} oder {g} (und deren Integrierbarkeit) so ist man auf der sicheren Seite. Um in der letzten Zeile von regulären Distributionen {T_f} und {T_g} zu allgemeinen Distributionen {T_1} und {T_2} überzugehen, muss das Argument von {T_f} (bzw. {T_1}) eine Testfunktion sein. Mit anderen Worten: Die Abbildung {\tau\mapsto T_2(V_{-\tau}\phi)} muss unendlich oft differenzierbar sein und kompakten Träger haben. Um Voraussetzungen zu formulieren, die das Falten von Distributionen erlaubt, benötigen wir noch den Begriff des Trägers einer Distribution:

    Definition 33 Der Träger {\mathrm{supp}(T)} einer Distribution {T\in\mathcal{D}(\Omega)'} ist wie folgt definiert: { t_0\in\mathrm{supp}(T)} falls für jedes {\epsilon>0} ein {\phi\in\mathcal{D}(\Omega)} mit {\mathrm{supp}(\phi)\subset B_\epsilon(t_0)} gibt, so dass {T(\phi)\neq 0}.

    Der folgende Satz gibt Bedingungen unter denen die Faltung von zwei Distributionen erklärt ist an; wir geben ihn ohne Beweis.

    Satz 34 Es seien {T_1,T_2\in\mathcal{D}({\mathbb R})'} Distributionen und {T_1} oder {T_2} habe kompakten Träger. Dann ist

    \displaystyle  (T_1*T_2)(\phi) = T_1(T_2(V_{-\tau}\phi))

    wohldefinierbar und wieder eine Distribution.

    Die Faltung von Distributionen wird zum Beispiel im Buch “Functional Analysis” von Walter Rudin behandelt, siehe auch mein Skript zu Fouriertransformation und Distributionen, Abschnitt 3.6. Dass die Definition der Faltung von Distributionen kompliziert ist, lässt sich auch schon im Speziallfall der Faltung von Distribution und Funktion sehen:

    Bemerkung 35 (Faltung von Distribution und Funktion) Mit dem Vorgehen aus dem obigen Satz lassen sich auch gewisse Funktionen mit gewissen Distributionen falten:

    1. Hat nämlich {f\in L^1_{\textup{loc}}({\mathbb R})} einen kompakten Träger, so hat die induzierte Distribution {T_f} den gleichen Träger (siehe Übungsaufgaben). Insbesondere ist

      \displaystyle  T_f( V_{-\tau}\phi) = \int_{\mathbb R} f(t)\phi(t+\tau){\mathrm d}{t} = (f*\phi)(-\tau)

      wieder eine Testfunktion und damit ist für jede Distribution {S} der Ausdruck

      \displaystyle  (S*T_f)(\phi) = S(T_f(V_{-\tau}\phi))

      wohldefiniert.

    2. Hat andererseits eine Distribution {S} kompakten Träger und ist {f\in L^1_{\textup{loc}}({\mathbb R})} (jetzt auch ohne kompakten Träger), dann ist {T_f(V_{-\tau}\phi) = \int_{\mathbb R} f(t)\phi(t+\tau) = (f*\phi)(-\tau)} zwar keine Testfunktion, aber immerhin unendlich oft differenzierbar (was aus der Ableitungsregel für die Faltung folgt). Um nun {S} auf {T_f(V_{-\tau}\phi) = (f*\phi)(-\tau)} anwenden zu können benötigen wir noch die Tatsache, dass sich Distributionen {S:\mathcal{D}({\mathbb R})\rightarrow{\mathbb C}} mit kompakten Träger auf den Raum {C^\infty({\mathbb R})} fortsetzen lassen, d.h. dass eine eindeutige stetige und lineare Fortsetzung {S:C^\infty({\mathbb R})\rightarrow{\mathbb C}} gibt. In diesem Sinne ist dann auch {S(T_f(V_{-\tau}\phi))} sinnvoll.

    Da wir in der Notation nicht immer zwischen Funktion {f} und induzierter Distribution {T_f} unterscheiden, schreiben wir auch {S*f} für die Faltung der Distributionen {S} und {T_f}.

    Beispiel 36 (Faltung mit {\delta} und {\delta'}) Es sei {T} eine Distribution. Dann ist

    \displaystyle  (\delta*T)(\phi) = \delta(T(V_{-\tau}\phi) = T(V_0\phi) = T(\phi)

    was nichts anderes bedeutet als

    \displaystyle  \delta*T = T.

    (Der Vollständigkeit halber betrachten wir noch {(T*\delta)(\phi) = T(\delta(V_{-\tau}\phi)) =T(\phi)}, es gilt also auch {T*\delta = T}). Speziell für Funktionen {f} folgt auch

    \displaystyle  \delta*f = f*\delta = f.

    Weiterhin gilt

    \displaystyle  \delta'(V_{-\tau}\phi) = -\phi'(\tau)

    und es folgt

    \displaystyle  (T*\delta')(\phi) = T(\delta'(V_{-\tau}\phi)) = -T(\phi') = T'(\phi)

    was nicht anderes bedeutet als

    \displaystyle  T*\delta' = T'.

    Für Funktionen ergibt sich

    \displaystyle  f*\delta' = f'\quad\text{(es gilt auch\ } \delta'*f = f'\text{)}.

    1.6. Lineare Differentialgleichungen und Anwendungen

    In diesem Abschnitt behandeln wir die Lösung von Differentialgleichungen mit Hilfe der Laplace-Transformation. Wir beginnen mit linearen Differentialgleichungen {n}-ter Ordnung: Wir betrachten das Polynom

    \displaystyle  P(s) = s^n + a_{n-1}s^{n-1} + \cdots a_0.

    Durch formales Einsetzen des Differentiationsoperators bekommen wir einen (linearen) Differentialoperator {n}-ter Ordnung

    \displaystyle  P(\tfrac{{\mathrm d}{}}{{\mathrm d}{t}}) y = y^{(n)} + a_{n-1} y^{(n-1)} + \cdots a_0 y

    Zum Aufwärmen betrachten wir die homogene Differentialgleichung (d.h. mit rechter Seite {\equiv 0}):

    Satz 37 Für die Lösung der Differentialgleichung

    \displaystyle  P(\tfrac{{\mathrm d}{}}{{\mathrm d}{t}}) y = 0

    mit

    \displaystyle  y(0) = y'(0) = \cdots y^{(n-2)}(0) = 0,\quad y^{(n-1)}(0)=1

    gilt

    \displaystyle  \mathcal{L}(y)(s) = \frac{1}{P(s)}.

    Beweis: Auf Grund der Anfangswerte folgt für {y}

    \displaystyle  \begin{array}{rcl}  \mathcal{L}(y')(s) &=& s\mathcal{L}(y)(s)\\ \vdots & & \vdots\\ \mathcal{L}(y^{(n-1)})(s) & = & s^{n-1}\mathcal{L}(y)(s)\\ \mathcal{L}(y^{(n)})(s) & = & s^{n}\mathcal{L}(y)(s) - 1. \end{array}

    Da {y} die Differentialgleichung erfüllt, folgt für {\mathcal{L}(y)(s)}:

    \displaystyle  s^n\mathcal{L}(y)(s) + a_{n-1}s^{n-1}\mathcal{L}(y)(s) + \cdots a_0\mathcal{L}(y)(s) = 1

    Und daher muss {P(s)\mathcal{L}(y)(s) = 1}, was die Behauptung zeigt. \Box

    Bemerkung 38 (Allgemeines Vorgehen zur Lösung der inhomogenen Gleichung) Für die inhomogene Differentialgleichung

    \displaystyle  P(\tfrac{{\mathrm d}{}}{{\mathrm d}{t}})y(t) = f(t)

    mit Anfangswerten {y(0) = c_0,\ \dots, y^{(n-1)}(0) = c_{n-1}} ergibt sich mit {F(s) = \mathcal{L}(f)(s)} für die Laplace-Transformierte der Lösung

    \displaystyle  \mathcal{L}(y)(s) = \frac{A(s)}{P(s)} + \frac{F(s)}{P(s)}

    mit einem Polynom {A} vom Grade {\leq n-1} (welches von den Koeffizienten {a_\nu} und den Anfangswerten {c_\nu} abhängt).

    1. Der Summand {\tfrac{A(s)}{P(s)}} ist eine rationale Funktion. Seine Rücktransformierte ist die Lösung {y_h} der homogenen Gleichung mit den Anfangswerten {c_\nu}. Wir bezeichnen mit {\lambda_\rho} ({\rho=1,\dots,r}) die verschiedenen Nullstellen des Nenners {P(s)} und mit {n_\rho} die zugehörige Vielfachheit. Dann hat {y_h} folgende Form

      \displaystyle  y_h(t) = \sum_{\rho=1}^r\sum_{\nu=1}^{n_\rho} \frac{b_{\rho,\nu}}{(\nu-1)!}t^{\nu-1}\exp(\lambda_\rho t)

      mit Koeffizienten {b_{\rho,\nu}} die sich aus der Partialbruchzerlegung von {A/P} ergeben. Wir beobachten, dass falls {\mathrm{Re}(\lambda_\rho)<0} (für alle {\rho}), die Lösung {y_h(t)} für {t\rightarrow 0} für alle Anfangswerte gegen Null strebt.

    2. Die Rücktransformierte {y_s} des Summanden {\tfrac{F(s)}{P(s)}} ist die Lösung der inhomogenen Gleichung mit Anfangswerten {c_\nu=0}. Ist {f} ein “exponentielles Polynom”, d.h. ein Ausdruck der Form {\sum_k d_k\exp(\lambda_k t)}, dann ist {F/P} eine rationale Funktion und die Rücktransformation ist mit Hilfe von Partialbruchzerlegung möglich.
    3. Um {y_s} zu bestimmen, kann man auch den “Faltungstrick” anwenden. Dazu sucht man eine Rücktransformierte {g} von {1/P}, d.h. {\mathcal{L}(g)(s) = 1/P(s)}. Auf Grund des Faltungssatzes~10 ist dann eine Rücktransformierte von {F(s)\frac{1}{P(s)}} durch {f*g} gegeben, also {y_s = f*g}.

    Bemerkung 39 (Interpretation des Faltungstricks) Der Faltungstrick hat folgende Interpretation: {g} ist die Lösung von

    \displaystyle   P(\tfrac{{\mathrm d}{}}{{\mathrm d}{t}}) y = 0,\quad y(0)= \cdots =y^{(n-2)}(0)=0,\quad y^{(n-1)}(0)=1. \ \ \ \ \ (2)

    Anders formuliert: {g} ist die Lösung der “distributionell zu verstehenden” Gleichung

    \displaystyle  P(\tfrac{{\mathrm d}{}}{{\mathrm d}{t}}) y = \delta

    welche ihren Träger in {[0,\infty{[}} hat. Man nennt {g} daher auch “Impulsantwort”. Begründung: Sei {u:{\mathbb R}\rightarrow{\mathbb C}} Lösung von (2). Dann ist {g(t) = H(t)u(t)} (mit der Heaviside-Funktion {H}). Distributionelles Ableiten mit Hilfe der Produktregel aus Beispiel 30 ergibt:

    \displaystyle  \begin{array}{rcl}  g' & = & \delta u + H u' = \underbrace{u(0)}_{=0} \delta + H u'\\ & = &Hu'\\ g'' &=& H u''\\ \vdots & & \vdots\\ g^{(n-1)} &=& H u^{(n-1)}\\ g^{(n)} &=& \delta u^{(n-1)} + H u^{(n)}\\ &=& \delta + H u^{(n)}. \end{array}

    Beispiel 40 (Homogene und inhomogene Lösungen) Wir betrachten die Differentialgleichung zweiter Ordnung

    \displaystyle  y'' - y = f,\quad y(0)=c_0,\quad y'(0) = c_1.

    Das zugehörige Polynom ist {P(s) = s^2-1} und die Laplace-Transformierte der Lösung ist

    \displaystyle  \mathcal{L}(y)(s) = \frac{c_0 s + c_1}{s^2-1} + \frac{F(s)}{s^2-1}.

    Die homogene Lösung {y_h} (also für {f=0}) ergibt sich nach Partialbruchzerlegung

    \displaystyle  \frac{c_0 s + c_1}{s^2-1} = \frac{c_0-c_1}{2}\frac{1}{s+1} + \frac{c_0+c_1}{2}\frac{1}{s-1}

    als

    \displaystyle  y_h(t) = \frac{c_0-c_1}{2}\exp(-t) + \frac{c_0+c_1}{2}\exp(t).

    Für die inhomogene Gleichung mit rechter Seite {f(t) = 1} und Null-Anfangswerten haben wir {\mathcal{L}(f)(s) = 1/s} und wegen

    \displaystyle  \mathcal{L}(y_1)(s) = \frac1s\frac{1}{s^2-1} = \frac12\frac{1}{s+1} + \frac12\frac{1}{s-1} - \frac1s

    die Lösung

    \displaystyle  y_1(t) = \frac12(\exp(t) + \exp(-t)) - 1 = \cosh(t) - 1.

    Bei der etwas komplizierteren rechte Seite {f(t) = \chi_{[a,b]}(t)} betrachten wir zwei Lösungsmöglichkeiten: Die Transformierte von {f} ist (vgl. Beispiel~13)

    \displaystyle  \mathcal{L}(f)(s) = \frac{\exp(-as) - \exp(-bs)}{s}.

    Daher ist die Laplace-Transformierte der Lösung

    \displaystyle  \mathcal{L}(y_\chi)(s) = \frac{\exp(-as)}{s(s^2-1)} - \frac{\exp(-bs)}{s(s^2-1)}

    und mit der Zeitverschiebungsregel und der Lösung {y_1} folgt

    \displaystyle  y_\chi(t) = H(t-a)y_1(t-a) - H(t-b)y_1(t-b).

    Andererseits können wir auch den Faltungstrick benutzen: Die Rücktransformierte von {1/P(s) = 1/(s^2-1)} ist {g(t) = \frac{\exp(t) - \exp(-t)}{2} = \sinh(t)} und die Lösung ist

    \displaystyle  y_\chi(t) = \chi_{[a,b]}* g (t).

    Beispiel 41 (Distributionelle rechte Seiten) Wir sind auch in der Lage Gleichungen mit Distributionen als rechte Seite zu lösen. Wir definieren die verschobene {\delta}-Distribution zu {a\in{\mathbb R}} als

    \displaystyle  \delta_a(\phi) = \phi(a)

    und betrachten

    \displaystyle  y'' - y = \delta_a,\quad y(0)=c_0,\quad y'(0) = c_1.

    Die homogene Lösung {y_h(t) = \frac{c_0-c_1}{2}\exp(-t) + \frac{c_0+c_1}{2}\exp(t)} ist uns schon aus dem vorherigen Beispiel bekannt. Die inhomogene Lösung {y_s} (mit Null-Anfangswert) ist die Rücktransformierte von {\mathcal{L}(\delta_a)(s)/(s^2-1)} und wegen {\mathcal{L}(\delta_a)(s) = \exp(-sa)} folgt nach der Zeitverschiebungsregel

    \displaystyle  y_s(t) = \sinh(t-a).

    (Dies sieht man auch mit dem Faltungstrick, denn es gilt {\delta_a*g(t) = g(t-a)}.)

    1.7. Injektivität von {\mathcal{L}} und Umkehrbarkeit

    Zur Inversion der Laplace-Transformation schaut man in der Praxis meist in Tabellen nach. Damit dieses Vorgehen auch gerechtfertig ist, muss man wissen, dass die Laplace-Transformation injektiv ist, d.h. das zwei verschiedene Funktionen auch verschiedene Laplace-Transformierte haben. Der Beweis dafür ist nicht sehr einfach:

    Satz 42 Es seien {f} und {g} Originale. Gilt dann {\mathcal{L}(f) = \mathcal{L}(g)}, so gilt {f=g} (fast überall).

    Bevor wir zum Beweis kommen: Die Gleichheit {\mathcal{L}(f) = \mathcal{L}(g)} muss nur auf einer beliebigen rechten Halbebene gelten (der Identitätssatz sorgt dann dafür, dass sie “auf ihren maximalen Definitionsgebieten” gleich sind). Als Hilfsmittel benötigen:

    Lemma 43 (Momentensatz) Es seien {a,b\in{\mathbb R}} und {\phi:[a,b]\rightarrow{\mathbb C}} stetig. Gilt dann für alle {n\in{\mathbb N}}

    \displaystyle  \int_a^b t^n\phi(t){\mathrm d}{t} = 0

    so ist {\phi=0}.

    Beweis: Durch getrenntes Betrachten von Real- und Imaginärteil können wir uns auf reellwertige Funktionen {\phi} beschränken. Nach dem Approximationssatz von Weierstraß gibt es zu jedem {\epsilon>0} ein Polynom {p_\epsilon}, so dass

    \displaystyle  \max_{t\in[a,b]}|\phi(t)- p_\epsilon(t)|\leq \epsilon.

    Es folgt für alle {t\in[a,b]}

    \displaystyle  -\epsilon|\phi(t)| \leq\phi(t)^2 - \phi(t)p_\epsilon(t)\leq\epsilon|\phi(t)|.

    Durch Integration von {a} bis {b} ergibt sich

    \displaystyle  \epsilon\int_a^b|\phi(t)|{\mathrm d}{t}\geq \int_a^b\phi(t)^2{\mathrm d}{t} - \int_a^b\phi(t)p_\epsilon(t){\mathrm d}{t}.

    Nach Voraussetzung gilt {\int_a^b\phi(t)p_\epsilon(t){\mathrm d}{t} = 0}, d.h für jedes {\epsilon>0} gilt

    \displaystyle  0\leq \int_a^b\phi(t)^2{\mathrm d}{t} \leq \epsilon\int_a^b|\phi(t)|{\mathrm d}{t}

    und daher

    \displaystyle  \int_a^b\phi(t)^2{\mathrm d}{t} = 0.

    Das Lemma ist bewiesen. \Box

    Beweis: (von Satz~42) Wir zeigen, dass aus {F(s) = \mathcal{L}(f)(s)=0} für {\mathrm{Re}(s)>\sigma_0(f)} folgt, dass {f=0} (fast überall). Dazu zeigen wir eine scheinbar schwächere Behauptung: Gibt es {s_0} mit {\mathrm{Re}(s_0)>\sigma_0(f)} und {\xi\geq 0}, so dass {F(s_0 + n\xi)=0} für {n=1,2,\dots}, so gilt {f=0} (fast überall). Wir definieren

    \displaystyle  \phi(t) = \int_0^tf(\tau)\exp(-s_0\tau){\mathrm d}{\tau}.

    Bemerke, dass {\phi} stetig (da {f} lokal integrierbar) und beschränkt (da der Grenzwert {\phi(t)\rightarrow F(s_0)} für {t\rightarrow\infty} existiert). Die Laplace-Transformierte von {\phi} ist

    \displaystyle  \begin{array}{rcl}  \mathcal{L}(\phi)(s) &=& \int_0^\infty\int_0^tf(\tau)\exp(-s_o\tau){\mathrm d}{\tau}\exp(-st){\mathrm d}{t}\\ &=& \int_0^\infty f(\tau)\exp(-s_0\tau)\underbrace{\int_\tau^\infty\exp(-st){\mathrm d}{t}}_{= \exp(-s\tau)/s}{\mathrm d}{\tau}\\ &=& \frac1s F(s+s_0). \end{array}

    Nach Voraussetzung gilt also {\mathcal{L}(\phi)(n\xi) = 0} für {n=1,2,\dots}, was nichts anderes heißt als

    \displaystyle  \int_0^\infty\phi(t)\exp(-t\xi)^n{\mathrm d}{t}=0\quad n=1,2,\dots.

    Wir substituieren {x=\exp(-t\xi)} (also {t = -\log(x)/\xi} und {{\mathrm d}{t} = -{\mathrm d}{x}/(x\xi)}) und bekommen

    \displaystyle  \frac{1}{\xi}\int_0^1\phi\big(-\tfrac{\log(x)}{\xi}\big) x^{n-1}{\mathrm d}{x} = 0,\quad n=1,2,\dots.

    Da die Abbildung {x\mapsto\phi\big(-\tfrac{\log(x)}{\xi}\big)} stetig ist, folgt aus dem Momentensatz {\phi(x)\equiv 0} und damit, dass {f(t)\exp(-s_0 t) = 0} (fast überall). \Box

    Wenden wir uns nun der Umkehrformel zu:

    Satz 44 Zu {f\in\mathcal{L}^1_{\textup{loc}}({\mathbb R})} (mit {f(t)=0} für {t<0}) mit Laplace-Transformierter {F(s) = \mathcal{L}(f)(s)} definieren wir die Größe

    \displaystyle  \sigma_1(f) = \inf\{c\ :\  f(t)\exp(-ct)\in L^1({\mathbb R})\}.

    Dann gilt für {a>\sigma_1(f)} und für alle {t\geq 0} in denen {f} stetig ist die Bromwich-Formel

    \displaystyle  f(t) = \frac{1}{2\pi\mathrm{i}}\int_{a-\mathrm{i}\infty}^{a+\mathrm{i}\infty} F(s)\exp(st){\mathrm d}{s}.

    Der Beweis benutzt einige Tatsachen, die wir im nächsten Abschnitt über die Fourier-Transformation beweisen werden und daher vertagen wir ihn.

  • An email by Thomas Vogt brought me to the website of the DMV (“Deutsche Mathematiker Vereinigung” – or should I write “Deutsche Mathematische Vereinigung”? But that’s another issue…) which is http://dmv.mathematik.de. He asked me if I could write a post about my recent short survey about the beginning of the Elsevier boycott (which is in German and available here).

    While I visited the DMV website I learned several interesting things:

    • On the top left of the website, there is a login button! If you are member of the DMV (You are not? And you are German? Come on – join!) and you know your Mitgliedsnummer, you can sign up right away. If you don’t know your Mitgliedsnummer (like me) you can ask the DMV (see here) to get it.
    • Once logged in, you can participate in the DMV Forum which is anything but deserted (well, it is not incredibly lively these days…).
    • But the most interesting thing was: There is even a kind of social-network functionality! Currently there are 692 members. Okay – its not Facebook but on the other hand, it is pretty focused; only mathematicians related to Germany. With that number of member I made the effort and looked over all of them. I found out that currently there was precisely one “friendship” within the whole network. If my effort pays off, I will be the person which has the highest number of friends! Let’s see…

    In this post I gladly announce that three problems that bothered me have been solved: The computational complexity of certifying RIP and NSP and the number of steps the homotopy method needs to obtain a solution of the Basis Pursuit problem.

    1. Complexity of RIP and NSP

    On this issue we have two papers:

    The first paper has the more general results and hence, we start with the second one: The main result of the second paper is this:

    Theorem 1 Let a matrix {A}, a positive integer {K} and some {0<\delta<1} be given. It is hard for NP under randomized polynomial-time reductions to check if {A} satisfies the {(K,\delta)} restricted isometry property.

    That does not yet say that it’s NP-hard to check if {\delta} is an RIP constant for {K}-sparse vectors but it’s close. I think that Dustin Mixon has explained this issue better on his blog than I could do here.

    In the first paper (which is, by the way, on outcome of the SPEAR-project in which I am involved…) the main result is indeed the conjectured NP-hardness of calculating RIP constants:

    Theorem 2 For a given matrix {A} and a positive integer {K}, it is NP-hard to compute the restricted isometry constant.

    Moreover, this is just a corollary to the main theorem of that paper which reads as

    Theorem 3 For a given matrix {A} and a positive integer {K}, the problem to decide whether {A} satisfies the restricted isometry property of order {K} for some constant {\delta<1} is coNP-complete.

    They also provide a slightly strengthened version of Theorem~1:

    Theorem 4 Let a matrix {A}, a positive integer {K} and some {0<\delta<1} be given. It is coNP-complete to check if {A} satisfies the {(K,\delta)} restricted isometry property.

    Moreover, the paper by Pfetsch and Tillmann also proves something about the null space property (NSP):

    Definition 5 A matrix {A} satisfies the null space property of order {K} if there is a constant {\alpha>0} such that for all elements {x} in the null space of {A} it holds that the sum of the {K} largest absolute values of {x} is smaller that {\alpha} times the 1-norm of {x}. The smallest such constant {\alpha} is called the null space constant of order {K}.

    Their main result is as follows:

    Theorem 6 F or a given matrix {A} and a positive integer {K}, the problem to decide whether {A} satisfies the null space property order {K} for some constant {\alpha<1} is coNP-complete. Consequently, it is NP-hard to compute the null space constant of {A}.

    2. Complexity of the homotopy method for Basis Pursuit

    The second issue is about the basis pursuit problem

    \displaystyle  \min_x \|x\|_1\quad\text{s.t.}\ Ax=b.

    which can be approximated by the “denoising variant”

    \displaystyle  \min_x \lambda\|x\|_1 + \tfrac12\|Ax-b\|_2^2.

    What is pretty interesting about the denoising variant is, that the solution {x(\lambda)} (if it is unique throughout) depends on {\lambda} in a piecewise linear way and converges to the solution of basis pursuit for {\lambda\rightarrow 0}. This leads to an algorithm for the solution of basis pursuit: Start with {\lambda=\|A^Tb\|_\infty} (for which the unique solution is {x(\lambda)=0}), calculate the direction of the “solution path”, follow it until you reach a “break point”, calculate the next direction and so on until {\lambda} hits zero. This is for example implemented for MATLAB in L1Homotopy (the SPAMS package also seems to have this implemented, however, I haven’t used it yet). In practice, this approach (usually called homotopy method) is pretty fast and moreover, only detects a few break points. However, an obvious upper bound on the number of break point is exponential in the number of entries in {x}. Hence, it seemed that one was faced with a situation similar to the simplex method for linear programming: The algorithms performs great an average but the worst case complexity is bad. That this is really true for linear programming is known since some time by the Klee-Minty example, an example for which the simplex method takes an exponential number of steps. What I asked myself for some time: Is there a Klee-Minty example for the homotopy method?

    Now the answer is there: Yes, there is!

    The denoising variant of basis pursuit is also known as LASSO regularization in the statistics literature and this explains the title of the paper which comes up with the example:

    Julien and Bin investigate the number of linear segments in the regularization path and first observe that this is upper bounded by {(3^p+1)/2} is {p} is the number of entries in {x} (i.e. the number of variables of the problem). Then they try to construct an instance that matches this upper bound. They succeed in a clever way: For a given instance {(A,b)} with a path with {k} linear segments they try to construct an instance which has one more variable such that the number of linear segments in increased by a factor. Their result goes like this:

    Theorem 7 Let {A\in{\mathbb R}^{n\times p}} have full rank and let {b\in{\mathbb R}^n} be in the range of {A}. Assume that the homotopy path has {k} linear segments and denote by {\lambda_1} the regularization parameter which corresponds to the smallest kink in the path. Now choose {b_{n+1}\neq 0} and {\alpha} such that

    \displaystyle   0<\alpha < \frac{\lambda_1}{2\|b\|_2^2 + b_{n+1}^2} \ \ \ \ \ (1)

    and define {\tilde b\in{\mathbb R}^{n+1}} and {\tilde A\in{\mathbb R}{(n+1)\times (p+1)}} by

    \displaystyle  \tilde b = \begin{bmatrix} b\\ b_{n+1} \end{bmatrix}, \quad \tilde A = \begin{bmatrix} A & 2\alpha b\\ 0 & \alpha b_{n+1} \end{bmatrix}.

    Then the homotopy path for the basis pursuit problem with matrix {\tilde A} and right hand side {\tilde b} has {3k-1} linear segments.

    With this theorem at hand, it is straightforward to recursively build a “Mairal-Yu”-example which matches the upper bound for the number of linear segments. The idea is to start with a {1\times 1} example and let it grow by one row and one column according to Theorem~7. We start with the simplest {1\times 1} example, namely {A = [1]} and {b=[1]}. To move to the next bigger example you can choose the next entry {b_{n+1}} and we always choose {1} for convenience. Moreover, you need the next {\alpha} and you need to know the smallest kink in the path. I calculated the paths and kinks with L1Packv2 by Ignace Loris because it is written in Mathematica and can use exact arithmetics with rational numbers (and you will see, that accuracy will be an issue even for small instances) and seemed bullet proof for me. Let’s see where this idea brings us:

    Example 1 (Mairal-Yu example)

    • Stage 1: We start with {n=p=1}, {b=[1]} and {A=[1]}. The homotopy path has one kink at {\lambda_1=1} (with corresponding solution {[0]}) and hence, two linear segments. Now let’s go to the next larger instance:
    • Stage 2: We can choose the entry {b_2} as we like and choose it equals to 1, i.e. our new {b} is

      \displaystyle  b = \begin{bmatrix} 1\\1 \end{bmatrix}.

      Now we have to choose {\alpha} according to (1), i.e

      \displaystyle  0 < \alpha < \frac{\lambda_1}{2\|b\|_2^2 + b_{n+1}^2} = \frac{1}{2+1} = \frac{1}{3}

      and we can choose, e.g., {\alpha = 1/4} which gives our new matrix

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

      The calculation of the new regularization path shows that it has exactly the announced number of 5 segments and the parameter of the smallest kink is {\lambda_1 = \frac{1}{13}}.

    • Stage 2: Again we choose {b_{n+1} = 1} giving

      \displaystyle  b = \begin{bmatrix} 1\\1\\1 \end{bmatrix}

      For the choice of {\alpha} we need that

      \displaystyle  0<\alpha < \frac{1}{13(4+1)} = \frac{1}{75}

      and we may choose

      \displaystyle  \alpha = \frac1{80}.

      which gives the next matrix

      \displaystyle  A = \begin{bmatrix} 1 & \frac12 & \tfrac{1}{40}\\ 0 & \frac14 & \tfrac{1}{40}\\ 0 & 0 & \tfrac{1}{80} \end{bmatrix}.

      We calculate the regularization path, observe that it has the predicted 14 segments and that the parameter of the smallest kink is {\lambda_1 = \frac{1}{193}}.

    • Stage 3: Again we choose {b_{n+1} = 1} giving

      \displaystyle  b = \begin{bmatrix} 1\\1\\1\\1 \end{bmatrix}

      For the choice of {\alpha} we need that

      \displaystyle  0<\alpha < \frac{1}{193(6+1)} = \frac{1}{1351}

      and we see that things are getting awkward here…

    Proceeding in this way we always increase the number of linear segments {k_n} for the {n\times n}-case from {k_n} to {k_{n+1} = 3k_n-1} in each step and one checks easily that this leads to {k_n = (3^n+1)/2} which is the worst case! If you are interested in the regularization path: I produced picture for the first three dimensions (well, I could not draw a 4d {\ell^1}-ball) and here they are:

    1d Mairal-Yu example


    2d Mairal-Yu example


    3d Mairal-Yu example

    It is not really easy to perceive the whole paths from the pictures because the magnitude of the entries vary strongly. I’ve drawn the path in red, each kink marked with a small circle. Moreover, I have drawn the according {\ell^1}-balls of the respective radii to provide more geometric information.

    The paper by Mairal and Yu has more results of the paths if one looks for approximate solutions of the linear system but I will not go into detail about them here.

    At least two questions come to mind:

    • The Mairal-Yu example is {n\times n}. What is the worst case complexity for the true rectangular case? In other words: What is the complexity for {p\times n} in terms of {p} and {n}?
    • The example and the construction leads to matrices that does not have normed columns and moreover, they are far from being equal in norm. But matrices with normed columns seem to be more “well behaved”. Does the worst case complexity lowers if the consider matrices with unit-norm columns? Probably one can construct a unit-norm example by proper choice of {b}

    Today I’ve been at the “Nordic Tomography Workshop” at the University of Helsinki. Actually, the Nordic European countries have an active and pretty large community in inverse problems and especially for the mathematics of tomography (have a look at the Finish Centre of Excellence in Inverse Problems Research to get an impression).

    The program of the workshop was very interesting, especially because of the mix of the people which range from theorists to practitioners and also incorporated some guys in the middle which have moved back and forth between theory and applications. However, the schedule was tight here and I won’t be able to comment on the talks. But basically, people keep working on applying TV regularization to tomography and the point was made that in the cases when the data is really incomplete then TV can somehow counteract and still lead to useful reconstructions.

    Happy Birthday regularize!

    Exactly one year ago I started this math blog as a kind of experiment. Let’s see what has happened since then:

    • I produced 46 posts (this one included) which I organized in
    • 9 categories (well, most posts are in “math”…) and I used
    • 55 different tags and there are
    • 74 comments (out of which 22 are pings).

    I blogged on papers I found and which I’d like to keep in some place (different from my filing cabinet or my harddisk), on topics which I’d got interested in, from conferences I attended, some posts were kind of off-topic and I started to post lecture notes.

    Here are some curiosities extracted from the site-stats tool:

    • The most used search term which brought a user here is “ivanov regularization” (63 times).
    • On place two and three are “sarrus rule” (61 times) and “rule of sarrus” (44 times). I hope I helped to reduce the well know {4\times 4} error which occurs in so many exams…
    • The entry which got the most views (besides the homepage itself) is “Dual spaces of continuous function” (although I think it is not very good…).

    Do I have some conclusion?

    • Blogging needs time and effort. That’s how it is.
    • However, blogging helps: It helps to read papers more thorough and to focus more on the questions “What does that mean for me?”, “How can I benefit from the new results?”. It also helps to get and keep in touch with other mathematicians. And it serves as some kind of archive for thoughts and ideas (although, I did not use this feature as much as I thought – probably because I remember things much better, once I blogged about them).
    • Hence, I continue to blog the way I used to and look forward to year number 2 of regularize. If you have some suggestions I would like to hear them.

    Follow

    Get every new post delivered to your Inbox.

    Join 49 other followers