On Iterative Algorithm and Perturbation Analysis for the Nonlinear Matrix Equation

doi:10.1007/s42967-021-00152-3

Abstract

Abstract: In this study, an iterative algorithm is proposed to solve the nonlinear matrix equation \begin{document}$ X+A^{*}{e}^{X}A=I_{n} $\end{document}. Explicit expressions for mixed and componentwise condition numbers with their upper bounds are derived to measure the sensitivity of the considered nonlinear matrix equation. Comparative analysis for the derived condition numbers and the proposed algorithm are presented. The proposed iterative algorithm reduces the number of iterations significantly when incorporated with exact line searches. Componentwise condition number seems more reliable to detect the sensitivity of the considered equation than mixed condition number as validated by numerical examples.

Key words: Mixed condition number, Componentwise condition number, Iterative algorithm, Perturbation analysis, Exact line search

CLC Number:

15A24
15A16

Chacha Stephen Chacha. On Iterative Algorithm and Perturbation Analysis for the Nonlinear Matrix Equation[J]. Communications on Applied Mathematics and Computation, 2022, 4(3): 1158-1174.

TrendMD

References

[1] Al-Mohy, A.H.: Algorithms for the matrix exponential and its Fréchet derivative. PhD Thesis, University of Manchester, UK (2010)
[2] Anderson, W.N., Morley, T.D., Trapp, G.E.: Positive solutions to

\begin{document}$ X=A-BX^{-1}B^{*} $\end{document}

. Linear Algebra Appl. 134, 53–62 (1990). https://doi.org/10.1016/0024-3795(90)90005-W
[3] Bean, N.G., Bright, L., Latouche, G., Pearce, P.K., Pollett, Taylor, P.G.: The quasi-stationary behaviour of quasi-birth-death processes. Ann. Appl. Prob. 7(1), 134–155 (1997)
[4] Chacha, C.S., Kim, H.-M.: Elementwise minimal nonnegative solutions for a class of nonlinear matrix equations. East Asian J. Appl. Math. 9, 665–682 (2019). https://doi.org/10.4208/eajam.300518.120119
[5] Chacha, C.S., Naqvi, S.M.R.S.: Condition numbers of the nonlinear matrix equation

\begin{document}$ X^{p}-A^{*}e^{X}A=I $\end{document}

. J. Funct. Spaces 2018, 1–8 (2018). https://doi.org/10.1155/2018/3291867
[6] Cucker, F., Diao, H., Wei, Y.: On mixed and componentwise condition numbers from Moore-Penrose inverse and linear least squares problems. Math. Comput. 76, 947–963 (2007)
[7] Diao, H.-A.: On condition numbers for least squares with quadric inequality constraint. Comput. Math. Appl. 73(4), 616–627 (2017). https://doi.org/10.1016/j.camwa.2016.12.033
[8] Elmikkawy, M., Atlan, F.: Remarks on two symmetric polynomials and some matrices. Appl. Math. Comput. 219(16), 8770–8778 (2013)
[9] Engwerda, J.C., Ran, A.C.M., Rijkeboer, A.L.: Necessary and sufficient conditions for the existence of a positive definite solutions of the matrix equation

\begin{document}$ X+A^{*}X^{-1}A=Q $\end{document}

. Linear Algebra Appl. 186, 255–275 (1993). https://doi.org/10.1016/0024-3795(93)90295-Y
[10] Gao, D.: On Hermitian positive definite solutions of the nonlinear matrix equation

\begin{document}$ {X-A^{*}e^{X}A = I} $\end{document}

. J. Appl. Math. Comput. 50, 109–116 (2016). https://doi.org/10.1007/s12190-014-0861-7
[11] Gohberg, I., Koltracht, I.: Mixed, componentwise, and structured condition numbers. SIAM. J. Matrix Anal. Appl. 14(3), 688–704 (1993). https://doi.org/10.1137/0614049
[12] Guo, G.H., Lancaster, P.: Iterative solution of two matrix equations. Math. Comput. 68(228), 1589–1603 (1999)
[13] Guo, X.-X., Wu, H.-X.: Two structure-preserving-doubling like algorithms to solve the positive definite solution of the equation

