É possível resolver PDEs não lineares sem usar a iteração de Newton-Raphson?

Estou tentando entender alguns resultados e gostaria de receber alguns comentários gerais sobre como resolver problemas não-lineares.

Equação de Fisher (um PDE de difusão da reação não linear),

{você}_{t} = d {você}_{x x} + β você (1 1 - você) = F (você)

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

de forma discreta,

{você}_{j}^{'} = eu você + β {você}_{j} (1 1 - {você}_{j}) = F (você)

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

onde é o operador diferencial e é o estêncil de discretização. $\boldsymbol{L}$ $\boldsymbol{u}=(u_{j-1}, u_j, u_{j+1})$

Método

Desejo aplicar um esquema implícito porque exijo estabilidade e tempo irrestrito. Para esse propósito, estou usando o método theta-(observe que fornece um esquema totalmente implícito e fornece o esquema trapezoidal ou "Crank-Nicolson"), $\theta$ $\theta=1$ $\theta=0.5$

{você}_{j}^{'} = θ F ({você}^{n + 1 1}) + (1 1 - θ) F ({você}^{n})

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

No entanto, para problemas não lineares, isso não pode ser feito porque a equação não pode ser escrita de forma linear.

Para contornar esse problema, tenho explorado duas abordagens numéricas,

Método IMEX

$u_{j}^{'} = \underset{θ - method diffusion term}{\underset{⏟}{θ L u^{n + 1} + (1 - θ) L u^{n}}} + \underset{Termo de reação totalmente explícito}{\underset{⏟}{β u_{j}^{n} (1 1 - {você}_{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}}$
A rota mais óbvia é ignorar a parte não linear do termo da reação e apenas atualizar o termo da reação com o melhor valor possível, isto é, a partir do passo anterior. Isso resulta no método IMEX.
Solucionador de Newton

ν^{k + 1 1} = ν^{k} - (Eu - θ τ {UMA}^{n})^{- 1 1} (ν^{k} - {você}_{n} - (1 1 - θ) τ F (W^{n}) - θ τ F (W^{n + 1 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)$

A equação completa -method pode ser resolvida usando a iteração Newton-Raphson para encontrar a variável de solução futura. Onde é o índice de iteração ( ) e é a matriz jacobiana de . Aqui eu uso os símbolos para variáveis de iteração de modo que elas sejam distinguidas da solução da equação em um ponto de tempo real . Na verdade, este é um solucionador de Newton modificado porque o jacobiano não é atualizado a cada iteração. $\theta$ $k$ $k\geq0$ $A^{n}$ $F(w^n)$ $\nu^{k}$ $u^n$

Resultados

Comparação da equação de Fisher de métodos numéricos.

Os resultados acima são calculados para uma etapa de tempo razoavelmente grande e mostram a diferença entre a abordagem da etapa de tempo e um solucionador de iteração de Newton completo.

Coisas que eu não entendo:

Surpreende-me que o método de escalonamento do tempo seja "OK", mas eventualmente fique atrás da solução analítica à medida que o tempo passa. ( NB, se eu tivesse escolhido um intervalo de tempo menor, a abordagem de intervalo de tempo apresentaria resultados fechados ao modelo analítico). Por que a abordagem de escalonamento do tempo fornece resultados razoáveis para uma equação não linear?
O modelo de Newton se sai muito melhor, mas começa a liderar o modelo analítico à medida que o tempo avança. Por que a precisão da abordagem de Newton diminui com o tempo? A precisão pode ser melhorada?
Por que existe uma característica geral que, após muitas iterações, o modelo numérico e o modelo analítico começam a divergir? Isso ocorre apenas porque o intervalo de tempo é muito grande ou isso sempre acontece?

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

Eu recomendo a leitura da análise básica de erros dos solucionadores ODE, por exemplo, em Hairer / Nørsett / Wanner, além de algumas análises de estabilidade. A maioria das suas perguntas será respondida então.

Guido Kanschat 27/08/13

@boyfarrell, para evitar confusão de colegas leitores, você deve colocar a terminologia exatamente onde explica seu método: 1. IMEX - explícito na não-linearidade e implícito na parte linear. 2. este é o esquema-

padrão , que normalmente exigirá que o método de Newton resolva a atualização

θ

$\theta$

Jan /

Olá @Jan, acho que consegui tudo. Obrigado novamente por sua ajuda.

precisa saber é o seguinte

Respostas:

Suponho que você tenha realizado uma discretização de espaço, para resolver o ODE (com valor vetorial) através de um esquema numérico que avança a aproximação na instância de tempo atual para o próximo valor

{\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$

Em seguida, suas perguntas se referem às propriedades explícitas , nas quais a atualização é escrita como

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$

u_{h}^{n + 1} = u_{h}^{n} + Φ_{i} (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 uma combinação de ambos (' IMEX ', consulte a resposta de @Jed Brown) em etapas de etapa única.

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

E minhas respostas baseiam-se em resultados da análise numérica de métodos de etapa única.

$F_h$
Você pode encontrar exemplos em que esquemas explícitos têm melhor desempenho. (Teoricamente, você pode reverter o tempo no seu exemplo, começar pelo valor do terminal e encontrar trocas implícitas e explícitas.) Se você fizer o erro de Newton suficientemente pequeno, ainda poderá melhorar a precisão diminuindo o intervalo de tempo ou usando o tempo esquemas de alta ordem.
$C$ $err \approx C \tau^p$ $p>0$ $\tau$

Mais algumas observações e a resposta final:

Os esquemas IMEX podem ser usados para tratar apenas a parte linear implicitamente, o que evita as soluções não lineares. Veja a resposta de Jed Brown.
$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}).$

$(*)$

Jan
fonte

Sim, apliquei o estêncil padrão de diferença central ao termo difusão. Não posso usar um esquema explícito (para o problema real que quero resolver) porque o tempo estável é irrealisticamente pequeno. É por isso que estou explorando opções IMEX ou implícitas. Em relação ao seu terceiro ponto, para evitar a acumulação de erros, devo usar métodos de várias etapas. O esquema Crank-Nicolson que usei acima (com o solucionador de Newton) é classificado como um método de várias etapas (ele tem dois pontos no tempo)? Fiquei surpreso que o erro aumentou com o tempo ao usar o método Newton Solver.

precisa saber é o seguinte

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, obrigado por explicar sobre o método CN. Sim, é interessante por que os métodos de várias etapas parecem ter menor acúmulo de erros. A razão pela qual o solucionador de Newton tem erros é porque é um método de etapa única, eu entendo agora. A propósito, eu sei que você gosta de Python. Eu fiz tudo o acima usando scipy, numpy e matplotlib, gist.github.com/danieljfarrell/6353776

boyfarrell

Eu removi o link para o artigo de Trefethen et. al. na integração IMEX de alta ordem da minha resposta, pois existem melhores referências para aprender sobre os esquemas IMEX.

Jan

Resposta curta

Se você deseja apenas precisão de segunda ordem e nenhuma estimativa de erro incorporada, é provável que fique satisfeito com a divisão de Strang: meio passo da reação, passo completo da difusão, meio passo da reação.

Resposta longa

A difusão de reação, mesmo com reação linear, é famosa por demonstrar erro de divisão. De fato, pode ser muito pior, incluindo "convergir" para estados estacionários incorretos, confundir estados estacionários com ciclos limite, confundir configurações estáveis e instáveis e muito mais. Veja Ropp, Shadid e Ober (2004) e Knoll, Chacon, Margolin e Mousseau (2003) para a perspectiva dos físicos computacionais sobre isso. Para a análise do matemático em termos de condições de ordem, consulte o livro de Hairer e Wanner sobre ODE rígido (os métodos Rosenbrock-W são um método IMEX linearmente implícito), Kennedy e Carpenter (2003) para o "aditivo" IMEX não linearmente implícito Runge-Kutta, e página de Emil Constantinescu para métodos IMEX mais recentes.

Em geral, os métodos IMEX têm mais condições de ordem do que os métodos implícitos e explícitos subjacentes. Os pares de métodos IMEX podem ser projetados com a estabilidade linear e não linear desejada e, assim, satisfazer todas as condições de pedido, até a ordem de design do método. A satisfação de todas as condições do pedido manterá o erro de divisão assintótica da mesma escala que o erro em cada esquema separadamente. Ele não diz nada sobre o regime pré-assintótico (grandes intervalos de tempo / requisito de baixa precisão), mas raramente é mais rigoroso que a resolução de cada parte separadamente. De qualquer forma, o erro de divisão é visível para o estimador de erros incorporado (ao usar o controle de erro adaptativo).

O PETSc possui muitos métodos IMEX das famílias Rosenbrock-W e Runge-Kutta aditiva e terá extrapolação e IMEX linear de várias etapas em nosso próximo lançamento.

Isenção de responsabilidade: escrevi grande parte do suporte à integração de tempo do PETSc e colaborei com Emil (link acima).

Jed Brown
fonte

Estou certamente abordando isso da perspectiva da física, para que todos os detalhes técnicos levem algum tempo para eu seguir, porque não estou familiarizado com muitos dos termos. Na verdade, sou experimentalista! Você explicaria um pouco mais sobre as condições do pedido? IMEX são esses métodos de várias etapas mencionados por Jan?

boyfarrell

Condições de ordem são relações entre coeficientes dos métodos ODE (por exemplo, entradas em um quadro Butcher para métodos Runge-Kutta) que devem ser satisfeitas para ter uma ordem de precisão. As condições do pedido são discutidas em qualquer livro ou artigo que projete métodos de integração ODE, mas basicamente equivale a aplicar repetidamente derivativos e termos correspondentes em uma expansão de Taylor. O número de condições de pedidos cresce rapidamente para os métodos de alta ordem, e é por isso que fica difícil projetar métodos de alta ordem. As barreiras são estabelecidas, mostrando que as condições da ordem são mutuamente incompatíveis.

Jed Brown