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.
An -stage Runge–Kutta discretization of , is given by
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.
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.
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.
|[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|
Non-linear stability of numerical methods. Alexander Ostermann (originator), Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Non-linear_stability_of_numerical_methods&oldid=12027