A new method for computing the closed-loop eigenvalues of a discrete-time algebraic Riccati equation (Q1105990)

A method for computing the closed-loop eigenvalues of the discrete-time algebraic Riccati equation for the optimal regulator problem \[ x_{k+1}=Fx_ k+G_ 1u_ k,\quad x(0)=x_ 0,\quad y_ k=Cx_ k,\quad x_ k\in {\mathbb{R}}\quad n \] \[ J=1/2\sum^{\infty}_{k=0}y^ T_ kQy_ k+u^ T_ kG_ 2u_ k),\quad Q\geq 0,\quad G_ 2>0 \] is given. The symplectic pencil N-\(\lambda\) L is considered, where \[ L=\left[ \begin{matrix} I&G \\ 0&F^ T \end{matrix} \right],\quad W=\left[ \begin{matrix} F&0 \\-H&I \end{matrix} \right],\quad G=G_ 1G_ 2^{-1}G_ 1^ T,\quad H=C^ TQ,\quad C=C^ T_ 1C_ 1 \] with \((F,G_ 1)\), \((F,C_ 1)\) stabilizable and detectable pair, respectively. The closed- loop eigenvalues, i.e. the eigenvalues of the optimally controlled system, are the eigenvalues \(\alpha_ 1,...,\alpha_ n\) with \(| \alpha_ i| <1\) of the pencil \(N-\lambda L\). The QZ algorithm [cf. \textit{C. B. Moler} and \textit{G. W. Stewart}, SIAM J. Numer. Anal. 10, 241-256 (1973; Zbl 0225.65046)] which is very simple and easy to implement uses about \(109 n^ 3\) flops to compute the eigenvalues of the pencil N-\(\lambda\) L, but it ignores the symplectic structure of the pencil. In the article a new method is proposed which uses \((\Gamma,{\tilde \Gamma})\)-orthogonal equivalence transformation. The key idea is to consider, instead of the pencil \(N-\lambda L\), the pencil \(P-\lambda Q\) where \(P=N\quad J\quad L^ T+L\quad J\quad N^ T,\) \(Q=L J L^ T\), \(J=\left[ \begin{matrix} 0&I_ n \\ -I_ n&0 \end{matrix} \right]\) which has the eigenvalues \(\lambda_ j+1/\lambda_ j\), where \(\lambda_ j\in \sigma (N-\lambda L).\) The special structure of the pencil \(P-\lambda Q\) is preserved throughout the algorithm such that the computed eigenvalues occur doubly in reciprocal pairs. The algorithm requires only \(173/6 n^ 3\) flows and \(4n^ 2\) storage. Some examples show that the approximation to the finite eigenvalues are of very high precision.