Efficient error control in numerical integration of ordinary differential equations and optimal interpolating variable-stepsize peer methods

R. Weiner ; G. Yu. Kulikov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 54 (2014) no. 4, pp. 591-607

Résumé

Automatic global error control of numerical schemes is examined. A new approach to this problem is presented. Namely, the problem is reformulated so that the global error is controlled by the numerical method itself rather than by the user. This makes it possible to find numerical solutions satisfying various accuracy requirements in a single run, which so far was considered unrealistic. On the other hand, the asymptotic equality of local and global errors, which is the basic condition of the new method for efficiently controlling the global error, leads to the concept of double quasi-consistency. This requirement cannot be satisfied within the classical families of numerical methods. However, the recently proposed peer methods include schemes with this property. There exist computational procedures based on these methods and polynomial interpolation of fairly high degree that find the numerical solution in a single run. If the integration stepsize is sufficiently small, the error of this solution does not exceed the prescribed tolerance. The theoretical conclusions of this paper are supported by the numerical results obtained for test problems with known solutions.

Bibliographie

[1] Berezin I. S., Zhidkov N. P., Metody vychislenii, v. 1, Gos. izd-vo fiz.-mat. lit-ry, M., 1962 | MR

[2] Kalitkin H. H., Chislennye metody, Nauka, M., 1978 | MR

[3] Bakhvalov N. S., Zhidkov N. P., Kobelkov G. M., Chislennye metody, Nauka, M., 1987 | MR | Zbl

[4] Dekker K., Verver Ya., Ustoichivost metodov Runge–Kutty dlya zhestkikh nelineinykh differentsialnykh uravnenii, Mir, M., 1988 | MR

[5] Arushanyan O. B., Zaletkin S. F., Chislennoe reshenie obyknovennykh differentsialnykh uravnenii na Fortrane, Izd-vo MGU, M., 1990 | MR | Zbl

[6] Khairer E., Nersett S., Vanner G., Reshenie obyknovennykh differentsialnykh uravnenii. Nezhestkie zadachi, Mir, M., 1990 | MR

[7] Khairer E., Vanner G., Reshenie obyknovennykh differentsialnykh uravnenii. Zhestkie i differentsialno-algebraicheskie zadachi, Mir, M., 1999

[8] Shampine L. F., Watts H. A., “Global error estimation for ordinary differential equations”, ACM Trans. Math. Software, 2 (1976), 172–186 | DOI | MR | Zbl

[9] Stetter H. J., “Global error estimation in ODE-solvers”, Numerical integration of differential equations and large linear systems, Proc. (Bielefeld, 1980), Lecture Notes in Mathematics, 968, ed. Hinze J., 1982, 269–279 | DOI | Zbl

[10] Shampine L. F., “Global error estimation for stiff ODEs”, Lecture Notes in Mathematics, 1066, 1984, 159–168 | DOI | MR | Zbl

[11] Skeel R. D., “Thirteen ways to estimate global error”, Numer. Math., 48 (1986), 1–20 | DOI | MR | Zbl

[12] Skeel R. D., “Global error estimation and the backward differentiation formulas”, Appl. Math. Comput., 31 (1989), 197–208 | DOI | MR | Zbl

[13] Higham D. J., “Global error versus tolerance for explicit Runge–Kutta methods”, IMA J. Numer. Anal., 11 (1991), 457–480 | DOI | MR | Zbl

[14] Novikov E. A., “Otsenka globalnoi oshibki $A$-ustoichivykh metodov resheniya zhestkikh sistem”, Dokl. AN, 343:4 (1995), 452–455 | MR | Zbl

[15] Aïd R., Levacher L., “Numerical investigations on global error estimation for ordinary differential equations”, J. Comput. Appl. Math., 82 (1997), 21–39 | DOI | MR | Zbl

