(agg-app)/2 在实际应用时,考虑到并不需要解出O,而只需要求出sin26,sin0和co就可以了。 如果限制θ值在-x/2<20≤π/2,则可令 容易推出 利用sin2θ,sinθ和cosθ的值,即得矩阵B的各元素。矩阵A经过旋转变换,选定的 非主对角元素ap及a4p(一般是绝对值最大的)就被消去,且其主对角元素的平方和增加了 2a2,而非主对角元素的平方和减少了2a2四,矩阵元素总的平方和不变。通过反复选取主 元素φ,并作旋转变换,就逐步将矩阵A变为对角矩阵。在对称矩阵中共有(n2-n)2个非主 对角元素要被消去,而每消去一个非主对角元素需要对2n个元素进行旋转变换,对一个元 素进行旋转变换需要2次乘法和1次加法,若各取一次乘法运算时间或一次加法运算时间为 一个单位时间,则消去一个非主对角元素需要3个单位运算时间,所以下述算法213的一 轮计算时间复杂度为(m2-n)/2*2n*3=3m(n-1)=O(n) 算法21.3单处理器上雅可比法求对称矩阵特征值的算法 输入:矩阵Anxn,E 输出:矩阵特征值 Eigenvalue (while(max >e)de (1.1)max=a[12] (1.2)for i=l to n de for户=汁+ I to n do if(a[/)>max)then max=a[i P=i, qj end if end for (1.3)Compute m-alp, q ], n(alg, q]. pl)2, w=sgn(n)*m/sqrt(m*m+n*n si2=w, sil=w/sqrt(2(1+ sqrt(l-y*w))), col=sqrt(l-sil*sil) blp,P=alp.]*col col+al, q*si l*sil+ alp. q]*si2 bl, q=alp,P]*sil*sil+ alg, q*col*col-alp, q*si2 b{q,p]=0,b{P,q}=0 (1.4)for户= I to n do if(≠p)and(≠q))then (ibp=alp col+ala sil (ii)bla=-alp. *sil +a[g]*col end if (1. 5)for i=l to n do( ) 2 2 qq pp pq a a a tg − −  = 在实际应用时，考虑到并不需要解出 θ，而只需要求出 sin2θ，sinθ 和 cosθ 就可以了。 如果限制 θ 值在-π/2 < 2θ ≤ π/2，则可令 2 2 ( ), sgn( ) 2 1 , m n m m apq n aqq app w n + = − = − = 容易推出： sin2 = w, 2(1 1 ) sin w2 w + −  = ,   2 cos = 1−sin 利用 sin2θ，sinθ 和 cosθ 的值，即得矩阵 B 的各元素。矩阵 A 经过旋转变换，选定的 非主对角元素 apq 及 aqp（一般是绝对值最大的）就被消去，且其主对角元素的平方和增加了 2 2apq ，而非主对角元素的平方和减少了 2a 2 pq，矩阵元素总的平方和不变。通过反复选取主 元素 apq，并作旋转变换，就逐步将矩阵 A 变为对角矩阵。在对称矩阵中共有(n 2 -n)/2 个非主 对角元素要被消去, 而每消去一个非主对角元素需要对 2n 个元素进行旋转变换, 对一个元 素进行旋转变换需要 2 次乘法和 1 次加法，若各取一次乘法运算时间或一次加法运算时间为 一个单位时间，则消去一个非主对角元素需要 3 个单位运算时间，所以下述算法 21.3 的一 轮计算时间复杂度为 (n 2 -n)/2*2n*3=3n 2 (n-1)=O(n 3 )。 算法 21.3 单处理器上雅可比法求对称矩阵特征值的算法 输入：矩阵 An×n，ε 输出：矩阵特征值 Eigenvalue Begin (1)while (max >ε) do (1.1) max=a[1,2] (1.2)for i=1 to n do for j= i+1 to n do if (│a[i,j]) │>max) then max =│a[i,j] │，p=i，q=j end if end for end for (1.3)Compute: m=- a[p,q]，n=(a[q,q]- a[p,p])/2，w=sgn(n)*m/sqrt(m*m+n*n)， si2=w，si1=w/sqrt(2(1+ sqrt(1-w*w)))，co1=sqrt(1-si1*si1)， b[p,p]= a[p,p]*co1*co1+ a[q,q]*si1*si1+ a[p,q]*si2， b[q,q]= a[p,p]*si1*si1+ a[q,q]*co1*co1- a[p,q]*si2， b[q, p]=0，b[p,q]=0 (1.4)for j=1 to n do if ((j ≠ p) and ( j ≠ q)) then (i)b[p,j]= a[p,j]*co1+ a[q,j]*si1 (ii)b[q,j]= -a[p,j]*si1 + a[q,j]*co1 end if end for (1.5)for i=1 to n do