A NEW VERSION OF THE SMITH METHOD FOR SOLVING SYLVESTER EQUATION AND DISCRETE-TIME SYLVESTER EQUATION

Jicheng Li; Ziya Mei; Xu Kong

doi:10.11948/2016040

2016 Volume 6 Issue 2

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2016 > 6(2): 582-599

Next Article Previous Article

Jicheng Li, Ziya Mei, Xu Kong. A NEW VERSION OF THE SMITH METHOD FOR SOLVING SYLVESTER EQUATION AND DISCRETE-TIME SYLVESTER EQUATION[J]. Journal of Applied Analysis & Computation, 2016, 6(2): 582-599. doi: 10.11948/2016040

Citation:

Jicheng Li, Ziya Mei, Xu Kong. A NEW VERSION OF THE SMITH METHOD FOR SOLVING SYLVESTER EQUATION AND DISCRETE-TIME SYLVESTER EQUATION[J]. Journal of Applied Analysis & Computation, 2016, 6(2): 582-599. doi: 10.11948/2016040

A NEW VERSION OF THE SMITH METHOD FOR SOLVING SYLVESTER EQUATION AND DISCRETE-TIME SYLVESTER EQUATION

1 School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an, 710049, People's Republic of China;
2 School of Mathematical Sciences, Liaocheng University, Liaocheng, 252000, People's Republic of China

Fund Project:

Abstract

Abstract

Recently, Xue etc.[37] discussed the Smith method for solving Sylvester equation AX + XB=C, where one of the matrices A and B is at least a nonsingular M-matrix and the other is an (singular or nonsingular) M-matrix. Furthermore, in order to find the minimal non-negative solution of a certain class of non-symmetric algebraic Riccati equations, Gao and Bai[17] considered a doubling iteration scheme to inexactly solve the Sylvester equations. This paper discusses the iterative error of the standard Smith method used in[17] and presents the prior estimations of the accurate solution X for the Sylvester equation. Furthermore, we give a new version of the Smith method for solving discrete-time Sylvester equation or Stein equation AXB + X=C, while the new version of the Smith method can also be used to solve Sylvester equation AX + XB=C, where both A and B are positive definite. We also study the convergence rate of the new Smith method. At last, numerical examples are given to illustrate the effectiveness of our methods.
- Sylvester equation /
- Discrete-time Sylvester equation /
- Smith method /
- Positive definite matrix /
- Convergence
MSC: 65F10;65F50

FullText(HTML)

References

