×

An efficient algorithm for solving general coupled matrix equations and its application. (English) Zbl 1208.65054

The authors present a method for the solution \(X_1, X_2, \dots , X_l,\) (here denoted by solution group of matrices) with \(X_j \in \mathbb{R}^{n_j \times m_j}, j = 1(1)l\), of the general coupled matrix equations
\[ \sum_{j=1}^l A_{ij}X_jB_{ij} = C_i, \quad i = 1(1)l, \]
for given \(A_{ij} \in \mathbb{R}^{p_i \times n_j}\), \(B_{ij} \in \mathbb{R}^{m_j \times q_i}\), and \(C_i \in \mathbb{R}^{p_i \times q_i}\), \(i,j = 1(1)l\).
Well-known special cases of these equations are the Sylvester and Lyapunov matrix equations that play e. g. a role in differential equations, control and stability theory. A large number of papers, which deal with these special cases including the applied methods, are quoted.
Unlike these methods in this paper an iterative algorithm is presented for the quite general coupled matrix equations that include several matrix equations extending them for the solution of large systems of linear equations used the conjugate gradient method. Assuming the consistence of the matrix equations, for any initial matrix group a solution group is found within finite iteration steps without roundoff errors. A least Frobenius norm solution can be derived choosing an appropriate initial matrix group. The authors prove that they can find the optimal approximation group in a Frobenius norm within the solution group set for any initial matrix group \(X_1^{(1)}, X_2^{(1)}, \dots , X_l^{(1)}\).
The algorithm is validated using some simple numerical examples of coupled Sylvester equations taken from the literature. A comparison of the results with Jacobi and Gauss-Seidel methods created by [F. Ding and T. Chen, SIAM J. Control Optim. 44, No. 6, 2269–2284 (2006, Zbl 1115.65035)] for Sylvester equations shows that the proposed conjugate gradient algorithm is more efficient.
Additionally, the application of the proposed method to \((R,S)\)-symmetric and \((R,S)\)-skew symmetric matrices is analyzed.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F10 Iterative numerical methods for linear systems
15A24 Matrix equations and identities

Citations:

