(n-1)(t,+mn)ogp= O(n log p),因此并行计算时间Tp=(n2-n)/3p+(n-1)(t+nhn)ogp MPI源程序请参见章末附录。 16QR分解 A=a]为一个n阶实矩阵,对A进行QR分解,就是求一个非奇异( Nonsingular)方阵Q 与上三角方阵R,使得A=QR。其中方阵Q满足:Q=g,称为正交矩阵 Orthogonal matrix) 因此QR分解又称为正交三角分解 16.1矩阵QR分解的串行算法 对A进行正交三角分解,可用一系列平面旋转矩阵左乘A,以使A的下三角元素逐个地 被消为0。设要消去的下三角元素为a(1>),则所用的平面旋转方阵为 C S 1 其中,除了(,0(/元素等于c,(u/元素与(,元素分别等于-s与s以外,其余元素皆与单位 方阵Ⅰ的对应元素相等,而c,s由下式计算: 其中,O为旋转角度。这样,在旋转后所得到的方阵A中,元素an'为0,A与A相比仅在 第i行、第j行上的元素不同: k=C×a1k+S×a 消去A的r=m(n-1)2个下三角元素后得到上三角阵R,实际上是用r个旋转方阵Q,Q2…,Q 左乘A,即 QQ-1…Q1A 设Qo=QQ-1…Q,易知Q为一正交方阵,则有 R=O04 Qo R OoR=OR 其中Q=Q01=Q0为一正交方阵,而Qo可以通过对单位阵进行同样的变换而得到这样可 得到A的正交三角分解。QR分解串行算法如下: 算法1811单处理器上矩阵的QR分解串行算法算法 输入:矩阵Anxm,单位矩阵Q 输出:矩阵Qnxm,矩阵Rnx(n-1)(ts+ntw)logp=O(n log p)，因此并行计算时间 Tp=(n 3 -n)/3p+(n-1)(ts+ntw)logp。 MPI 源程序请参见章末附录。 1.6 QR 分 解 A=[aij] 为一个 n 阶实矩阵，对 A 进行 QR 分解，就是求一个非奇异(Nonsingular)方阵 Q 与上三角方阵 R，使得 A=QR。其中方阵 Q 满足：QT=Q−1，称为正交矩阵(Orthogonal Matrix)， 因此 QR 分解又称为正交三角分解。 1.6.1 矩阵 QR 分解的串行算法 对 A 进行正交三角分解，可用一系列平面旋转矩阵左乘 A，以使 A 的下三角元素逐个地 被消为 0。设要消去的下三角元素为 aij(i>j)，则所用的平面旋转方阵为： 其中，除了(i,i)(j,j)元素等于 c，(i,j)元素与(j,i)元素分别等于−s 与 s 以外，其余元素皆与单位 方阵 I 的对应元素相等，而 c,s 由下式计算： 2 2 cos / a jj a jj aij c =  = + 2 2 sin / aij a jj aij s =  = + 其中，θ 为旋转角度。这样，在旋转后所得到的方阵 A' 中，元素 ' aij 为 0，A' 与 A 相比仅在 第 i 行、第 j 行上的元素不同： jk jk aik a = c  a + s  ' ik jk aik a = −s  a + c  ' (k =1,2,..., n) 消去 A 的 r=n(n-1)/2 个下三角元素后得到上三角阵 R，实际上是用 r 个旋转方阵 Q1,Q2,…,Qr 左乘 A，即： R= Qr Qr-1…Q1A 设 Q0=Qr Qr-1…Q1，易知 Q0 为一正交方阵，则有： R= Q0A 即 A = Q0 −1R= Q0 TR= QR 其中 Q= Q0 −1 =Q0 T为一正交方阵，而 Q0 可以通过对单位阵 I 进行同样的变换而得到, 这样可 得到 A 的正交三角分解。QR 分解串行算法如下： 算法 18.11 单处理器上矩阵的 QR 分解串行算法算法 输入：矩阵 An×n，单位矩阵 Q 输出：矩阵 Qn×n，矩阵 Rn×n                     − = 1 1 1 1 s c c s Qij