Linearized implicit time stepping

Question

Consider the general FD implicit time stepping scheme

$\frac{x_{t+1} - x_t}{\Delta t} = f(x_{t+1})$,

where $x$ is the vector variable of interest and $f$ is some function, generally non-linear.

We can advance from $x_{t}$ to $x_{t+1}$ using Newton's method to solve the above non-linear equation. However, this can get quite costly.

If instead we write $f(x_{t+1}) \approx f(x_t) + J_f (x_t)(x_{t+1}-x_t) $, where $J_f$ denotes the Jacobian of $f$, we obtain the time-stepping scheme

$x_{t+1} - x_t = \left(I - \Delta t \, J_f(x_t) \right)^{-1} \, \Delta t f(x_t)$.

Can anybody tell me anything about this very general scheme, any references? What's its name? Stability properties?

Answer 1

This particular example is often called linearly implicit Euler. Its linear stability is identical to nonlinearly implicit Euler, but the nonlinear stability can be a limiting factor, especially for larger time steps. You can find some discussion for reaction-diffusion systems in Ropp, Shadid, and Ober 2004.

More formally, this is the simplest example of a Rosenbrock method. There is a good chapter in Hairer and Wanner's Solving Ordinary Differential Equations II: Stiff and Differential Algebraic Problems, including work-precision diagrams for a suite of benchmark problems. For most problems, Rosenbrock methods are very efficient for moderate tolerances. Fully implicit methods can typically take slightly larger time steps for strongly nonlinear problems and extremely high order approaches are good when very tight tolerances are needed. Note that there are also Rosenbrock-W methods which only require an approximation of the Jacobian.

For software, you can find the RODAS Fortran 77 implementation from Hairer and Wanner. I also implemented this family of methods in PETSc, which may be appropriate if you have a use for parallel linear algebra or sparse direct solvers. To experiment, you might start by looking at this ODE example written in Python which produces this figure. You can compare different methods using run-time options, e.g. -ts_type sundials will produce this figure.