95:
because rational functions are able to approximate functions with poles rather well (compared to polynomial functions), given that there are enough higher-power terms in the denominator to account for nearby poles. While a polynomial interpolation or extrapolation only yields good results if the
103:. However, it has the advantage of requiring only one derivative evaluation per substep (asymptotically for a large number of substeps), and, in addition, as discovered by Gragg, the error of a modified midpoint step of size
96:
nearest pole is rather far outside a circle around the known data points in the complex plane, rational function interpolation or extrapolation can have remarkable accuracy even in the presence of nearby poles.
131:. This makes the modified midpoint method extremely useful to the Bulirsch–Stoer method as the accuracy increases two orders at a time when the results of separate attempts to cross the interval
145:). Furthermore, the modified midpoint method is a modification of the regular midpoint method to make it more stable, but because of the extrapolation this does not really matter (
463:
410:
377:
369:
332:
360:
141:, p. 228), in their discussion of the method, say that rational extrapolation in this case is nearly never an improvement over polynomial interpolation (
543:
428:
25:
252:
229:
319:, implementation of the Bulirsch–Stoer algorithm by Ernst Hairer and Gerhard Wanner (for other routines and license conditions, see their
353:
99:
The modified midpoint method by itself is a second-order method, and therefore generally inferior to fourth-order methods like the
496:
481:
240:
346:
37:
326:
64:
The idea of
Richardson extrapolation is to consider a numerical calculation whose accuracy depends on the used stepsize
33:
395:
506:
400:
29:
476:
100:
80:, fitting a (chosen) analytic function to the resulting points, and then evaluating the fitting function for
486:
491:
471:
522:
390:
338:
433:
52:
because of the importance of a result about the error function of the modified midpoint method, due to
501:
453:
84: = 0, thus trying to approximate the result of the calculation with infinitely fine steps.
36:
in
Richardson-type applications, and the modified midpoint method, to obtain numerical solutions to
448:
92:
418:
298:
204:
17:
91:
as fitting functions for
Richardson extrapolation in numerical integration is superior to using
290:
248:
225:
196:
88:
69:
273:
Shampine, Lawrence F.; Baca, Lorraine S. (1983), "Smoothing the extrapolated midpoint rule",
443:
282:
188:
53:
40:(ODEs) with high accuracy and comparatively little computational effort. It is named after
438:
423:
221:
41:
537:
302:
208:
385:
316:
258:
179:
Deuflhard, Peter (1983), "Order and stepsize control in extrapolation methods",
45:
294:
200:
320:
166:
286:
192:
241:"Section 17.3. Richardson Extrapolation and the Bulirsch-Stoer Method"
342:
239:
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007).
76:, performing the numerical calculation with various values of
216:
Hairer, Ernst; Nørsett, Syvert Paul; Wanner, Gerhard (1993),
218:
Solving ordinary differential equations I: Nonstiff problems
247:(3rd ed.). New York: Cambridge University Press.
167:"Modified Midpoint Method — XMDS2 3.1.0 documentation"
370:
Numerical methods for ordinary differential equations
26:
numerical solution of ordinary differential equations
515:
462:
409:
376:
138:
245:Numerical Recipes: The Art of Scientific Computing
135:with increasing numbers of substeps are combined.
354:
8:
146:
361:
347:
339:
142:
123:each, and expressed as a power series in
87:Bulirsch and Stoer recognized that using
158:
28:which combines three powerful ideas:
7:
50:Gragg–Bulirsch–Stoer (GBS) algorithm
544:Numerical integration (quadrature)
139:Hairer, Nørsett & Wanner (1993
14:
497:Backward differentiation formula
127:, contains only even powers of
101:fourth-order Runge–Kutta method
38:ordinary differential equations
34:rational function extrapolation
1:
48:. It is sometimes called the
482:List of Runge–Kutta methods
560:
335:, implementation in Java.
329:, implementation in C++.
321:Fortran and Matlab Codes
147:Shampine & Baca 1983
30:Richardson extrapolation
22:Bulirsch–Stoer algorithm
487:Linear multistep method
492:General linear methods
472:Exponential integrator
523:Symplectic integrator
507:Gauss–Legendre method
275:Numerische Mathematik
181:Numerische Mathematik
464:Higher-order methods
454:Leapfrog integration
411:Second-order methods
220:, Berlin, New York:
93:polynomial functions
24:is a method for the
477:Runge–Kutta methods
449:Newmark-beta method
396:Semi-implicit Euler
378:First-order methods
333:Apache Commons Math
434:Beeman's algorithm
419:Verlet integration
287:10.1007/BF01390211
193:10.1007/BF01418332
89:rational functions
18:numerical analysis
531:
530:
401:Exponential Euler
254:978-0-521-88068-8
231:978-3-540-56670-0
111:substeps of size
70:analytic function
551:
429:Trapezoidal rule
363:
356:
349:
340:
305:
269:
267:
266:
257:. Archived from
234:
211:
171:
170:
163:
107:, consisting of
72:of the stepsize
68:as an (unknown)
60:Underlying ideas
54:William B. Gragg
559:
558:
554:
553:
552:
550:
549:
548:
534:
533:
532:
527:
511:
458:
439:Midpoint method
424:Velocity Verlet
405:
372:
367:
313:
272:
264:
262:
255:
238:
232:
222:Springer-Verlag
215:
178:
175:
174:
165:
164:
160:
155:
62:
42:Roland Bulirsch
12:
11:
5:
557:
555:
547:
546:
536:
535:
529:
528:
526:
525:
519:
517:
513:
512:
510:
509:
504:
499:
494:
489:
484:
479:
474:
468:
466:
460:
459:
457:
456:
451:
446:
441:
436:
431:
426:
421:
415:
413:
407:
406:
404:
403:
398:
393:
391:Backward Euler
388:
382:
380:
374:
373:
368:
366:
365:
358:
351:
343:
337:
336:
330:
324:
312:
311:External links
309:
308:
307:
281:(2): 165–175,
270:
253:
236:
230:
213:
187:(3): 399–422,
173:
172:
157:
156:
154:
151:
143:Deuflhard 1983
61:
58:
13:
10:
9:
6:
4:
3:
2:
556:
545:
542:
541:
539:
524:
521:
520:
518:
514:
508:
505:
503:
500:
498:
495:
493:
490:
488:
485:
483:
480:
478:
475:
473:
470:
469:
467:
465:
461:
455:
452:
450:
447:
445:
444:Heun's method
442:
440:
437:
435:
432:
430:
427:
425:
422:
420:
417:
416:
414:
412:
408:
402:
399:
397:
394:
392:
389:
387:
384:
383:
381:
379:
375:
371:
364:
359:
357:
352:
350:
345:
344:
341:
334:
331:
328:
327:BOOST library
325:
322:
318:
315:
314:
310:
304:
300:
296:
292:
288:
284:
280:
276:
271:
261:on 2011-08-11
260:
256:
250:
246:
242:
237:
233:
227:
223:
219:
214:
210:
206:
202:
198:
194:
190:
186:
182:
177:
176:
168:
162:
159:
152:
150:
148:
144:
140:
136:
134:
130:
126:
122:
118:
114:
110:
106:
102:
97:
94:
90:
85:
83:
79:
75:
71:
67:
59:
57:
55:
51:
47:
43:
39:
35:
32:, the use of
31:
27:
23:
19:
386:Euler method
278:
274:
263:. Retrieved
259:the original
244:
217:
184:
180:
161:
137:
132:
128:
124:
120:
116:
112:
108:
104:
98:
86:
81:
77:
73:
65:
63:
49:
21:
15:
46:Josef Stoer
265:2011-08-17
153:References
303:121097742
295:0029-599X
209:121911947
201:0029-599X
538:Category
502:Yoshida
516:Theory
323:page).
317:ODEX.F
301:
293:
251:
228:
207:
199:
20:, the
299:S2CID
205:S2CID
291:ISSN
249:ISBN
226:ISBN
197:ISSN
44:and
283:doi
189:doi
149:).
16:In
540::
297:,
289:,
279:41
277:,
243:.
224:,
203:,
195:,
185:41
183:,
115:=
56:.
362:e
355:t
348:v
306:.
285::
268:.
235:.
212:.
191::
169:.
133:H
129:h
125:h
121:n
119:/
117:H
113:h
109:n
105:H
82:h
78:h
74:h
66:h
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.