Benutzer:Eigenwert

Bei nichtlinearen Gleichungssytemen sucht man einen Punkt $x\in \mathbb {R} ^{n}$, der in der Regel $n$ nichtlinearen Bedingungen $F(x)=0$ genügt, wobei $F:\,\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ eine nichtlineare Funktion (Abbildung) darstellt. Bei vielen Anwendungen enthält die Funktion $F$ Problemparameter, etwa $t\in \mathbb {R}$ welche verschiedene Werte annehmen können. Ein bekanntes Beispiel ist das reale Pendel, dessen Schwingungsdauer nichtlinear von der reduzierten Pendellänge abhängt. In diesem Fall lautet das Gleichungssystem korrekter $F(x,t)=0$ und auch die Lösung $x$ hängt vom Parameter $t$ ab und bildet daher eine Lösungs-Kurve

$x(t):\quad F{\big (}x(t),t)=0,\quad t\in [0,1].$

Als möglicher Bereich des Parameters $t$ wurde dabei das Intervall $[0,1]$ gewählt. Die Existenz einer glatten Kurve folgt unter geeigneten Voraussetzungen aus dem Satz über implizite Funktionen. Homotopie-Verfahren (auch Fortsetzungsverfahren genannt) sind numerische Verfahren, die solche implizit definierten Kurven verfolgen.

Homotopie für nichtlineare Gleichungssysteme

Eine prinzipielle Schwierigkeit beim Einsatz des Newton-Verfahrens ist die Bestimmung einer Start-Näherung, die nahe genug an der Lösung ${\hat {x}}$ liegen muß, um Konvergenz zu erreichen. Dieses Problem kann man durch Einbettung in eine Homotopie und die Verfolgung der Lösungskurve umgehen. Es sei jetzt $G(x)=0,\ x\in \mathbb {R} ^{n}$ das zu lösende nichtlineare Gleichungssystem mit Lösung ${\hat {x}}$. Dann kann man etwa durch

$F(x,t)=0,\quad F(x,t):=G(x)-(1-t)G(y),\quad t\in [0,1],$

mit einem festen $y\in \mathbb {R} ^{n}$ ein Hilfsproblem definieren, dessen Lösung man an der Stelle $t=0$ kennt: $0{\stackrel {!}{=}}F(x,0)=G(x)-G(y)$ ergibt offensichtlich $x(0)=y$. Andererseits ist die mit $G$ gesuchte Lösung gerade die an der Stelle $t=1$: $0{\stackrel {!}{=}}F(x,1)=G(x)$, also ${\hat {x}}=x(1)$. Mit den im folgenden Abschnitt beschriebenen Verfahren kann nun die Kurve $x(t)$ von der bekannten Lösung in $t=0$ zur gesuchten in $t=1$ verfolgt werden.

Numerische Kurvenverfolgung

Das schon erwähnte Newton-Verfahren konvergiert sehr schnell (quadratisch), aber nur bei genügend genauer Startnäherung. Dies nutzt man bei der Kurvenverfolgung so aus, dass man den Parameter $t$ in kleinen Schritten vergrößert, etwa von $0\leq t_{m-1}$ auf $t_{m}=t_{m-1}+h_{m}$. Dann ist die alte Lösung $x(t_{m-1})$ für kleines $h_{m}$ eine gute Startnäherung für das Problem $F(x(t_{m}),t_{m})=0$:

Trivialer Prädiktor

$\,\!x_{0}(t_{m}):=x(t_{m-1})$

$\left.{\begin{array}{l}D_{x}F(x_{k}(t_{m}),t_{m})s_{k}=-F(x_{k}(t_{m}),t_{m}),\\x_{k+1}(t_{m}):=x_{k}(t_{m})+s_{k},\end{array}}\right\}k=0,1,\ldots .$

Dabei ist $\,\!D_{x}F$ eine Kurzschreibweise für die quadratische Jacobi-Matrix der partiellen Ableitungen nach den Variablen $x_{1},\ldots ,x_{n}$.

Datei:Trivialpredict.png

Newtonschritt mit trivialem Prädiktor

Sie bildet die Matrix des linearen Gleichungssystems, das in jedem Newtonschritt für die Korrekturen $s_{k}$ zu lösen ist. Eine Skizze des Vorgehens zeigt die Graphik.

In der Graphik sieht man, dass man eine bessere Startnäherung erhält, wenn man vom Punkt $x(t_{m-1})$ aus in Richtung der Kurventangente geht. Die Tangente kann mit Hilfe der Kettenregel bestimmt werden. Denn da die Funktion $F(x(t),t)$ identisch verschwindet, tut dies auch ihre Ableitung,

$0\equiv {\frac {d}{dt}}F(x(t),t)=D_{x}F(x(t),t)x'(t)+D_{t}F(x(t),t).$

Im Punkt $t_{m-1}$ kann also die Tangentenrichtung $z_{m-1}:=x'(t_{m-1})$ aus einem linearen Gleichungssytem bestimmt werden. Dieses Verfahren lautet folgendermaßen.

Tangentialer Prädiktor

$\left.{\begin{array}{l}D_{x}F{\big (}x(t_{m-1}),t_{m-1}{\big )}z_{m-1}=-D_{t}F{\big (}x(t_{m-1}),t_{m-1}{\big )},\\x_{0}(t_{m}):=x(t_{m-1})+h_{m}z_{m-1},\end{array}}\right\}$

$\left.{\begin{array}{l}D_{x}F(x_{k}(t_{m}),t_{m})s_{k}=-F(x_{k}(t_{m}),t_{m}),\\x_{k+1}(t_{m}):=x_{k}(t_{m})+s_{k},\end{array}}\right\}k=0,1,\ldots .$

Datei:Tangentialpredict.png

Newtonschritt mit Tangential-Prädiktor

Gegenüber dem einfachen Verfahren wurde nur die erste Gleichung ersetzt. Die Skizze zeigt, dass der Startfehler den die (grün gezeichneten) Newtonschritte überbrücken müssen, i.d.R. wesentlich kleiner als beim trivialen Prädiktor ist, bei einer glatten Kurve in der Größenordnung $O(h^{2})$.

Literatur

• P. Deuflhard, A. Hohmann: Numerische Mathematik, de Gruyter, 1991, ISBN 3-11-012917-5
• E.L. Allgower, K. Georg: Introduction to numerical continuation methods. SIAM Philadelphia, 2003, ISBN 0-89871-544-X