[1]	A.C. Antoulas, Approximation of Large-Scale Dynamical Systems, Advances in Design and Control, SIAM, Philadelphia, PA, 2005. Google Scholar
[2]	L. Bao, Y. Lin, and Y. Wei, Krylov subspace methods for the generalized Sylvester equation, Appl. Math. Comput., 175(2006), 557-573. Google Scholar
[3]	R.H. Bartels, and G.W. Stewart, Algorithm 432:Solution of the matrix equation AX + XB=C, Circ. Syst. Signal Proc., 13(1994), 820-826. Google Scholar
[4]	U. Baur, and P. Benner, Cross-gramian based model reduction for data-sparse systems, Electr. Trans. Num. Anal., 31(2008), 256-270. Google Scholar
[5]	R. Bhatia, and P. Rosenthal, How and why to solve the operator equation AX -XB=Y, Bull. Lond. Math. Soc., 29(1997), 1-21. Google Scholar
[6]	G. Birkhoff, R.S. Varga, and D. Young, Alternating direction implicit methods, Advances in Computing, Academic, New York, 3(1962), 189-273. Google Scholar
[7]	A. Bouhamidi, M. Hached, K. Jbilou, A preconditioned block Arnoldi method for large scale Lyapunov and algebraic Riccati equations, J. Global. Optim., (2015), 1-14. Google Scholar
[8]	D. Calvetti, N. Levenberg, and L. Reichel, Iterative methods for X-AXB=C, J. Comput. Appl. Math., 86(1997), 73-101. Google Scholar
[9]	D. Calvetti, and L. Reichel, Application of ADI iterative methods to the restoration of noisy images, SIAM J. Matrix Anal. Appl., 17(1996), 165-186. Google Scholar
[10]	C.H. Choi and A.J. Laub, Efficient matrix-valued algorithm for solving stiff Riccati differential equations, IEEE Trans. Automat. Control, 35(1990), 770-776. Google Scholar
[11]	B. Datta, Numerical Methods for Linear Control Systems, Elsevier Academic Press, 2004. Google Scholar
[12]	B.N. Datta, and K. Datta, Theoretical and computational aspects of some linear algebra problems in control theory, in:C.I. Byrnes, A. Lindquist (Eds.), Computational and Combinatorial Methods in Systems Theory, Elsevier, Amsterdam, 201-212, 1986. Google Scholar
[13]	L. Dieci, Numerical integration of the differential Riccati equation and some related issues, SIAM J. Numer. Anal., 29(1992), 781-815. Google Scholar
[14]	A. El Guennouni, K. Jbilou, and J. Riquet, Block Krylov subspace methods for solving large Sylvester equations, Numer. Algorithms, 29(2002), 75-96. Google Scholar
[15]	N.S. Ellner, and E.L. Wachspress, Alternating direction implicit iteration for systems with complex spectra, SIAM J. Numer. Anal., 28(1991), 859-870. Google Scholar
[16]	W. Enright, Improving the efficiency of matrix operations in the numerical solution of stiff ordinary differential equations, ACM Trans. Math. Softw., 4(1978), 127-136. Google Scholar
[17]	Y.-H. Gao, and Z.-Z. Bai, On inexact Newton methods based on doubling iteration scheme for non-symmetric algebraic Riccati equations, Numer. Linear Algebra Appl., 18(2010), 325-341. Google Scholar
[18]	G.H. Golub, S. Nash, and C. Van Loan, A Hessenberg-Schur method for the problem AX +XB=C, IEEE Trans. Automat. Contr., AC-24(1979), 909-913. Google Scholar
[19]	G.H. Golub, and C.F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, Maryland, 1996. Google Scholar
[20]	R.A. Horn, and C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1991. Google Scholar
[21]	A.S. Householder, The Theory of Matrices in Numerical Analysis, Blaisdell, New York, 1964. Google Scholar
[22]	D.Y. Hu, and L. Reichel, Krylov-subspace methods for the Sylvester equation, Linear Algebra Appl., 172(1992), 283-313. Google Scholar
[23]	Tiexiang Li, Peter Chang-Yi Weng, Eric King-wah Chu, and Wen-Wei Lin, Large-scale Stein and Lyapunov equations, Smith method, and applications, Numer. Algorithms, 63(2013)(4), 727-752. Google Scholar
[24]	M. Lin, and C. Chinag, A note on Sylvester-type equations, J. Franklin. I., 352(2015)(5), 2171-2186. Google Scholar
[25]	M. Robbe, and M. Sadkane, A convergence analysis of GMRES and FOM methods for Sylvester equations, Numer. Algorithms, 30(2002), 71-89. Google Scholar
[26]	D.E. Rutherford, On the solution of the matrix equation AX+XB=C, Nederl. Akad. Wetensch. Proc. Ser. A., 35(1932), 53-59. Google Scholar
[27]	Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Press, New York, 1995. Google Scholar
[28]	Y. Saad, and M.H. Schultz, GMRES, A generalized minimal residual algorithm for nonsymmetric linear systems, SIAM J. Sci. Statist.Comput, 7(1986), 856-869. Google Scholar
[29]	V. Simoncini, On the numerical solution of AX -XB=C, BIT, 366(1996), 181-193. Google Scholar
[30]	R.A. Smith, Matrix equation XA+BX=C, SIAM J.Appl.Math, 16(1968)(1), 198-201. Google Scholar
[31]	D. Sorensen, and A. Antoulas, The Sylvester equation and approximate balanced reduction, Linear Algebra Appl, 351-352(2002), 671-700. Google Scholar
[32]	G. Starke, and R.S. Varga, A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations, Numer. Math., 64(1993), 213-240. Google Scholar
[33]	J.P. Thiran, M. Matelart, and B.Le Bailly, On the generalized ADI method for the matrix equation X -AXB=C, J. Comput. Appl. Math, 156(2003), 285-302. Google Scholar
[34]	E.L. Wachspress, Iterative solution of the Lyapanov matrix equation, Appl. Math. Lett., 1(1988), 87-90. Google Scholar
[35]	E.L. Wachspress, in:D.R. Kincaid, L.J. Hayes (Eds.), The ADI Minimax Problem for Complex Spectra in Iterative Methods for Large Linear Systems, Academic, San Diego, 251-271, 1990. Google Scholar
[36]	J. Xue, S. Xu, and R.-C. Li, Accurate solutions of M-matrix Sylvester equations, Numer. Math., doi:10.1007/s00211-011-0420-1, 2011. Google Scholar
[37]	B. Zhou, J. Lam, and G.-R. Duan, On Smith-type iterative algorithms for the Stein matrix equation, Appl. Math. Lett., 22(2009)(7), 1038-1044. Google Scholar
[38]	D. Zhou, Guo. Chen, and Q. Cai, On modified HSS iteration methods for continuous Sylvester equations, Appl. Math. Comput., 263(2015), 84-93. Google Scholar
[39]	R. Zhou, X. Wang, and X. Tang, A generalization of the Hermitian and skew-Hermitian splitting iteration method for solving Sylvester equations, Appl. Math. Comput., 271(2015), 609-617. Google Scholar