一類多項(xiàng)式特征值問題的向后誤差分析及應(yīng)用

袁　飛

(廈門大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院,福建 漳州 363105)

本文中考慮如下多項(xiàng)式特征值的向后誤差:

(λkAT+λlA)z,

(1)

其中，k,l∈Z，A是一個(gè)n×n復(fù)矩陣,它只在右上角有一個(gè)m×m塊為非零塊且m≤n/2,λ和z為特征值和特征向量．

本文中引用了參考文獻(xiàn)[1]中多項(xiàng)式特征值問題向后誤差的定義和標(biāo)記，其重要性在于研究算法的穩(wěn)定性和質(zhì)量,它與向前誤差、條件數(shù)之間有如下關(guān)系：向前誤差≤向后誤差×條件數(shù).可以看出向后誤差與條件數(shù)會(huì)直接影響到數(shù)值結(jié)果的誤差估計(jì)．

擾動(dòng)理論和向后誤差分析有廣泛應(yīng)用,如:線性系統(tǒng)[2]、最小二乘問題、一般特征值問題和廣義特征值問題[3-4],以及物理學(xué)中的過阻尼物理系統(tǒng)[5-6]．近年來有很多文獻(xiàn)對(duì)向后誤差的概念進(jìn)行了闡述[1，3-4],Rigal等[2]給出了線性系統(tǒng)的向后誤差分析,Fraysse等[3-4]將向后誤差分析推廣到了多項(xiàng)式特征值問題,Duffin[6]介紹了一些特殊矩陣的向后誤差,Stewart等[7]也提到了一些特殊矩陣的向后誤差．

本文中考慮的多項(xiàng)式特征值(λ4AT+λlA)z=0來自于二次特征值問題(λ2AT+A)z=0,本文中把它推廣到(λkAT+λlA)z=0,在后面的應(yīng)用舉例中,將以鐵軌在高速列車通過時(shí)的振動(dòng)問題的有限元模型中產(chǎn)生的二次特征值問題為例,使用本文中的方法求出該問題的向后誤差．

二次特征值問題在許多領(lǐng)域有豐富的應(yīng)用[8-13],如汽車制動(dòng)系統(tǒng)中的有限元系統(tǒng)[11],地震工程[9],保守結(jié)構(gòu)系統(tǒng)和非保守結(jié)構(gòu)系統(tǒng)分析[12-13],以及最小二乘問題[10]等．但是二次以上特征值問題的向后誤差分析并沒有很好地得到解決,很多問題難以求出向后誤差．

本文中的例子是鐵軌在高速列車通過時(shí)的振動(dòng)問題的有限元模型中產(chǎn)生的二次特征值問題[14-16]．該問題對(duì)文獻(xiàn)[17]的對(duì)稱多項(xiàng)式特征值問題以及文獻(xiàn)[18-22]有很大的推動(dòng)作用．Chu等[18]為該問題建立了有限元模型,Guo等[23]對(duì)該問題提出一種高精度的保持特征值結(jié)構(gòu)的doubling算法,Lu等[24-25]對(duì)該算法進(jìn)行改進(jìn),減少了計(jì)算量和計(jì)算時(shí)間．袁飛等[26]使用回文特征值問題向后誤差的分析方法給出了該問題在文獻(xiàn)[22]的定義下的一種向后誤差．由于參考文獻(xiàn)[1]定義的多項(xiàng)式特征值問題向后誤差更為精準(zhǔn)和實(shí)用,本文中將會(huì)用新的方法,給出該二次特征值問題在參考文獻(xiàn)[1]定義下的向后誤差．

1　相關(guān)定義定理

1.1　一些基本定義

考慮如下非線性特征值問題:

P(λ)z=0,

(2)

其中，矩陣P(λ)的元素為含λ的多項(xiàng)式，形式為

P(λ)=λsAs+λs-1As-1+…+A0,

其中，Al∈Cn×n,l=0，1，…，s,稱P為λ-矩陣[1]．