Zbl 1115.65035
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aliev, F. A.; Larin, V. B., (Optimization of Linear Control Systems: Analytical Methods and Computational Algorithms. Optimization of Linear Control Systems: Analytical Methods and Computational Algorithms, Stability and Control: Theory, Methods and Applications, vol. 8 (1998), Gordon and Breach) · Zbl 0961.93004
[2] Calvetti, D.; Reichel, L., Application of ADI iterative methods to the restoration of noisy images, SIAM J. Matrix Anal. Appl., 17, 165-186 (1996) · Zbl 0849.65101
[3] Dieci, L.; Osborne, M. R.; Russel, R. D., A Riccati transformation method for solving linear bvps. I: Theoretical aspects, SIAM J. Numer. Anal., 25, 5, 1055-1073 (1988) · Zbl 0664.65074
[4] Enright, W. H., Improving the efficiency of matrix operations in the numerical solution of stiff ordinary differential equations, ACM Trans. Math. Softw., 4, 127-136 (1978) · Zbl 0382.65029
[5] Epton, M. A., Methods for the solution of \(A X D - B X C = E\) and its applications in the numerical solution of implicit ordinary differential equations, BIT, 20, 341-345 (1980) · Zbl 0452.65015
[6] Higham, N. J., Perturbation theory and backward error analysis for \(A X - X B = C\), BIT, 33, 124-136 (1993) · Zbl 0781.65034
[7] Hu, Q.; Cheng, D., The polynomial solution to the Sylvester matrix equation, Appl. Math. Lett., 19, 859-864 (2006) · Zbl 1117.15011
[8] Gantmacher, F. R., Theory of Matrices (1959), Chelsea: Chelsea New York · Zbl 0085.01001
[9] Müller, P. C., Stability of linear mechanical systems with holonomic constraints, Appl. Mech. Rev., 46, 160-164 (1993)
[10] Lancaster, P.; Rodman, L., The Algebraic Riccati Equation (1995), Oxford University Press: Oxford University Press Oxford
[11] Laub, A. J.; Heath, M. T.; Paige, C. C.; Ward, R. C., Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms, IEEE Trans. Automat. Control, 32, 115-122 (1987) · Zbl 0624.93025
[12] Dehghan, M.; Hajarian, M., On the reflexive solutions of the matrix equation \(A X B + C Y D = E\), Bull. Korean Math. Soc., 46, 511-519 (2009) · Zbl 1170.15004
[13] Dehghan, M.; Hajarian, M., A lower bound for the product of eigenvalues of solutions to matrix equations, Appl. Math. Lett., 22, 1786-1788 (2009) · Zbl 1190.15022
[14] M. Dehghan, M. Hajarian, The reflexive and anti-reflexive solutions of a linear matrix equation and systems of matrix equations, Rocky Mountain J. Math. (in press); M. Dehghan, M. Hajarian, The reflexive and anti-reflexive solutions of a linear matrix equation and systems of matrix equations, Rocky Mountain J. Math. (in press) · Zbl 1198.15011
[15] Peng, Y. X.; Hu, X. Y.; Zhang, L., An iteration method for the symmetric solutions and the optimal appromation solution of the matrix equation \(A X B = C\), Appl. Math. Comput., 160, 763-777 (2005)
[16] Peng, Z. H.; Hu, X. Y.; Zhang, L., An efficient algorithm for the least-squares reflexive solution of the matrix equation \(A_1 X B_1 = C_1, A_2 X B_2 = C_2\), Appl. Math. Comput., 181, 988-999 (2006) · Zbl 1115.65048
[17] Peng, Z. Y.; Peng, Y. X., An efficient iterative method for solving the matrix equation \(A X B + C Y D = E\), Numer. Linear Algebra Appl., 13, 473-485 (2006)
[18] Shi, Y.; Ding, F.; Chen, T., Multirate crosstalk identification in xDSL systems, IEEE Trans. Commun., 54, 1878-1886 (2006)
[19] Shi, Y.; Ding, F.; Chen, T., 2-norm based recursive design of transmultiplexers with designable filter length, Circuits Systems Signal Process., 25, 447-462 (2006) · Zbl 1130.94312
[20] Shi, Y.; Ding, F.; Chen, T., Multirate crosstalk identification in xDSL systems, IEEE Transactions on Communication, 54, 1878-1886 (2006)
[21] Shi, Y.; Yu, B., Output feedback stabilization of networked control systems with random delays modeled by Markov chains, IEEE Trans. Automat. Control, 54, 1668-1674 (2009) · Zbl 1367.93538
[22] Shi, Y.; Fang, H.; Yan, M., Kalman filter-based adaptive control for networked systems with unknown parameters and randomly missing outputs, Int. J. Robust Nonlinear Control, 19, 1976-1992 (2009) · Zbl 1192.93118
[23] Wang, Q. W.; Zhang, H. S.; Song, G. J., A new solvable condition for a pair of generalized Sylvester equations, Electron, J. Linear Algebra, 18, 289-301 (2009) · Zbl 1190.15019
[24] Zhou, B.; Duan, G. R., An explicit solution to the matrix equation \(A X - X F = B Y\), Linear Algebra Appl., 402, 345-366 (2005)
[25] Zhou, B.; Yan, Z. B., Solutions to right coprime factorizations and generalized Sylvester matrix equations, Trans. Inst. Meas. Control, 30, 397-426 (2008)
[26] Zhou, B.; Duan, G. R.; Li, Z. Y., Gradient based iterative algorithm for solving coupled matrix equations, Systems Control Lett., 58, 327-333 (2009) · Zbl 1159.93323
[27] Zhou, B.; Li, Z. Y.; Duan, G. R.; Wang, Y., Solutions to a family of matrix equations by using the Kronecker matrix polynomials, Appl. Math. Comput., 212, 327-336 (2009) · Zbl 1181.15020
[28] Guennouni, A. E.; Jbilou, K.; Riquet, A. J., Block Krylov subspace methods for solving large Sylvester equations, Numer. Algorithms, 29, 75-96 (2002) · Zbl 0992.65040
[29] Robbé, M.; Sadkane, M., Use of near-breakdowns in the block Arnoldi method for solving large Sylvester equations, Appl. Numer. Math., 58, 486-498 (2008) · Zbl 1136.65046
[30] Starke, G.; Niethammer, W., SOR for \(A X - X B = C\), Linear Algebra Appl., 154, 355-375 (1991) · Zbl 0736.65031
[31] Lin, Y., Minimal residual methods augmented with eigenvectors for solving Sylvester equations and generalized Sylvester equations, Appl. Math. Comput., 181, 487-499 (2006) · Zbl 1148.65029
[32] Bao, L.; Lin, Y.; Wei, Y., A new projection method for solving large Sylvester equations, Appl. Numer. Math., 57, 521-532 (2007) · Zbl 1118.65028
[33] Kagström, B.; Westin, L., Generalized Schur methods with condition estimators for solving the generalized Sylvester equation, IEEE Trans. Automat. Control, 34, 745-751 (1989) · Zbl 0687.93025
[34] Kagström, B.; Poromaa, P., LAPACK-style algorithms and software for solving the generalized Sylvester equation and estimating the separation between regular matrix pairs, ACM Trans. Math. Software, 22, 78-103 (1996) · Zbl 0884.65031
[35] Wang, Q. W.; Chang, H. X.; Ning, Q., The common solution to six quaternion matrix equations with applications, Appl. Math. Comput., 198, 209-226 (2008) · Zbl 1141.15016
[36] Wang, Q. W.; Zhang, F., The reflexive re-nonnegative definite solution to a quaternion matrix equation, Electron. J. Linear Algebra, 17, 88-101 (2008) · Zbl 1147.15012
[37] Wang, Q. W.; Zhang, H. S.; Yu, S. W., On solutions to the quaternion matrix equation \(A X B + C Y D = E\), Electron. J. Linear Algebra, 17, 343-358 (2008)
[38] Wang, Q. W.; Woude, J. W.; Chang, H. X., A system of real quaternion matrix equations with applications, Linear Algebra Appl., 431, 2291-2303 (2009) · Zbl 1180.15019
[39] Wang, Q. W.; Li, C. K., Ranks and the least-norm of the general solution to a system of quaternion matrix equations, Linear Algebra Appl., 430, 1626-1640 (2009) · Zbl 1158.15010
[40] Wang, Q. W., Bisymmetric and centrosymmetric solutions to systems of real quaternion matrix equations, Comput. Math. Appl., 49, 641-650 (2005) · Zbl 1138.15003
[41] Wang, Q. W., The general solution to a system of real quaternion matrix equations, Comput. Math. Appl., 49, 665-675 (2005) · Zbl 1138.15004
[42] Smith, R. A., Matrix equation, \(X A + B X = C\), SIAM J. Appl. Math., 16, 198-201 (1968) · Zbl 0157.22603
[43] Roberts, J. D., Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Internat. J. Control, 32, 677-687 (1980) · Zbl 0463.93050
[44] Wachspress, E., Iterative solution of the Lyapunov matrix equation, Appl. Math. Lett., 1, 87-90 (1988) · Zbl 0631.65037
[45] Penzl, T., A cyclic low-rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput., 21, 1401-1418 (2000) · Zbl 0958.65052
[46] Gugercin, S.; Sorensen, D. C.; Antoulas, A. C., A modified low-rank Smith method for large-scale Lyapunov equations, Numer. Algor., 32, 27-55 (2003) · Zbl 1034.93020
[47] Dehghan, M.; Hajarian, M., Efficient iterative method for solving the second-order Sylvester matrix equation \(E V F^2 - A V F - C V = B W\), IET Control Theory Appl., 3, 1401-1408 (2009)
[48] Zhou, B.; Duan, G. R., A new solution to the generalized Sylvester matrix equation \(A V - E V F = B W\), Systems Control Lett., 55, 193-198 (2006)
[49] Zhou, B.; Duan, G. R., Solutions to generalized Sylvester matrix equation by Schur decomposition, Internat. J. Systems Sci., 38, 369-375 (2007) · Zbl 1126.65034
[50] Zhou, B.; Li, Z. Y.; Duan, G. R.; Wang, Y., Weighted least squares solutions to general coupled Sylvester matrix equations, J. Comput. Appl. Math., 224, 759-776 (2009) · Zbl 1161.65034
[51] Zhou, B.; Duan, G. R., On the generalized Sylvester mapping and matrix equations, Systems Control Lett., 57, 200-208 (2008) · Zbl 1129.93018
[52] Ding, F.; Chen, T., Gradient based iterative algorithms for solving a class of matrix equations, IEEE Trans. Automat. Control, 50, 1216-1221 (2005) · Zbl 1365.65083
[53] Ding, F.; Chen, T., Iterative least squares solutions of coupled Sylvester matrix equations, Systems Control Lett., 54, 95-107 (2005) · Zbl 1129.65306
[54] Ding, F.; Chen, T., On iterative solutions of general coupled matrix equations, SIAM J. Control Optim., 44, 2269-2284 (2006) · Zbl 1115.65035
[55] Ding, F.; Liu, P. X.; Ding, J., Iterative solutions of the generalized Sylvester matrix equations by using the hierarchical identification principle, Appl. Math. Comput., 197, 41-50 (2008) · Zbl 1143.65035
[56] Ding, F.; Chen, T., Hierarchical gradient-based identification of multivariable discrete-time systems, Automatica, 41, 315-325 (2005) · Zbl 1073.93012
[57] Ding, F.; Chen, T., Hierarchical least squares identification methods for multivariable systems, IEEE Trans. Autom. Contr., 50, 397-402 (2005) · Zbl 1365.93551
[58] Dehghan, M.; Hajarian, M., An iterative algorithm for the reflexive solutions of the generalized coupled Sylvester matrix equations and its optimal approximation, Appl. Math. Comput., 202, 571-588 (2008) · Zbl 1154.65023
[59] Dehghan, M.; Hajarian, M., An iterative algorithm for solving a pair of matrix equations \(A Y B = E, C Y D = F\) over generalized centro-symmetric matrices, Comput. Math. Appl., 56, 3246-3260 (2008) · Zbl 1165.15301
[60] Dehghan, M.; Hajarian, M., Finite iterative algorithms for the reflexive and anti-reflexive solutions of the matrix equation \(A_1 X_1 B_1 + A_2 X_2 B_2 = C\), Math. Comput. Model., 49, 1937-1959 (2009) · Zbl 1171.15310
[61] Dehghan, M.; Hajarian, M., An iterative method for solving the generalized coupled Sylvester matrix equations over generalized bisymmetric matrices, Appl. Math. Modelling, 34, 639-654 (2010) · Zbl 1185.65054
[62] M. Dehghan, M. Hajarian, On the reflexive and anti-reflexive solutions of the generalized coupled Sylvester matrix equations, Int. J. Systems Sci. (in press); M. Dehghan, M. Hajarian, On the reflexive and anti-reflexive solutions of the generalized coupled Sylvester matrix equations, Int. J. Systems Sci. (in press) · Zbl 1196.65081
[63] Dehghan, M.; Hajarian, M., The general coupled matrix equations over generalized bisymmetric matrices, Linear Algebra Appl., 432, 1531-1552 (2010) · Zbl 1187.65042
[64] Reid, J. K., On the method of conjugate gradients for the solution of large sparse systems of linear equations, (Reid, J. K., Large Sparse Sets of Linear Equations (1971), Academic Press: Academic Press New York) · Zbl 0259.65037
[65] Trench, W. F., Minimization problems for \((R, S)\)-symmetric and \((R, S)\)-skew symmetric matrices, Linear Algebra Appl., 389, 23-31 (2004) · Zbl 1059.15019
[66] Trench, W. F., Characterization and properties of \((R, S)\)-symmetric, \((R, S)\)-skew symmetric, and \((R, S)\)-conjugate matrices, SIAM J. Matrix Anal Appl., 26, 748-757 (2005) · Zbl 1080.15022
[67] Chen, H. C., Generalized reflexive matrices: Special properties and applications, SIAM J. Matrix Anal. Appl., 19, 140-153 (1998) · Zbl 0910.15005
[68] Liao, A.; Xie, D. X., Least-squares solution of a class of inverse eigenvalue problems for bisymmetric nonnegative definite matrices, Math. Numer. Sinica, 2, 209-218 (2001) · Zbl 1495.65049
[69] Woodgate, K. G., Least-squares solution of \(F = P G\) over positive semidefinite symmetric \(P\), Linear Algebra Appl., 245, 171-190 (1996) · Zbl 0856.90106
[70] Xie, D. X.; Zhang, L., Least-squares solutions of inverse problems for anti-symmetric matrices, J. Engrg. Math., 4, 25-34 (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.