Embedded symmetric nested implicit Runge–Kutta methods of Gauss and Lobatto types for solving stiff ordinary differential equations and Hamiltonian systems

G. Yu. Kulikov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 6, pp. 986-1007

Résumé

A technique for constructing nested implicit Runge–Kutta methods in the class of mono-implicit formulas of this type is studied. These formulas are highly efficient in practice, since the dimension of the original system of differential equations is preserved, which is not possible in the case of implicit multistage Runge–Kutta formulas of the general from. On the other hand, nested implicit Runge–Kutta methods inherit all major properties of general formulas of this form, such as $A$-stability, symmetry, and symplecticity in a certain sense. Moreover, they can have sufficiently high stage and classical orders and, without requiring high extra costs, can ensure dense output of integration results of the same accuracy as the order of the underlying method. Thus, nested methods are efficient when applied to the numerical integration of differential equations of various sorts, including stiff and nonstiff problems, Hamiltonian systems, and invertible equations. In this paper, previously proposed nested methods based on the Gauss quadrature formulas are generalized to Lobatto-type methods. Additionally, a unified technique for constructing all such methods is proposed. Its performance is demonstrated as applied to embedded examples of nested implicit formulas of various orders. All the methods constructed are supplied with tools for local error estimation and automatic variable-stepsize mesh generation based on an optimal stepsize selection. These numerical methods are verified by solving test problems with known solutions. Additionally, a comparative analysis of these methods with Matlab built-in solvers is presented.

Bibliographie

[1] Gaiton A., Fiziologiya krovoobrascheniya: Minutnyi ob'em serdtsa i ego regulyatsiya, Meditsina, M., 1969

[2] Grodinz F., Teoriya regulirovaniya i biologicheskie sistemy, Mir, M., 1966

[3] Marchuk G. I., Matematicheskie metody v immunologii. Vychislitelnye metody i eksperimenty, Nauka, M., 1991 | MR

[4] Nerreter V., Raschet elektricheskikh tsepei na personalnoi EVM, Energoatomizdat, M., 1991

[5] Konyukhova N. B., Lima P. M., Morgado M. L., Soloviev M. B., “Bubbles and droplets in nonlinear physics models: Analysis and numerical simulation of singular nonlinear boundary value problems”, Somr. Maths. Math. Phys., 48:11 (2008), 2018–2058 | MR

[6] Lima P. M., Konyukhova N. B., Chemetov N. V., Sukov A. I., “Analytical-numerical investigation of bubble-type solutions of nonlinear singular problems”, J. Comput. Appl. Math., 189 (2006), 260–273 | MR | Zbl

[7] Kulikov G. Yu., Lima P. M., Morgado M. L., “Analysis and numerical approximation of singular boundary value problems with the p-Laplacian in fluid mechanics”, J. Comput. Appl. Math., 262 (2014), 87–104 | MR | Zbl

[8] Frogerais P., Bellanger J.-J., Senhadji L., “Various ways to compute the continuous-discrete extended Kalman filter”, IEEE Trans. Automat. Control, 57:4 (2012), 1000–1004 | MR

[9] Kulikov G. Yu., Kulikova M. V., “Accurate numerical implementation of the continuous-discrete extended Kalman filter”, IEEE Trans. Automat. Control, 59:1 (2014), 273–279 | MR

[10] Kulikov G. Yu., Kulikova M. V., “Accurate state estimation in the Van der Vusse reaction”, Proc. 2014 IEEE MultiConference on Systems and Control (2014), 759–764

[11] Kulikov G. Yu., Kulikova M. V., “The accurate continuous-discrete extended Kalman filter for continuous-time stochastic systems”, Russian J. Numer. Anal. Math. Modelling, 30:6 (2015)

[12] Kulikova M. V., Kulikov G. Yu., “Square-root accurate continuous-discrete extended Kalman filter for target tracking”, Proc. 52-nd IEEE Conference on Decision and Control (2013), 7785–7790

[13] Kulikova M. V., Kulikov G. Yu., “Adaptive ODE solvers in extended Kalman filtering algorithms”, J. Comput. Appl. Math., 262 (2014), 205–216 | MR | Zbl

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

[15] Shtetter Kh., Analiz metodov diskretizatsii dlya obyknovennykh differentsialnykh uravnenii, Mir, M., 1978 | MR

[16] Rakitskii Yu. V., Ustinov S. M., Chernorutskii N. G., Chislennye metody resheniya zhestkikh sistem, Nauka, M., 1979 | MR

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

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

[19] Arushanyan A. B., Zaletkin S. F., Chislennoe reshenie obyknovennykh differentsialnykh uravnenii na Fortrane, Izd-vo MGU, M., 1990

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

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

[22] Lebedev V. I., Funktsionalnyi analiz i vychislitelnaya matematika, Fizmatlit, M., 2005

