A family of Anadromic numerical methods for matrix Riccati differential equations
Authors:
RenCang Li and William Kahan
Journal:
Math. Comp. 81 (2012), 233265
MSC (2010):
Primary 65L05
Published electronically:
May 6, 2011
MathSciNet review:
2833494
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Matrix Riccati Differential Equations (MRDEs) , where , appear frequently throughout applied mathematics, science, and engineering. Naturally, the existing conventional RungeKutta methods and linear multistep methods can be adapted to solve MRDEs numerically. Indeed, they have been adapted. There are a few unconventional numerical methods, too, but they are suited more for timeinvariant MRDEs than timevarying ones. For stiff MRDEs, existing implicit methods which are preferred to explicit ones require solving nonlinear systems of equations (of possibly much higher dimensions than the original problem itself of, for example, implicit RungeKutta methods), and thus they can pose implementation difficulties and also be expensive. In the past, the property of an MRDE which has been most preserved is the symmetry property for a symmetric MRDE; many other crucial properties have been discarded. Besides the symmetry property, our proposed methods also preserve two other important properties  Bilinear Rational Dependence on the initial value, and a Generalized Inverse Relation between an MRDE and its complementary MRDE. By preserving the generalized inverse relation, our methods are accurately able to integrate an MRDE whose solution has singularities. By preserving the property of bilinear dependence on the initial value, our methods also conserve the rank of change to the initial value and a solution's monotonicity property. Our methods are anadromic, meaning if an MRDE is integrated by one of our methods from to and then integrated backward from to using the same method, the value at is recovered in the absence of rounding errors. This implies that our methods are necessarily of even order of convergence. For timeinvariant MRDEs, methods of any even order of convergence are established, while for timevarying MRDEs, methods of order as high as 10 are established; but only methods of order up to 6 are stated in detail. Our methods are semiimplicit, in the sense that there are no nonlinear systems of matrix equations to solve, only linear ones, unlike any preexisting implicit method. Given the availability of high quality codes for linear matrix equations, our methods can easily be implemented and embedded into any application software package that needs a robust MRDE solver. Numerical examples are presented to support our claims.
 1.
M. Abramowitz and I. A. Stegun (editors), Handbook of mathematical functions with formulas, graphs, and mathematical tables, 9th printing ed., Dover Publications, Inc., New York, 1970.
 2.
E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov, and D. Sorensen, LAPACK users' guide, 3rd ed., SIAM, Philadelphia, 1999.
 3.
Uri
M. Ascher, Robert
M. M. Mattheij, and Robert
D. Russell, Numerical solution of boundary value problems for
ordinary differential equations, Prentice Hall Series in Computational
Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1988. MR 1000177
(90h:65120)
 4.
I.
Babuška and V.
Majer, The factorization method for the numerical solution of
twopoint boundary value problems for linear ODEs, SIAM J. Numer.
Anal. 24 (1987), no. 6, 1301–1334. MR 917454
(88m:65114), 10.1137/0724085
 5.
David Bindel, Private communication, 2003.
 6.
David
L. Brown and Jens
Lorenz, A highorder method for stiff boundary value problems with
turning points, SIAM J. Sci. Statist. Comput. 8
(1987), no. 5, 790–805. MR 902743
(90a:34030), 10.1137/0908067
 7.
