zbMATH — the first resource for mathematics

Structure-preserving doubling algorithms for nonlinear matrix equations. (English) Zbl 1435.65006
Fundamentals of Algorithms 14. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-1-61197-535-2/pbk; 978-1-61197-536-9/ebook). xii, 144 p. (2018).
The main task of this work is to solve the eigenvalue problem \(\mathcal{A}Z-\lambda\mathcal{B}ZM\) where \(\mathcal{A,B}\in\mathbb{C}^{(m+n)\times(m+n)}\) are block matrices, \(Z^T=[I~~X^T]\in\mathbb{C}^{m\times(m+n)}\) and \(M\in\mathbb{C}^{m\times m}\). The doubling strategy refers to iteratively computing \(\mathcal{A}_kZ_k-\lambda\mathcal{B}_kZ_kM^{2^k}\) for \(k=1,2,\ldots\). With a proper choice of the blocks in \(\mathcal{A}\) and \(\mathcal{B}\), the matrix \(X\) will be the solution of one of the following three types of matrix equations \begin{align*} XDX-AX-XB+C&=0, \tag{1}\\ BX(I+GX)^{-1}A+H-X&=0, \tag{2}\\ X+BX^{-1}A&=Q. \tag{3} \end{align*}
In thefirst two cases, a reduction of the blocks into the following standard form is possible: \[ \mathcal{A}_i=\left[\begin{matrix} E_i & 0\\-X_i&I\end{matrix}\right]\text{ and } \mathcal{B}_i=\left[\begin{matrix} I & -Y_i\\0&F_i\end{matrix}\right]\text{ or } \mathcal{B}_i=\left[\begin{matrix} -Y_i & I\\ F_i&0\end{matrix}\right], \] where the second form requires \(m=n\). The challenge is to formulate algorithms that update the blocks \(X_i,Y_i,E_i,F_i\), keeping the structure preserved.
A dual system basically switches the role of \(X_i\) and \(Y_i\) as well as \(E_i\) and \(F_i\) but it requires a different matrix \(N\) replacing \(M\). The algorithms are described including the starting values and the stopping criteria. The convergence analysis is simple in the regular case \(\rho(M)\rho(N)<1\), and is more involved in the critical case \(\rho(M)\rho(N)=1\).
The authors consider Riccati equations as special cases where an extra symmetry on the blocks or other special properties are imposed. Equations of type (3) are more involved and are treated in a separate chapter. In the latter chapters the problems are placed in an application context, and the details of the algorithms and their convergence are explained. Numerical examples illustrate the performance.
This booklet is clearly written and can be used to choose the appropriate algorithm for any given problem. It can be used as a basic text for an advanced course in applied numerical linear algebra.

65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
65F45 Numerical methods for matrix equations
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A24 Matrix equations and identities
Full Text: DOI