Improved methods and starting values to solve the matrix equations 𝑋±𝐴*𝑋⁻¹𝐴=𝐼 iteratively

Ivanov, Ivan; Hasanov, Vejdi; Uhlig, Frank

doi:10.1090/S0025-5718-04-01636-9

Improved methods and starting values to solve the matrix equations $X\pm A^*X^{-1}A=I$ iteratively
HTML articles powered by AMS MathViewer

by Ivan G. Ivanov, Vejdi I. Hasanov and Frank Uhlig PDF

Math. Comp. 74 (2005), 263-278 Request permission

Abstract:

The two matrix iterations $X_{k+1}=I\mp A^*X_k^{-1}A$ are known to converge linearly to a positive definite solution of the matrix equations $X\pm A^*X^{-1}A=I$, respectively, for known choices of $X_0$ and under certain restrictions on $A$. The convergence for previously suggested starting matrices $X_0$ is generally very slow. This paper explores different initial choices of $X_0$ in both iterations that depend on the extreme singular values of $A$ and lead to much more rapid convergence. Further, the paper offers a new algorithm for solving the minus sign equation and explores mixed algorithms that use Newton’s method in part.

References

W. N. Anderson Jr., T. D. Morley, and G. E. Trapp, Positive solutions to $X=A-BX^{-1}B^*$, Linear Algebra Appl. 134 (1990), 53–62. MR 1060009, DOI 10.1016/0024-3795(90)90005-W
B. L. Buzbee, G. H. Golub, and C. W. Nielson, On direct methods for solving Poisson’s equations, SIAM J. Numer. Anal. 7 (1970), 627–656. MR 287717, DOI 10.1137/0707049
S. M. El-Sayed, Theorems for the Existence and Computing of Positive Definite Solutions for Two Nonlinear Matrix Equation, Proc. of 25$^{th}$ Spring Conference of the Union of Bulgarian Mathematicians, Kazanlak, 1996, pp.155-161, (in Bulgarian).
Salah M. El-Sayed and André C. M. Ran, On an iteration method for solving a class of nonlinear matrix equations, SIAM J. Matrix Anal. Appl. 23 (2001/02), no. 3, 632–645. MR 1896810, DOI 10.1137/S0895479899345571
Jacob C. Engwerda, André C. M. Ran, and Arie L. Rijkeboer, Necessary and sufficient conditions for the existence of a positive definite solution of the matrix equation $X+A^*X^{-1}A=Q$, Linear Algebra Appl. 186 (1993), 255–275. MR 1217209, DOI 10.1016/0024-3795(93)90295-Y
Jacob C. Engwerda, On the existence of a positive definite solution of the matrix equation $X+A^{\mathsf T}X^{-1}A=I$, Linear Algebra Appl. 194 (1993), 91–108. MR 1243822, DOI 10.1016/0024-3795(93)90115-5
Augusto Ferrante and Bernard C. Levy, Hermitian solutions of the equation $X=Q+NX^{-1}N^*$, Linear Algebra Appl. 247 (1996), 359–373. MR 1412761, DOI 10.1016/0024-3795(95)00121-2
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Chun-Hua Guo and Peter Lancaster, Iterative solution of two matrix equations, Math. Comp. 68 (1999), no. 228, 1589–1603. MR 1651757, DOI 10.1090/S0025-5718-99-01122-9
Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0175290
Ivan G. Ivanov and Salah M. El-sayed, Properties of positive definite solutions of the equation $X+A^*X^{-2}A=I$, Linear Algebra Appl. 279 (1998), no. 1-3, 303–316. MR 1637909, DOI 10.1016/S0024-3795(98)00023-8
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
Olga Taussky, Matrices $C$ with $C^{n}\rightarrow 0$, J. Algebra 1 (1964), 5–10. MR 161865, DOI 10.1016/0021-8693(64)90003-1
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
Xingzhi Zhan, Computing the extremal positive definite solutions of a matrix equation, SIAM J. Sci. Comput. 17 (1996), no. 5, 1167–1174. MR 1404867, DOI 10.1137/S1064827594277041