(2)for j=l to n do sF=s+AU门*A[ (3)BU]=sqrt(su) (4 )if([o j]*[o. jk0)then BUF-BU] endif end for End 上述算法的一轮迭代要进行n(n-1)/2次旋转变换,而一次旋转变换需要做3次内积运算, 若取一次乘法或一次加法运算时间为一个单位时间,则需要6q个单位时间,另外,还要对 四列子向量中元素进行正交计算花费12q个单位时间,所以一轮迭代需要的计算时间 T=m(n-1)6g;内积计算需要通信,一轮迭代共做归约操作n(nl)2次,每次通信量为3,因 而通信时间T2=[2,(√P-1)+3(P-1*m(n-1)/2。由此得出一轮迭代的并行计算时 间 Ip=Ti+T2。 MPI源程序请参见所附光盘 14求一般矩阵全部特征值的QR方法 141QR方法求一般矩阵全部特征值的串行算法 在186节中,我们介绍了对一个n阶方阵A进行QR分解的并行算法,它可将A分解 成A=QR的形式,其中R是上三角矩阵,Q是正交矩阵,即满足QQ=1。利用QR方法也可 求方阵特征值,它的基本思想是: 首先令A1=A,并对A1进行QR分解,即:A|=QR;然后对A1作如下相似变换:A2 =Q1A1Q=Q1Q1RQ1=RQ,即将R1Q1相乘得到A2;再对A2进行QR分解得A2=Q2R2, 然后将R2Q2相乘得A3。反复进行这一过程,即得到矩阵序列:A1,A2,…,Am,Am+1,…,它 们满足如下递推关系:A=QR1;A+=RQ(=1,2,…,m…)其中Q均为正交阵,R均为上 三角方阵。这样得到的矩阵序列{1}或者将收敛于一个以A的特征值为对角线元素的上三 角矩阵,形如 n 或者将收敛于一个特征值容易计算的块上三角矩阵。 算法218单处理器上QR方法求一般矩阵全部特征值的算法 输入:矩阵Anxm,单位矩阵Q, 输出:矩阵特征值 Eigenvalu Begin (1)while((p>c)and(count<1000))de (1. 1)p=0, count=count +1 (1.2)QR_ DECOMPOSITION(A,QR)算法181对矩阵A进行QR分解(1)su=0 (2)for j=1 to n do su=su+A[j,i]* A[j,i] end for (3)B[j]=sqrt(su) (4)if (I[0,j]*a[0,j]<0) then B[j]= - B[j] endif end for End 上述算法的一轮迭代要进行n(n-1)/2次旋转变换, 而一次旋转变换需要做3次内积运算， 若取一次乘法或一次加法运算时间为一个单位时间，则需要 6q 个单位时间，另外，还要对 四列子向量中元素进行正交计算花费 12q 个单位时间，所以一轮迭代需要的计算时间 T1=n(n-1)6q；内积计算需要通信，一轮迭代共做归约操作 n(n-1)/2 次，每次通信量为 3，因 而通信时间 T2= [2t s ( p −1) + 3tw ( p −1)]*n(n −1) 2 。由此得出一轮迭代的并行计算时 间 Tp=T1+T2。 MPI 源程序请参见所附光盘。 1.4 求一般矩阵全部特征值的 QR 方法 1.4.1 QR 方法求一般矩阵全部特征值的串行算法 在 18.6 节中，我们介绍了对一个 n 阶方阵 A 进行 QR 分解的并行算法，它可将 A 分解 成 A=QR 的形式，其中 R 是上三角矩阵，Q 是正交矩阵，即满足 Q TQ=I。利用 QR 方法也可 求方阵特征值，它的基本思想是： 首先令 A1=A，并对 A1 进行 QR 分解，即： A1= Q1 R1；然后对 A1 作如下相似变换：A2 = Q1 -1A1 Q1= Q1 -1 Q1 R1 Q1= R1Q1，即将R1Q1 相乘得到A2；再对A2 进行QR分解得A2 = Q2 R2， 然后将 R2Q2 相乘得 A3。反复进行这一过程，即得到矩阵序列：A1, A2, …, Am, Am+1 ,…，它 们满足如下递推关系：Ai= Qi Ri ；Ai+1= Ri Qi (i=1,2, …, m,…)其中 Qi 均为正交阵，Ri 均为上 三角方阵。这样得到的矩阵序列 Ai 或者将收敛于一个以 A 的特征值为对角线元素的上三 角矩阵，形如：                 n          * * * * * * * * * 3 2 1 或者将收敛于一个特征值容易计算的块上三角矩阵。 算法 21.8 单处理器上 QR 方法求一般矩阵全部特征值的算法 输入：矩阵 An×n,单位矩阵 Q，ε 输出：矩阵特征值 Eigenvalue Begin (1) while ((p>ε) and (count<1000)) do (1.1)p=0 , count = count +1 (1.2)QR_DECOMPOSITION(A,Q,R) /*算法 18.11 对矩阵 A 进行 QR 分解