實對稱區(qū)間矩陣特征值確界的交錯定理及其應(yīng)用

成龍 ,李耀堂

(1.重慶對外經(jīng)貿(mào)學(xué)院數(shù)學(xué)與計算機(jī)學(xué)院,重慶 401520;2.云南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,云南 昆明 650091)

1.引言

在許多科學(xué)和工程問題中,由于測量誤差、計算誤差和數(shù)據(jù)變化等因素都會導(dǎo)致描述該問題的數(shù)學(xué)系統(tǒng)中的參數(shù)難以精確確定.如何解決不確定參數(shù)對系統(tǒng)特性的影響就顯得尤為重要.此時,區(qū)間分析就發(fā)揮了其強(qiáng)大的作用.[1-2]區(qū)間分析是考慮在各種因素影響的條件下,給出一個包含真實結(jié)果的區(qū)間.1966年,MOORE在文[1]中奠定了區(qū)間分析的理論基礎(chǔ).隨后,區(qū)間分析被廣泛應(yīng)用于化學(xué)與結(jié)構(gòu)工程、控制電路設(shè)計、計算機(jī)圖形學(xué)和行為生態(tài)學(xué)等領(lǐng)域.[1-3]

在許多實際應(yīng)用中,由于面對系統(tǒng)的各種不確定因素,系統(tǒng)的雅可比矩陣的元素往往取值于某個實區(qū)間中,即系統(tǒng)的雅可比矩陣為區(qū)間矩陣,且系統(tǒng)的特性由該區(qū)間矩陣的特征值決定.因此區(qū)間矩陣特征值界的估計問題吸引了眾多學(xué)者的關(guān)注和研究.[4-21]例如: 1982年,DEIF在文[11]中利用特征值不等式和非線性規(guī)劃理論,在特征向量分量符號不變的條件下,得到了一類特殊的區(qū)間矩陣――實對稱區(qū)間矩陣特征值的算法;2010年,HLAD′IK等學(xué)者在文[15]中給出了實區(qū)間矩陣特征值界的估計;2017年,HLAD′IK在文[16]中進(jìn)一步給出了計算特征向量分量符號不變的實對稱三對角區(qū)間矩陣各特征值確界的算法.但是,在應(yīng)用中特征向量分量符號不變的條件往往很難滿足,因此這些算法難以應(yīng)用.另一方面,文[17]中證明了精確計算實對稱區(qū)間矩陣各特征值的確界是NP-難問題.因此,尋找實對稱區(qū)間矩陣各特征值界的估計算法具有重要意義.本文將在建立實對稱區(qū)間矩陣特征值確界的交錯定理的基礎(chǔ)上,給出實對稱三對角區(qū)間矩陣各特征值界的估計算法.

2.預(yù)備知識

為了敘述方便,本節(jié)給出實對稱區(qū)間矩陣的相關(guān)概念和符號,以及與實對稱矩陣特征值相關(guān)的預(yù)備知識.

定義2.1[22]設(shè)A=(aij)∈Rm×n,B=(bij)∈Rm×n,對任意的i=1,2,···,m;j=1,2,···,n,若aij ≥0,則記A ≥0;若aij>0,則記A>0;若aij-bij ≥0,則記A ≥B;若aij-bij>0,則記A>B.

1966年,MOORE首次提出區(qū)間矩陣的概念,即元素為閉區(qū)間的矩陣,其定義如下.

稱Ak為A的k階主子矩陣;稱為AI的k階主子區(qū)間矩陣.

定義2.5設(shè)AS是實對稱區(qū)間矩陣,定義AS的k階主子區(qū)間矩陣為

定義2.6[11]設(shè)AI是n階區(qū)間矩陣,稱AI中所有矩陣的特征值組成的集合為區(qū)間矩陣AI的特征值,記為λ(AI),即

一般來講,n階區(qū)間矩陣AI的特征值λ(AI)是復(fù)數(shù)域上的一個集合.但對于實對稱區(qū)間矩陣AS,因為AS中的矩陣都是實對稱矩陣,再由實對稱矩陣的特征值都是實數(shù)知λ(AS)為實數(shù)域上的集合.下面討論λ(AS)在實軸上的分布情況.

在下文中,實對稱矩陣A=(aij)n×n的特征值都按升序排列,即

引理2.1[11]若記λi(AS)=則λi(AS)為閉區(qū)間,即

