Solving Ordinary Differential Equations II

Stiff equations are problems for which explicit methods don’t work. Curtiss & Hirschfelder (1952) explain stiffness on one-dimensional examples such as 1.1$$ y' = - 50\left( {y - \cos x} \right). $$

The first analysis of instability phenomena and step size restrictions for hyperbolic equations was made in the famous paper of Courant, Friedrichs & Lewy (1928). Later, many authors undertook a stability analysis, very often independently, in order to explain the phenomena encountered in the foregoing section. An early and beautiful paper on this subject is Guillou & Lago (1961).

Methods are called A -stable if there are no stability restrictions for y′ = λy, Re λ < 0 and h > 0. This concept was introduced by Dahlquist (1963) for linear multistep methods, but also applied to Runge-Kutta processes. Ehle (1968) and Axelsson (1969) then independently investigated the A -stability of implicit Runge-Kutta methods and proposed new classes of A -stable methods. A nice paper of Wright (1970) studied collocation methods.

Order stars, discovered by searching for a better understanding of the stability properties of the Padé approximations to ez (Wanner, Hairer & Nørsett 1978), offered nice and unexpected access to many other results: the “second barrier” of Dahlquist, the Daniel & Moore conjecture, highest possible order with real poles, comparison of stability domains (Jeltsch & Nevanlinna 1981, 1982), order bounds for hyperbolic or parabolic difference schemes (e.g., Iserles & Strang 1983, Iserles & Williamson 1983, Jeltsch 1988).

In Sect. II.7 the first implicit Runge-Kutta methods were introduced. As we saw in Sect. IV.3, not all of them are suitable for the solution of stiff differential equations. This section is devoted to the collection of several classes of fully implicit Runge-Kutta methods possessing good stability properties.

We continue to quote from this nice paper: “To integrate a system of n differential equations, an implicit method with a full s × s matrix requires the solution of ns simultaneous implicit (in general nonlinear) equations in each time step (...) One way to circumvent this difficulty is to use a lower triangular matrix (a _ij )(i.e., a matrix with a _ij = 0 for i < j); the equations may then be solved in s successive stages with only an n -dimensional system to be solved at each stage”. In accordance with many authors, and in disaccordance with others (see above), we call such a method diagonally implicit (DIRK).

... is discussed in this section. Among the methods which already give satisfactory results for stiff equations, Rosenbrock methods are the easiest to program. We shall describe their theory in this section, which will lead us to our first “stiff” code. Rosenbrock methods belong to a large class of methods which try to avoid nonlinear systems and replace them by a sequence of linear systems. We therefore call these methods linearly implicit Runge-Kutta methods. In the literature such methods are often called “semi-implicit” (or was it “semi-explicit”?), or “generalized” or “modified” or “adaptive” or “additive” Runge-Kutta methods.

If the dimension of the differential equation y′ = f(x, y) is n, then the s -stage fully implicit Runge-Kutta method (3.1) involves a n · s -dimensional nonlinear system for the unknowns g₁, ... , g _s . An efficient solution of this system is the main problem in the implementation of an implicit Runge-Kutta method.

Extrapolation of explicit methods is an interesting approach to solving nonstiff differential equations (see Sect. II.9). Here we show to what extent the idea of extrapolation can also be used for stiff problems. We shall use the results of Sect. I1.8 for the existence of asymptotic expansions and apply them to the study of those implicit and linearly implicit methods, which seem to be most suitable for the computation of stiff differential equations. Our theory here is restricted to classical h → 0 order, the study of stability domains and A -stability.

After having seen so many different methods and ideas in the foregoing sections, it is legitimate to study how all these theoretical properties pay off in numerical efficiency.

The stability analysis of the preceeding sections is based on the transformation of the Jacobian J ≈ ∂f / ∂y to diagonal form (see Formulas (2.5), (2.6) of Sect. IV.2). Especially for large-dimensional problems, however, the matrix which performs this transformation may be badly conditioned and destroy all the nice estimations which have been obtained.

Here we enter a new era, the study of stability and convergence for general nonlinear systems. All the “crimes” and diverse omissions of which we have been guilty in earlier sections, especially in Sect. IV.2, shall now be repaired.

We shall give a constructive characterization of all irreducible B -stable Runge-Kutta methods (Theorem 13.15). Because of Theorem 12.16 we first have to study quadrature formulas with positive weights.

Since the Runge-Kutta methods studied in the foregoing sections are all implicit, we have to ensure that the numerical solutions, for which we have derived so many nice results, also really exist. The existence theory for implicit Runge-Kutta methods, presented in Volume I (Theorem 11.7.2), is for the non-stiff case only, where hL is small (L the Lipschitz constant). This is not a reasonable assumption for the stiff case.

