imported>Aka: Tippfehler entfernt

2025-05-19T19:29:03Z

Neue Seite

'''Homotopie-Verfahren''' (auch als '''Homotopiemethode''', '''Fortsetzungs-''' oder '''Einbettungsverfahren''' bezeichnet) sind Berechnungsmethoden in der [[Numerische Mathematik|numerischen Mathematik]] zur Bestimmung von Lösungen [[Gleichungssystem#Einteilung nach (Nicht)Linearität|nichtlinearer Gleichungssysteme]]. Ziel ist es dabei, den [[Konvergenzbereich]] eines Verfahrens zur Lösung nichtlinearer Gleichungssysteme (wie zum Beispiel des Newtonverfahrens) zu vergrößern.

== Vorbetrachtung ==
Eine Lösung eines nichtlinearen Gleichungssystems <math>F(x)=0</math> ist ein Punkt <math>x\in\R^n</math>, der in der Regel <math>n</math> nichtlinearen Bedingungen <math>F_1(x)=F_2(x)=\cdots=F_n(x)=0</math> genügt, die zu einer vektorwertigen nichtlinearen [[Funktion (Mathematik)|Funktion]] (Abbildung) <math>F:\,\R^n\to\R^n</math> zusammengefasst werden. Bei vielen Anwendungen enthält die Funktion <math>F</math> Problemparameter, etwa <math>t\in\R</math>, welche verschiedene Werte annehmen können. Ein bekanntes Beispiel ist das reale [[Mathematisches Pendel|Pendel]], dessen Schwingungsdauer nichtlinear von der reduzierten Pendellänge abhängt. In diesem Fall lautet das [[Gleichungssystem]] korrekter <math>F(x,t)=0</math>, und auch die Lösung <math>x</math> hängt vom Parameter <math>t</math> ab und bildet daher eine Lösungs[[Kurve (Mathematik)|kurve]] <math>x \colon [0,1] \to \R^n</math> mit
:<math> F\bigl(x(t),t\bigr)=0</math> für alle <math>t \in [0,1]</math>
Als möglicher Bereich des Parameters <math>t</math> wurde dabei [[ohne Beschränkung der Allgemeinheit]] das Intervall <math>[0,1]</math> gewählt.
Die Existenz einer glatten Kurve folgt unter geeigneten Voraussetzungen aus dem [[Satz über implizite Funktionen]].
''Homotopie-Verfahren'' sind numerische Verfahren, die solche implizit definierten Kurven verfolgen.

== Homotopie für nichtlineare Gleichungssysteme ==
Eine prinzipielle Schwierigkeit beim Einsatz des [[Newton-Verfahren]]s ist die Bestimmung einer Start-Näherung, die nahe genug an der Lösung <math>\hat x</math> liegen muss, um Konvergenz zu erreichen. Dieses Problem kann man durch Einbettung in eine [[Homotopie]] und die Verfolgung der Lösungskurve umgehen. Es sei jetzt <math>G(x)=0,\ x\in\R^n</math> das zu lösende nichtlineare Gleichungssystem mit Lösung <math>\hat x</math>. Dann kann man etwa durch
:<math>F(x,t)=0,\quad F(x,t):=G(x)-(1-t)G(y),\quad t\in[0,1],</math>
mit einem festen <math>y\in\R^n</math> ein Hilfsproblem definieren, dessen Lösung man an der Stelle <math>t=0</math> kennt: <math>0\stackrel!=F(x,0)=G(x)-G(y)</math> ergibt offensichtlich <math>x(0)=y</math>. Andererseits ist die mit <math>G</math> gesuchte Lösung gerade die an der Stelle <math>t=1</math>: <math>0\stackrel!=F(x,1)=G(x)</math>, also <math>\hat x=x(1)</math>. Mit den im folgenden Abschnitt beschriebenen Verfahren kann nun die Kurve <math>x(t)</math> von der bekannten Lösung in <math>t=0</math> zur gesuchten in <math>t=1</math> verfolgt werden.

== Numerische Kurvenverfolgung ==
Das schon erwähnte [[Newton-Verfahren#Lokale quadratische Konvergenz|Newton-Verfahren]] konvergiert sehr schnell (quadratisch), aber nur lokal bei genügend genauer Startnäherung. Dies wird bei der Kurvenverfolgung ausgenutzt, dass der Parameter <math>t</math> in kleinen Schritten vergrößert wird, etwa von <math>0\le t_{m-1}</math> auf <math>t_m=t_{m-1}+h_m\,</math>. Dann ist die alte Lösung <math>x(t_{m-1})</math> für eine kleine Schrittweite <math>h_m</math> eine gute Startnäherung für das Problem <math>F(x(t_m),t_m)=0</math>:
:''Trivialer Prädiktor''
:::<math>\,\! x_0(t_m):=x(t_{m-1})</math>,
: ''Korrektoriteration''
:::<math>
\left.\begin{array}{rl}
D_x F(x_k(t_m),t_m) v_k=&-F(x_k(t_m),t_m),\\[0.3em]
x_{k+1}(t_m)=&x_k(t_m)+v_k,
\end{array}\right\} k=0,1,\ldots.
</math>
Dabei ist <math>\,\! D_x F</math> eine Kurzschreibweise für die quadratische [[Jacobi-Matrix]] der [[Partielle Ableitung|partiellen Ableitungen]] nach den Variablen <math>x_1,\ldots,x_n</math>.

Sie bildet die Matrix des [[Lineares Gleichungssystem|linearen Gleichungssystems]], das in jedem Newtonschritt für die Korrekturen <math>s_k</math> zu lösen ist. Eine Skizze dieses Vorgehens zeigt das erste Diagramm.
[[Datei:Trivialpredict.png|Newtonschritt mit trivialem Prädiktor]]

Das zweite Diagramm verdeutlicht, dass man eine bessere Startnäherung erhält, wenn man vom Punkt <math>x(t_{m-1})</math> aus in Richtung der Kurventangente geht. Die [[Tangente]] kann mit Hilfe der [[Kettenregel]] bestimmt werden. Denn da die Funktion <math>F(x(t),t)</math> identisch verschwindet, tut dies auch ihre Ableitung,
:<math> 0\equiv \frac{d}{dt}F(x(t),t)=D_x F(x(t),t)x'(t)+D_t F(x(t),t).</math>
Im Punkt <math>t_{m-1}</math> kann also die [[Tangente]]nrichtung <math>z_{m-1}:=x'(t_{m-1})</math> aus einem linearen Gleichungssystem bestimmt werden.
Dieses Verfahren lautet folgendermaßen:
: ''Tangentialer Prädiktor''
:::<math>
\left.\begin{array}{rl}
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),\\[0.3em]
x_0(t_m) =& x(t_{m-1})+h_m z_{m-1},
\end{array}\right\}
</math>
: ''Korrektoriteration''
:::<math>
\left.\begin{array}{rl}
D_x F(x_k(t_m),t_m) v_k =& -F(x_k(t_m),t_m),\\
x_{k+1}(t_m) =& x_k(t_m)+v_k,
\end{array}\right\} k=0,1,\ldots.
</math>

