在這篇文章，我們考慮對於迴文二次特徵值問題$(lambda^{2}A_{1}^{ op}+lambda A_{0}+A_{1})x=0$的擾動分析，其中$A_{0}^{ op}=A_{0}$且$A_{0},~A_{1}inBbb{C}^{n imes n}$。二次特徵值問題的係數矩陣，其迴文結構說明出特徵值具有互為倒數的性質。為了有效且精準的計算特徵值問題，保有特徵值互為倒數的特性是相當重要且有意義的。在2006年，Mackey等人在文章[17]中提出對於問題的迴文線性轉換，而在2007年Qian等人在文章[21]中提出另一種線性轉換，將二次迴文特徵值問題擴大轉換成一個辛廣義特徵值問題。此外，在文章[23,21]中提出兩種典型對於解廣義特徵值問題的保結構演算法，其中分別為URV-based方法和Patel-like方法。

近來，Lin在文章[21]中證明出URV-based方法和Patel-like方法的等價關係。這樣一來，利用URV-based方法計算第一種線性轉換的計算量比利用Patel-like方法計算第二種線性轉換的計算量多了兩倍。

基於Tisseur在文章[25]中的想法，我們比較這兩種廣義特徵值問題的條件數。因此我們的結論是計算第二種線性轉換的特徵值比計算第一種線性轉換的特徵值較為準確。

最後，我們數值成果說明以上的結論。

In this paper, we consider the perturbation analysis corresponding to the palindromic quadratic eigenvalue problem $(lambda^{2}A_{1}^{ op}+lambda A_{0}+A_{1})x=0$, where $A_{0}^{ op}=A_{0}$ and $A_{0},A_{1}inBbb{C}^{n imes n}$. The palindromic structure of the coefficient matrices of the quadratic eigenvalue problem shows the reciprocal characteristic for the eigenvalues. In order to solve the eigenvalue problem efficiently and accurately, preserving the reciprocal property is significant. In $2006$, Mackey et al. [17] proposed a palindromic linearization for the problem and in $2007$, Qian et al. [21] gave another linearization for the problem which transfers the palindromic quadratic eigenvalue problem to an enlarged symplectic generalized eigenvalue problem. Moreover, there are two more typical structure-preserving algorithms for solving the corresponding generalized eigenvalue problems in [23,21] which are called URV-based method and Patel-like algorithm, respectively.

Recently, Lin [21] shows an equivalent relation between
URV-based method and Patel-like algorithm so that the computation cost for the first type linearization using URV-based method is about a double more than that for the second type linearization using the Patel-like algorithm.

Based on the idea of Tisseur [25], we compare the condition
number of both generalized eigenvalue problems. We hence conclude that the computed eigenvalues of the second type linearization can be computed more accurate than that of the first type.

Finally, numerical implementation illustrates the conclusions above.

[1].A.L. ANDREW, K.-W.E. CHU AND P. LANCASTER, Derivatives of eigenvalues and eigenvectors of nonlinear eigenvalue problems,SIAM J. Matrix Anal.Applic., (1993), Vol.14, pp. 903-926.

[2].Adam Bojanczyk, Gene H. Golub, and Paul Van Dooren. The periodic schur decomposition:~algorithms and applications, In Proc. SPIE conference, (1992), Vol.1770,

[3].E.K.W. Chu, T.M. Hwang, W.W. Lin and C.T. Wu, Vibration of Fast Trains, Palindromic Eigenvalue Problems and Structure-Preserving Doubling Algorithms, Journal of
Computational and Applied Mathematics, (2008), Vol. 219, pp. 237-252.

[4].R.W. Clough, S. Mojtahedi, Earthquake response analysis considering non-proportional damping, Earthquake Engrg. Struct. Dyn., (1976), Vol.4, pp. 489-496.

[5].A. Hilliges. Numerische L"{o}sung von quadratischen eigenwertproblemen mit Anwendungen in der Schiendynamik.
Master's thesis, Technical University Berlin, Germany, July 2004.

