商鈺瑩，張美黎，呂洪斌，王信存

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

1 引 言

非負(fù)矩陣是一個重要的矩陣類，它在數(shù)值分析、概率統(tǒng)計、組合分析、動態(tài)規(guī)劃、運(yùn)籌學(xué)、數(shù)理經(jīng)濟(jì)和人口統(tǒng)計學(xué)等方面都具有重要應(yīng)用［1-2］，而對非負(fù)矩陣最大特征值的估計與計算又是非負(fù)矩陣?yán)碚撝械慕?jīng)典內(nèi)容，在數(shù)值代數(shù)中具有重要意義.

設(shè) A=(aij) ∈ 瓘n×n，記 N={1，2，…，n}，ri(A)=i∈ N，I是單位矩陣，σ(A)={λ1(A)，λ2(A)，…，λn(A)}表示矩陣A的譜集，ρ(A)=表示矩陣A的譜半徑.若A=(aij)∈Rn×n，且 aij≥0，i，j∈N，則稱A為非負(fù)矩陣，記為A∈Nn.由Perron-Frobenius定理［1-2］知ρ(A) ∈σ(A)，稱為非負(fù)矩陣A的最大特征值，也稱ρ(A)為非負(fù)矩陣A的Perron根，其對應(yīng)的特征向量可取為非負(fù)的，也稱為非負(fù)矩陣A的最大特征向量.

定義1［3］設(shè)A，如果存在置換矩陣P，使得，其中B為A的r×r階主子矩陣，D為A的(n－r)×(n－r)階主子矩陣(其中1≤r＜n)，則稱矩陣A是可約的，否則稱矩陣A是不可約的.

關(guān)于非負(fù)矩陣譜半徑(最大特征值)的界，有著名的Perron-Frobenius定理:

定理1［1-2］設(shè)A=(aij)∈Nn，ρ(A)是A的譜半徑，則

冪法是求矩陣最大特征值與最大特征向量的經(jīng)典數(shù)值方法［4］，但是冪法的最大缺點(diǎn)［4］就是收斂速度比較慢，當(dāng)然也有條件限制.關(guān)于不可約非負(fù)矩陣最大特征值的算法，文獻(xiàn)［5-7］給出了不同的迭代方法.本文利用不可約非負(fù)矩陣及C-W函數(shù)的性質(zhì)，給出了一種改進(jìn)的計算不可約非負(fù)矩陣最大特征值的C-W算法.

2 C-W函數(shù)

令 R+為全體非負(fù)實(shí)數(shù)集合，記={x=(x1，x2，…，xn)T∈ Rn:xi≥ 0，i=1，2，…，n}，Hn={0}.

定義2［2］設(shè)A∈Nn不可約，下列兩個從Hn到R+的函數(shù)

若存在某個i，使得xi=0且(Ax)i≠0，則定義GA(x)=+!，稱為伴隨于矩陣A的Collatz-Wielandt函數(shù)，簡稱為矩陣A的C-W函數(shù).

關(guān)于C-W函數(shù)有如下性質(zhì):

定理2(C-W定理)［2］設(shè)FA(x)，GA(x)是n階不可約非負(fù)矩陣A的C-W函數(shù)，則

(ⅰ)FA(x)及GA(x)都是零次齊次式.

(ⅱ)如果d是滿足Ax－dx≥0，x∈Hn的最大實(shí)數(shù)，那么d=FA(x);如果e是滿足Ax－ex≤0，x∈Hn的最小實(shí)數(shù)，那么e=GA(x).

(ⅲ) 如果 x ∈ Hn，且 y=(I+A)n－1x，那么 FA(y) ≥ FA(x)，GA(y) ≤ GA(x).

(ⅳ)FA(x)≤s，GA(x)≥t，其中s、t分別為A的最大、最小列和.

3 迭代格式與收斂定理

設(shè) A ∈ Nn不可約，令 B=(A+ αI)n－1，α ＞ 0，則由非負(fù)矩陣的經(jīng)典理論知 B 為正矩陣［1，2］.對任取的初始向量x(0)∈Hn，定義如下迭代格式