Prothero & Robinson (1974) were the first to discover the order reduction of implicit Runge-Kutta methods when applied to stiff differential equations. Frank, Schneid & Ueberhuber (1981) then introduced the “concept of B -convergence”, which furnishes global error estimates independent of the stiffness.

A general k-step multistep method is of the form 1.1 $${\alpha _k}{y_{m + k}} + {\alpha _{k - 1}}{y_{m + k - 1}} + \ldots + {\alpha _0}{y_m} = h\left( {{\beta _k}{f_{m + k}} + \ldots + {\beta _0}{f_m}} \right).$$

Dahlquist’s condition p ≤ 2 for the order of an A -stable linear multistep method is a severe restriction for efficient practical calculations of high precision. There are only two ways of “breaking” this barrier: either weaken the condition;or strengthen the method.

The search for higher order A -stable multistep methods is carried out in two main directions: Use higher derivatives of the solutions;Throw in additional stages, off-step points, super-future points and the like, which leads into the large field of general linear methods.

We have seen in the foregoing sections that the highest possible order of A -stable linear multistep methods is two; furthermore, the second derivative Enright methods as well as the SDBDF methods were seen to be A -stable for p ≤ 4; the three-stage Radau multistep methods were A -stable for p ≤ 6. In this section we shall see that these observations are special cases of a general principle, the so-called “Daniel-Moore conjecture” which says that the order of an A -stable multistep method involving either s derivatives or s implicit stages satisfies p ≤ 2s. Before proceeding to its proof, we should become familiar with Riemann surfaces.

This section presents numerical results of multistep codes on precisely the same problems as in Sect. IV.10. These are, in increasing dimension, VDPOL (the van der Pol equation (IV.10.1)), ROBER (the famous Robertson problem (IV.10.2)), OREGO (the Oregonator (IV.10.3)), HIRES (the physiological problem (IV.10.4)), E5 (the badly scaled chemical reaction (IV.10.5)), PLATE ((IV.10.6), a car moving on a plate, the only linear and non autonomous problem), BEAM (the nonlinear elastic beam equation (IV.1.10’) with n = 40), CUSP (the cusp catastrophe (IV.10.8)), BRUSS (the brusselator (IV.1.6’) with one-dimensional diffusion α = 1/50 and n = 500), and KS (the one-dimensional Kuramoto-Sivashinsky equation (IV.10.11) with n = 1022). We have not included here the problems BECKDO and BRUSS-2D, since they require a special treatment of the linear algebra routines.

The first stability results for nonlinear differential equations and multistep methods are fairly old (Liniger 1956, Dahlquist 1963), older than similar studies for Runge-Kutta methods.

Theorems 6.10 and 6.11 give satisfactory convergence results for G -stable one-leg methods and A -stable multistep methods. But there are only few such methods and their highest order is two (Theorem 1.4). It is therefore interesting to relax the requirement of A -stability and to investigate higher-order multistep and one-leg methods. This section is devoted to linear stiff problems, while Sect. V.8 will treat non-linear problems.

In Sect. V.6 we have seen a convergence result for one-leg methods (Theorem 6.10) applied to nonlinear problems satisfying a one-sided Lipschitz condition. An extension to linear multistep methods has been given in Theorem 6.11. A different and direct proof of this result will be the first goal of this section. Unfortunately, such a result is valid only for A -stable methods (whose order cannot exceed two). The subsequent parts of this section are then devoted to convergence results for nonlinear problems, where the assumptions on the method are relaxed (e.g., A(α) -stability), but the class of problems considered is restricted. We shall present two different theories: the multiplier technique of Nevanlinna & Odeh (1981) and Lubich’s perturbation approach via the discrete variation of constants formula (Lubich 1991).

In Sections IV.12 and V.6 we have studied the nonlinear stability of Runge-Kutta methods (B -stability) and of one-leg methods (G-stability). It is natural to ask whether these theories can be combined within the class of general linear methods. This work was initiated by Burrage & Butcher (1980).

Singular perturbation problems (SPP) have several origins in applied mathematics. One comes from fluid dynamics and results in linear boundary value problems containing a small parameter ε (the coefficient of viscosity) such that for ε → 0 the differential equation loses the highest derivative (see Exercise 1 below). Others originate in the study of nonlinear oscillations with large parameters (van der Pol 1926, Dorodnicyn 1947) or in the study of chemical kinetics with slow and fast reactions (see e.g., Example (IV.1.4)).

The aim of this section is to study convergence of multistep methods when applied to singular perturbation problems (Runge-Kutta methods will be treated in Sect. VI.3). We are interested in estimates that hold uniformly for ε → 0. The results of the previous chapters cannot be applied. Since the Lipschitz constant of the singular perturbation problem (1.5) is of size O(ε−1), the estimates of Sect. 111.4 are useless. Also the one-sided Lipschitz constant is in general O(ε−1), so that the convergence results of Sect. V.8 can neither be applied. Let us start by considering the reduced problem.