在本文中,ΔAl表示Al的誤差．為方便表示,令

ΔP(λ)=λsΔAs+λs-1ΔAs-1+…+ΔA0．

對(duì)于復(fù)數(shù)λ,令

本文中使用的2-范數(shù)與文獻(xiàn)[1]相同，為‖x‖2=(x*x)1/2,‖A‖2=max{‖Ax‖2:‖x‖2=1}.

1.2　多項(xiàng)式特征值問題向后誤差的定義

本文中引用了文獻(xiàn)[1]中多項(xiàng)式特征值問題向后誤差的定義和標(biāo)記．

‖ΔAl‖2≤‖El‖2，l=0，1，…，s}.

(3)

(4)

從定理1可以看出,求多項(xiàng)式特征值問題向后誤差的關(guān)鍵在于求出每個(gè)‖ΔAl‖2對(duì)應(yīng)的上界‖El‖2．

作為對(duì)比,給出文獻(xiàn)[26]中定義的二次特征值問題的向后誤差.

對(duì)于P(λ)=λ2AT+λQ+A,定義A0=A,A1=Q,A2=AT．假設(shè)(ξ,ν)是P(λ)的一個(gè)近似特征值對(duì),則定義高速列車震動(dòng)分析問題的向后誤差ΔF:

2　向后誤差的求法

在本節(jié)中,將討論多項(xiàng)式特征值問題(1)的向后誤差:

(λkAT+λlA)z=0,

其中k,l∈Z,A是一個(gè)n×n復(fù)矩陣,它只在右上角有一個(gè)m×m塊為非零塊且m≤n/2,λ和z為特征值和特征向量．

在1.2的討論中可以知道,求該問題向后誤差的關(guān)鍵在于求出‖ΔA‖2的上界．由本文中對(duì)2-范數(shù)的定義可以得到

‖A‖2≤‖A‖F(xiàn).

于是,只需要求出‖ΔA‖F(xiàn)的下界,即可得出‖ΔA‖2的上界．本文中利用如下定理來求式(1)的向后誤差．

定理2對(duì)于多項(xiàng)式特征值問題:

(λkAT+λlA)z=0,

其中

Z+為Z的Moore-Penrose逆矩陣[27]．

證明首先把式(1)寫成分塊矩陣的形式:

(5)

其中A12是m×m塊為非零塊且m≤n/2．把z寫為如下形式：

z=(z1z2z3)T,

其中z1和z3是m×1向量,z2是剩余部分．

于是式(5)可以表示為

(6)

(7)

把它寫成類似式(6)的形式:

(8)

只需求出‖ΔA12‖F(xiàn)的下界即可得到‖ΔA‖F(xiàn)的下界．令

ΔA12={aij},i,j=1,2,…,m,

ai:表示ΔA12的第i行;a:j表示ΔA12的第j列，則式(9)，(10)可分別寫成如下形式：

(11)

(12)

其中，0都表示1×m的一行0,那么整個(gè)系數(shù)矩陣(11)，(12)均是m×m2階的.

把式(11)和(12)整合起來寫成如下方程:

Zx=a,

(13)

其中

證畢．

3　高速列車振動(dòng)分析問題的向后誤差

在高速列車的振動(dòng)分析[23-25]中,P(λ)=λ2AT+λQ+A,對(duì)應(yīng)特征方程為:

(λ2AT+λQ+A)z=0.

(14)

其中A和Q為n×n復(fù)矩陣,且具有如下特殊結(jié)構(gòu):

Q=Kt+iωDt-ω2Mt∈Cn×n,

A=Kc+iωDc-ω2Mc∈Cn×n,

其中，i為虛數(shù)單位,ω>0為外力的頻率,Kt、Dt、Mt、Kc、Dc、Mc都是m×m的分塊實(shí)矩陣,每個(gè)塊有k×k個(gè)元素

A和Q都是m×m的分塊矩陣,每個(gè)塊有k×k個(gè)元素,即n=m×k;此外,Q是塊三對(duì)角陣,A只有位于(1,m)位置的一個(gè)塊為非零塊A13．

