Perturbation analysis for antitriangular Schur decomposition (Q2910958)

So-called palindromic quadratic eigenvalue problems are arising from vibration analysis of fast trains NEWLINE\[NEWLINE P\left( \lambda\right) x=\left( \lambda^{2}A_{1}+\lambda A_{0} +A_{1}^{T}\right) x=0,\tag{1} NEWLINE\]NEWLINE where \(A_{0}\) and \(A_{1}\) are square \(n\times n\) matrices with \(A_{0} ^{T}=A_{0}.\) The scalar \(\lambda\) and the nonzero vector \(x\) are eigenvalue and eigenvector, respectively. The known algorithm is leading to the following transformation NEWLINE\[NEWLINE\lambda\left(\begin{matrix} A_{1}^{T} & A_{0}-A_{1}\\ A_{1}^{T} & A_{1} \end{matrix} \right) +\left(\begin{matrix} A_{1} & A_{1}\\ A_{0}-A_{1}^{T} & A_{1}^{T} \end{matrix} \right). \tag{2} NEWLINE\]NEWLINE Therefore, the problem is reduced to compute the eigenvalue of a ``matrix pencil'' NEWLINE\[NEWLINE \lambda Z+Z^{T}. NEWLINE\]NEWLINE The known approach is to linearize \((1)\) to the matrix pencil and to compute the antitriangular decomposition of \(Z\). This is not satisfactory as the \(QR\)-algorithm has computational complexity of \(O\left( n^{4}\right) \). (Another method for palindromic quadratic and linear problems is the structure preserving doubling algorithm.)NEWLINENEWLINEUp to this point, in the literature, a perturbation analysis of Schur decomposition was studied and extended to matrix pencils. Moreover, perturbation bounds for a periodic Schur decomposition was previously shown. The main contribution here is to provide a perturbation bound for an antitriangular Schur decomposition. This is equivalent to analyze the perturbation of the structured generalized Schur decomposition of \(\lambda Z+Z^{T}\).NEWLINENEWLINELet \(Z\) be a complex \(n\times n\) matrix. The factoring \(Z=\overline{U} MU^{H}\) is called an antitriangular Schur decomposition of \(Z\) if \(U\) is a unitary \(n\times N\) matrix and \(M\) is an \(N\times n\) antitriangular matrix, i.e. \(m_{i,j}=0\) for \(i+j\leq n\), where\(\overline{U}\) and \(U^{H}\) denote the conjugate and conjugate transpose. The perturbation bounds of such a decomposition are given and proven to depend inversely to NEWLINE\[NEWLINE f\left( M\right) :=\min_{\left\| X_{N}\right\| _{F}=1}\left\| (\mathrm{Aup}(MX_{L}-\overline{X}_{U}M),\mathrm{Aup}(M^{T}X_{L}-\overline{X}_{U}M^{T} )\right\| _{F}, NEWLINE\]NEWLINE where \(X_{L}\),\ X\(_{U}\) are strictly lower and upper triangular parts of \(X\); \(X_{N}=X_{L}+X_{U}\), Aup\(\left( Y\right) \) is the strictly upper antitriangular part of \(Y\). The value \(\sqrt{2}/f\left( M\right) \) can be used to characterize the condition number of the decomposition.