注2.1稱λi(AS)為實對稱區(qū)間矩陣AS的第i個特征值區(qū)間,簡稱為AS的第i個特征值;稱(AS),λi(AS)分別為AS的第i個特征值的上確界和下確界.

注2.2由引理2.1知實對稱區(qū)間矩陣AS的特征值由n個閉區(qū)間的并集組成,即

由于實對稱區(qū)間矩陣AS的第i個特征值λi(AS)和第j個特征值λj(AS)(i=j)都為實數(shù)軸上的區(qū)間,故可能重合,并且精確計算AS各特征值的確界是NP-難問題.[17]本文研究AS各特征值的確界,以便給出AS各特征值界的估計.

為討論方便,下面先回憶實對稱矩陣特征值的交錯定理和Weyl 定理.

引理2.2[22](實對稱矩陣特征值的交錯定理) 設(shè)A ∈Rn×n為對稱矩陣,Sn-1(A)表示A的所有n-1階主子矩陣構(gòu)成的集合,則對任意An-1∈Sn-1(A),有

由引理2.2可直接得到如下推論.

推論2.1[22]設(shè)對稱矩陣A ∈Rn×n,Sk(A)表示A的所有k階主子矩陣構(gòu)成的集合,則對任意Ak ∈Sk(A),有

推論2.1說明實對稱矩陣A的所有k階主子矩陣的最大特征值中的最小者是矩陣A的第k個特征值的上界.

引理2.3[22](實對稱矩陣特征值的Weyl定理) 設(shè)A,B ∈Rn×n為對稱矩陣,則對任意的i ∈N,有

3.實對稱區(qū)間矩陣特征值確界的交錯定理

引理2.2給出了實對稱矩陣特征值的交錯定理,那么實對稱區(qū)間矩陣的特征值是否具有類似的結(jié)論呢? 下面討論該問題.

對An-1和A應(yīng)用引理2.2,有

由(3.2)式、(3.3)式和(3.4)式得

同理可證k=1,2,···,n-2時,有

由(3.7)式、(3.8)式和(3.9)式得

同理可證k=1,2,···,n-2時,有

綜上(3.5)式、(3.6)式、(3.10)式和(3.11)式即得(3.1)式.

由定理3.1可得如下推論.

推論3.1設(shè)AS是實對稱區(qū)間矩陣,記Sk(AS)表示AS的所有k階主子區(qū)間矩陣構(gòu)成的集合,則對任意的∈Sk(AS),有

證當(dāng)k=1,2,···,n-1時,由定理3.1可得

如此遞推,可得如下不等式:

綜上即得(3.12)式.

推論3.1表明實對稱區(qū)間矩陣AS的所有k階主子區(qū)間矩陣的最大特征值的上確界中的最小者是AS的第k個特征值的一個上界.記該上界為(AS),即

定理3.1說明實對稱區(qū)間矩陣各特征值的上確界具有交錯性質(zhì).同樣的,實對稱區(qū)間矩陣各特征值的下確界也具有交錯性質(zhì),即有如下定理3.2,其證明過程類似于定理3.1的證明,略去.

定理3.2(實對稱區(qū)間矩陣特征值下確界的交錯定理) 設(shè)AS是實對稱區(qū)間矩陣,記Sn-1(AS)表示AS的所有n-1階主子區(qū)間矩陣構(gòu)成的集合,則對任意的∈Sn-1(AS),有

由定理3.2可直接得如下推論.其證明過程類似于推論3.1的證明,略去.

推論3.2設(shè)AS是實對稱區(qū)間矩陣,Sk(AS)表示AS的所有k階主子區(qū)間矩陣構(gòu)成的集合,則對任意的∈Sk(AS),有

推論3.2說明實對稱區(qū)間矩陣AS的所有n+1-k階主子區(qū)間矩陣的最小特征值的下確界中的最大者是AS的第k個特征值的一個下界.記該下界為(AS),即

4.實對稱三對角區(qū)間矩陣特征值界的估計

