Homotopieverfahren

Homotopie-Verfahren (auch als Homotopiemethode, Fortsetzungs– oder Einbettungsverfahren bezeichnet) sind Berechnungsmethoden in der numerischen Mathematik zur Bestimmung von Lösungen 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 $F(x)=0$ ist ein Punkt $x\in \mathbb {R} ^{n}$, der in der Regel $n$ nichtlinearen Bedingungen $F_{1}(x)=F_{2}(x)=\cdots =F_{n}(x)=0$ genügt, die zu einer vektorwertigen nichtlinearen Funktion (Abbildung) $F:\,\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ zusammengefasst werden. 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ösungskurve $x\colon [0,1]\to \mathbb {R} ^{n}$ mit

$F{\bigl (}x(t),t{\bigr )}=0$ für alle $t\in [0,1]$

Als möglicher Bereich des Parameters $t$ wurde dabei ohne Beschränkung der Allgemeinheit das Intervall $[0,1]$ 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-Verfahrens ist die Bestimmung einer Start-Näherung, die nahe genug an der Lösung ${\hat {x}}$ 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 $G(x)=0,\ x\in \mathbb {R} ^{n}$ das zu lösende nichtlineare Gleichungssystem mit Lösung ${\hat {x}}$. Dann kann man etwa durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x,t)=0,\quad F(x,t):=G(x)-(1-t)G(y),\quad t\in[0,1],}

mit einem festen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y\in\R^n} ein Hilfsproblem definieren, dessen Lösung man an der Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t=0} kennt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0\stackrel!=F(x,0)=G(x)-G(y)} ergibt offensichtlich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x(0)=y} . Andererseits ist die mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} gesuchte Lösung gerade die an der Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t=1} : Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0\stackrel!=F(x,1)=G(x)} , also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat x=x(1)} . Mit den im folgenden Abschnitt beschriebenen Verfahren kann nun die Kurve Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x(t)} von der bekannten Lösung in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t=0} zur gesuchten in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t=1} verfolgt werden.

Numerische Kurvenverfolgung

Das schon erwähnte Newton-Verfahren konvergiert sehr schnell (quadratisch), aber nur lokal bei genügend genauer Startnäherung. Dies wird bei der Kurvenverfolgung ausgenutzt, dass der Parameter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} in kleinen Schritten vergrößert wird, etwa von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0\le t_{m-1}} auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_m=t_{m-1}+h_m\,} . Dann ist die alte Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x(t_{m-1})} für eine kleine Schrittweite Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_m} eine gute Startnäherung für das Problem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x(t_m),t_m)=0} :

Trivialer Prädiktor

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \,\! x_0(t_m):=x(t_{m-1})} ,

Korrektoriteration

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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. }

Dabei ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \,\! D_x F} eine Kurzschreibweise für die quadratische Jacobi-Matrix der partiellen Ableitungen nach den Variablen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_1,\ldots,x_n} .

Sie bildet die Matrix des linearen Gleichungssystems, das in jedem Newtonschritt für die Korrekturen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_k} zu lösen ist. Eine Skizze dieses Vorgehens zeigt das erste Diagramm. Newtonschritt mit trivialem Prädiktor

Das zweite Diagramm verdeutlicht, dass man eine bessere Startnäherung erhält, wenn man vom Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x(t_{m-1})} aus in Richtung der Kurventangente geht. Die Tangente kann mit Hilfe der Kettenregel bestimmt werden. Denn da die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x(t),t)} identisch verschwindet, tut dies auch ihre Ableitung,

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_{m-1}} kann also die Tangentenrichtung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_{m-1}:=x'(t_{m-1})} aus einem linearen Gleichungssystem bestimmt werden. Dieses Verfahren lautet folgendermaßen:

Tangentialer Prädiktor

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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\} }

Korrektoriteration

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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. }

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

Newtonschritt mit Tangential-Prädiktor

Das Diagramm zeigt, dass der Startfehler, den die (grün gezeichneten) Newtonschritte überbrücken müssen, in der Regel wesentlich kleiner als beim trivialen Prädiktor ist, bei einer glatten Kurve in der Größenordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(h_m^2)} . Diese Verbesserung erfordert sogar nur einen unwesentlichen Zusatzaufwand, denn die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_x F\big(x(t_{m-1}),t_{m-1}\big)} entspricht der aus dem Newtonschritt. Man kann daher die letzte LR-Zerlegung aus dem Newton-Verfahren für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x(t_{m-1})} zur Berechnung der Tangente Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_{m-1}} wiederverwenden.

Bei der praktischen Durchführung versucht man, die Konvergenz des Newton-Verfahrens durch Schrittweitensteuerung sicherzustellen. Dazu wählt man die Schrittweite Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_m} so, dass die Kontraktion in den beiden ersten Newton-Schritten genügend klein ist, insbesondere kleiner eins. Wenn sich das gewählte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_m} nachträglich als zu groß herausstellt und das Newton-Verfahren schlecht oder gar nicht konvergiert, wiederholt man den Schritt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_{m-1}\to t_m=t_{m-1}+h_{m-1}} mit einem kleineren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_m} .

Verfolgung allgemeiner Kurven

Die beschriebenen Verfahren arbeiten nur dann problemlos, wenn die Funktion F genügend oft differenzierbar ist und die Jacobi-Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_x F} überall 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n+1)} -te Komponente der Unbekannten bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y=(x_1,\ldots,x_n,t)^T} und parametrisiert die Kurve nach ihrer Bogenlänge s. Dann sucht man alle Lösungen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y(s):\quad F(y(s))=0} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F:\,\R^{n+1}\to\R^n}

ist. Dieses Gleichungssystem ist unterbestimmt und hat unendlich viele Lösungen, die unter geeigneten Voraussetzungen eine glatte Lösungskurve Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y(s)} bilden.

Wie zuvor folgt aus der Kettenregel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F'(y(s))y'(s)\equiv0} , dass die Tangentenrichtung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y'(s)} das homogene Gleichungssystem mit der vollen Jacobimatrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F'=\partial F/\partial y\in\R^{n\times(n+1)}} erfüllt, also im 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 von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F'(y)} liegt. Diese Richtung wird automatisch durch die Moore-Penrose-Pseudoinverse von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F'} berechnet. Bei diesem Verfahren wird eine Approximation an die Bogenlänge s schrittweise vergrößert:

Allgemeiner Prädiktor-Korrektor-Schritt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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} }

Die Bezeichnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\ldots)^+} bezeichnet dabei die erwähnte Pseudoinverse.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pm z_{m-1}} festgelegt. Man wählt das Vorzeichen natürlich so, dass das Innenprodukt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_{m-1}^Tz_{m-2}>0} ist, um in einer Richtung vorzugehen.
• Die beiden Teilschritte können mit der QR-Zerlegung der transponierten Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \,(F'(y))^T=QR} effizient ausgeführt werden. Die Tangentenrichtung erhält man mit einem beliebigen Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u\not=0} durch Normierung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \,(E-QQ^T)u} , wenn der letzte Ausdruck ungleich null ist.
• Die Newton-Korrektur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \,v_k=y_{k+1}(s_m)-y_k(s_m)} berechnet man über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_k=-Q\tilde v_k} , wobei der Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde v_k\in\R^n} das quadratische Dreiecksystem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R^T\tilde v_k=F(y_k(s_m))} löst.

Literatur

• Werner 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 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.
• Schwetlick, H. und Kretschmar, H.: Numerische Verfahren für Naturwissenschaftler und Ingenieure. Fachbuchverlag Leipzig, 1991, ISBN 3-343-00580-0, S. 200. 
• 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.