非负矩阵最大特征值的拟幂型算法

王信存，吕洪斌

(1.辽东学院师范学院，辽宁 丹东 118003；2.北华大学数学与统计学院，吉林 吉林 132013)

0 引言

非负矩阵是一类重要矩阵，有着广泛的应用背景[1-4]，其中非负矩阵最大特征值的性质在其理论研究与应用中具有重要地位，其估计与计算是非负矩阵理论中的经典内容，在数值代数中具有重要意义.对非负矩阵的更高维的非负张量的研究及应用价值尤为重大[5-8].

设Mn()、Mn()分别表示实数域、复数域上的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)的简单回路集合.+表示正整数集合，表示n阶正对角阵的集合，I为对应阶数的单位矩阵.

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

计算矩阵最大特征值的经典算法是幂算法，但因其对矩阵的条件要求苛刻且一般情况下收敛速度较慢，因此有必要寻找计算非负矩阵最大特征值的其他方法.关于不可约非负矩阵最大特征值的计算已有一些研究成果：文献[10]给出了一种矩阵对角相似变换的全步迭代法，并给出了13种具体的参数选择形式，对不可约非负矩阵最大特征值的计算进行了较为系统的研究；文献[11-12]给出了一类特殊的不可约非负矩阵(本原矩阵)最大特征值的对角相似迭代算法；文献[13]给出了一般不可约非负矩阵最大特征值的对角相似迭代算法；文献[14]利用非负矩阵行和的非负平方根作对角相似变换，给出了计算不可约非负矩阵最大特征值的另一种对角相似迭代算法；文献[15]给出了基于幂函数的计算不可约非负矩阵最大特征值的对角相似算法；文献[16]首先对不可约非负矩阵进行变换，利用Collatz-Wielandt函数给出了一种含参变量的计算不可约非负矩阵最大特征值的算法.本文应用矩阵的对角相似变换构造了不可约非负矩阵最大特征值及其对应特征向量的拟幂型算法，本文提出的算法与计算矩阵最大特征值的对角相似迭代算法相比每一步的运算量大大减少，而与幂法比较在每一步运算量基本不变的情况下迭代次数大大减少，具有较高的计算效率，且算法适用于任意不可约非负矩阵最大特征值的计算.

1 算法构造

给出著名的Perron-Frobenius定理：

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

应用定理1和矩阵的对角相似变换给出计算非负矩阵最大特征值及其对应特征向量的数值算法的构造过程.

由上述构造过程，给出如下计算非负矩阵最大特征值的数值算法.

算法1

步1 计算

2 算法收敛性分析

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

证明由算法构造知

证明由算法构造知

引理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 数值算例

应用Matlab R2016b通过具体数值算例分析上述算法.所有数值实验均在4 GB内存Intel CPU 15-4210的PC上完成.

例1

表1 不同算法计算ρ(A)的效率比较

当n=6，ε=10-5时，ρ(A)=8.656 45，对应的特征向量为

由例1知，本文算法与计算不可约非负矩阵最大特征值的幂法相比，迭代次数明显减少，这可以大大提高数值计算的稳定性；在迭代时间上本文算法也有一定的优势，并且通过恰当的选择参数，可以进一步提高算法的计算效率.