[16] Calvo M., Higham D. J., Montijano J. I., Rández L., “Stepsize selection for tolerance proportionality in explicit Runge–Kutta codes”, Adv. Comput. Math., 7 (1997), 361–382 | DOI | MR | Zbl

[17] Kulikov G. Yu., Shindin S. K., “Ob effektivnom vychislenii asimptoticheski vernykh otsenok lokalnoi i globalnoi oshibok dlya mnogoshagovykh metodov s postoyannymi koeffitsientami”, Zh. vychisl. matem. i matem. fiz., 44:5 (2004), 840–861 | MR

[18] Kulikov G. Yu., Shindin S. K., “O mnogoshagovykh metodakh interpolyatsionnogo tipa s avtomaticheskim kontrolem globalnoi oshibki”, Zh. vychisl. matem. i matem. fiz., 44:8 (2004), 1388–1409 | MR | Zbl

[19] Kulikov G. Yu., Merkulov A. I., “Ob odnoshagovykh kollokatsionnykh metodakh so starshimi proizvodnymi dlya resheniya obyknovennykh differentsialnykh uravnenii”, Zh. vychisl. matem. i matem. fiz., 44:10 (2004), 1782–1807 | MR | Zbl

[20] Kulikov G. Yu., “One-step methods and implicit extrapolation technique for index 1 differential-algebraic systems”, Russian J. Numer. Anal. Math. Model., 19:6 (2004), 527–553 | DOI | MR | Zbl

[21] Shampine L. F., “Error estimation and control for ODEs”, J. Sci. Comput., 25 (2005), 3–16 | DOI | MR | Zbl

[22] Kulikov G. Yu., Shindin S. K., “Global error estimation and extrapolated multistep methods for index 1 differential-algebraic systems”, BIT, 45 (2005), 517–542 | DOI | MR | Zbl

[23] Kulikov G. Yu., Shindin S. K., “One-leg variable-coefficient formulas for ordinary differential equations and local-global step size control”, Numer. Algorithms, 43 (2006), 99–121 | DOI | MR | Zbl

[24] Lang J., Verwer J. G., “On global error estimation and control for initial value problems”, SIAM J. Sci. Comput., 29 (2007), 1460–1475 | DOI | MR | Zbl

[25] Kulikov G. Yu., Khrustaleva E. Yu., “Ob avtomaticheskom upravlenii razmerom shaga i poryadkom v neyavnykh odnoshagovykh ekstrapolyatsionnykh metodakh”, Zh. vychisl. matem. i matem. fiz., 48:9 (2008), 1580–1606 | MR

[26] Kulikov G. Yu., Shindin S. K., “Local and global error estimation in Nordsieck methods”, Russian J. Numer. Anal. Model., 23:6 (2008), 567–595 | MR | Zbl

[27] Kulikov G. Yu., Weiner R., “Global error control in implicit parallel peer methods”, Russian J. Numer. Anal. Math. Model., 25:2 (2010), 131–146 | DOI | MR | Zbl

[28] Kulikov G. Yu., Weiner R., “Global error estimation and control in linearly-implicit parallel two-step peer $\mathrm{W}$-methods”, J. Comput. Appl. Math., 236 (2011), 1226–1239 | DOI | MR | Zbl

[29] Kulikov G. Yu., “Global error control in adaptive Nordsieck methods”, SIAM J. Sci. Comput., 34 (2012), A839–A860 | DOI | MR | Zbl

[30] Kulikov G. Yu., “Cheap global error estimation in some Runge–Kutta pairs”, IMA J. Numer. Anal., 33 (2013), 136–163 | DOI | MR | Zbl

[31] Kulikov G. Yu., “Adaptive Nordsieck formulas with advanced global error control mechanisms”, Russian J. Numer. Anal. Math. Model., 28:4 (2013), 321–352 | DOI | Zbl

[32] Weiner R., Kulikov G. Yu., “Local and global error estimation and control within explicit two-step peer triples”, J. Comput. Appl. Math., 262 (2014), 261–270 | DOI | MR