式中:x(k)是把y(k)標(biāo)準(zhǔn)化所得的向量，即 x(k)!=1.下面將證明由此產(chǎn)生的向量序列{x(k):k=1，2，…}收斂于A的一個最大特征向量，正數(shù)列{FA(x(k)):k=1，2，…}及{GA(x(k)):k=1，2，…}都收斂于A的最大特征值ρ(A).

定理3設(shè)A∈Nn不可約，B=(A+αI)n－1，α ＞ 0，{x(k):k=1，2，…}為由迭代格式(1)所得的向量序列，則

證明:按C-W函數(shù)的定義，對任意正整數(shù)k有

再由C-W定理(ⅳ)知{FA(x(k)):k=1，2，…}是有上界的單調(diào)不減實(shí)數(shù)列，從而存在極限，令

由于x(k)∈Hn且B=(A+ αI)n－1，α ＞ 0為正矩陣，故Bx(k)為正向量，從而x(k+1)為正向量，k=1，2，….又因 x(k+1)=1，故{x(k):k=1，2，…}是有界實(shí)向量序列，從而存在它的一個收斂子序列{u(k):k=1，2，…}.記=z，則z是正的標(biāo)準(zhǔn)向量，且滿足Az－lz≥0.

假設(shè) Az － lz≠ 0，由 Bz=(ρ(A)+ α)n－1z，α ＞ 0，有

從而由C-W函數(shù)的性質(zhì)有l(wèi)＜FA(z)=FA()=(u(k))=l的矛盾.所以Az－ lz=0，也就是Az=lz，即正向量z為不可約非負(fù)矩陣A的一個正特征向量.由非負(fù)矩陣的經(jīng)典理論［1-2］可知，任何不可約非負(fù)方陣A的任何正特征向量都對應(yīng)于A的最大特征值，并且不計數(shù)量倍數(shù)的差別是唯一的.據(jù)此得z=是矩陣A的唯一的標(biāo)準(zhǔn)最大特征向量，(x(k))=ρ(A)是矩陣A的最大特征值.

再由C-W迭代格式(1)的定義可知x(k+1)連續(xù)依賴于x(k)，從而由=z得到l=z.k

同理可證，{GA(x(k)):k=1，2，…}是有下界的單調(diào)不增實(shí)數(shù)列，從而存在極限(x(k))=h，滿足Az－h(huán)z≤0，其中z=為正向量.再利用與上面類似的推理又得Az=hz及h=ρ(A)，即(x(k)) 為矩陣A的最大特征值.證畢.

推論1設(shè)A∈Nn不可約，{x(k):k=0，1，2，…}是由迭代格式(1)所得到的向量序列，則0＜FA(x(0))≤…≤FA(x(k))≤FA(x(k+1))≤…≤ρ(A)≤…≤GA(x(k+1))≤GA(x(k))≤…≤GA(x(0)).

4 算法及分析

步0 給出不可約非負(fù)矩陣A=(aij)n×n，ε ＞ 0，x(0)=(1，1，…，1)T∈Rn(或Hn中任何向量);

步1 計算 B=(A+ αI)n－1，α ＞ 0;

步4 如果GA(x(k))－FA(x(k))＜ε，停止迭代，輸出ρ(A)= (GA(x(k))+FA(x(k)))/2，否則轉(zhuǎn)至步2.下面應(yīng)用MATLAB通過具體例子分析上述算法.

例1設(shè)

表1 不同的α＞0計算ρ(A)的迭代次數(shù)Tab.1 Calculate the number of iterations of ρ(A)with different α ＞ 0(ε =10－5)

由表1知，當(dāng)α=11，ε=10－5時，本文算法的收斂速度是文獻(xiàn)［6-7］算法的5倍.

對于一般的可約非負(fù)矩陣A∈Nn，可以將其化為可約標(biāo)準(zhǔn)形，再對對角塊矩陣應(yīng)用本文算法，求得其最大特征值ρ(A).