In the preceding section we have proved convergence of multistep methods for singular perturbation problems. The same techniques do not yield optimal estimates for Runge-Kutta methods. We therefore investigate more thoroughly the structure of the solutions of singular perturbation problems. A first systematic study of the qualitative aspects of such problems is due to Tikhonov (1952). Asymptotic expansions were then analyzed by Vasil’eva (1963). Classical books on this subject are Wasow (1965), O’Malley (1974), and Tikhonov, Vasil’eva & Sveshnikov (1985).

This section is devoted to the extension of Rosenbrock methods (see Sect. IV.7) to differential-algebraic equations in semi-explicit form (4.1a)$$ y' = f\left( {y,z} \right),y\left( {{x_0}} \right) = {y_0} $$(4.1d)$$ 0 = g\left( {y,z} \right),z\left( {{x_0}} \right) = {z_0}. $$

The numerical computations of Sect. IV.10 have revealed the extrapolation code SEULEX as one of the best method for very stringent tolerances. The aim of the present section is to justify theoretically the underlying numerical method, the extrapolated linearly implicit Euler method, for singular perturbation problems as a representative of stiff equations.

Quasilinear differential equations are usually understood to be equations in which the highest derivative appears linearly. In the case of first order ODE systems, they are of the form (6.1)$$ C\left( y \right) \cdot y' = f\left( y \right), $$ where C(y) is a n × n -matrix. In the regions where C(y) is invertible, Eq. (6.1) can be written as (6.1)$$ y = C{\left( y \right)^{ - 1}} \cdot f\left( y \right) $$ and every ODE-code can be applied by solving at every function call a linear system. But this would destroy, for example, a banded structure of the Jacobian and it is therefore often preferable to treat Eq. (6.1) directly. If the matrix C is everywhere of rank m (m < n), Eq. (6.1) represents a quasilinear differential-algebraic system.

The most general form of a differential-algebraic system is that of an implicit differential equation 1.1$F\left( {u',u} \right) = 0$ where F and u have the same dimension. We always assume F to be sufficiently differentiable. A non-autonomous system is brought to the form (1.1) by appending x to the vector u, and by adding the equation x′ = 1.

We have seen in Sect. VI.1 that the numerical treatment of problems of index 1, which are either in the half-explicit form (1.13) or in the form Mu′ = φ(u), is not much more difficult than that of ordinary differential equations. For higher index problems the situation changes completely. This section is devoted to the study of several approaches that are all based on the idea of modifying the problem in such a way that the index is reduced.

Convergence results of multistep methods for problems of index at least 2 are harder to obtain than for semi-explicit index 1 problems (see Section VI.2). A first convergence result for BDF schemes, valid for linear constant coefficient DAE’s of arbitrary index, was given by Sincovec, Erisman, Yip & Epton (1981). Convergence of BDF for nonlinear DAE systems was then studied by Gear, Gupta & Leimkuhler (1985), Lötstedt & Petzold (1986) and Brenan & Engquist (1988). An independent convergence analysis was given by Griepentrog & März (1986), März (1990). They considered general linear multistep methods and problems, where the differential and algebraic equations (and/or variables) are not explicitly separated.

This section is devoted to the convergence of implicit Runge-Kutta methods for semi-explicit index 2 systems (3.1) which satisfy (3.2).

For an application of the convergence result of the preceding section (Theorem 4.5) it is desirable to know the optimal values of r in (4.16). Comparing the Taylor expansions of the exact and numerical solutions we derive conditions for c _i , a _ij , b _j which are equivalent to (4.16). For collocation methods we recover the result of Theorem 4.9. For other methods (such as Lobatto IIIC) the estimates of Lemma 4.4 are substantially improved.

The methods of Sects. VII.3 and VII.4 do not use the semi-explicit structure of the differential-algebraic equation (6.1)$$ y' = f\left( {y,z} \right),0 = g\left( y \right) $$ (y ∈ ℝn, z ∈ ℝm) and can as well be applied to more general situations. Here we shall show how this structure can be exploited for the derivation of new, efficient integration methods. The main idea is to discretize the differential variables y in an explicit manner, and the algebraic variables z in an implicit manner.

After having seen several different approaches for the numerical solution of constrained mechanical systems, we are interested in their efficiency when applied to a concrete situation. We consider two particular multibody mechanisms with constraints, one nonstiff and one stiff. General references for the computation of mechanical systems are Haug (1989) and Roberson & Schwertassek (1988).

In principle, all approaches discussed in Sect. VII.2 can be employed for the numerical solution of constrained Hamiltonian systems. A disadvantage of these index reduction methods is, as we shall see below, that the symplectic structure of the flow is destroyed by the discretization.