基于幂函数的非负矩阵谱半径的数值算法

吕洪斌，刘桂敏

(1.北华大学数学与统计学院，吉林 吉林 132013；2.兰州大学数学与统计学院，甘肃 兰州 730000)

1 基本定义和相关结果

为叙述方便，我们约定Mn()、Mn()分别表示实数域、复数域上的n×n阶矩阵集合；分别表示n维欧氏空间上的非负向量和正向量的集合；N={1，2，…，n}；σ(A)={λ∈：Ax=λx，0≠x∈n}表示矩阵A∈Mn()的谱集；λi(A)表示矩阵A的谱半径；Γ(A)表示矩阵A的有向图[1]；C(A)表示Γ(A)的简单回路[1]集合；表示n阶正对角阵的集合.

定义1[1-2]设A=(aij)∈Mn()，如果存在n阶置换矩阵P，使得其中A11为r×r阶矩阵(1≤r

定义2若A=(aij)∈Mn()，且aij≥0，i、j∈N，则称A为非负矩阵，记为A∈Mn(+).

关于非负矩阵的谱性质有经典的Perron-Frobenius定理.

定理1[1]设A=(aij)∈Mn(+)不可约，r(A)为A的谱半径，则

(ⅰ)r(A)为A的代数重数为1的单重特征值.

由定理1知，谱半径r(A)是非负矩阵A的按模最大特征值，也称为非负矩阵的最大特征值.

对于非负矩阵谱半径上下界的估计，有著名的Perron-Frobenius定理.

定理2[1]设A=(aij)∈Mn(+)，r(A)是A的谱半径，则

非负矩阵在很多领域都有重要应用[2-4]，而非负矩阵谱半径的估计与计算是非负矩阵理论中的经典内容.关于不可约非负矩阵谱半径的计算有幂法[5]、基于Collatz-Wielandt函数的算法[6-7]、对角相似迭代算法[8-11]等.本文应用矩阵的对角相似变换，基于幂函数给出不可约非负矩阵最大特征值的拟幂型数值算法，与幂法相比，本文提出的算法在每步运算量基本不变的前提下，减少了迭代次数和计算时间，并且算法适用于所有不可约非负矩阵谱半径的计算.

2 算法构造

设A=(aij)∈Mn(+)不可约，0<α<1，记A不妨设否则，由定理2知则由定理2可知对取从而A(1)为不可约非负矩阵，且σ(A(1))=σ(A(0)).记则取从而A(2)为不可约非负矩阵，且有σ(A(2))=σ(A(1)).如此继续下去，由A(k+1)得到相似的不可约非负矩阵序列最小行和序列与最大行和序列同时，变换前后的矩阵具有相同的零元模式.

由上述构造过程，我们给出如下计算非负矩阵谱半径的数值算法.

算法1

给定不可约非负矩阵A=(aij)∈Mn(+)，ε>0，0<α<1.

步1 计算

3 算法收敛性

对于上述迭代矩阵，容易证明：

引理1设A=(aij)∈Mn(+)不可约，对∀γ∈C(A)，记γ：i1→i2→…→ir→ir+1=i1，∀k∈+，则有

引理2设A=(aij)∈Mn(+)不可约，r(A)是A的谱半径，不妨设则对前述迭代矩阵序列最小行和序列单调递增有上界，最大行和序列单调递减有下界，且

引理3设A=(aij)∈Mn(+)不可约，如果aij>0，i、j∈N，则+，其中，a

所以有

由于A不可约，对aij≠0，∀i、j∈N，i≠j存在Γ(A)的一条有向路径[1]γ：i→j→j1→…→jr→jr+1=i，使得

于是有

定理3设A=(aij)∈Mn(+)不可约，r(A)是A的谱半径，则在前述矩阵序列和记号下，有

类似上式进一步有

⋮

因此，∀i∈N，有

进一步，∀q∈+，应用引理2有

4 数值算例

下面应用Matlab R2016b通过具体数值算例分析上述算法.所有数值实验均在4 GB内存Intel CPU 15-4210的PC上完成.我们随机给出一个5×5阶矩阵.

例1

表1 不同算法计算r(A)迭代次数和计算时间比较Tab.1 Comparison of iterations times and computation time for computing r(A) with different algorithms

由例1知，本文算法与幂法相比，迭代次数和迭代时间明显减少，因而计算效率大大提高.