10
$\begingroup$

Right now I have a code that uses the Crank-Nicholson algorithm, but I think that I would like to move to a higher-order algorithm for timestepping. I know that the Crank-Nicholson algorithm is stable in the domain I want to work in, but I am concerned that some other algorithms may not be.

I know how to calculate the stability region of an algorithm, but it can be kind of a pain. Does anybody know of any good reference for the stability properties of a large number of timestepping algorithms for parabolic PDEs?

$\endgroup$
5
$\begingroup$

My personal favourite is the book by John Strikwerda, "Finite Difference Schemes and Partial Differential Equations".

He has a really nice treatment of the stability theory using Fourier analysis. I only have the first edition, where he doesn't introduce the idea of a stability region. According to the SIAM website, the second edition has added this material.

$\endgroup$
10
$\begingroup$

Very short answer: for a comprehensive reference, you can't beat Hairer and Wanner volume II.

Short answer: Here are some MATLAB scripts to plot the stability region of a linear multistep or Runge-Kutta method, given the coefficients. You could also use the Python package nodepy (disclaimer: it's my package and it's not the most polished piece of software, but plotting stability regions is one thing it does very well). Instructions for plotting stability regions are here.

Longer answer: there are three classes of methods you could be interested in here.

  • $A$-stable methods, where all of the left half of the complex plane lies in the stability region. The most well-known examples are backward Euler (1st order) and the implicit trapezoidal method (which is what Crank-Nicholson uses). For these methods, you don't need to know the details of the stability region; as long as the eigenvalues of your spatial discretization lie in the left half-plane, you'll have unconditional stability (no step size restriction). Due to the second Dahlquist barrier, you have to use Runge-Kutta methods if you want high order and $A$-stability. Some examples of such methods are the Gauss-Legendre, Radau, and Lobatto methods. All of those are fully implicit and thus rather expensive.

  • $A(\alpha)$-stable methods, which include a sector in the left half-plane, including all of the negative real axis. The most prominent of these are the backward differentiation (BDF) methods and a variant known as "numerical differentiation formulas", which are implemented in MATLAB's ode15s(). These are unconditionally stable as long as the eigenvalues of your spatial discretization lie in that sector, so the only thing you need to know about the stability region is the angle $\alpha$, which you can find in any reference on ODE solvers (for instance, p. 175 of LeVeque).

  • Explicit methods, which will necessary include only a finite interval on the negative real axis. There are special "stabilized" explicit methods (in particular, the Runge-Kutta-Chebyshev methods) that have large negative real axis stability regions and are suitable for mildly stiff problems, but usually not for parabolic problems. A good entrance to that literature is this paper, which includes lots of information about the stability regions.

I've assumed throughout that you're only interested in absolute stability. For parabolic problems you would likely want an $L$-stable method as well, but it's simple to check $L$-stability of a method.

Update: If you really need to know everything about this topic, get a copy of Dekker and Verwer's monograph. It has one of the best existing introductions to concepts like one-sided Lipschitz constants, the logarithmic norm, and several deeper stability concepts. It's out of print but you can usually find used copies on Amazon (for a price!)

$\endgroup$
  • $\begingroup$ Hairer II is definitely the best. It's probably the only place to find PI stepsize adaptivity get a mention. But it misses important details like extra order conditions for Rosenbrock methods on parabolic PDEs for example. Of course no book can have everything, but there should be something better specifically on the topic of parabolic PDEs. $\endgroup$ – Chris Rackauckas Jul 8 '17 at 7:28

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.