本文中僅討論矩陣A的向后誤差．下面將用第2節(jié)中的方法討論此二次特征值問題在第1節(jié)定義下的向后誤差．

(15)

該問題等價(jià)于本文中第2節(jié)中研究的特征多項(xiàng)式(1)在k=2,l=0時(shí)的向后誤差問題．故可直接用第2節(jié)中的方法解決這個(gè)問題．

由第2節(jié)的定理1,可以得到問題(15)的向后誤差為

其中，

其中Z+為Z的Moore-Penrose逆矩陣[27]．

4　數(shù)值實(shí)驗(yàn)

下面給出數(shù)值結(jié)果,本節(jié)使用的矩陣與文獻(xiàn)[23-25]給出的模型相同．用于數(shù)值實(shí)驗(yàn)的3個(gè)矩陣的大小分別為(k,m)=(159,11),(303,19),(705,51)．系數(shù)矩陣A和Q的形式由本文引言部分給出．振動(dòng)頻率ω的取值為1 000．

對(duì)于每組系數(shù)矩陣A和Q對(duì)應(yīng)的二次特征值問題P(λ)z=0,本文中首先使用文獻(xiàn)[5]中的算法求出它的全部近似特征值和特征向量,然后隨機(jī)從中取出一個(gè)近似特征值對(duì)(λ,z)．使用文獻(xiàn)[26]中定理3方法求出該問題的向后誤差表示為ΔF,用本文中的方法求出的向后誤差表示為ΔA,結(jié)果如表1所示，可見ΔA的誤差更小．

表1　數(shù)值實(shí)驗(yàn)結(jié)果

5　結(jié)　論

本文中介紹了多項(xiàng)式特征值問題向后誤差相關(guān)的概念,并且使用文獻(xiàn)[1]中多項(xiàng)式特征值問題向后誤差的定義,求出了特征值問題(λkAT+λlA)z=0的向后誤差．鐵軌在高速列車通過時(shí)的振動(dòng)問題的有限元模型中產(chǎn)生的二次特征值問題(λ2AT+λQ+A)z=0屬于回文二次特征值問題,所以參考文獻(xiàn)[26]中處理回文二次特征值問題的方法來分析該二次特征值問題的向后誤差．由于文獻(xiàn)[1]定義的多項(xiàng)式特征值問題向后誤差更為精準(zhǔn)和實(shí)用,本文中使用新的方法,給出該二次特征值問題在參考文獻(xiàn)[1]定義下的向后誤差．在本文中最后,對(duì)于參考文獻(xiàn)[23-25]給出的3個(gè)鐵軌在高速列車通過時(shí)的振動(dòng)問題的有限元模型,給出了一些數(shù)值實(shí)例,并且與參考文獻(xiàn)[26]給出的向后誤差進(jìn)行對(duì)比．

參考文獻(xiàn)：

[1]TISSEUR F.Backward error and condition of polynomial eigenvalue problems[J].Linear Algebra and Its Applications,2000,309:339-361.

[2]RIGAL J L,GACHES J.On the compatibility of a given solution with the data of a linear system[J].Journal of the ACM,1967,14(3):543-548.

[3]FRAYSSE V,TOUMAZOU V.A note on the normwise perturbation theory for the regular generalized eigenpro-blem[J].Numerical Linear Algebra with Applications,1998,5(1):1-10.

[4]HIGHAM D J,HIGHAM N J.Structured backward error and condition of generalized eigenvalue problems[J].SIAM Journal on Matrix Analysis and Applications,1998,20(2):493-512.

[5]LANCASTER P,SNEDDON I N,STARK M,et al.Lambda-matrices and vibrating systems[M].Oxford:Pergamon Press,1966:187-190.

[6]DUFFIN R J.A minimax theory for overdamped networks[J].J Rat Mech Anal,1954,4(2):221-233.

