8
$\begingroup$

I'm having difficulty understanding how to apply Newton iteration to nonlinear PDEs and then use a fully implicit scheme to time step. For example, I want to solve Burgers equation

$$u_{t} + u u_{x} - u_{xx} = 0$$

So discretising time using a Backward Euler

$$u_{t} = \frac{u^{n+1} - u^{n}}{h}$$

we find that

\begin{align} &\frac{u^{n+1} - u^{n}}{h} + u^{n+1} (u^{n+1})_{x} - (u^{n+1})_{xx} = 0 \\ &u^{n+1} - h (u^{n+1})_{xx} + h u^{n+1} (u^{n+1})_{x} = u^{n} \\ &(I - h D^{2}) u^{n+1} + h u^{n+1} D u^{n+1} = u^{n} \\ &(I - h D^{2}) u^{n+1} + N(u^{n+1}) = u^{n} \ \ \ (1) \end{align}

where $N$ represents our nonlinear term (note that the nonlinear term is written implicitly). Now, we want to apply Newton iteration to this nonlinear ODE, but here is where I get stuck:

  1. Do we just apply Newton Iteration to the LHS of $(1)$, ignoring the $u^{n}$ term, i.e., solve $(I - h D^{2}) u^{n+1} + N(u^{n+1}) = 0$? Or are we supposed to include the $u^{n}$ term? (Just a reminder, I want to time step using a fully implicit scheme after using Newton iteration, so I believe we just want to solve the LHS = 0).

  2. What are we then supposed to do with the information from the initial guess and result of our Newton iteration? How do we use this information in our time stepping?

As I'm sure is painfully obvious, I'm quite confused as to how to approach this problem. If someone could give a detailed description of how to apply Newton iteration and time stepping to nonlinear PDEs (not elliptic PDEs though), or could help me with the problem at hand, I would be very grateful. Thanks in advance.

$\endgroup$
7
$\begingroup$

It's a bit easier to see if you write your equation in the a semi-discretised system of the form $u^{\prime}(t) = F(u(t))$ and with the application of the $\theta$-method and approximating $u^{\prime}(t) \approx (w^{n+1} - w^{n})/\tau$ this gives,

$$w^{n+1} - w^{n} - (1-\theta) \tau F(w^n) - \theta\tau F(w^{n+1}) = 0$$

with unknown vector $w^{n+1}$ and time step $\tau$. Here $u^{\prime}(t)$ is the non discretised time partial derivative and $F(u(t))$ represents your discretised spatial derivatives evaluated at $u(t)$ at time $t$. Using the $\theta$-method gives you a bit of flexibility as you can change the method between fully implicit to fully explicit (and anywhere in between).

This equation can be solved using Newton iteration,

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

where $k$ is the iteration index ($k\geq0$) and $A^{n}$ is the Jacobian matrix of $F(w^n)$. We use the symbol $\nu^{k}$ for iteration variables such that they are distinguished from solution of the equation at a real time point $u^n$. As you said the iteration needs an initial value, it is perfectly valid to choose $\nu^0 = w^0$ or for a better estimate we can precompute one iteration $\nu^0 = w^0 + \tau F(w^{0})$. Strictly speaking this is the so-called modified Newton iteration because the Jacobian is not updated during the iteration which is known to work well for stiff PDEs.

$\endgroup$
  • $\begingroup$ Thanks for your response. I should have been more specific, I'm actually already at the point of using Newton Iteration and have been solving the problem as such, and have plots of the solution. But my main problem is how to time step afterwards? I thought we wanted to "annihilate" the nonlinear term and then time step a linear ODE afterwards? Or have I totally missed the point of Newton Iteration? Also, could you please include a step by step method as to how you got your Newton Iteration equation? I apologise for asking so many questions, I'm just having a bit of difficulty at the moment. $\endgroup$ – mattos Sep 13 '15 at 12:34
  • $\begingroup$ I think you have missed the point. You discretise your nonlinear equations then iterate (starting off with a guess value) to solve the equations to give $w^1$ at time point $t^1$ (this generates a sequence of improved values which I denoted as the $\nu$ terms). You then move on to time point $t^2$ and repeat. I cannot derive it for you, you can find this on the web. You asked how to solve nonlinear PDEs with Newtons method, which I have answered. I recommend marking this as answered and opening new questions if you need other help. $\endgroup$ – boyfarrell Sep 13 '15 at 13:51
  • $\begingroup$ Looks like there is an error in the Newton iteration formula? Consider $\theta=0$ for a fully explicit method, and the Jacobian matrix is multiplied by 0. Or am I missing something? Thanks $\endgroup$ – Cogicero Apr 5 at 18:13
  • $\begingroup$ Check out p.127 books.google.co.uk/books?isbn=3540034404 it has more information. I’ve implemented numerical algorithms with that and it works. $\endgroup$ – boyfarrell Apr 6 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.