非负矩阵最大特征值的计算

张美黎，刘桂敏，吕洪斌

(北华大学数学与统计学院，吉林 吉林 132013)

0 引 言

非负矩阵在数值分析、概率统计、组合分析、动态规划、运筹学等方面发挥着重要作用，作为非负矩阵理论的经典内容，其最大特征值的估计和计算在许多领域有着广泛的应用[1-4].关于非负矩阵最大特征值的计算有很多精典结果，如幂法[5]、对角迭代算法[6-8]以及基于C-W函数的算法[9-10]等.本文在考虑矩阵的正对角相似变换下研究非负矩阵最大特征值的计算.

定义1[1，4]设A=(aij)∈n×n，若存在置换矩阵P使得

其中，A11为r阶方阵(1≤r≤n-1)，A22为n-r阶方阵，则称A为可约矩阵，否则称A为不可约矩阵.

关于非负矩阵的谱性质有如下结果：

关于非负矩阵最大特征值的上下界有如下结果：

1 算法构造

下面我们利用矩阵的对角相似变换构造迭代矩阵序列.

在上述迭代矩阵序列下，我们有如下算法：

算法1

步1.计算

2 算法收敛性

对于算法1我们有：

(1)

(2)

容易证明：

由引理2和式(1)、(2)，有

由于A是不可约的，所以A的有向图Γ(A)是强连通的[1]，∀k∈+，A和A(k)具有相同的零元模式，所以Γ(A(k))是强连通的.

(3)

从式(3)，有

……类似地有

…

…

从而，对于∀k∈+，有

对于算法1收敛，但A是可约矩阵.

下面讨论非负不可约矩阵的Perron向量的数值算法.

即

故有

3 算法分析

算法2

步1.计算

如果αk<ε转步3，否则

下面应用MATLAB通过具体例子分析算法2.

例1

应用本文算法2、文献[7]中的算法，计算矩阵A的最大特征值ρ(A).表1给出了本文算法2和文献[7]算法的数值计算结果.

表1 不同算法计算矩阵A的最大特征值迭代次数比较

由例1可知，算法2的迭代次数少于文献[7]中算法的迭代次数，且算法2更具有一般性，参数的选择方便，在迭代每步引入一个适合的变参数，可减少迭代次数，提高计算效率.