對角相似變換下的非負矩陣最大特征值算法

王信存,呂洪斌,商鈺瑩

(1.遼東學院 師范學院,遼寧 丹東 118003；2.北華大學 數學與統計學院,吉林 吉林 132013)

1 引言與預備知識

非負矩陣在計算數學、線性規劃、計算機科學技術、自動控制等領域應用廣泛[1-3],非負矩陣最大特征值的估計與計算是非負矩陣理論中的經典內容,在數值代數中具有重要意義.

設Mn()和Mn()分別表示實數域和復數域上的n×n階矩陣集合,N={1,2,…,n},+表示正整數集合.設A=(aij)∈Mn(),記表示矩陣A的有向圖,C(A)表示Γ(A)的簡單回路集合,σ(A)表示矩陣A的譜集,表示矩陣A的譜半徑,表示n階正對角矩陣的集合,E表示單位矩陣.若A=(aij)∈Mn(),且aij≥0(i,j∈N),則稱A為非負矩陣,記為A∈Mn(+).設A∈Mn(+),由Perron-Frobenius定理[1,4]知ρ(A)∈σ(A),稱為非負矩陣A的最大特征值,也稱ρ(A)為非負矩陣A的Perron根.對A=(aij)∈Mn(+),α∈,記A(α)=A+αE,ri(A(α))=ri(A)+α∶=ri(α),i∈N.

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

設A=(aij)∈Mn(+)不可約，Ax=ρ(A)x,x∈n,則x可取為正向量，且當‖x‖1=1時稱x為A的Perron向量[4].

目前,關于不可約非負矩陣最大特征值的計算已有很多成果,如: 文獻[5]給出了13種具體算法,對不可約非負矩陣最大特征值的計算進行了系統研究；文獻[6-7]的算法適用于不可約非負矩陣,但涉及指數運算；文獻[8-10]給出的算法適用于一類不可約非負矩陣,即對角元素均非零或至少有一個非零元素的本原矩陣.本文給出一類基于對角相似變換的不可約非負矩陣最大特征值和對應特征向量的算法,結果表明,該算法計算簡潔,并適用于所有不可約非負矩陣.

定理1(Perron-Frobenius定理)[4]設A=(aij)∈Mn(+),ρ(A)是A的最大特征值,則

設A=(aij)∈Mn(+)是不可約的,記不妨設r(0)

類似于文獻[7,9]的證明，有:

引理1設A=(aij)∈Mn(+)不可約,?γ∈C(A),記γ:i1→i2→…→ir→ir+1=i1,則?m∈+,有

引理2設……