實對稱三對角區(qū)間矩陣是一類特殊的實對稱區(qū)間矩陣,通常由微分方程的有限元和有限差分離散化產(chǎn)生,例如:離散多質(zhì)點彈簧系統(tǒng)的剛度矩陣等.在文[14]中,YUAN證明了實對稱三對角區(qū)間矩陣的最大和最小特征值的上、下確界等價求4個實對稱三對角矩陣的極值特征值.在文[16]中,HLAD′IK在區(qū)間矩陣的特征向量分量符號不變的條件下,給出了計算實對稱三對角區(qū)間矩陣特征值確界的算法.但實對稱三對角區(qū)間矩陣的特征向量的分量符號不變這個條件太強(qiáng),往往難以滿足,參見下文中的例5.2.這就要求我們進(jìn)一步研究,探討可以估計任意實對稱三對角區(qū)間矩陣各特征值界的方法,即給出計算實對稱三對角區(qū)間矩陣各特征值的外近似區(qū)間(即包含特征值的閉區(qū)間)的新算法.

本節(jié)應(yīng)用上節(jié)所獲實對稱區(qū)間矩陣特征值確界的交錯定理構(gòu)造實對稱三對角區(qū)間矩陣TS各特征值上界和下界的估計式,最后給出計算TS各特征值外近似區(qū)間的算法.

定義4.1[14]設(shè)區(qū)間矩陣稱TS為實對稱三對角區(qū)間矩陣,其中Tc,T?分別為TS的中點矩陣和半徑矩陣.顯然,對于任意的T ∈TS,T具有以下形式:

在文[14]中,YUAN證明了實對稱三對角區(qū)間矩陣TS的最大特征值的上確界等于TS中的如下矩陣U的最大特征值,即有如下引理4.1.

引理4.1[14]設(shè)TS是形如(4.1)式的實對稱三對角區(qū)間矩陣,令

證首先證明-TS是實對稱三對角區(qū)間矩陣.因為TS是實區(qū)間矩陣,由區(qū)間矩陣的定義知,-TS也是實區(qū)間矩陣;設(shè)T是TS中任意的對稱三對角矩陣,則-T ∈-TS,又-T也是實對稱三對角矩陣,所以-TS是實對稱三對角區(qū)間矩陣.

現(xiàn)在證明TS和-TS的特征值的確界滿足(4.2)式,即需證明

設(shè)實對稱三對角矩陣T和-T的特征值分別為:

由矩陣特征值的定義知,T和-T的特征值滿足

由引理2.1知,對任意的i ∈N,存在T ∈TS,滿足

又由(4.4)式知

由(4.5)式和(4.6)式即得(4.3)式.

注4.2定理4.1說明TS的第i個特征值的下確界(下界)可以通過求-TS的第n+1-i個特征值的上確界(上界)的相反數(shù)給出,所以本文只給出計算TS各特征值上界的估計式.

由引理4.1和推論3.1可以給出估計實對稱三對角區(qū)間矩陣各特征值上界的方法,即有如下定理4.2.

定理4.2設(shè)TS是形如(4.1)式的實對稱三對角區(qū)間矩陣,則對任意的k ∈N,

是TS的第k個特征值λk(TS)的一個上界,且

定理4.3設(shè)TS是形如(4.1)式的實對稱三對角區(qū)間矩陣,則對任意的k ∈N,有

其中Tc,T?分別為TS的中點矩陣和半徑矩陣,j=0,1,···,n-k,Sn-j(T?)表示矩陣T?的所有n-j階主子矩陣構(gòu)成的集合.

證由實對稱三對角區(qū)間矩陣TS可表示為TS=[Tc-T?,Tc+T?]知,任意的T ∈TS可表示為T=Tc+δT,其中δT ∈[-T?,T?]為實對稱矩陣.由引理2.3知,對任意的k ∈N有

其中j=0,···,n-k.再由定理4.2得

由(4.8)式和(4.9)式即得(4.7)式.

由引理4.2知,TS與TS的子集合TD={T ∈TS|aii=?i ∈N}的各特征值有相同的上界.由于TD仍是實對稱三對角區(qū)間矩陣,將定理4.3的結(jié)論應(yīng)用于TD可以得到TS各特征值上界的估計,即有下面的定理4.4.

Tc,T?分別是TS的中點矩陣和半徑矩陣,j=0,1,···,n-k,Sn-j(T?-D)表示矩陣T?-D的所有n-j階主子矩陣構(gòu)成的集合.

由于定理4.2-4.4都是實對稱三對角區(qū)間矩陣TS各特征值上界的估計式.下面將三個定理的結(jié)果取最小者作為實對稱三對角區(qū)間矩陣TS各特征值的上界,給出計算TS各特征值外近似區(qū)間的如下算法.

算法4.1

5.數(shù)值例子

