呂洪斌, 張美黎, 商鈺瑩, 王信存
(1. 北華大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 吉林 吉林 132013; 2. 遼東學(xué)院 師范學(xué)院, 遼寧 丹東118003)
非負(fù)矩陣在計(jì)算數(shù)學(xué)、 線性規(guī)劃、 計(jì)算機(jī)科學(xué)、 自動(dòng)控制等領(lǐng)域應(yīng)用廣泛[1-3], 在與其密切相關(guān)的不可約M-矩陣、 對(duì)角占優(yōu)矩陣的判定中具有重要作用[4], 非負(fù)矩陣最大特征值的估計(jì)[5-7]與計(jì)算[4,8-10]是非負(fù)矩陣?yán)碚撝械慕?jīng)典內(nèi)容.
Hn={x=(x1,x2,…,xn)T:xi≥0,i=1,2,…,n}{0},
設(shè)A=(aij)∈Mn(+), ?i∈N, 記: det(λE-A)=0}表示矩陣A的譜集;表示矩陣A的譜半徑. 由Perron-Frobenius定理[1,4]知, 若A∈Mn(+), 則r(A)∈σ(A), 稱為矩陣A的最大特征值; 其對(duì)應(yīng)的特征向量可取為非負(fù)向量, 稱為矩陣A的最大特征向量. 進(jìn)一步, 當(dāng)A∈Mn(+)不可約時(shí), 稱r(A)為不可約非負(fù)矩陣A的Perron根, 其對(duì)應(yīng)的正特征向量稱為矩陣A的Perron向量[1,11].
定義1[1,11]設(shè)矩陣A=(aij)∈Mn(), 如果存在n階置換矩陣P, 使得
則稱矩陣A是可約的, 否則稱矩陣A是不可約的, 其中A11為r×r階矩陣(1≤r 定理1[11-12]設(shè)A∈Mn(+)不可約,r(A)是A的譜半徑, 則: 定理2[11-12]設(shè)A=(aij)∈Mn(+),r(A)是A的最大特征值, 則 目前, 關(guān)于不可約非負(fù)矩陣最大特征值的計(jì)算主要有基于矩陣正對(duì)角相似變換下的算法[8-9]及應(yīng)用非負(fù)矩陣的Collatz-Wielandt(C-W)函數(shù)算法[10]. 設(shè)A∈Mn(+)不可約,r(A)是A的最大特征值, 由文獻(xiàn)[11]知, 則問(wèn)題將被簡(jiǎn)化. 本文利用非負(fù)矩陣的C-W函數(shù), 給出一種求不可約非負(fù)方陣最大特征值和最大特征向量的數(shù)值算法, 由于每一步迭代都可根據(jù)實(shí)際選擇一個(gè)適合的參數(shù), 因此算法具有簡(jiǎn)單和收斂快的特點(diǎn). 定義2[11-12]設(shè)A=(aij)∈Mn(+)不可約, (1) FA(x)和GA(x)為兩個(gè)從Hn到+的函數(shù). 定義GA(x)=+∞, 若存在某個(gè)i, 使得xi=0且(Ax)i≠0, 則稱其為伴隨于矩陣A的Collatz-Wielandt函數(shù), 簡(jiǎn)稱為矩陣A的C-W函數(shù). 定理3(C-W定理)[12]設(shè)A=(aij)∈Mn(+)不可約,FA(x),GA(x)是A的C-W函數(shù), 則: 1)FA(x)和GA(x)都是零次齊次式; 2) 如果d是滿足Ax-dx≥0(x∈Hn)的最大實(shí)數(shù), 則d=FA(x); 如果e是滿足Ax-ex≤0(x∈Hn)的最小實(shí)數(shù), 則e=GA(x); 3) 如果x∈Hn, 且y=(E+A)n-1x, 則FA(y)≥FA(x),GA(y)≤GA(x); 4)FA(x)≤s,GA(x)≥t, 其中s,t分別為A的最大、 最小列和. 設(shè)A=(aij)∈Mn(+)不可約,則當(dāng)m≥n-2時(shí)Bm為正矩陣[12]. 對(duì)任取的初始向量x(0)∈Hn, ‖x(0)‖∞=1, 定義如下迭代格式: (2) 定理4設(shè)A∈Mn(+)不可約,為由迭代格式(2)定義的向量序列, 則 證明: 由C-W函數(shù)的定義式(1), 對(duì)任意k=0,1,2,…, 有 Ax(k)-FA(x(k))x(k)≥0, 于是, 當(dāng)k≥m時(shí)有 BmAx(k)-FA(x(k))Bmx(k)≥0. 因?yàn)锳Bm=BmA, 故有 A(Bmx(k))-FA(x(k))(Bmx(k))≥0, 進(jìn)而得 Ax(k+1)-FA(x(k))x(k+1)≥0. (3) 由定理3中2)得 FA(x(k))≤FA(x(k+1)),k=m,m+1,…, 由定理3中4)知{FA(x(k)):k=m,m+1,…}是有上界的單調(diào)不減非負(fù)實(shí)數(shù)列, 從而存在極限. 又由定理3中4)及A不可約知, 知 Au-au>0, 注1若A∈Mn(+),aii>0(i=1,2,…,n), 為提高收斂速度可取αi<0, 滿足 注2由迭代格式的構(gòu)造及定理4的證明過(guò)程知,m可取為滿足m≥n-2的任意正整數(shù), 因此可把式(2)進(jìn)一步優(yōu)化為: x(k)=y(k)/‖y(k)‖∞,k=1,2,…. 算法步驟如下: 4) 輸出特征值r(A)=(GA(x)+FA(x))/2及特征向量x. 注3算法中的參數(shù)α可根據(jù)實(shí)際情況進(jìn)行選取. 下面應(yīng)用MATLAB軟件分析上述算法. 例1 分別利用本文算法(取αi=rmax-rmin-n)和文獻(xiàn)[4,8]的算法計(jì)算r(A6)的迭代次數(shù), 對(duì)比結(jié)果列于表1. 其中應(yīng)用本文算法、 文獻(xiàn)[4]算法、 文獻(xiàn)[8]中算法9計(jì)算r(A6), 每一步迭代所需的乘法、 除法和加法運(yùn)算次數(shù)基本相同. 由表1可見, 在迭代次數(shù)上本文算法具有明顯優(yōu)勢(shì). 表1 不同算法計(jì)算矩陣A6的最大特征值迭代次數(shù)比較 例2 表2 不同算法計(jì)算矩陣A的最大特征值迭代次數(shù)比較 由表2可見, 本文算法的迭代次數(shù)是文獻(xiàn)[8]和文獻(xiàn)[9]算法的1/2和1/4次, 但其乘法、 除法和加法的運(yùn)算次數(shù)基本相同, 再次表明了本文算法的優(yōu)勢(shì).2 主要結(jié)果
3 數(shù)值算法及分析