[23] Shalashilin V. I., Kuznetsov E. B., Metod prodolzheniya resheniya po parametru i nailuchshaya parametrizatsiya v prikladnoi matematike i mekhanike, Editorial URSS, M., 1999 | MR

[24] Sanz-Serna J. M., Calvo M. P., Numerical Hamilton problems, Chapman Hall, London, 1994 | MR

[25] Hairer E., Lubich C., Wanner G., Geometric numerical integration: structure preserving algorithms for ordinary differential equations, Springer-Verlag, Berlin, 2002 | MR | Zbl

[26] Butcher J. C., Numerical methods for ordinary differential equations, John Wiley Sons, Chichester, 2008 | MR | Zbl

[27] Butcher J. C., “On the implementation of implicit Runge–Kutta methods”, BIT, 16 (1976), 237–240 | MR | Zbl

[28] Bickart T. A., “An efficient solution process for implicit Runge–Kutta methods”, SIAM J. Numer. Anal., 14 (1977), 1022–1027 | MR | Zbl

[29] Cash J. R., “On a class of implicit Runge–Kutta procedures”, J. Inst. Math. Appl., 19 (1977), 455–470 | MR | Zbl

[30] Cash J. R., “On a note of the computational aspects of a class of implicit Runge–Kutta procedures”, J. Inst. Math. Appl., 20 (1977), 425–441 | MR | Zbl

[31] Cash J. R., Singhal A., “Mono-implicit Runge–Kutta formulae for the numerical integration of stiff differential systems”, IMA J. Numer. Anal., 2 (1982), 211–227 | MR | Zbl

[32] Alexander R., “Diagonally implicit Runge–Kutta methods for stiff ODEs”, SIAM J. Numer. Anal., 14 (1977), 1006–1024 | MR

[33] Alt R., Methodes A-stables pour l'integration de systemes differentiels mal conditionnes, PhD thesis, Universite Paris, Paris, 1971

[34] Crouzeix M., Sur I'approximation des equations differentielles operationnelles lineaires par de methodes de Runge–Kutta, PhD thesis, Universite Paris, Paris, 1975

[35] Kurdi M., Stable high order methods for time discretization of stiff differential equations, PhD thesis, University of California, California, 1974 | MR

[36] Skvortsov L. M., “Diagonalno neyavnye FSAL-metody Runge–Kutty dlya zhestkikh i differentsialno-algebraicheskikh sistem”, Matem. modelirovanie, 14:2 (2002), 3–17 | MR

[37] Kvaerno A., “Singly diagonally implicit Runge–Kutta methods with an explicit first stage”, BIT, 44 (2004), 489–502 | MR | Zbl

[38] Skvortsov L. M., “Diagonalno-neyavnye metody Runge–Kutty dlya zhestkikh zadach”, Zh. vychisl. matem. i matem. fiz., 46:12 (2006), 2209–2222 | MR

[39] Skvortsov L. M., “Odnokratno neyavnye diagonalno rasshirennye metody Runge–Kutty chetvertogo poryadka”, Zh. vychisl. matem. i matem. fiz., 54:5 (2014), 755–765 | Zbl

[40] Skvortsov L. M., Kozlov O. S., “Effektivnaya realizatsiya diagonalno-neyavnykh metodov Runge–Kutty”, Matem. modelirovanie, 26:1 (2014), 96–108 | Zbl

[41] Norsett S. P., Semi-explicit Runge–Kutta methods, Report No 6/74, Dept. of Math., University of Trondheim, Trondheim, 1974

[42] 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 | MR

[43] Burrage K., “A special family of Runge–Kutta methods for solving stiff differential equations”, BIT, 18 (1978), 22–41 | MR | Zbl

[44] Burrage K., Butcher J. C., Chipman F. H., “An implementation of singly implicit Runge–Kutta methods”, BIT, 20 (1980), 326–340 | MR | Zbl

[45] Norsett S. P., “Runge–Kutta methods with multiple real eigenvalue only”, BIT, 16 (1976), 388–393 | MR | Zbl

[46] Butcher J. C., Cash J. R., “Towards efficient Runge–Kutta methods for stiff systems”, SIAM J. Numer. Anal., 27 (1990), 753–761 | MR | Zbl

[47] Butcher J. C., Chen D. J. L., “A new type of singly implicit Runge–Kutta methods”, Appl. Numer. Math., 34 (2000), 179–188 | MR | Zbl

[48] Norsett S. P., Wolfbrandt A., “Attainable order of rational approximations to the exponential function with only real poles”, BIT, 17 (1977), 200–208 | MR | Zbl

[49] Van Bokhoven W. M. G., “Efficient higher order implicit one-step methods for integration of stiff differential equations”, BIT, 20 (1980), 34–43 | MR | Zbl