本節(jié)應(yīng)用本文的定理4.2-4.4和算法4.1,計算兩個實對稱三對角區(qū)間矩陣各特征值的外近似區(qū)間,并與幾個現(xiàn)有算法進(jìn)行比較.在表1和表2中,P1、P2、P3和P分別表示利用定理4.2-4.4和算法4.1得到實對稱三對角區(qū)間矩陣各特征值的外近似區(qū)間;Q表示HLAD′IK等學(xué)者在文[15]中給出的實對稱區(qū)間矩陣各特征值的外近似區(qū)間;M表示HLAD′IK在文[16]中給出的實對稱三對角區(qū)間矩陣各特征值的近似區(qū)間.

表1 實對稱三對角區(qū)間矩陣TS各特征值的近似區(qū)間

表2 實對稱三對角區(qū)間矩陣KS各特征值的近似區(qū)間

例5.1求如圖1中具有單位質(zhì)量和區(qū)間剛度的離散四質(zhì)點彈簧系統(tǒng)的剛度矩陣各特征值界的估計.其中各彈簧的剛度系數(shù)分別為k1=1000±10N/m;k2=2000±15N/m;k3=3000±20N/m;k4=4000±25N/m;k5=5000±30N/m.

圖1 四質(zhì)點彈簧系統(tǒng)

根據(jù)離散多質(zhì)點彈簧系統(tǒng)的剛度矩陣與剛度系數(shù)之間的關(guān)系可得到該彈簧系統(tǒng)的區(qū)間剛度矩陣為

一方面,對比表1中P與Q的數(shù)據(jù),不難發(fā)現(xiàn)利用算法4.1得到TS各特征值的外近似區(qū)間更小,運(yùn)行時間也更少.另一方面,由于該例子的特殊性,TS的特征向量分量符號保持不變,故可用文[16]中的算法進(jìn)行計算,M中給出TS各特征值的近似區(qū)間就等于TS的各特征值區(qū)間,再對比P中的數(shù)據(jù),可以觀察到利用算法4.1得到TS各特征值的外近似區(qū)間與TS的各特征值區(qū)間差距不大,并且不用去驗證TS是否滿足先驗條件,計算成本也更小.觀察P1、P2、P3中的數(shù)據(jù)還可以發(fā)現(xiàn),當(dāng)實對稱三對角區(qū)間矩陣各特征值區(qū)間重疊較少或不重疊時,利用定理4.3和定理4.4進(jìn)行特征值區(qū)間的估計,結(jié)果較為理想;而利用定理4.2進(jìn)行特征值區(qū)間的估計,結(jié)果并不理想.

例5.2計算實對稱三對角區(qū)間矩陣KS各特征值的界,其中

對比表2中P與Q的結(jié)果,可以發(fā)現(xiàn)利用算法4.1得到KS各特征值的外近似區(qū)間更小,運(yùn)行時間也更少.又因為KS不滿足文[16]中所給算法的適用條件,所以不能給出KS各特征值的外近似區(qū)間.而本文給出的算法4.1能夠更好的獲得任意實對稱三對角區(qū)間矩陣各特征值的外近似區(qū)間.觀察P1、P2、P3中的數(shù)據(jù)還可以發(fā)現(xiàn),當(dāng)實對稱三對角區(qū)間矩陣各特征值區(qū)間重疊較多時,利用定理4.2進(jìn)行特征值區(qū)間的估計,結(jié)果較為理想;而利用定理4.3和定理4.4進(jìn)行特征值區(qū)間的估計,結(jié)果并不理想.

以上兩個例子表明,由于算法4.1是將三個定理的結(jié)果取最小者作為實對稱三對角區(qū)間矩陣各特征值的上界,故本文的算法克服了實對稱三對角區(qū)間矩陣各特征值區(qū)間重疊情況對估計結(jié)果的影響,所以本文算法能夠較好的估計任意實對稱三對角區(qū)間矩陣的各特征值區(qū)間.

6.總結(jié)

本文將實對稱矩陣特征值的交錯定理推廣到實對稱區(qū)間矩陣,給出了實對稱區(qū)間矩陣特征值確界的交錯定理,并應(yīng)用其給出了計算實對稱三對角區(qū)間矩陣特征值界的新算法.文中數(shù)值例子表明,與一些現(xiàn)有算法相比,本文算法適用于所有的實對稱三對角區(qū)間矩陣,得到的界較為精確,計算成本也更加小.