¿Es posible resolver PDE no lineales sin usar la iteración Newton-Raphson?

Estoy tratando de entender algunos resultados y agradecería algunos comentarios generales sobre cómo abordar problemas no lineales.

La ecuación de Fisher (una PDE de reacción-difusión no lineal),

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

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

en forma discreta,

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

donde es el operador diferencial y es la plantilla de discretización. $\boldsymbol{L}$ $\boldsymbol{u}=(u_{j-1}, u_j, u_{j+1})$

Método

Deseo aplicar un esquema implícito porque necesito estabilidad y un paso de tiempo sin restricciones. Para este propósito estoy usando el método theta-(tenga en cuenta que da un esquema totalmente implícito y da el esquema trapezoidal o "Crank-Nicolson"), $\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})$

Sin embargo, para problemas no lineales esto no se puede hacer porque la ecuación no se puede escribir en forma lineal.

Para solucionar este problema, he estado explorando dos enfoques numéricos,

Método IMEX

${tu}_{j}^{'} = \underset{θ - término de difusión del método}{\underset{⏟}{θ L {tu}^{norte + 1} + (1 - θ) L {tu}^{norte}}} + \underset{Término de reacción completamente explícito}{\underset{⏟}{β {tu}_{j}^{norte} (1 - {tu}_{j}^{norte})}}$ $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 ruta más obvia es ignorar la parte no lineal del término de reacción y simplemente actualizar el término de reacción con el mejor valor posible, es decir, el del paso de tiempo anterior. Esto da como resultado el método IMEX.
Solucionador de Newton

ν^{k + 1} = ν^{k} - (yo - θ τ {UN}^{norte})^{- 1} (ν^{k} - {tu}_{norte} - (1 - θ) τ F (w^{norte}) - θ τ F (w^{norte + 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)$

La ecuación completa del método se puede resolver utilizando la iteración de Newton-Raphson para encontrar la variable de solución futura. Donde es el índice de iteración ( ) y es la matriz jacobiana de . Aquí uso los símbolos para las variables de iteración de modo que se distingan de la solución de la ecuación en un punto en tiempo real . Esto es en realidad un solucionador de Newton modificado porque el jacobiano no se actualiza con cada iteración. $\theta$ $k$ $k\geq0$ $A^{n}$ $F(w^n)$ $\nu^{k}$ $u^n$

Resultados

Comparación de ecuaciones de Fisher de métodos numéricos.

Los resultados anteriores se calculan para un paso de tiempo razonablemente grande y muestran la diferencia entre el enfoque de paso de tiempo y un solucionador de iteración de Newton completo.

Cosas que no entiendo:

Me sorprende que el método de paso de tiempo "OK", pero eventualmente se queda atrás de la solución analítica a medida que pasa el tiempo. ( Nota: si hubiera elegido un paso de tiempo más pequeño, el enfoque de paso de tiempo da resultados cerrados al modelo analítico). ¿Por qué el enfoque de paso de tiempo da resultados razonables a una ecuación no lineal?
El modelo de Newton funciona mucho mejor, pero comienza a liderar el modelo analítico a medida que pasa el tiempo. ¿Por qué la precisión del enfoque de Newton disminuye con el tiempo? ¿Se puede mejorar la precisión?
¿Por qué hay una característica general que después de muchas iteraciones, el modelo numérico y el modelo analítico comienzan a divergir? ¿Es esto solo porque el paso de tiempo es demasiado largo o esto siempre sucederá?

numerical-analysis nonlinear-equations implicit-methods newton-method explicit-methods boyfarrell
fuente

Recomiendo leer el análisis de error básico de los solucionadores de ODE, por ejemplo en Hairer / Nørsett / Wanner, más algunos de los análisis de estabilidad. La mayoría de sus preguntas serán respondidas entonces.

Guido Kanschat

@boyfarrell, para evitar la confusión de otros lectores, debe poner la terminología justo al explicar su método: 1. IMEX: explícito en la no linealidad e implícito en la parte lineal. 2. Este es el esquema

estándar , que generalmente requerirá el método de Newton para resolver la actualización

θ

$\theta$

enero

Hola @ Jan Creo que tengo todo. De nuevo, gracias por tu ayuda.

boyfarrell

Respuestas:

Supongo que ha realizado una discretización de espacio, de modo que se trata de resolver la ODE (valor vectorial) mediante un esquema numérico que avanza la aproximación en la instancia de tiempo actual al siguiente valor

{\dot{tu}}_{h} (t) = F_{h} (t, {tu}_{h} (t)), en [0, T], {tu}_{h} (0 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$

Luego, sus preguntas se refieren a propiedades explícitas , donde la actualización se escribe como

{tu}_{h}^{norte + 1} = {tu}_{h}^{norte} + Φ_{mi} (t^{norte}, τ, {tu}_{h}^{norte}),

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

{tu}_{h}^{norte + 1} = {tu}_{h}^{norte} + Φ_{yo} (t^{norte}, τ, {tu}_{h}^{norte + 1}, {tu}_{h}^{norte}), (*)

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

o una combinación de ambos (' IMEX ', ver la respuesta de @Jed Brown) esquemas de paso de tiempo de un solo paso.

$u_h^{n+1}$ $(*)$

Y mis respuestas se basan en los resultados del análisis numérico de los métodos de un solo paso.

$F_h$
Puede encontrar ejemplos donde los esquemas explícitos funcionan mejor. (Teóricamente, puede revertir el tiempo en su ejemplo, comenzar desde el valor terminal y encontrar intercambios implícitos y explícitos). Si hace que el error de Newton sea lo suficientemente pequeño, aún puede mejorar la precisión al disminuir el paso de tiempo o al usar el tiempo -programas de pasos de orden superior.
$C$ $err \approx C \tau^p$ $p>0$ $\tau$

Algunas observaciones más y la respuesta final:

Los esquemas IMEX se pueden usar para tratar solo la parte lineal implícitamente, lo que evita las soluciones no lineales. Ver la respuesta de Jed Brown.
${tu}_{h}^{norte + 1} = Φ_{metro} (t^{norte}, τ, {tu}_{h}^{norte + 1}, {tu}_{h}^{norte}, {tu}_{h}^{norte - 1}) .$ $u_h^{n+1} = \Phi_m(t^n,\tau,u_h^{n+1},u_h^n,u_h^{n-1}).$

$(*)$

ene
fuente

Sí, he aplicado la plantilla estándar de diferencia central al término de difusión. No puedo usar un esquema explícito (para el problema real que quiero resolver) porque el paso de tiempo estable es irrealmente pequeño. Es por eso que estoy explorando IMEX u opciones implícitas. Con respecto a su tercer punto, para evitar la acumulación de errores, debo usar métodos de varios pasos. ¿El esquema de Crank-Nicolson que he usado anteriormente (con el solucionador Newton) está clasificado como un método de varios pasos (tiene dos puntos en el tiempo)? Me sorprendió que el error aumentara con el tiempo al usar el método de solución 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, gracias por explicarme sobre el método CN. Sí, es interesante por qué los métodos de varios pasos parecen tener una menor acumulación de errores. La razón por la que el solucionador Newton tiene acumulación de errores es porque es un método de un solo paso, lo entiendo ahora. Por cierto, sé que te gusta Python. Hice todo lo anterior usando scipy, numpy y matplotlib, gist.github.com/danieljfarrell/6353776

boyfarrell

He eliminado el enlace al documento de Trefethen et. Alabama. sobre la integración IMEX de alto orden de mi respuesta, ya que hay mejores referencias para aprender sobre los esquemas IMEX.

Jan

Respuesta corta

Si solo desea una precisión de segundo orden y ninguna estimación de error incrustada, es probable que esté satisfecho con la división de Strang: medio paso de reacción, paso completo de difusión, medio paso de reacción.

Respuesta larga

La reacción-difusión, incluso con reacción lineal, es famosa por demostrar error de división. De hecho, puede ser mucho peor, incluyendo "converger" a estados estacionarios incorrectos, confundir los estados estacionarios con ciclos límite, confundir configuraciones estables e inestables, y más. Ver Ropp, Shadid y Ober (2004) y Knoll, Chacon, Margolin y Mousseau (2003) para la perspectiva de los físicos computacionales sobre esto. Para el análisis del matemático en términos de las condiciones del pedido, consulte el libro de Hairer y Wanner sobre la ODE rígida (los métodos de Rosenbrock-W son un método IMEX linealmente implícito), Kennedy y Carpenter (2003) para el "aditivo" IMEX no linealmente implícito Runge-Kutta, y la página de Emil Constantinescu para métodos IMEX más recientes.

En general, los métodos IMEX tienen más condiciones de orden que los métodos implícitos y explícitos subyacentes solos. Los pares de métodos IMEX pueden diseñarse con la estabilidad lineal y no lineal deseada, de modo que satisfagan todas las condiciones de orden hasta el orden de diseño del método. Satisfacer todas las condiciones del pedido mantendrá el error de división asintótico de la misma escala que el error en cada esquema por separado. No dice nada sobre el régimen preasintótico (pasos de tiempo largos / requisito de baja precisión), pero rara vez es más estricto que la resolución de cada parte por separado. En cualquier caso, el error de división es visible para el estimador de error incorporado (cuando se usa el control de error adaptativo).

PETSc tiene muchos métodos IMEX de las familias Rosenbrock-W y aditivo Runge-Kutta , y tendrá extrapolación e IMEX multipaso lineal en nuestro próximo lanzamiento.

Descargo de responsabilidad: escribí gran parte del soporte de integración de tiempo de PETSc y colaboro con Emil (vinculado anteriormente).

Jed Brown
fuente

Ciertamente me estoy acercando a esto desde una perspectiva física, por lo que todos los detalles técnicos me llevan un tiempo para seguirlos porque no estoy familiarizado con muchos de los términos. En realidad soy un experimentalista! ¿Podría explicar un poco más sobre las condiciones del pedido? IMEX son estos métodos de varios pasos mencionados por Jan?

boyfarrell

Las condiciones de orden son relaciones entre coeficientes de métodos ODE (por ejemplo, entradas en un cuadro de carnicero para métodos Runge-Kutta) que deben cumplirse para tener un orden de precisión. Las condiciones de pedido se analizan en cualquier libro o documento que diseñe métodos de integración de ODE, pero básicamente equivale a aplicar repetidamente derivados y términos coincidentes en una expansión de Taylor. El número de condiciones de pedido crece rápidamente para los métodos de alto orden, por lo que se hace difícil diseñar métodos de alto orden. Las barreras se establecen al mostrar que las condiciones del pedido son mutuamente incompatibles.

Jed Brown