Developing a Stable Method for Computing the Matrix Sign Function with Applications to Algebraic Riccati and Sylvester Equations

Subject Areas : International Journal of Industrial Mathematics

پرندوش عطایی دلشاد ¹ , طاهر لطفی ²

1 - Department of Mathematics, Hamedan Branch, Islamic Azad University, Hamedan, Iran.
2 - Department of Mathematics, Hamedan Branch, Islamic Azad University, Hamedan, Iran.

Received: 2020-11-28 Accepted : 2021-12-08 Published : 2022-04-01

Keywords: Algebraic Riccati equation, Matrix sign function, Stable Sylvester ‎equation.‎, Kung-Traub method,

Abstract :

This paper aims to propose a constructive methodology for determining the matrix sign function for a stable variant of the Kung-Traub method. It analytically shows that the new scheme is asymptotically stable. Different numerical experiments compare the new scheme's behavior with the existing matrix iteration of the same type. Finally, the given approach applies to solve the algebraic Riccati equation and the Sylvester equation.

References:

 [1] F. A. Aliev, V. B. Larin, Optimization of Linear Control Systems: Analytical Methods and Computational Algorithms, volume 8 of Stability and Control: Theory, Methods and Applications, Gordon and Breach, 1998.
[2] P. Ataei Delshad, T. Lotfi, On the local convergence of Kung-Traubs two-point method and its dynamics, Appl Math 65 (2020) 379-406. http://dx.doi.org/10. 21136/AM.2020.0322-18/
[3] R. H. Bartels, G. W. Stewart, Solution of the matrix equation AX + XB = C, Algorithm 432. Comm. ACM. 15 (1972) 820-826.
[4] P. Benner, E. S. Quintana-Ort´ı, G. Quintana-Ort´ı, Solving Stable Sylvester Equations via Rational Iterative Schemes,Journal of Scientific Computing 28 (2006) 51-83. http://dx.doi.org/10.1007/s10915-005-9007-2/
[5] P. Benner, Factorized Solution of Sylvester Equations with Applications in Control, In Proc. of the 16th International Symposium on Mathematical Theory of Network and Systems, 2004.
[6] A. Bunse-Gerstner, Computational solution of the algebraic Riccati equation, Journal of the Society of Instrument and Control Engineers (SICE) 38 (1996) 632-639.
[7] S. Barrachina, P. Benner, E. S. QuintanaOrt´ı, Efficient algorithms for generalized algebraic Bernoulli equations based on the matrix sign function,Numerical Algorithms 46 (2007) 351-368.
[8] A. Cayley, A memoir on the theory of matrices, Philos. Trans. Roy. Soc. London 148 (1858) 17-37.
[9] D. Calvetti, L. Reichel, Application of ADI iterative methods to the restoration of noisy images, SIAM J. Matrix Anal. Appl. 17 (1996) 165-186.
[10] A. Cordero, F. Soleymani, J. R.Torregrosa, M. ZakaUllah, Numerically stable improved Chebyshev-Halley type schemes for matrix sign function, Journal of Computational and Applied Mathematics 318 ( 2017) 189-198.
[11] J. P. Charlier, P. Van Dooren, A systolic algorithm for Riccati and Lyapunov equations, Math. Control Signals Systems 2 (1989) 109-136.
[12] L. Dieci, M. R. Osborne, R. D. Russell, A Riccati transformation method for solving linear bvps, I: Theoretical aspects, SIAM J. Numer. Anal. 25 (1988) 1055-1073.
[13] W. H. Enright, Improving the efficiency of matrix operations in the numerical solution of stiff ordinary differential equations, ACM Trans. Math. Softw. 4 (1987) 127-136.
[14] F. Filbir, Computation of the structured stability radius via matrix sign function, Systems and Control Letters 22 (1994) 341-349.
[15] G. H. Golub, S. Nash, C. F. Van Loan, A Hessenberg-Schur method for the problem AX+XB = C, IEEE Trans. Automat. Control AC. 24 (1979) 909-913.
[16] G. H. Golub, C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, third edition, 1996.
[17] M. Ghorbanzadeh, K. Mahdiani, F. Soleymani, T. Lotfi, A Class of Kung-Traub-Type Iterative Algorithms for Matrix Inversion, International Journal of Applied and Computational Mathematics 2 (2016) 641-648.
[18] J. D. Gardiner, A. J. Laub, Parallel algorithms for algebraic Riccati equations, Internat. J. Control 54 (1991) 1317-1333.
[19] J. D. Gardiner, A Stabilized matrix sign function algorithm for solving algebraic Riccati equations, SIAM J. SCI. COMPUT 18 (1997) 1393-1411.
[20] H. V. Henderson, S. R. Searle, On deriving the inverse of a sum of matrices, SIAM Rev. 23 (1981) 53-60.
[21] N. J. Higham, Functions of Matrices: Theory and Computation, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008.
[22] D. Y. Hu, L. Reichel, Application of ADI iterative methods to the restoration of noisy images, Linear Algebra Appl. 172 (1992) 283-313.
[23] B. Iannazzo, Numerical solution of certain nonlinear matrix equations (Ph.D. thesis), Dipartimento di Matematica, Universit`a diPisa, 2007.
[24] B. Iannazzo, A family of rational iterations and its application to the computation of the matrix pth root, SIAM J. Matrix Anal. Appl. 30 (2008) 1445-1462.
[25] F. Khaksar Haghani, A generalized Steffensen’s method for matrix sign function, Applied Mathematics and Computation 260 (2015) 249-256.
[26] C. S. Kenney, A. J. Laub, On scaling Newton’s method for polar decomposition and the matrix sign function, SIAM J. Matrix Anal. Appl. 13 (1992) 688-706.
[27] C. S. Kenney, A. J. Laub, P. M. Papadopoulos, Matrix-sign algorithms for Riccati equations, IMA J. Math. Cont. Infor. 9 (1992) 331-344.
[28] H. T. Kung, J. F. Traub, Optimal order of one-point and multi-point iteration, J. ACM. 21 (1974) 643-651.
[29] N. Kyurkchiev, A. Iliev, A refinement of some overre-laxation algorithms for solving a system of linear equations, Serdica Journal of Computing 7 (2013) 245-256.
[30] T. Lotfi, S. Sharifi, M. Salimi, S. Siegmund, A new class of three-point methods with optimal convergence order eight and its dynamics, Numerical examples 68 (2015) 261-288.
[31] T. Lotfi, P. Bakhtiari, A. Cordero, K. Mahdiani, J. R. Torregrosa, Some new efficient multipoint iterative methods for solving nonlinear systems of equations, International Journal of Computer Mathematics 92 (2015) 1921-1934
[32] M. S. Misrikhanov, V. N. Ryabchenko, A matrix sign function in problems of the analysis and design of linear systems, Automation and Remote Control 69 (2008) 198-222.
[33] M. S. Petkovi´c, B. Neta, L. D. Petkovi´c, J. Dˇzuni´c, Multipoint Methods for Solving Nonlinear Equations, Elsevier, New York, 2013.
[34] J. D. Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function,Reprint of Technical Report No. TR-13, CUED/B-Control, Cambridge University, Engineering Department, 1971.
[35] P. Pandey, C. Kenney, A. J. Laub, parallel algorithm for the matrix sign function, Internat. J. High Speed Computing 2 (1990) 181-191.
[36] A. R. Soheili, F. Toutounian, F. Soleymani, A fast convergent numerical method for matrix sign function with application in SDEs, Journal of Computational and Applied Mathematics 282 (2015) 167-178.
[37] J. J. Sylvester, Additions to the articles, "On a New Class of Theorems," and "On Pascal’s Theorem", Philosophical  Magazine 37 (1850) 363-370.
[38] J. F. Steffensen, Remarks on iteration, Skandinavisk Aktuarietidskrift 16 (1933) 64-72.
[39] M. Trott, The Mathematica Guide book for Numerics, Springer, NewYork, NY, USA, 2006.
[40] E. L. Wachspress, Iterative solution of the Lyapunov matrix equation, Appl. Math. Letters 107 (1988) 87-90.