[7]STEWART G W,SUN J.Matrix perturbation theory[M].London:Academic Press,1990:1-94.

[8]MACKEY D S,MACKEY N,MEHL C,et al.Numerical methods for palindromic eigenvalue problems:computing the anti-triangular schur form[J].Numerical Linear Algebra with Applications,2009,16(1):63-86.

[9]GANDER W,GOLUB G H,VON MATT U.A constrained eigenvalue problem[J].Linear Algebra and Its Applications,1989,114/115:815-839.

[10]CLOUGH R W,MOJTAHEDI S.Earthquake response analysis considering non-proportional damping[J].Earthquake Engineering & Structural Dynamics,1976,4(5):489-496.

[11]KOMZSIK L.Implicit computational solution of genera-lized quadratic eigenvalue problems[J].Finite Elements in Analysis & Design,2001,37(10):799-810.

[12]SMITH H A,SINGH R K,SORENSEN D C.Formulation and solution of the non-linear,damped eigenvalue problem for skeletal systems[J].International Journal for Numerical Methods in Engineering,1995,38(18):3071-3085.

[13]ZHENG Z C,REN G X,WANG W J.A reduction method for large scale unsymmetric eigenvalue problems in structural dynamics[J].J Sound and Vibration,1997,199(2):253-268.

[14]KOMZSIK L.Implicit computational solution of genera-lized quadratic eigenvalue problems[M].Manuscript:the MacNeal-Schwendler Corporation,1998:56-72.

[15]SMITH H A,SINGH R K,SORENSEN D C.Formulation and solution of the non-linear,damped eigenvalue problem for skeletal systems[J].International Journal for Numerical Methods in Engineering,1995,38(18):3071-3085

[16]IPSEN I C F.Accurate eigenvalues for fast trains[J].SIAM News,2004,37(9):1-2.

[17]MACKEY D S,MACKEY N,MEHL C,et al.Structured polynomial eigenvalue problems:good vibrations from good linearizations[J].SIAM Journal on Matrix Analysis and Applications,2006,28(4):1029-1051.

[18]CHU E K W,HWANG T M,LIN W W,et al.Vibration of fast trains,palindromic eigenvalue problems and structure-preserving doubling algorithms[J].Journal of Computational and Applied Mathematics,2008,219(1):237-252.

[19]HUANG T M,LIN W W,QIAN J.Structure-preserving algorithms for palindromic quadratic eigenvalue problems arising from vibration of fast trains[J].SIAM Journal on Matrix Analysis and Applications,2008,30(4):1566-1592.

[20]KRESSNER D,SCHR?DER C,WATKINS D S.Implicit QR algorithms for palindromic and even eigenvalue problems[J].Numerical Algorithms,2009,51(2):209-238.

[21]LANCASTER P,PRELLS U,RODMAN L.Canonical structures for palindromic matrix polynomials[J].Oper Matrices,2007,1(4):469-489.

[22]LI R C,LIN W W,WANG C S.Structured backward error for palindromic polynomial eigenvalue problems[J].Numerische Mathematik,2010,116(1):95-122.

[23]GUO C H,LIN W W.Solving a structured quadratic eigenvalue problem by a structure-preserving doubling algorithm[J].SIAM Journal on Matrix Analysis and Applications，2010,31(5):2784-2801.

[24]LU L,YUAN F,LI R C.A new look at the doubling algorithm for a structured palindromic quadratic eigenvalue problem[J].Numerical Linear Algebra with Applications，2015，22:393-409.

[25]LU L,YUAN F,LI R C.An improved structure-preserving doubling algorithm for a structured palindromic quadratic eigenvalue problem[R].Arlington,UT:University of Texas at Arlington,2014.

[26]袁飛,盧琳璋,李仁倉.一類二次特征值問題的向后誤差分析[J].廈門大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,55(1):97-102.

[27]PENROSE R.A generalized inverse for matrices[J].Mathematical Proceedings of the Cambridge Philosophical Society,1955,51(3):406-413.