Roland
Bulirsch and Josef
Stoer, Numerical treatment of ordinary differential equations by
extrapolation methods, Numer. Math. 8 (1966),
1–13. MR
0191095 (32 #8504)
 8.
Philippe
Chartier, Ernst
Hairer, and Gilles
Vilmart, Numerical integrators based on
modified differential equations, Math.
Comp. 76 (2007), no. 260, 1941–1953 (electronic). MR 2336275
(2008g:65082), 10.1090/S0025571807019679
 9.
Chiu
H. Choi and Alan
J. Laub, Constructing Riccati differential equations with known
analytic solutions for numerical experiments, IEEE Trans. Automat.
Control 35 (1990), no. 4, 437–439. MR
1047997, 10.1109/9.52297
 10.
Chiu
H. Choi and Alan
J. Laub, Efficient matrixvalued algorithms for solving stiff
Riccati differential equations, IEEE Trans. Automat. Control
35 (1990), no. 7, 770–776. MR 1058361
(91f:93038), 10.1109/9.57015
 11.
ChiaChun Chou and Robert E. Wyatt, Computational method for the quantum HamiltonJacobi equation: Bound states in one dimension, J. Chem. Phys. 125 (2006), no. 17, 174103.
 12.
E. J. Davison and M. C. Maki, The numerical solution of the matrix differential Riccati equation, IEEE Trans. Automat. Control AC18 (1973), 7173.
 13.
James
W. Demmel, Applied numerical linear algebra, Society for
Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942
(98m:65001)
 14.
P.
Deuflhard, Recent progress in extrapolation methods for ordinary
differential equations, SIAM Rev. 27 (1985),
no. 4, 505–535. MR 812452
(86m:65075), 10.1137/1027140
 15.
Luca
Dieci, Numerical integration of the differential Riccati equation
and some related issues, SIAM J. Numer. Anal. 29
(1992), no. 3, 781–815. MR 1163357
(93b:65093), 10.1137/0729049
 16.
Luca
Dieci and Timo
Eirola, Positive definiteness in the numerical solution of Riccati
differential equations, Numer. Math. 67 (1994),
no. 3, 303–313. MR 1269499
(95b:65099), 10.1007/s002110050030
 17.
Luca
Dieci and Timo
Eirola, Preserving monotonicity in the numerical solution of
Riccati differential equations, Numer. Math. 74
(1996), no. 1, 35–47. MR 1400214
(97j:65114), 10.1007/s002110050206
 18.
Luca
Dieci, Michael
R. Osborne, and Robert
D. Russell, A Riccati transformation method for solving linear
BVPs. I. Theoretical aspects, SIAM J. Numer. Anal. 25
(1988), no. 5, 1055–1073. MR 960866
(90b:65153), 10.1137/0725061
 19.
Luca
Dieci, Michael
R. Osborne, and Robert
D. Russell, A Riccati transformation method for solving linear
BVPs. II. Computational aspects, SIAM J. Numer. Anal.
25 (1988), no. 5, 1074–1092. MR 960867
(90b:65154), 10.1137/0725062
 20.
Gene
H. Golub and Charles
F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins
Studies in the Mathematical Sciences, Johns Hopkins University Press,
Baltimore, MD, 1996. MR 1417720
(97g:65006)
 21.
William
B. Gragg, On extrapolation algorithms for ordinary initial value
problems, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal.
2 (1965), 384–403. MR 0202318
(34 #2191)
 22.
E. Hairer, S. P. Nørsett, and G. Wanner, Solving ordinary differential equations I, 2nd ed., SpringerVerlag, New York, 1992.
 23.
Ernst Hairer, Private communication, December 10, 2009.
 24.
Ernst
Hairer, Christian
Lubich, and Gerhard
Wanner, Geometric numerical integration, 2nd ed., Springer
Series in Computational Mathematics, vol. 31, SpringerVerlag, Berlin,
2006. Structurepreserving algorithms for ordinary differential equations.
MR
2221614 (2006m:65006)
 25.
Nicholas
J. Higham, FORTRAN codes for estimating the onenorm of a real or
complex matrix, with applications to condition estimation, ACM Trans.
Math. Software 14 (1988), no. 4, 381–396
(1989). MR
1062484, 10.1145/50063.214386
 26.
Nicholas
J. Higham, Accuracy and stability of numerical algorithms,
Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA,
1996. MR
1368629 (97a:65047)
 27.
William
Kahan and RenCang
Li, Composition constants for raising the
orders of unconventional schemes for ordinary differential
equations, Math. Comp. 66
(1997), no. 219, 1089–1099.
MR
1423077 (97m:65120), 10.1090/S0025571897008739
 28.
William
Kahan and RenChang
Li, Unconventional schemes for a class of ordinary differential
equations—with applications to the Kortewegde Vries equation,
J. Comput. Phys. 134 (1997), no. 2, 316–331. MR 1458831
(98b:65078), 10.1006/jcph.1997.5710
 29.
Charles
S. Kenney and Roy
B. Leipnik, Numerical integration of the differential matrix
Riccati equation, IEEE Trans. Automat. Control 30
(1985), no. 10, 962–970. MR 804133
(87a:34018), 10.1109/TAC.1985.1103822
 30.
Huibert
Kwakernaak and Raphael
Sivan, Linear optimal control systems, WileyInterscience
[John Wiley & Sons], New YorkLondonSydney, 1972. MR 0406607
(53 #10394)
 31.
Demetrios
G. Lainiotis, Generalized Chandrasekhar algorithms: timevarying
models, IEEE Trans. Automatic Control AC21 (1976),
no. 5, 728–732. MR 0421806
(54 #9800)
 32.
Demetrios
G. Lainiotis, Partitioned Riccati solutions and integrationfree
doubling algorithms, IEEE Trans. Automatic Control
AC21 (1976), no. 5, 677–689. MR 0421805
(54 #9799)
 33.
Alan
J. Laub, Schur techniques for Riccati differential equations,
Feedback control of linear and nonlinear systems (Bielefeld/Rome, 1981),
Lecture Notes in Control and Inform. Sci., vol. 39, Springer, Berlin,
1982, pp. 165–174. MR
837458, 10.1007/BFb0006827
 34.
R.
B. Leipnik, A canonical form and solution for the matrix Riccati
differential equation, J. Austral. Math. Soc. Ser. B
26 (1985), no. 3, 355–361. MR 776321
(86f:34005), 10.1017/S0334270000004550
 35.
RenCang Li and William Kahan, A family of anadromic numerical methods for matrix riccati differential equations, Tech. Report 200920, Department of Mathematics, University of Texas at Arlington, 2009, Available at http://www.uta.edu/math/preprint/.
 36.
, Modifying implicit midpoint rules for linear ordinary differential equation, Tech. Report 201002, Department of Mathematics, University of Texas at Arlington, 2010, Available at http://www.uta.edu/math/preprint/.
 37.
D.
W. Rand and P.
Winternitz, Nonlinear superposition principles: a new numerical
method for solving matrix Riccati equations, Comput. Phys. Comm.
33 (1984), no. 4, 305–328. MR 770094
(86i:58118), 10.1016/00104655(84)90136X
 38.
William
T. Reid, Monotoneity properties of solutions of Hermitian Riccati
matrix differential equations, SIAM J. Math. Anal. 1
(1970), 195–213. MR 0262596
(41 #7202)
 39.
William
T. Reid, Riccati differential equations, Academic Press, New
YorkLondon, 1972. Mathematics in Science and Engineering, Vol. 86. MR 0357936
(50 #10401)
 40.
Ilan
Rusnak, Almost analytic representation for the solution of the
differential matrix Riccati equation, IEEE Trans. Automat. Control
33 (1988), no. 2, 191–193. MR
922796, 10.1109/9.388
 41.
Jeremy
Schiff and S.
Shnider, A natural approach to the numerical integration of Riccati
differential equations, SIAM J. Numer. Anal. 36
(1999), no. 5, 1392–1413 (electronic). MR 1706774
(2000d:34024), 10.1137/S0036142996307946
 42.
Michel
Sorine and Pavel
Winternitz, Superposition laws for solutions of differential matrix
Riccati equations arising in control theory, IEEE Trans. Automat.
Control 30 (1985), no. 3, 266–272. MR 778430
(86e:34013), 10.1109/TAC.1985.1103934
 43.
Lloyd
N. Trefethen and David
Bau III, Numerical linear algebra, Society for Industrial and
Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820
(98k:65002)
 44.
David
R. Vaughan, A negative exponential solution for the matrix Riccati
equation, IEEE Trans. Automatic Control AC14 (1969),
72–75. MR
0250727 (40 #3959)
 45.
David
S. Watkins, Fundamentals of matrix computations, Pure and
Applied Mathematics (New York), WileyInterscience [John Wiley & Sons],
New York, 2002. Second editon. MR 1899577
(2003a:65002)
 46.
M.
I. Zelikin, Control theory and optimization. I, Encyclopaedia
of Mathematical Sciences, vol. 86, SpringerVerlag, Berlin, 2000.
Homogeneous spaces and the Riccati equation in the calculus of variations;
A translation of Homogeneous spaces and the Riccati equation in the
calculus of variations (Russian), “Faktorial”, Moscow, 1998;
Translation by S. A. Vakhrameev. MR 1739679
(2001a:49002)
 1.
 M. Abramowitz and I. A. Stegun (editors), Handbook of mathematical functions with formulas, graphs, and mathematical tables, 9th printing ed., Dover Publications, Inc., New York, 1970.
 2.
 E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov, and D. Sorensen, LAPACK users' guide, 3rd ed., SIAM, Philadelphia, 1999.
 3.
 U. M. Ascher, R. M. Mattheij, and R. D. Russell, Numerical solution of boundary value problems for ordinary differential equations, PrenticeHall, Englewood Cliffs, NJ, 1988. MR 1000177 (90h:65120)
 4.
 I. Babuška and V. Majer, The factorization method for the numerical solution of two point boundary value problems for linear ODE's, SIAM J. Numer. Anal. 24 (1987), 13011334. MR 917454 (88m:65114)
 5.
 David Bindel, Private communication, 2003.
 6.
 David L. Brown and Jens Lorenz, A highorder method for stiff boundary value problems with turning points, SIAM J. Sci. Statist. Comput. 8 (1987), no. 5, 790805. MR 902743 (90a:34030)
 7.
 R. Bulirsch and J. Stoer, Numerical treatment of ordinary differential equations by extrapolation methods, Numer. Math. 8 (1966), 113. MR 0191095 (32:8504)
 8.
 Philippe Chartier, Ernst Hairer, and Gilles Vilmart, Numerical integrators based on modified differential equations, Math. Comp. 76 (2007), no. 260, 19411953. MR 2336275 (2008g:65082)
 9.
 C. H. Choi and A. J. Laub, Constructing Riccati differential equations with known analytic solutions for numerical experiments, IEEE Trans. Automat. Control 35 (1990), 437439. MR 1047997
 10.
 , Efficient matrixvalued algorithm for solving stiff Riccati differential equations, IEEE Trans. Automat. Control 35 (1990), 770776. MR 1058361 (91f:93038)
 11.
 ChiaChun Chou and Robert E. Wyatt, Computational method for the quantum HamiltonJacobi equation: Bound states in one dimension, J. Chem. Phys. 125 (2006), no. 17, 174103.
 12.
 E. J. Davison and M. C. Maki, The numerical solution of the matrix differential Riccati equation, IEEE Trans. Automat. Control AC18 (1973), 7173.
 13.
 J. Demmel, Applied numerical linear algebra, SIAM, Philadelphia, PA, 1997. MR 1463942 (98m:65001)
 14.
 P. Deuflhard, Recent progress in extrapolation methods for ordinary differential equations, SIAM Rev. 27 (1985), 505535. MR 812452 (86m:65075)
 15.
 L. Dieci, Numerical integration of the differential Riccati equation and some related issues, SIAM J. Numer. Anal. 29 (1992), no. 3, 781815. MR 1163357 (93b:65093)
 16.
 L. Dieci and T. Eirola, Positive definiteness in the numerical solution of Riccati differential equations, Numer. Math. 67 (1994), 303313. MR 1269499 (95b:65099)
 17.
 , Preserving monotonicity in the numerical solution of Riccati differential equations, Numer. Math. 74 (1996), 3547. MR 1400214 (97j:65114)
 18.
 L. Dieci, M. R. Osborne, and R. D. Russell, A Riccati transformation method for solving linear BVPs. I: Theoretical aspects, SIAM J. Numer. Anal. 25 (1988), no. 5, 10551073. MR 960866 (90b:65153)
 19.
 , A Riccati transformation method for solving linear BVPs. II: Computational aspects, SIAM J. Numer. Anal. 25 (1988), no. 5, 10741092. MR 960867 (90b:65154)
 20.
 G. H. Golub and C. F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins University Press, Baltimore, Maryland, 1996. MR 1417720 (97g:65006)
 21.
 W. Gragg, On extrapolation methods for ordinary initialvalue problems, SIAM J. Numer. Anal. 2 (1965), 384403. MR 0202318 (34:2191)
 22.
 E. Hairer, S. P. Nørsett, and G. Wanner, Solving ordinary differential equations I, 2nd ed., SpringerVerlag, New York, 1992.
 23.
 Ernst Hairer, Private communication, December 10, 2009.
 24.
 Ernst Hairer, Christian Lubich, and Gerhard Wanner, Geometric numerical integration: Structurepreserving algorithms for ordinary differential equations, 2nd ed., Springer Series in Computational Mathematics, no. 31, Springer, Berlin, 2006. MR 2221614 (2006m:65006)
 25.
 N. J. Higham, FORTRAN codes for estimating the onenorm of a real or complex matrix, with applications to condition estimation, ACM Trans. Math. Software 14 (1988), 381396. MR 1062484
 26.
 , Accuracy and stability of numerical algorithms, SIAM, Philadephia, 1996. MR 1368629 (97a:65047)
 27.
 W. Kahan and RenCang Li, Composition constants for raising the orders of unconventional schemes for ordinary differential equations, Math. Comp. 66 (1997), 10891099. MR 1423077 (97m:65120)
 28.
 , Unconventional schemes for a class of ordinary differential equationswith applications to the Kortewegde Vries, J. Comput. Phys. 134 (1997), 316331. MR 1458831 (98b:65078)
 29.
 C. S. Kenney and R. B. Leipnik, Numerical integration of the differential matrix Riccati equation, IEEE Trans. Automat. Control AC30 (1985), no. 10, 962970. MR 804133 (87a:34018)
 30.
 H. Kwakernaak and R. Sivan, Linear optimal control systems, Wiley Interscience, New York, 1972. MR 0406607 (53:10394)
 31.
 D. G. Lainiotis, Generalized Chandrasekhar algorithms: Timevarying models, IEEE Trans. Automat. Control AC21 (1976), 728732. MR 0421806 (54:9800)
 32.
 , Partitioned Riccati solutions and integrationfree doubling algorithms, IEEE Trans. Automat. Control AC21 (1976), 677689. MR 0421805 (54:9799)
 33.
 A. J. Laub, Schur techniques for Riccati differential equations, Feedback Control of Linear and Nonlinear Systems (New York) (D. Hinrichsen and A. Isidori, eds.), SpringerVerlag, 1982. MR 837458
 34.
 R. B. Leipnik, A canonical form and solution for the matrix Riccati differential equation, Bull. Australian Math. Soc. 26 (1985), 355361. MR 776321 (86f:34005)
 35.
 RenCang Li and William Kahan, A family of anadromic numerical methods for matrix riccati differential equations, Tech. Report 200920, Department of Mathematics, University of Texas at Arlington, 2009, Available at http://www.uta.edu/math/preprint/.
 36.
 , Modifying implicit midpoint rules for linear ordinary differential equation, Tech. Report 201002, Department of Mathematics, University of Texas at Arlington, 2010, Available at http://www.uta.edu/math/preprint/.
 37.
 D. W. Rand and P. Winternitz, Nonlinear superposition principles: A new numerical method for solving matrix Riccati equations, Comput. Phys. Commun. 33 (1984), 305328. MR 770094 (86i:58118)
 38.
 W. T. Reid, Monotoneity properties of solutions of Hermitian Riccati differential equations, SIAM J. Math. Anal. 1 (1970), no. 2, 195213. MR 0262596 (41:7202)
 39.
 , Riccati differential equations, Academic Press, New York, 1972. MR 0357936 (50:10401)
 40.
 I. Rusnak, Almost analytic representation for the solution of the differential matrix Riccati equation, IEEE Trans. Automat. Control 33 (1988), 191193. MR 922796
 41.
 Jeremy Schiff and S. Shnider, A natural approach to the numerical integration of Riccati differential equations, SIAM J. Numer. Anal. 36 (1999), no. 5, 13921413. MR 1706774 (2000d:34024)
 42.
 M. Sorine and P. Winternitz, Superposition laws for solutions of differential matrix Riccati equations arising in control theory, IEEE Trans. Automat. Control AC30 (1985), 266272. MR 778430 (86e:34013)
 43.
 Lloyd N. Trefethen and David Bau, III, Numerical linear algebra, SIAM, Philadelphia, 1997. MR 1444820 (98k:65002)
 44.
 D. R. Vaughan, A negative exponential solution for the matrix Riccati equation, IEEE Trans. Automat. Control AC14 (1969), 7275. MR 0250727 (40:3959)
 45.
 D. S. Watkins, Fundamentals of matrix computations, 2nd ed., John Wiley & Sons, New York, 2002. MR 1899577 (2003a:65002)
 46.
 M. I. Zelikin, Control theory and optimization i: Homogeneous spaces and the Riccati equation in calculus of variations, Encyclopaedia of Mathematical Sciences, vol. 86, Springer, Berlin, 2000, Originally published in Russian in 1998 and translated into English by S. A. Vakhrameev. MR 1739679 (2001a:49002)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2010):
65L05
Retrieve articles in all journals
with MSC (2010):
65L05
Additional Information
RenCang Li
Affiliation:
Department of Mathematics, University of Texas at Arlington, P.O. Box 19408, Arlington, Texas 760190408
Email:
rcli@uta.edu
William Kahan
Affiliation:
Department of Mathematics, and of Electric Engineering & Computer Science, University of California at Berkeley, Berkeley, California 94720
Email:
wkahan@eecs.berkeley.edu
DOI:
http://dx.doi.org/10.1090/S002557182011024981
Keywords:
Matrix Riccati differential equations,
solution singularity,
anadromic numerical method,
group of twosided bilinear rational functions,
generalized inverse relation.
Received by editor(s):
August 25, 2009
Received by editor(s) in revised form:
October 30, 2010
Published electronically:
May 6, 2011
Additional Notes:
This work was supported in part by the National Science Foundation Grant DMS0810506.
Article copyright:
© Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
