矩阵特征值计算.doc

文档介绍：9 矩阵特征值计算
在实际的工程计算中,经常会遇到求n阶方阵A的特征值(Eigenvalue)与特征向量(Eigenvector)的问题。对于一个方阵A,如果数值λ使方程组
Ax=λx
即(A-λIn)x=0有非零解向量(Solution Vector)x,则称λ为方阵A的特征值,而非零向量x为特征值λ所对应的特征向量,其中In为n阶单位矩阵。
由于根据定义直接求矩阵特征值的过程比较复杂,因此在实际计算中,往往采取一些数值方法。本章主要介绍求一般方阵绝对值最大的特征值的乘幂(Power)法、求对称方阵特征值的雅可比法和单侧旋转(One-side Rotation)法以及求一般矩阵全部特征值的QR方法及一些相关的并行算法。
求解矩阵最大特征值的乘幂法
乘幂法及其串行算法
在许多实际问题中,只需要计算绝对值最大的特征值,而并不需要求矩阵的全部特征值。乘幂法是一种求矩阵绝对值最大的特征值的方法。记实方阵A的n个特征值为λi i=(1,2, …,n),且满足:
│λ1│≥│λ2│≥│λ3│≥…≥│λn│
特征值λi对应的特征向量为xi。乘幂法的做法是:①取n维非零向量v0作为初始向量;②对于k=1,2, …,做如下迭代:
uk =Avk-1 vk= uk /║uk║∞
直至ε为止,这时vk+1就是A的绝对值最大的特征值λ1所对应的特征向量x1。若vk-1与vk的各个分量同号且成比例,则λ1=║uk║∞;若vk-1与vk的各个分量异号且成比例,则λ1= -║uk║∞。若各取一次乘法和加法运算时间、一次除法运算时间、一次比较运算时间为一个单位时间,则因为一轮计算要做一次矩阵向量相乘、一次求最大元操作和一次规格化操作,+2n=O(n2 )。
单处理器上乘幂法求解矩阵最大特征值的算法
输入:系数矩阵An×n,初始向量v n×1,ε
输出:最大的特征值max
Begin
while (│diff│>ε) do
(1)for i=1 to n do
()sum=0
()for j= 1 to n do
sum=sum+a[i,j]*x[j]
end for
()b[i]= sum
end for
(2)max=│b[1]│
(3)for i=2 to n do
if (│b[i]│>max) then max=│b[i]│ end if
end for
(4)for i=1 to n do
x[i] =b[i]/max
end for
(5)diff=max-oldmax , oldmax=max
end while
End
乘幂法并行算法
乘幂法求矩阵特征值由反复进行矩阵向量相乘来实现,因而可以采用矩阵向量相乘的数据划分方法。设处理器个数为p,对矩阵A按行划分为p块,每块含有连续的m行向量,这里,编号为i的处理器含有A的第im至第(i+1)m-1行数据,(i=0,1, …,p-1),初始向量v被广播给所有处理器。
各处理器并行地对存于局部存储器中a的行块和向量v做乘积操作,并求其m维结果向量中的最大值localmax,然后通过归约操作的求最大值运算得到整个n维结果向量中的最大值max并广播给所有处理器,各处理器利用max进行规格化操作。最后通过扩展收集操作将各处理器中的维结果向量按处理器编号连接起来并广播给所有处理器,以进行下一次迭代计算,直至收敛。具体算法框架描述如下:
乘幂法求解矩阵最大特征值的并行算法
输入:系数矩阵An×n,初始向量v n×1,ε
输出:最大的特征值max
Begin
对所有处理器my_rank(my_rank=0,…, p-1)同时执行如下的算法:
while (│diff│>ε) do /* diff 为特征向量的各个分量新旧值之差的最大值*/
(1)for i=0 to m-1 do /*对所存的行计算特征向量的相应分量*/
()sum=0
()for j= 0 to n-1 do
sum=sum+a[i,j]*x[j]
end for
()b[i]= sum
end for
(2)localmax=│b[0]│/*对所计算的特征向量的相应分量
求新旧值之差的最大值localmax */
(3)for i=1 to m-1 do
if (│b[i]│>localmax) then localmax=│b[i]│ end if
end for
(4)用Allreduce操作求出所有处理器中localmax值的最大值max
并广播到所有处理器中
(5)for i=0to m-1