[50] Kulikov G. Yu., Shindin S. K., “On a family of cheap symmetric one5step methods of order four”, Computational Science, ICCS 2006, 6th International Conference (Reading, UK, May 28–31, 2006), v. I, Lecture Notes in Computer Science, 3991, 2006, 781–785

[51] Kulikov G. Yu., Merkulov A. I., Shindin S. K., “Asymptotic error estimate for general Newton-type methods and its application to differential equations”, Russian J. Numer. Anal. Math. Modelling, 22:6 (2007), 567–590 | MR | Zbl

[52] Kulikov G. Yu., Shindin S. K., “Numerical tests with Gauss-type nested implicit Runge–Kutta formulas”, Computational Science, ICCS 2007, 7th International Conference (Beijing, China, May 27–30, 2007), v. I, Lecture Notes in Computer Science, 4487, 2007, 136–143

[53] Kulikov G. Yu., Shindin S. K., “Adaptive nested implicit Runge–Kutta formulas of Gauss type”, Appl. Numer. Math., 59 (2009), 707–722 | MR | Zbl

[54] Kulikov G. Yu., “Automatic error control in the Gauss-type nested implicit Runge–Kutta formula of order 6”, Russian J. Numer. Anal. Math. Modelling, 24:2 (2009), 123–144 | MR | Zbl

[55] Kulikov G. Yu., Kuznetsov E. B., Khrustaleva E. Yu., “O kontrole globalnoi oshibki v neyavnykh gnezdovykh metodakh Runge–Kutty gaussovskogo tipa”, Sib. zh. vychisl. matem., 14:3 (2011), 245–259 | Zbl

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

[57] Lebedev V. I., “Kak reshat yavnymi metodami zhestkie sistemy differentsialnykh uravnenii”, Vychisl. protsessy i sistemy, 8, Nauka, M., 1991, 237–291 | Zbl

[58] Lebedev V. I., Medovikov A. A., “Yavnyi metod vtorogo poryadka tochnosti dlya resheniya zhestkikh sistem obyknovennykh differentsialnykh uravnenii”, Izv. vyssh. uchebn. zavedenii. Matem., 1998, no. 9, 55–63

[59] Lebedev V. I., “Yavnye raznostnye skhemy dlya resheniya zhestkikh zadach s kompleksnym ili razdelimym spektrom”, Zh. vychisl. matem. i matem. fiz., 40:12 (2000), 1801–1812 | MR | Zbl

[60] Verwer J. G., “Explicit Runge–Kutta methods for parabolic partial differential equations”, Appl. Numer. Math., 22:1–3 (1996), 359–379 | MR | Zbl

[61] Sommeijer B. P., Shampine L. F., Verwer J. G., “RKC: An explicit solver for parabolic PDEs”, J. Comput. Appl. Math., 88:2 (1997), 315–326 | MR

[62] Medovikov A. A., “High order explicit methods for parabolic equations”, BIT, 38:1–3 (1998), 372–390 | MR | Zbl

[63] Abdulle A., Medovikov A. A., “Second order Chebyshev methods based on orthogonal polynomials”, Numer. Math., 90:1 (2001), 1–18 | MR | Zbl

[64] Skvortsov L. M., “Yavnyi mnogoshagovyi metod chislennogo resheniya zhestkikh differentsialnykh uravnenii”, Zh. vychisl. matem. i matem. fiz., 47:6 (2007), 959–967 | MR | Zbl

[65] Martin-Vaquero J., Janssen B., “Second-order stabilized explicit Runge–Kutta methods for stiff problems”, Comput. Phys. Communs., 180:10 (2009), 1802–1810 | MR | Zbl

[66] Skvortsov L. M., “Yavnye mnogoshagovye metody s rasshirennymi oblastyami ustoichivosti”, Zh. vychisl. matem. i matem. fiz., 50:9 (2010), 1539–1549 | MR | Zbl

[67] Skvortsov L. M., “Yavnye stabilizirovannye metody Runge–Kutty”, Zh. vychisl. matem. i matem. fiz., 57:7 (2011), 1236–1250

[68] Skvortsov L. M., “Prostoi sposob postroeniya mnogochlenov ustoichivosti dlya yavnykh stabilizirovannykh metodov Runge–Kutty”, Matem. modelirovanie, 23:1 (2011), 81–86 | MR

[69] Bulatov M. V., Tygliyan A. V., Filippov S. S., “Ob odnom klasse odnoshagovykh odnostadiinykh metodov dlya zhestkikh sistem obyknovennykh differentsialnykh uravnenii”, Zh. vychisl. matem. i matem. fiz., 57:7 (2011), 1251–1265

[70] Dahlquist G., Stability and error bounds in the numerical integration of ordinary differential equations, Trans. Royal Inst. of Technology, 130, Stockholm, 1959 | MR | Zbl

[71] Dahlquist G., “A special stability problem for linear multistep methods”, BIT, 3 (1963), 27–43 | MR | Zbl

[72] 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 | MR | Zbl

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