The Computational Complexity of Extrapolation Methods

被引：0

作者：

Ilie, Silvana ^{[1
]}

Corless, Robert M. ^{[2
,3
]}

Essex, Chris ^{[3
]}

机构：

[1] Lund Univ, Ctr Math Sci, Numer Anal, Box 118, SE-22100 Lund, Sweden

[2] Univ Western Ontario, Ontario Res Ctr Comp Algebra, London, ON N6A 5B7, Canada

[3] Univ Western Ontario, Dept Appl Math, London, ON N6A 5B7, Canada

来源：

MATHEMATICS IN COMPUTER SCIENCE | 2009年 / 2卷 / 04期

关键词：

Ordinary differential equations; initial value problems; adaptive step-size control; Holder mean; extrapolation;

D O I：

10.1007/s11786-007-0040-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper analyzes the cost of extrapolation methods for non-stiff ordinary differential equations depending on the number of digits of accuracy requested. Extrapolation of the explicit midpoint rule is applied for various number sequences. We show that for sequences with arithmetic growth, the cost of the method is polynomial in the number of digits of accuracy, while for sequences of numbers with geometric growth, the cost is super-polynomial with respect to the same parameter.

引用

页码：557 / 566

页数：10

共 25 条

[1] NUMERICAL TREATMENT OF ORDINARY DIFFERENTIAL EQUATIONS BY EXTRAPOLATION METHODS [J].

BULIRSCH, R ;

STOER, J .

NUMERISCHE MATHEMATIK, 1966, 8 (01) :1-&

[2]

Butcher J. C., 1987, NUMERICAL ANAL ORDIN

[3] ORDER, STEPSIZE AND STIFFNESS SWITCHING [J].

BUTCHER, JC .

COMPUTING, 1990, 44 (03) :209-220

[4]

Corless R. M., 2001, SIGSAM B COMMUN COMP, V34, P7

[5] A new view of the computational complexity of IVP for ODE [J].

Corless, RM .

NUMERICAL ALGORITHMS, 2002, 31 (1-4) :115-124

[6] Polynomial cost for solving IVP for high-index DAE [J].

Corless, Robert M. ;

Ilie, Silvana .

BIT NUMERICAL MATHEMATICS, 2008, 48 (01) :29-49

[7] ORDER AND STEPSIZE CONTROL IN EXTRAPOLATION METHODS [J].

DEUFLHARD, P .

NUMERISCHE MATHEMATIK, 1983, 41 (03) :399-422

[8] RECENT PROGRESS IN EXTRAPOLATION METHODS FOR ORDINARY DIFFERENTIAL-EQUATIONS [J].

DEUFLHARD, P .

SIAM REVIEW, 1985, 27 (04) :505-535

[9]

Gragg W.B, 1965, SIAM J, V2, P384

[10]

Gragg W. B., 1963, THESIS

← 1 2 3 →