\begin{document}$ X-A^{H}\overline{X}^{-1}A=Q $\end{document}

. Commun. Appl. Math. Comput. 3, 123–135 (2021). https://doi.org/10.1007/s42967-020-00062-w
[14] Han, Y.-H., Kim, H.-M.: Newton’s method for symmetric and bisymmetric solvents of nonlinear matrix equations. J. Korean Math. Soc. 50(4), 755–770 (2013). https://doi.org/10.4134/JKMS.2013.50.4.755
[15] Higham, N., Al-Mohy, A.H.: Computing the Fréchet derivative of the matrix exponential, with an application to condition number estimation. SIAM J. Matrix Anal. Appl. 30, 1639–1657 (2009)
[16] Higham, N.J., Kim, H.-M.: Solving a quadratic matrix equation by Newton’s method with exact line searches. SIAM J. Matrix Anal. Appl. 23, 303–316 (2001)
[17] Ivanov, I.G., Hasanov, V.I., Uhlig, F.: Improved methods and starting values to solve the matrix equations

\begin{document}$ X \pm A^{*}X^{-1}A=I $\end{document}

iteratively. Math. Comput. 74(249), 263–278 (2005)
[18] Jarre, F., Toint, P.L.: Simple examples for the failure of Newton’s method with line search for strictly convex minimization. Math. Program. 158, 23–34 (2016). https://doi.org/10.1007/s10107-015-0913-2
[19] Jia, Z., Zhao, M., Wang, M., Ling, S.: Solvability theory and iteration method for one self-adjoint polynomial matrix equation. J. Appl. Math. ID 681605 (2014). https://doi.org/10.1155/2014/681605
[20] Jia, Z.-G., Zhao, M.-X.: A structured condition number for self-adjoint polynomial matrix equations with applications in linear control. J. Comput. Appl. Math. 331, 208–216 (2018). https://doi.org/10.1016/j.cam.2017.09.046
[21] Liu, L.: Mixed and componentwise condition numbers of nonsymmetric algebraic Riccati equation. Appl. Math. Comput. 218, 7595–7601 (2012). https://doi.org/10.1016/j.amc.2012.01.026
[22] Liu, L.-D., Lu, X.: Two kinds of condition numbers for the quadratic matrix equation. Appl. Math. Comput. 219(16), 8759–8769 (2013)
[23] Long, J.-H., Hu, X.-Y., Zhang, L.: Improved Newton’s method with exact line searches to solve quadratic matrix equation. J. Comput. Appl. Math. 222, 645–654 (2008). https://doi.org/10.1016/j.cam.2007.12.018
[24] Mascarenhas, W.F.: The BFGS method with exact line searches fails for non-convex objective functions. Math. Program. Ser. A 99, 49–61 (2004)
[25] Mathias, R.: Evaluating the Fréchet derivative of the matrix exponential. Numer. Math. 63(1), 213–226 (1992). https://doi.org/10.1007/BF01385857
[26] Phillips, G.M., Taylor, P.J.: Theory and Applications of Numerical Analysis. 2nd edn. Academic Press, London (1996)
[27] Ran, A.C.M., Reurings, M.C.B.: On the nonlinear matrix equation

\begin{document}$ X+A^{*}\mathscr {F}(X)A=Q $\end{document}

?: solutions and perturbation theory. Linear Algebra Appl. 346, 15–26 (2002). https://doi.org/10.1016/S0024-3795(01)00508-0
[28] Relton, S., Higham, N.J.: Higher order Fréchet derivative of matrix functions and their applications. SIAM J. Matrix Anal. Appl. 35(3), 1019–1037 (2014)
[29] Rice, J.R.: A theory of condition. SIAM J. Numer. Anal. 3(2), 287–310 (1966)
[30] Seo, J.H., Kim, H.-M.: Convergence of pure and relaxed Newton methods for solving a matrix polynomial equation arising in stochastic models. Linear Algebra Appl. 440, 34–49 (2014). https://doi.org/10.1016/j.laa.2013.10.043
[31] Wu, C.L., Adler, R.J.: Nonlinear matrix algebra and engineering applications. J. Comput. Appl. Math. I(1), 25–37 (1975)