非負矩陣最大特征值的擬冪型算法

王信存，呂洪斌

(1.遼東學院師范學院，遼寧 丹東 118003；2.北華大學數(shù)學與統(tǒng)計學院，吉林 吉林 132013)

0 引言

非負矩陣是一類重要矩陣，有著廣泛的應用背景[1-4]，其中非負矩陣最大特征值的性質(zhì)在其理論研究與應用中具有重要地位，其估計與計算是非負矩陣理論中的經(jīng)典內(nèi)容，在數(shù)值代數(shù)中具有重要意義.對非負矩陣的更高維的非負張量的研究及應用價值尤為重大[5-8].

設Mn()、Mn()分別表示實數(shù)域、復數(shù)域上的n×n階實、復矩陣集合，表示n維歐氏空間的所有正向量集合，N={1，2，…，n}.若A=(aij)∈Mn()，且aij≥0，i，j∈N，則稱A為非負矩陣，記為A∈Nn.用表示矩陣A∈Mn()的譜半徑，其中σ(A)表示矩陣A的譜集.設A∈Nn，由Perron-Frobenius定理[9]知ρ(A)∈σ(A)，也稱ρ(A)為非負矩陣A的Perron根.設A=(aij)∈Mn()，Γ(A)表示矩陣A的有向圖，C(A)表示Γ(A)的簡單回路集合.+表示正整數(shù)集合，表示n階正對角陣的集合，I為對應階數(shù)的單位矩陣.

定義1[9]設矩陣A=(aij)∈Mn().如果存在n階置換矩陣P，使得其中A11為r×r階矩陣(其中1≤r

計算矩陣最大特征值的經(jīng)典算法是冪算法，但因其對矩陣的條件要求苛刻且一般情況下收斂速度較慢，因此有必要尋找計算非負矩陣最大特征值的其他方法.關于不可約非負矩陣最大特征值的計算已有一些研究成果：文獻[10]給出了一種矩陣對角相似變換的全步迭代法，并給出了13種具體的參數(shù)選擇形式，對不可約非負矩陣最大特征值的計算進行了較為系統(tǒng)的研究；文獻[11-12]給出了一類特殊的不可約非負矩陣(本原矩陣)最大特征值的對角相似迭代算法；文獻[13]給出了一般不可約非負矩陣最大特征值的對角相似迭代算法；文獻[14]利用非負矩陣行和的非負平方根作對角相似變換，給出了計算不可約非負矩陣最大特征值的另一種對角相似迭代算法；文獻[15]給出了基于冪函數(shù)的計算不可約非負矩陣最大特征值的對角相似算法；文獻[16]首先對不可約非負矩陣進行變換，利用Collatz-Wielandt函數(shù)給出了一種含參變量的計算不可約非負矩陣最大特征值的算法.本文應用矩陣的對角相似變換構(gòu)造了不可約非負矩陣最大特征值及其對應特征向量的擬冪型算法，本文提出的算法與計算矩陣最大特征值的對角相似迭代算法相比每一步的運算量大大減少，而與冪法比較在每一步運算量基本不變的情況下迭代次數(shù)大大減少，具有較高的計算效率，且算法適用于任意不可約非負矩陣最大特征值的計算.

1 算法構(gòu)造

給出著名的Perron-Frobenius定理：

定理1[4]設A=(aij)∈Nn，ρ(A)是A的最大特征值，則

應用定理1和矩陣的對角相似變換給出計算非負矩陣最大特征值及其對應特征向量的數(shù)值算法的構(gòu)造過程.

由上述構(gòu)造過程，給出如下計算非負矩陣最大特征值的數(shù)值算法.

算法1

步1 計算

2 算法收斂性分析

引理1 設A∈Nn不可約，?γ∈C(A)，記γ：i1→i2→…→ir→ir+1=i1，則?k∈+，有

證明由算法構(gòu)造知

證明由算法構(gòu)造知

引理3 設A=(aij)∈Nn不可約，則對任意aij≠0有

(1)

由(1)式和引理2有

(2)

從而由(1)和(2)式有

對aij≠0，?i，j∈N.設i≠j.由于A不可約，存在一條有向路徑γ：i→j→j1→…→jr→jr+1=i，有ajljl+1≠0，l=1，2，…，r.因此，由

和(1)—(2)式有

從而有

于是再由(1)式有

注1 由引理3知

定理2 設A=(aij)∈Nn不可約，ρ(A)是A的最大特征值，在前述矩陣序列和記號下算法1收斂，即有

因為A不可約，所以其有向圖Γ(A)是強連通的[5].又對?k∈+，A與A(k)有相同的零元模式，所以Γ(A(k))也是強連通的.

應用上式有

類似上面的討論有

?

因此，?i∈N，有

進一步，?q∈+有

3 數(shù)值算例

應用Matlab R2016b通過具體數(shù)值算例分析上述算法.所有數(shù)值實驗均在4 GB內(nèi)存Intel CPU 15-4210的PC上完成.

例1

表1 不同算法計算ρ(A)的效率比較

當n=6，ε=10-5時，ρ(A)=8.656 45，對應的特征向量為

由例1知，本文算法與計算不可約非負矩陣最大特征值的冪法相比，迭代次數(shù)明顯減少，這可以大大提高數(shù)值計算的穩(wěn)定性；在迭代時間上本文算法也有一定的優(yōu)勢，并且通過恰當?shù)倪x擇參數(shù)，可以進一步提高算法的計算效率.