Gegenüber dem einfachen Verfahren wurde nur die erste Gleichung ersetzt.

[[Datei:Tangentialpredict.png|Newtonschritt mit Tangential-Prädiktor]]

Das Diagramm zeigt, dass der Startfehler, den die (grün gezeichneten) [[Newton-Verfahren|Newtonschritte]] überbrücken müssen, in der Regel wesentlich kleiner als beim trivialen Prädiktor ist, bei einer glatten Kurve in der Größenordnung <math>O(h_m^2)</math>.
Diese Verbesserung erfordert sogar nur einen unwesentlichen Zusatzaufwand, denn die Matrix <math>D_x F\big(x(t_{m-1}),t_{m-1}\big)</math> entspricht der aus dem Newtonschritt. Man kann daher die letzte [[LR-Zerlegung]] aus dem [[Newton-Verfahren]] für <math>x(t_{m-1})</math> zur Berechnung der Tangente <math>z_{m-1}</math> wiederverwenden.

Bei der praktischen Durchführung versucht man, die Konvergenz des [[Newton-Verfahren]]s durch [[Schrittweitensteuerung]] sicherzustellen. Dazu wählt man die Schrittweite <math>h_m</math> so, dass die [[Kontraktion (Mathematik)|Kontraktion]] in den beiden ersten Newton-Schritten genügend klein ist, insbesondere kleiner eins. Wenn sich das gewählte <math>h_m</math> nachträglich als zu groß herausstellt und das Newton-Verfahren schlecht oder gar nicht konvergiert, wiederholt man den Schritt <math>t_{m-1}\to t_m=t_{m-1}+h_{m-1}</math> mit einem kleineren <math>h_m</math>.

== Verfolgung allgemeiner Kurven ==
Die beschriebenen Verfahren arbeiten nur dann problemlos, wenn die Funktion ''F'' genügend oft [[Differentiation|differenzierbar]] ist und die [[Jacobi-Matrix]] <math>D_x F</math> überall [[Reguläre Matrix|regulär]] ist. Gilt letzteres nicht mehr, können Umkehrpunkte und Verzweigungspunkte der Kurve auftreten.

