Non-linear stability of numerical methods

Numerical stability theory for the initial value problem , , where , is concerned with the question of whether the numerical discretization inherits the dynamic properties of the differential equation. Stability concepts are usually based on structural assumptions on . For non-linear problems, the breakthrough was achieved by G. Dahlquist in his seminal paper [a3]. There, he studied multi-step discretizations of problems satisfying a one-sided Lipschitz condition. Let denote an inner product on and let be the induced norm.

Runge–Kutta methods.

An -stage Runge–Kutta discretization of , is given by

Here, denotes the step-size and is the Runge–Kutta approximation to . (For a thorough discussion of such methods, see [a1], [a2], and [a4]; see also Runge–Kutta method.)

B-stability.

If the problem satisfies the global contractivity condition

then the difference of two solutions is a non-increasing function of . Let , denote the numerical solutions after one step of size with initial values , , respectively. A Runge–Kutta method is called B-stable (or sometimes BN-stable), if the contractivity condition implies for all . Examples of B-stable Runge–Kutta methods are given below. The definition of B-stability extends to arbitrary one-step methods in an obvious way.

Algebraic stability.

A Runge–Kutta method is called algebraically stable if its coefficients satisfy

i) , ;

ii) is positive semi-definite. Algebraic stability plays an important role in the theory of B-convergence. Note that algebraic stability implies B-stability. For non-confluent methods, i.e. for , both concepts are equivalent. The following families of implicit Runge–Kutta methods are algebraically stable and therefore B-stable: Gauss, RadauIA, RadauIIA, LobattoIIIC.

Error growth function.

Let () denote the class of all problems satisfying the one-sided Lipschitz condition

For , this condition is weaker than contractivity and allows trajectories to expand with increasing . For any given real number and step-size , set and denote by the smallest number for which the estimate holds for all problems in . The function is called error growth function. For B-stable Runge–Kutta methods, the error growth function is superexponential, i.e. satisfies and for all , having the same sign. This result can be used in the asymptotic stability analysis of Runge–Kutta methods, see [a5].

Linear multi-step methods.

A linear multi-step discretization of is given by

Let and be the generating polynomials. Using the normalization , the associated one-leg method is defined by

(For a thorough discussion, see [a4].) A one-leg method is called G-stable if there exists a real symmetric positive-definite -dimensional matrix such that any two numerical solutions satisfy for all step-sizes , whenever the problem is contractive (). Here, and

G-stability is closely related to linear stability: If the generating polynomials have no common divisor, then the multi-step method is A-stable if and only if the corresponding one-leg method is G-stable. Thus, the -step BDF method is G-stable. There is also a purely algebraic condition that implies G-stability.

The concepts of G-stability and algebraic stability have been successfully extended to general linear methods, see [a1] and [a4].

Notwithstanding the merits of B- and G-stability, contractive problems have quite simple dynamics. Other classes of problems have been considered that admit a more complex behaviour. For a review, see [a7].

The long-time behaviour of time discretizations of non-linear evolution equations is an active field of research at the moment (1998). Basically, two different approaches exist for the analysis of numerical stability:

a) energy estimates;

b) estimates for the linear problem, combined with perturbation techniques. Whereas energy estimates require algebraic stability on the part of the methods, linear stability (A()-stability) is sufficient for the second approach. (For an illustration of these techniques in connection with convergence, see [a6].) Both approaches offer their merits. The latter, however, is in particular important for methods that are not B-stable, e.g., for linearly implicit Runge–Kutta methods.

References

[a1]	J. Butcher, "The numerical analysis of ordinary differential equations: Runge–Kutta and general linear methods" , Wiley (1987)
[a2]	K. Dekker, J.G. Verwer, "Stability of Runge–Kutta methods for stiff nonlinear differential equations" , North-Holland (1984)
[a3]	G. Dahlquist, "Error analysis for a class of methods for stiff non-linear initial value problems" , Numerical Analysis, Dundee 1975 , Lecture Notes Math. , 506 , Springer (1976) pp. 60–72
[a4]	E. Hairer, G. Wanner, "Solving ordinary differential equations II: Stiff and differential-algebraic problems" , Springer (1996) (Edition: Second, revised)
[a5]	E. Hairer, M. Zennaro, "On error growth functions of Runge–Kutta methods" Appl. Numer. Math. , 22 (1996) pp. 205–216
[a6]	Ch. Lubich, A. Ostermann, "Runge–Kutta approximations of quasi-linear parabolic equations" Math. Comp. , 64 (1995) pp. 601–627
[a7]	A. Stuart, A.R. Humphries, "Model problems in numerical stability theory for initial value problems" SIAM Review , 36 (1994) pp. 226–257