求矩阵最大特征值的并行和串形算法
需积分: 3 69 浏览量
2012-11-27
10:06:13
上传
评论
收藏 435KB DOC 举报
1. 9 矩阵特征值计算
在实际的工程计算中，经常会遇到求 n 阶方阵 A 的特征值(Eigenvalue)与特征向量
(Eigenvector)的问题。对于一个方阵 A，如果数值 λ 使方程组
Ax=λx
即 (A-λI
n
)x=0 有非零解向量(Solution Vector)x，则称 λ 为方阵 A 的特征值，而非零向量 x 为
特征值 λ 所对应的特征向量，其中 I
n
为 n 阶单位矩阵。
由于根据定义直接求矩阵特征值的过程比较复杂，因此在实际计算中，往往采取一些
数值方法。本章主要介绍求一般方阵绝对值最大的特征值的乘幂(Power)法、求对称方阵特
征值的雅可比法和单侧旋转(One-side Rotation)法以及求一般矩阵全部特征值的 QR 方法及
一些相关的并行算法。
1.1 求解矩阵最大特征值的乘幂法
1.1.1 乘幂法及其串行算法
在许多实际问题中，只需要计算绝对值最大的特征值，而并不需要求矩阵的全部特征
值。乘幂法是一种求矩阵绝对值最大的特征值的方法。记实方阵 A 的 n 个特征值为 λ
i
i=(1,2, …,n)，且满足：
│λ
1
│≥│λ
2
│≥│λ
3
│≥…≥│λ
n
│
特征值 λ
i
对应的特征向量为 x
i
。乘幂法的做法是：①取 n 维非零向量 v
0
作为初始向量；②
对于 k=1,2, …,做如下迭代：
u
k
=Av
k-1
v
k
= u
k
/║u
k
║
∞
直至 ε 为止，这时 v
k+1
就是 A 的绝对值最大的特征值 λ
1
所对应
的特征向量 x
1
。若 v
k-1
与 v
k
的各个分量同号且成比例，则 λ
1
=║u
k
║
∞
；若 v
k-1
与 v
k
的各个分量
异号且成比例，则 λ
1
= -║u
k
║
∞
。若各取一次乘法和加法运算时间、一次除法运算时间、一
次比较运算时间为一个单位时间，则因为一轮计算要做一次矩阵向量相乘、一次求最大元
操作和一次规格化操作，所以下述乘幂法串行算法 21.1 的一轮计算时间为 n
2
+2n=O(n
2
)。
算法 21.1 单处理器上乘幂法求解矩阵最大特征值的算法
输入：系数矩阵 A
n×n
，初始向量 v
n×1
，ε
输出：最大的特征值 max
Begin
while (│diff│>ε) do
(1)for i=1 to n do
(1.1)sum=0
(1.2)for j= 1 to n do
sum=sum+a[i,j]*x[j]
剩余31页未读，继续阅读
资源评论
lpcffnomal
- 粉丝: 0
- 资源: 1