Nach Umkehrpunkten verläuft die Kurve „rückwärts“, in Verzweigungspunkten spaltet sie sich auf. In beiden Fällen ist daher eine (eindeutige) Parametrisierung nach der Variable ''t'' nicht mehr möglich. Daher betrachtet man ''t'' einfach als <math>(n+1)</math>-te Komponente der Unbekannten bei <math>y=(x_1,\ldots,x_n,t)^T</math> und parametrisiert die Kurve nach ihrer Bogenlänge ''s''. Dann sucht man alle Lösungen
:::<math> y(s):\quad F(y(s))=0</math>, wobei <math>F:\,\R^{n+1}\to\R^n</math>
ist. Dieses [[Gleichungssystem]] ist unterbestimmt und hat unendlich viele Lösungen, die unter geeigneten Voraussetzungen eine glatte Lösungskurve <math>y(s)</math> bilden.

Wie zuvor folgt aus der Kettenregel <math>F'(y(s))y'(s)\equiv0</math>, dass die [[Tangente]]nrichtung <math>y'(s)</math> das homogene Gleichungssystem mit der vollen [[Jacobimatrix]] <math>F'=\partial F/\partial y\in\R^{n\times(n+1)}</math> erfüllt, also im [[Kern (Algebra)|Kern]] dieser Matrix liegt. Damit kann also wieder ein Prädiktor berechnet werden. Auch das [[Newton-Verfahren]] ist durchführbar, indem man eine Richtung wählt, die orthogonal zur Kurventangente, also zum [[Kern (Algebra)|Kern]] von <math>F'(y)</math> liegt. Diese Richtung wird automatisch durch die Moore-Penrose-[[Pseudoinverse]] von <math>F'</math> berechnet. Bei diesem Verfahren wird eine [[Approximation]] an die Bogenlänge ''s'' schrittweise vergrößert:
:''Allgemeiner Prädiktor-Korrektor-Schritt''
:::<math>
\begin{array}{rl}
F'\big(y(s_{m-1})\big)z_{m-1}&=0,\ \|z_{m-1}\|_2=1,\\
s_m&:=s_{m-1}+h_m,\\
y_0(s_m)&:=y(s_{m-1})+h_mz_{m-1};\\
y_{k+1}(s_m)&:=y_k(s_m)-\Big(F'(y_k(s_m))\Big)^+\,F(y_k(s_m)),\ k=0,1,\ldots.
\end{array}
</math>

Die Bezeichnung <math>(\ldots)^+</math> bezeichnet dabei die erwähnte [[Pseudoinverse]].

[[Datei:Tangentialhomotop.png|Tangential-Prädiktor und Newtonschritt bei Kurve mit Umkehrpunkten]]

Das dritte Diagramm skizziert dieses Vorgehen, der (grün gezeichnete) Newtonschritt verläuft ungefähr orthogonal zur Kurve und hat daher auch im Umkehrpunkt (vertikaler Verlauf der Kurve) keine Schwierigkeiten.

: ''Bemerkungen'':
:* Durch die erste Bedingung ist noch nicht die Richtung der Tangente <math>\pm z_{m-1}</math> festgelegt. Man wählt das [[Vorzeichen (Zahl)|Vorzeichen]] natürlich so, dass das [[Innenprodukt]] <math>z_{m-1}^Tz_{m-2}>0</math> ist, um in einer Richtung vorzugehen.
:* Die beiden Teilschritte können mit der [[QR-Zerlegung]] der [[Transponierte Matrix|transponierten Matrix]] <math>\,(F'(y))^T=QR</math> effizient ausgeführt werden. Die Tangentenrichtung erhält man mit einem beliebigen Vektor <math>u\not=0</math> durch Normierung von <math>\,(E-QQ^T)u</math>, wenn der letzte Ausdruck ungleich null ist.
:* Die Newton-Korrektur <math>\,v_k=y_{k+1}(s_m)-y_k(s_m)</math> berechnet man über <math>v_k=-Q\tilde v_k</math>, wobei der Vektor <math>\tilde v_k\in\R^n</math> das quadratische Dreiecksystem <math>R^T\tilde v_k=F(y_k(s_m))</math> löst.

== Literatur ==
* [[Werner C. Rheinboldt]]: ''Numerical Analysis of Parametrized Nonlinear Equations.'' John Wiley and Sons, New York 1986, ISBN 0-471-88814-1. (siehe auch das [[FORTRAN]]-Modul PITCON als Teil der netlib.org-Bibliothek [https://netlib.org/contin/ ''contin''])
* 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.
* {{Literatur
|Autor=Schwetlick, H. und Kretschmar, H.
|Titel=Numerische Verfahren für Naturwissenschaftler und Ingenieure
|Verlag=Fachbuchverlag Leipzig
|Jahr=1991
|Seiten=200
|ISBN=3-343-00580-0
|Kommentar=
}}
* [[Martin Hermann (Mathematiker)|M. Hermann]]: ''Numerische Mathematik, Band 1: Algebraische Probleme''. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020. ISBN 978-3-11-065665-7.

[[Kategorie:Numerische Mathematik]]

Homotopieverfahren - Versionsgeschichte

imported>Aka: Tippfehler entfernt