Ist es möglich, nichtlineare PDEs ohne Newton-Raphson-Iteration zu lösen?

Ich versuche einige Ergebnisse zu verstehen und würde mich über einige allgemeine Kommentare zum Umgang mit nichtlinearen Problemen freuen.

Fisher-Gleichung (eine nichtlineare Reaktions-Diffusions-PDE),

u_{t} = d u_{x x} + β u (1 - u) = F (u)

$u_t = du_{xx} + \beta u (1 - u) = F(u)$

in diskretisierter Form,

u_{j}^{'} = L u + β u_{j} (1 - u_{j}) = F (u)

$u_j^{\prime} = \boldsymbol{L}\boldsymbol{u} + \beta u_j (1 - u_j) = F(\boldsymbol{u})$

Dabei ist der Differentialoperator und die Diskretisierungsschablone. $\boldsymbol{L}$ $\boldsymbol{u}=(u_{j-1}, u_j, u_{j+1})$

Methode

Ich möchte ein implizites Schema anwenden, da ich Stabilität und einen uneingeschränkten Zeitschritt benötige. Zu diesem Zweck verwende ich die thgr; -Methode (beachte, dass ein vollständig implizites Schema ergibt und das trapezförmige oder "Crank-Nicolson" -Schema ergibt). $\theta$ $\theta=1$ $\theta=0.5$

u_{j}^{'} = θ F (u^{n + 1}) + (1 - θ) F (u^{n})

$u_{j}^{\prime} = \theta F(\boldsymbol{u}^{n+1}) + (1-\theta) F(\boldsymbol{u}^{n})$

Bei nichtlinearen Problemen ist dies jedoch nicht möglich, da die Gleichung nicht linear geschrieben werden kann.

Um dieses Problem zu umgehen, habe ich zwei numerische Ansätze untersucht:

IMEX-Methode

$u_{j}^{'} = \underset{θ - method diffusion term}{\underset{⏟}{θ L u^{n + 1} + (1 - θ) L u^{n}}} + \underset{Vollständig expliziter Reaktionsbegriff}{\underset{⏟}{β u_{j}^{n} (1 - u_{j}^{n})}}$ $u_j^{\prime} = \underbrace{\theta\boldsymbol{L}\boldsymbol{u^{n+1}} + (1-\theta)\boldsymbol{L}\boldsymbol{u^{n}}}_{\theta-\text{method diffusion term}} + \underbrace{\beta u_j^{n} (1 - u_j^{n})}_{\text{Fully explicit reaction term}}$
Der naheliegendste Weg ist, den nichtlinearen Teil des Reaktionsbegriffs zu ignorieren und den Reaktionsbegriff nur mit dem bestmöglichen Wert zu aktualisieren, dh dem aus dem vorherigen Zeitschritt. Dies führt zur IMEX-Methode.
Newton-Löser

ν^{k + 1} = ν^{k} - (ich - θ τ {EIN}^{n})^{- 1} (ν^{k} - u_{n} - (1 - θ) τ F (w^{n}) - θ τ F (w^{n + 1}))

$\nu^{k+1} = \nu^{k} - (I - \theta\tau A^{n})^{-1} \left( \nu^{k} - u_{n} - (1-\theta) \tau F(w^n) - \theta\tau F(w^{n+1}) \right)$

Die vollständige Methodengleichung kann unter Verwendung einer Newton-Raphson-Iteration gelöst werden, um die zukünftige Lösungsvariable zu finden. Dabei ist der Iterationsindex ( ) und die Jacobi-Matrix von . Hier verwende die Symbole I für Iterationsvariablen , so dass sie aus der Lösung der Gleichung bei einer Echtzeit Punkt auszeichnen . Dies ist tatsächlich ein modifizierter Newton-Löser, da der Jacobian nicht bei jeder Iteration aktualisiert wird. $\theta$ $k$ $k\geq0$ $A^{n}$ $F(w^n)$ $\nu^{k}$ $u^n$

Ergebnisse

Fischers Gleichungsvergleich numerischer Methoden.

Die obigen Ergebnisse wurden für einen relativ großen Zeitschritt berechnet und zeigen den Unterschied zwischen dem Zeitschritt-Ansatz und einem vollständigen Newton-Iterationslöser.

Dinge, die ich nicht verstehe:

Ich bin überrascht, dass die Zeitschrittmethode "OK" ist, aber mit der Zeit hinter der analytischen Lösung zurückbleibt. ( Hinweis: Wenn ich einen kleineren Zeitschritt gewählt hätte, würde der Zeitschritt-Ansatz zu Ergebnissen führen, die für das analytische Modell nicht relevant sind.) Warum liefert der Zeitschrittansatz vernünftige Ergebnisse für eine nichtlineare Gleichung?
Das Newton-Modell schneidet viel besser ab, beginnt jedoch mit der Zeit, das analytische Modell anzuführen. Warum nimmt die Genauigkeit des Newton-Ansatzes mit der Zeit ab? Kann die Genauigkeit verbessert werden?
Warum gibt es ein allgemeines Merkmal, dass nach vielen Iterationen das numerische Modell und das analytische Modell auseinander zu gehen beginnen? Liegt das nur daran, dass der Zeitschritt zu groß ist, oder geschieht dies immer?

numerical-analysis nonlinear-equations implicit-methods newton-method explicit-methods Boyfarrell
quelle

Ich empfehle, die grundlegende Fehleranalyse von ODE-Lösern zu lesen, zum Beispiel in Hairer / Nørsett / Wanner, sowie einen Teil der Stabilitätsanalyse. Die meisten Ihrer Fragen werden dann beantwortet.

Guido Kanschat

@boyfarrell, um Verwirrung bei anderen Lesern zu vermeiden, sollten Sie die Terminologie genau an die Stelle setzen, an der Sie Ihre Methode erklären: 1. IMEX - explizit in der Nichtlinearität und implizit im linearen Teil. 2. Dies ist der Standard -Schema, das wird in der Regel der Newton-Verfahren benötigt für das Update zu lösen

θ

$\theta$

Jan

Hallo Jan, ich glaube ich habe alles. Danke nochmal für deine Hilfe.

Boyfarrell

Antworten:

Ich gehe davon aus, dass Sie eine Raumdiskretisierung durchgeführt haben, um die (vektorielle) ODE über ein numerisches Schema , die die Approximation vorrückt am aktuellen Zeitinstanz auf den nächsten Wert , bei .

{\dot{u}}_{h} (t) = F_{h} (t, u_{h} (t)), am [0, T], u_{h} (0) = α .

$\dot u_h(t) = F_h(t,u_h(t)), \text{ on [0,T] }, u_h(0) = \alpha.$

Φ

$\Phi$

u_{h}^{n}

$u_h^n$

t = t^{n}

$t=t^n$

u_{h}^{n + 1}

$u_h^{n+1}$

t = t^{n + 1} := t^{n} + τ

$t=t^{n+1}:=t^n+\tau$

Dann beziehen sich Ihre Fragen auf explizite Eigenschaften , wobei das Update als schreibt

u_{h}^{n + 1} = u_{h}^{n} + Φ_{e} (t^{n}, τ, u_{h}^{n}),

$u_h^{n+1} = u_h^n + \Phi_e(t^n,\tau,u_h^n),\quad \quad \quad$

implizit , geschrieben wie

u_{h}^{n + 1} = u_{h}^{n} + Φ_{ich} (t^{n}, τ, u_{h}^{n + 1}, u_{h}^{n}), (*)

$u_h^{n+1} = u_h^n + \Phi_i(t^n,\tau,u_h^{n+1},u_h^n), \quad \quad \quad (*)$

oder eine Kombination aus beiden (' IMEX ', siehe @Jed Browns Antwort) einstufigen Zeitschrittschemata.

In diesem Aufbau ist die Newton- Methode einfach ein Ansatz, um die möglicherweise nichtlinearen in Systemen zu lösen, die sich aus . $u_h^{n+1}$ $(*)$

Meine Antworten basieren auf Ergebnissen der numerischen Analyse von Einzelschrittmethoden.

Wenn Sie konvergente Schemata in Bezug auf die Konvergenzreihenfolge verwenden, bietet die Verwendung impliziter Schemata keinen generellen Vorteil (siehe 2.). Für steife Systeme, z. B. Ihr Laplace-System, gibt es jedoch implizite Schemata, die ohne zeitliche Einschränkungen stabil sind. Theoretisch erhalten Sie für das explizite Schema jedoch bessere Ergebnisse mit kleineren , solange Ihre Gleichung selbst stabil ist (z. B. unter Bezugnahme auf Picard-Lindelof-Theorem, wenn im zweiten Argument ist) und Ihre Zeit -Schritt ist nicht zu klein. $F_h$
Sie können Beispiele finden, bei denen explizite Schemata eine bessere Leistung erbringen. (Theoretisch können Sie die Zeit in Ihrem Beispiel umkehren, vom Endwert ausgehen und implizite und explizite Änderungen feststellen.) Wenn Sie den Newton-Fehler ausreichend klein machen, können Sie die Genauigkeit noch verbessern, indem Sie den Zeitschritt verringern oder die Zeit verwenden -Schemata höherer Ordnung.
Die Konstante in der Fehlerschätzung für den globalen Fehler wächst exponentiell mit der Länge des Zeitintervalls. Siehe z. B. hier für das explizite Euler-Schema. Dies gilt für jede Einzelschrittmethode. Da die Schätzung vom Typ , , verschiebt ein kleinerer Zeitschritt nur diesen Effekt. $C$ $err \approx C \tau^p$ $p>0$ $\tau$

Noch einige Bemerkungen und die endgültige Antwort:

IMEX-Schemata können verwendet werden, um nur den linearen Teil implizit zu behandeln, wodurch die nichtlinearen Lösungen vermieden werden. Siehe Jed Browns Antwort.
Crank-Nicolson ist eine einstufige Methode. Die "Multi" in Multi-Step-Methoden bezieht sich auf die Verwendung einer Reihe von vorhergehenden Zeitschritten, um das aktuelle Update zu definieren. ZB wie Dies unterscheidet sich stark von Einzelschritt- und auch Teilschritt- oder IMEX-Methoden, bei denen die Aktualisierung so definiert ist, dass sie sich nicht auf vorherige Werte bezieht. $u_{h}^{n + 1} = Φ_{m} (t^{n}, τ, u_{h}^{n + 1}, u_{h}^{n}, u_{h}^{n - 1}) .$ $u_h^{n+1} = \Phi_m(t^n,\tau,u_h^{n+1},u_h^n,u_h^{n-1}).$

Meine Antwort lautet also: Ja , Sie können nichtlineare PDEs ohne Newtons Methode lösen. Sie können explizite Schemata, IMEX-Schemata oder sogenannte linear implizite Methoden (z. B. die Rosenbrock-Methoden) verwenden. Sie können auch andere Ansätze anwenden, um die Systeme aus wie Festkomma-Iterationen oder in bestimmten Fällen algebraischen Solvern zu lösen . $(*)$

Jan
quelle

Ja, ich habe die Standard-Zentraldifferenzschablone auf den Diffusionsbegriff angewendet. Ich kann kein explizites Schema verwenden (für das eigentliche Problem, das ich lösen möchte), da der stabile Zeitschritt unrealistisch klein ist. Aus diesem Grund untersuche ich IMEX oder implizite Optionen. In Bezug auf Ihren dritten Punkt muss ich ein mehrstufiges Verfahren anwenden, um die Fehlerakkumulation zu vermeiden. Ist das oben verwendete Crank-Nicolson-Schema (mit dem Newton-Solver) als Mehrschrittmethode klassifiziert (es hat zwei Zeitpunkte)? Ich war überrascht, dass der Fehler mit der Zeit zunahm, wenn die Newton-Lösungsmethode verwendet wurde.

Boyfarrell

Crank-Nicolson ist ein einstufiges Verfahren, wie sie schreibt , als

u_{h}^{n + 1} = u_{h}^{n} + Φ (t^{n}, τ^{n}, u_{h}^{n}, u_{h}^{n + 1})

$u_h^{n+1}=u_h^n + \Phi(t^n,\tau^n,u_h^n,u_h^{n+1})$

OK, danke für die Erklärung der CN-Methode. Ja, es ist interessant, warum die Mehrschrittmethoden eine geringere Fehlerakkumulation aufweisen. Der Grund, warum der Newton-Löser Fehler aufweist, ist, dass es sich um eine Einzelschrittmethode handelt, die ich jetzt verstehe. Übrigens, ich weiß, dass Sie Python mögen. Ich habe das alles mit scipy, numpy und matplotlib gemacht, gist.github.com/danieljfarrell/6353776

boyfarrell

Ich habe den Link zum Artikel von Trefethen et. al. zur hochrangigen IMEX-Integration aus meiner Antwort, da es bessere Referenzen gibt, um mehr über IMEX-Schemata zu erfahren.

Jan

Kurze Antwort

Wenn Sie nur eine Genauigkeit zweiter Ordnung und keine eingebettete Fehlerschätzung wünschen, sind Sie wahrscheinlich mit der Strang-Aufteilung zufrieden: halber Reaktionsschritt, voller Diffusionsschritt, halber Reaktionsschritt.

Lange Antwort

Die Reaktionsdiffusion, auch bei linearer Reaktion, ist berühmt für den Nachweis von Teilungsfehlern. In der Tat kann es viel schlimmer sein, einschließlich "Konvergieren" zu falschen stationären Zuständen, Verwechseln von stationären Zuständen mit Grenzzyklen, Verwechseln von stabilen und instabilen Konfigurationen und mehr. Siehe hierzu Ropp, Shadid und Ober (2004) sowie Knoll, Chacon, Margolin und Mousseau (2003). Zur Analyse des Mathematikers hinsichtlich der Ordnungsbedingungen siehe Hairer und Wanners Buch über steife ODE (Rosenbrock-W-Methoden sind eine linear implizite IMEX-Methode), Kennedy und Carpenter (2003) für das nichtlinear implizite IMEX-Additiv Runge-Kutta. und Emil Constantinescus Seite für neuere IMEX-Methoden.

Im Allgemeinen weisen IMEX-Methoden mehr Ordnungsbedingungen auf als die zugrunde liegenden impliziten und expliziten Methoden. IMEX-Methodenpaare können mit gewünschter linearer und nichtlinearer Stabilität entworfen werden und erfüllen alle Ordnungsbedingungen bis zur Entwurfsreihenfolge der Methode. Wenn Sie alle Bestellbedingungen erfüllen, bleibt der asymptotische Teilungsfehler in derselben Größenordnung wie der Fehler in jedem Schema separat. Es sagt nichts über das präasymptotische Regime aus (große Zeitschritte / geringe Genauigkeitsanforderungen), ist jedoch selten strenger als die Auflösung jedes Teils für sich. In jedem Fall ist der Aufteilungsfehler für den eingebetteten Fehlerschätzer sichtbar (bei Verwendung der adaptiven Fehlerkontrolle).

PETSc verfügt über viele IMEX-Methoden der Rosenbrock-W- und der additiven Runge-Kutta- Familie und wird in unserer nächsten Version über Extrapolation und linearen IMEX mit mehreren Schritten verfügen.

Haftungsausschluss: Ich habe einen Großteil der Unterstützung für die PETSc-Zeitintegration geschrieben und arbeite mit Emil (oben verlinkt) zusammen.

Jed Brown
quelle

Ich nähere mich dem sicherlich aus physikalischer Sicht, so dass alle technischen Details einige Zeit in Anspruch nehmen, weil ich mit vielen Begriffen nicht vertraut bin. Ich bin eigentlich ein Experimentator! Würden Sie uns die Bestellbedingungen etwas näher erläutern? IMEX sind diese mehrstufigen Methoden von Jan erwähnt?

Boyfarrell

Ordnungsbedingungen sind Beziehungen zwischen Koeffizienten von ODE-Methoden (z. B. Einträge in einem Metzgertableau für Runge-Kutta-Methoden), die erfüllt sein müssen, um eine Ordnungsgenauigkeit zu haben. Die Bestellbedingungen werden in jedem Buch oder in jedem Artikel erläutert, in dem ODE-Integrationsmethoden entwickelt werden. Grundsätzlich bedeutet dies jedoch, dass Ableitungen und übereinstimmende Begriffe in einer Taylor-Erweiterung wiederholt angewendet werden. Die Anzahl der Ordnungsbedingungen nimmt bei Methoden höherer Ordnung schnell zu, weshalb es schwierig wird, Methoden höherer Ordnung zu entwerfen. Barrieren werden dadurch errichtet, dass gezeigt wird, dass die Auftragsbedingungen nicht miteinander vereinbar sind.

Jed Brown