[6].D.J. Higham, N.J. Higham, Structured backward error and condition of generalized eigenvalue problems, SIAM J. Matrix Anal. Appl., (1998), Vol.20(2), pp. 493-512.

[7].John J. Hench and Alan J. Laub. Numerical solution of the discrete-time periodic Riccati equation.IEEE Trans. Automat. Control, (1994), Vol.39(6), pp. 1197-1210.

[8].N.J. Higham, Ren-cang Li, F. Tisseur, Backward error of polynomial eigenproblems solved by linearization, SIAM J. Matrix Anal. Appl., (2007), Vol.29, pp. 1218-1241.

[9].A. Hilliges, C. Mehl, and V. Mehrmann. On the solution of palindromic eigenvalue problems. In Proceedings 4th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS), JYV"{a}skyl"{a}, Finland, 2004.

[10].C.F. Ipsen. Accurate eigenvalues for fast trains. SIAM News, 37, 2004.

[11].Daniel Kressner. An efficient and reliable implementation of the periodic QZ algorithm. In IFAC Workshop on Periodic Control Systems, 2001.

[12].L. Komzsik,Implicit computational solution of generalized quadratic eigenvalue problems,Manuscript, The MacNeal-Schwendler Corporation, 1998.

[13].M. Karow, D. Kressner, F. Tisseur, Structured eigenvalue condition numbers, SIAM J. Matrix Anal.
Appl., (2006), Vol.28, pp. 1052-1068.

[14].W.W. Lin, A new method for computing the closed loop eigenvalues of a discrete-time algebraic Riccati
equation, Linear Algebra Appl., (1987), Vol.6, pp.
157-180.

[15].W.-W. Lin and S.-F. Xu. Convergence analysis of structure-preserving doubling algorithms for Riccati-tye
matrix equations. SIAM Matrix Anal. Appl., (2006), Vol.28(1), pp. 26-39.

[16].D.S. Mackey, N. Mackey, C. Mehl and V. Mehrmann, Vector spaces of linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl., (2006), Vol.28, pp. 971-1004.

[17].D.S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann, Structured polynomial eigenvalue problems: Good
vibrations from good linearizations, SIAM J. Matrix Anal.
Appl., (2006), Vol.28, pp. 1029-1051.

[18].R.V. Patel, On computing the eigenvalues of a symplectic pencil, Linear Algebra Appl., (1993), Vol.188-189, pp. 591-611.

[19].T. Pappas, A.J. Laub and N.R. Sandell, On the numerical solution of the discrete-time algebraic Riccati
equation, IEEE Trans. Auto. Control, (1980), Vol.25, pp.
631-641.

[20].J. Qian, Structure-preserving algorithms for palindromic and even eigenvalue problems, 2007,
preprint.

[21].J. Qian, T.M. Hwang and W.W.Lin, Structure-preserving algorithms for palindromic quadratic eigenvalue problems arising from vibration on fast trains, SIAM J. Matrix Anal. Appl., (2009), Vol.30, pp. 1566-1592.

[22].Robert C. Thompson. Pencils of complex and real symmetric and skew matrices. Linear Algebra Appl., (1991), Vol.147, pp. 323-371.

[23].C. Schr"{o}der. URV decomposition based structured methods for palindromic and even eigenvalue problems, Technical report, TU Berlin, MATHEON, Germany, 2007, preprint 375.

[24].G.W. Stewart and J. Sun. Matrix Perturbation Theory. Academic Press, London, 1990.

[25].F. Tisseur, Backward error and condition of polynomial eigenvalue problems, Linear Algebra Appl., (2000), Vol.309, pp. 339-361.

[26].F. Tisseur and K. Meerbergen, The quadratic eigenvalue problem, SIAM Rev., (2001), Vol.43, pp. 235-286.

[27].Andreas Varga and Paul Van Dooren. Computational methods for periodic systems-an overview. In Proc. of IFAC Workshop on Periodic Control Systems, Como, Italy, (2001), pp. 171-176.