Est-il possible de résoudre des PDE non linéaires sans utiliser l'itération de Newton-Raphson?

J'essaie de comprendre certains résultats et j'apprécierais quelques commentaires généraux sur la résolution des problèmes non linéaires.

L'équation de Fisher (PDE à réaction-diffusion non linéaire),

u_{t} = ré u_{X X} + β u (1 - u) = F (u)

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

sous forme discrétisée,

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})$

où $\boldsymbol{L}$ est l'opérateur différentiel et $\boldsymbol{u}=(u_{j-1}, u_j, u_{j+1})$ est le pochoir de discrétisation.

Méthode

Je souhaite appliquer un schéma implicite car j'ai besoin de stabilité et d'un pas de temps illimité. Dans ce but, j'utilise la méthode $\theta$ , (notez que $\theta=1$ donne un schéma entièrement implicite et $\theta=0.5$ donne le schéma trapézoïdal ou "Crank-Nicolson"),

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})$

Cependant, pour les problèmes non linéaires, cela ne peut pas être fait car l'équation ne peut pas être écrite sous une forme linéaire.

Pour contourner ce problème, j'ai exploré deux approches numériques,

Méthode IMEX

$u_{j}^{'} = \underset{θ - method diffusion term}{\underset{⏟}{θ L u^{n + 1} + (1 - θ) L u^{n}}} + \underset{Fully explicit reaction term}{\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}}$
La voie la plus évidente est d'ignorer la partie non linéaire du terme de réaction et de simplement mettre à jour le terme de réaction avec la meilleure valeur possible, c'est-à-dire celle du pas de temps précédent. Il en résulte la méthode IMEX.
Solveur Newton

ν^{k + 1} = ν^{k} - (I - θ τ A^{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)$

L' équation complète de la méthode peut être résolue à l'aide d'une itération de Newton-Raphson pour trouver la future variable de solution. Où est l'indice d'itération ( ) et est la matrice jacobienne de . Ici, j'utilise les symboles pour les variables d'itération telles qu'elles se distinguent de la solution de l'équation à un point temps réel . Il s'agit en fait d'un solveur Newton modifié car le jacobien n'est pas mis à jour à chaque itération. $\theta$ $k$ $k\geq0$ $A^{n}$ $F(w^n)$ $\nu^{k}$ $u^n$

Résultats

Comparaison d'équations de Fisher des méthodes numériques.

Les résultats ci-dessus sont calculés pour un pas de temps raisonnablement grand et ils montrent la différence entre l'approche pas à pas et un solveur d'itération de Newton complet.

Choses que je ne comprends pas:

Je suis surpris que la méthode du pas de temps "OK" mais elle finit par prendre du retard sur la solution analytique au fil du temps. ( NB si j'avais choisi un pas de temps plus petit, alors l'approche pas à pas donne des résultats proches du modèle analytique). Pourquoi l'approche pas à pas donne-t-elle des résultats raisonnables à une équation non linéaire?
Le modèle de Newton fait beaucoup mieux, mais commence à diriger le modèle analytique au fil du temps. Pourquoi la précision de l'approche de Newton diminue-t-elle avec le temps? La précision peut-elle être améliorée?
Pourquoi y a-t-il une caractéristique générale qui, après de nombreuses itérations, puis le modèle numérique et le modèle analytique commencent à diverger? Est-ce simplement parce que le pas de temps est trop grand ou est-ce toujours le cas?

numerical-analysis nonlinear-equations implicit-methods newton-method explicit-methods boyfarrell
la source

Je recommande de lire l'analyse d'erreur de base des solveurs ODE, par exemple dans Hairer / Nørsett / Wanner, ainsi qu'une partie de l'analyse de stabilité. On répondra alors à la plupart de vos questions.

Guido Kanschat

@boyfarrell, pour éviter la confusion des autres lecteurs, vous devez mettre la terminologie là où vous expliquez votre méthode: 1. IMEX - explicite dans la non-linéarité et implicite dans la partie linéaire. 2. il s'agit du programme standard, qui nécessitera généralement la méthode de Newton pour la mise à jour

θ

$\theta$

Jan

Bonjour @Jan, je pense que j'ai tout. Merci encore pour votre aide.

boyfarrell

Réponses:

Je suppose que vous avez effectué une discrétisation spatiale, de manière à résoudre l'ODE (à valeur vectorielle) via un schéma numérique qui avance l'approximation à l'instance de temps courante à la valeur suivante à .

{\dot{u}}_{h} (t) = F_{h} (t, u_{h} (t)), on [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$

Ensuite, vos questions se réfèrent aux propriétés d' explicit , où la mise à jour s'écrit comme

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$

implicite , écrit comme

u_{h}^{n + 1} = u_{h}^{n} + Φ_{je} (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 (*)$

ou une combinaison des deux (« IMEX », voir la réponse de @Jed Brown) en un seul pas.

Dans cette configuration, la méthode de Newton est simplement une approche pour résoudre les éventuellement non linéaires dans les résultant de . $u_h^{n+1}$ $(*)$

Et mes réponses se basent sur les résultats de l'analyse numérique des méthodes en une seule étape.

Si vous utilisez des schémas convergents, en termes d'ordre de convergence, il n'y a aucun avantage général à utiliser des schémas implicites (voir. 2.). Cependant, pour les systèmes rigides, par exemple votre système contenant un laplacien, il existe des schémas implicites qui sont stables sans restrictions de pas de temps. Néanmoins, en théorie, pour le schéma explicite, vous obtenez de meilleurs résultats avec des pas de temps plus petits, tant que votre équation elle-même est stable (par exemple, en se référant au théorème de Picard-Lindelof, si est Lipshitz dans le deuxième argument) et votre temps -le pas n'est pas trop petit. $F_h$
Vous pouvez trouver des exemples où les schémas explicites fonctionnent mieux. (Théoriquement, vous pouvez inverser l'heure dans votre exemple, commencer à partir de la valeur terminale et trouver des échanges implicites et explicites.) Si vous faites l'erreur de Newton suffisamment petite, vous pouvez toujours améliorer la précision en diminuant le pas de temps ou en utilisant l'heure -des plans progressifs d'ordre supérieur.
La constante dans l'estimation d'erreur pour l'erreur globale croît de façon exponentielle avec la longueur de l'intervalle de temps. Voir, par exemple, ici pour le schéma d'Euler explicite. Cela est vrai pour chaque méthode en une seule étape. Comme l'estimation est de type , , un pas de temps plus petit ne fait que reporter cet effet. $C$ $err \approx C \tau^p$ $p>0$ $\tau$

Quelques remarques supplémentaires et la réponse finale:

Les schémas IMEX peuvent être utilisés pour ne traiter implicitement que la partie linéaire, ce qui évite les résolutions non linéaires. Voir la réponse de Jed Brown.
Crank-Nicolson est une méthode en une seule étape. Le «multi» dans les méthodes en plusieurs étapes fait référence à l'utilisation d'un certain nombre de pas de temps précédents pour définir la mise à jour actuelle. Par exemple, comme Ceci est très différent des méthodes en une seule étape et en plusieurs étapes ou IMEX, où la mise à jour est définie et ne revient pas aux valeurs précédentes. $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}).$

Donc, ma réponse est: Oui , vous pouvez résoudre des PDE non linéaires sans la méthode de Newton. Vous pouvez utiliser des schémas explicites, des schémas «IMEX» ou des méthodes dites implicitement linéaires (par exemple les méthodes de Rosenbrock). De plus, vous pouvez utiliser d'autres approches pour résoudre les systèmes à partir de comme l'itération en virgule fixe ou, dans certains cas, les solveurs algébriques. $(*)$

Jan
la source

Oui, j'ai appliqué le pochoir de différence centrale standard au terme de diffusion. Je ne peux pas utiliser un schéma explicite (pour le vrai problème que je veux résoudre) car le pas de temps stable est trop petit. C'est pourquoi j'explore IMEX ou les options implicites. Concernant votre troisième point, pour éviter l'accumulation d'erreurs je dois utiliser une méthode en plusieurs étapes. Le schéma de Crank-Nicolson que j'ai utilisé ci-dessus (avec le solveur de Newton) est-il classé comme une méthode en plusieurs étapes (il a deux points dans le temps)? J'ai été surpris que l'erreur augmente avec le temps lors de l'utilisation de la méthode du solveur de Newton.

boyfarrell

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 merci d'avoir expliqué la méthode CN. Oui, il est intéressant de savoir pourquoi les méthodes en plusieurs étapes semblent avoir une accumulation d'erreur plus faible. La raison pour laquelle le solveur Newton a une accumulation d'erreurs est qu'il s'agit d'une méthode en une seule étape, je comprends maintenant. Au fait, je sais que vous aimez Python. J'ai fait tout ce qui précède en utilisant scipy, numpy et matplotlib, gist.github.com/danieljfarrell/6353776

boyfarrell

J'ai supprimé le lien vers l'article de Trefethen et. Al. sur l'intégration IMEX d'ordre élevé de ma réponse car il existe de meilleures références pour en savoir plus sur les schémas IMEX.

Jan

Réponse courte

Si vous ne voulez qu'une précision de second ordre et aucune estimation d'erreur intégrée, il y a de fortes chances que vous soyez satisfait du fractionnement de Strang: demi-étape de réaction, étape complète de diffusion, demi-étape de réaction.

Longue réponse

La réaction-diffusion, même avec une réaction linéaire, est célèbre pour démontrer l'erreur de fractionnement. En effet, cela peut être bien pire, y compris "converger" vers des états stationnaires incorrects, confondre des états stationnaires avec des cycles limites, confondre des configurations stables et instables, et plus encore. Voir Ropp, Shadid et Ober (2004) et Knoll, Chacon, Margolin et Mousseau (2003) pour la perspective des physiciens computationnels à ce sujet. Pour l'analyse du mathématicien en termes de conditions de commande, voir le livre de Hairer et Wanner sur l'ODE rigide (les méthodes de Rosenbrock-W sont une méthode IMEX implicitement linéaire), Kennedy et Carpenter (2003) pour Runge-Kutta "additif" IMEX "implicite" non implicite. et la page d'Emil Constantinescu pour les méthodes IMEX plus récentes.

En général, les méthodes IMEX ont plus de conditions d'ordre que les méthodes implicites et explicites sous-jacentes seules. Les paires de méthodes IMEX peuvent être conçues avec la stabilité linéaire et non linéaire souhaitée et afin qu'elles satisfassent à toutes les conditions d'ordre jusqu'à l'ordre de conception de la méthode. Le respect de toutes les conditions de commande conservera séparément l'erreur de fractionnement asymptotique de la même échelle que l'erreur dans chaque schéma. Il ne dit rien sur le régime pré-asymptotique (grands pas de temps / exigence de faible précision), mais il est rarement plus strict que la résolution de chaque partie séparément. Dans tous les cas, l'erreur de fractionnement est visible pour l'estimateur d'erreur intégré (lors de l'utilisation du contrôle d'erreur adaptatif).

PETSc possède de nombreuses méthodes IMEX des familles Rosenbrock-W et Runge-Kutta additives , et aura une extrapolation et un IMEX linéaire à plusieurs étapes dans notre prochaine version.

Avertissement: J'ai écrit une grande partie du support d'intégration de temps PETSc et collaborer avec Emil (lié ci-dessus).

Jed Brown
la source

J'aborde certainement cela du point de vue de la physique, donc tous les détails techniques prennent un certain temps à suivre, car je ne connais pas beaucoup de termes. Je suis en fait expérimentaliste! Pourriez-vous expliquer un peu plus les conditions de commande? IMEX sont ces méthodes en plusieurs étapes mentionnées par Jan?

boyfarrell

Les conditions d'ordre sont des relations entre les coefficients des méthodes ODE (par exemple, les entrées dans un tableau Butcher pour les méthodes Runge-Kutta) qui doivent être satisfaites pour avoir un ordre d'exactitude. Les conditions de commande sont discutées dans tout livre ou article qui conçoit des méthodes d'intégration ODE, mais cela revient essentiellement à appliquer à plusieurs reprises des dérivés et des termes correspondants dans une expansion de Taylor. Le nombre de conditions de commande augmente rapidement pour les méthodes de haut niveau, c'est pourquoi il devient difficile de concevoir des méthodes de haut niveau. Des barrières sont établies en montrant que les conditions d'ordre sont mutuellement incompatibles.

Jed Brown