From Encyclopedia of Mathematics
Revision as of 18:23, 7 February 2011 by (talk) (Importing text file)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

The theory of B-convergence predicts the convergence properties of discretization methods, implicit Runge–Kutta methods in particular, applied to initial value problems for systems of non-linear ordinary differential equations (cf. Runge–Kutta method; Initial conditions; Differential equation, ordinary).

Problem class and historical background.

Concerning the class of ordinary differential equations considered, the underlying assumption is that satisfies a one-sided Lipschitz condition

If (the so-called one-sided Lipschitz constant of ) is of moderate size, the initial value problem is easily proved to be well-conditioned throughout. Of particular interest are stiff problems (cf. also Stiff differential system). Stiffness means that that the underlying ordinary differential equation admits smooth solutions, with moderate derivatives, together with non-smooth ( "transient" ) solutions rapidly converging towards smooth ones. In the stiff case, the conventional Lipschitz constant of inevitably becomes large; therefore the classical error bounds for discretization methods (which depend on ) are of no use for an appropriate characterization and analysis of methods which are able to efficiently integrate a stiff problem. Thus there is a need for a special convergence theory applicable in the presence of stiffness.

The idea to use (instead of ) as the problem-characterizing parameter goes back to [a7], where it was used in the analysis of multi-step methods. The point is that stiffness is often compatible with moderate values of , while . In the same spirit, the concept of B-stability was introduced in [a4], [a5], [a6] in the context of implicit Runge–Kutta methods, and an algebraic criterion on the implicit Runge–Kutta coefficients entailing B-stability was derived ( "algebraic stability in numerical analysisalgebraic stability" ). The notion of -stability enables realistic estimates of the propagation of inevitable perturbations like local discretization errors.

The concept of B-convergence.

In the convergence theory of implicit Runge–Kutta methods applied to stiff problems, stability is essential but also the analysis of local errors is non-trivial: straightforward estimates are affected by and do not reflect reality. For a simple scalar model class, the local error of implicit Runge–Kutta schemes was studied in [a13]. It turned out that the order observed for practically relevant stepsizes is usually reduced compared to smooth, non-stiff situations.

In [a9], [a10], [a11], the convergence properties of implicit Runge–Kutta schemes are studied and the notion of B-convergence is introduced. A B-convergence result is nothing but a realistic global error estimate based on the parameter but unaffected by . Besides relying on B-stability, the essential point are sharp local error estimates which require a special internal stability property called BS-stability. The latter can be concluded from a certain algebraic condition on the Runge–Kutta coefficients ( "diagonal stability in numerical analysisdiagonal stability" ). Explicit error bounds have been derived for Gauss, Radau-IA and Radau-IIA schemes; the corresponding "B-convergence order" is in accordance with the observations from [a13]. B-convergence results for Lobatto-IIIC schemes are given in [a14].

An overview on the "B-theory" of implicit Runge–Kutta methods is presented in [a8]. Another relevant text is [a12].

Further developments.

Concerning the relevance of the B-theory for stiff problems, there remains a gap. The point is that for most stiff problems there is a strong discrepancy between the local and the global condition: Neighbouring solutions may locally strongly diverge, such that the problem is locally ill-conditioned. This is a transient effect, leaving the good global condition unaffected. But it inevitably implies that the one-sided Lipschitz constant is strongly positive (like ). For details, cf. [a1], where it is shown that remains moderate only for a restricted class of stiff problems, namely with Jacobians that are "almost normal" . In general, however, is large and positive, and the B-convergence bounds based on become unrealistically large.

As a consequence, not even linear stiff problems are satisfactorily covered. In [a2] the B-theory is extended to semi-linear stiff problems of the form , where has a smoothly varying eigensystem and is smooth. However, this does not cover a sufficiently large class of non-linear problems. Current work concentrates on a more natural, geometric characterization of stiffness; cf., e.g., [a3].


[a1] W. Auzinger, R. Frank, G. Kirlinger, "A note on convergence concepts for stiff problems" Computing , 44 (1990) pp. 197–208
[a2] W. Auzinger, R. Frank, G. Kirlinger, "An extension of B-convergence for Runge–Kutta methods" Appl. Numer. Math. , 9 (1992) pp. 91–109
[a3] W. Auzinger, R. Frank, G. Kirlinger, "Extending convergence theory for nonlinear stiff problems, Part I" BIT , 36 (1996) pp. 635–652
[a4] K. Burrage, J.C. Butcher, "Stability criteria for implicit Runge–Kutta methods" SIAM J. Numer. Anal. , 16 (1979) pp. 46–57
[a5] J.C. Butcher, "A stability property of implicit Runge–Kutta methods" BIT , 15 (1975) pp. 358–361
[a6] M. Crouzeix, "Sur la B-stabilité des méthodes de Runge–Kutta" Numer. Math. , 32 (1979) pp. 75–82
[a7] G. Dahlquist, "Error analysis for a class of methods for stiff nonlinear initial value problems" , Numerical Analysis , Lecture Notes in Mathematics , 506 (1976) pp. 60–72
[a8] K. Dekker, J.G. Verwer, "Stability of Runge–Kutta methods for stiff nonlinear differential equations" , North-Holland (1984)
[a9] R. Frank, J. Schneid, C.W. Ueberhuber, "The concept of B-convergence" SIAM J. Numer. Anal. , 18 (1981) pp. 753–780
[a10] R. Frank, J. Schneid, C.W. Ueberhuber, "Stability properties of implicit Runge–Kutta methods" SIAM J. Numer. Anal. , 22 (1985) pp. 497–515
[a11] R. Frank, J. Schneid, C.W. Ueberhuber, "Order results for implicit Runge–Kutta methods applied to stiff systems" SIAM J. Numer. Anal. , 22 (1985) pp. 515–534
[a12] E. Hairer, G. Wanner, "Solving ordinary differential equations" , II: stiff and differential-algebraic problems , Springer (1991)
[a13] A. Prothero, A. Robinson, "On the stability and accuracy of one-step methods for solving stiff systems of ordinary differential equations" Math. Comp. , 28 (1974) pp. 145–162
[a14] J. Schneid, "B-convergence of Lobatto IIIC formulas" Numer. Math. , 51 (1987) pp. 229–235
How to Cite This Entry:
B-convergence. W. AuzingerR. Frank (originator), Encyclopedia of Mathematics. URL:
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098