[33] Kulikov G. Yu., “On quasi-consistent integration by Nordsieck methods”, J. Comput. Appl. Math., 225 (2009), 268–287 | DOI | MR | Zbl

[34] Skeel R. D., “Analysis of fixed-stepsize methods”, SIAM J. Numer. Anal., 13 (1976), 664–685 | DOI | MR | Zbl

[35] Skeel R. D., Jackson L. W., “Consistency of Nordsieck methods”, SIAM J. Numer. Anal., 14 (1977), 910–924 | DOI | MR | Zbl

[36] Burrage K., Butcher J. S., “Non-linear stability of a general class of differential equation methods”, BIT, 20 (1980), 185–203 | DOI | MR | Zbl

[37] Kulikov G. Yu., Weiner R., “Doubly quasi-consistent parallel explicit peer methods with built-in global error estimation”, J. Comput. Appl. Math., 233 (2010), 2351–2364 | DOI | MR | Zbl

[38] Schmitt B. A., Weiner R., “Parallel two-step $\mathrm{W}$-methods with peer variables”, SIAM J. Numer. Anal., 42 (2004), 265–286 | DOI | MR

[39] Weiner R., Schmitt B. A., Podhaisky H., “Parallel “Peer” two-step $\mathrm{W}$-methods and their application to MOL-systems”, Appl. Math., 48 (2004), 425–439 | MR | Zbl

[40] Podhaisky H., Weiner R., Schmitt B. A., “Rosenbrock-type “peer” methods”, Appl. Numer. Math., 53 (2005), 409–420 | DOI | MR | Zbl

[41] Schmitt B. A., Weiner R., Erdmann K., “Implicit parallel peer methods for initial value problems”, Appl. Numer. Math., 53 (2005), 457–470 | DOI | MR | Zbl

[42] Weiner R., Schmitt B. A., Podhaishy H., “Multi-implicit peer two-step $\mathrm{W}$-methods for parallel time integration”, BIT, 45 (2005), 197–217 | DOI | MR | Zbl

[43] Podhaisky H., Weiner R., Schmitt B. A., “Linearly-implicit two-step methods and their implementation in Nordsieck form”, Appl. Numer. Math., 56 (2006), 374–387 | DOI | MR | Zbl

[44] Weiner R., Biermann K., Schmitt B. A., Podhaisky H., “Explicit two-step peer methods”, Comput. Math. Appl., 55 (2008), 609–619 | DOI | MR | Zbl

[45] Weiner R., Schmitt B. A., Podhaisky H., Jebens S., “Superconvergent explicit two-step peer methods”, J. Comput. Appl. Math., 223 (2009), 753–764 | DOI | MR | Zbl

[46] Kulikov G. Yu., Weiner R., “Variable-stepsize interpolating explicit parallel peer methods with inherent global error control”, SIAM J. Sci. Comput., 32:4 (2010), 1695–1723 | DOI | MR | Zbl

[47] Kulikov G. Yu., Shindin S. K., “Nordsieck methods on nonuniform grids: Stability and order reduction phenomenon”, Math. Comput. Simul., 72 (2006), 47–56 | DOI | MR | Zbl

[48] Kulikov G. Yu., “O reshenii problemy poteri tochnosti v kvazisoglasovannykh metodakh Nordsika s peremennym shagom integrirovaniya”, Zh. vychisl. matem. i matem. fiz., 52:11 (2012), 2004–2022 | MR | Zbl

[49] Crouzeix M., Lisbona F. J., “The convergence of variable-stepsize, variable formula, multistep methods”, SIAM J. Numer. Analys., 21 (1984), 512–534 | DOI | MR | Zbl

[50] Prothero A., Robinson A., “On the stability and accuracy of one-step methods for solving stiff systems of ordinary differential equations”, Math. Comp., 24 (1974), 145–162 | DOI | MR