13松弛法 131松弛法及其串行算法 为了加快雅可比迭代与高斯塞德尔迭代的收敛速度,可采用松弛法。以高斯-塞德尔迭 代为例,首先,由高斯塞德尔迭代格式求得第k+1次迭代值x4+,即 (b-∑ax-∑ 然后计算第k+1次迭代值与第k次迭代值之差;即: 最后在第k次迭代值的基础上,加上这个差的一个倍数作为实际的第k1次迭代值,即: v(x{+1-x) 其中w为一个常数。综合以上过程,可以得到如下迭代格式: +)=(-m)x)+m(b-2可x-是ax)(=12…) 其中,ν称为松弛因子,为保证收敛,要求松弛因子w满足:0<<2。当⑩>1时,称 之为超松弛法,此时,{+)的比重被加大:当=1时,它就成了一般的高斯塞德尔迭代。 实际应用时,可根据系数矩阵的性质及对其反复计算的经验来决定适合的松弛因子w。若取 次乘法和加法运算时间或一次比较运算时间为一个单位时间,则下述算法20.5一轮计算 时间计算为n2+m=O(m)。 算法20.5单处理器上松弛法求解线性方程组的算法 输入:系数矩阵Axn,常数向量bnx1,E,初始解向量x×1 输出:解向量xn×1 (1)for i=l to n de end for (2)p=+1 (3) while(p≥ε)do (3. 1)for i=l to n do (ii)for j= if(≠then S St aij xj end if (i)y=(1-)x+(b-s)ai (iv)if(ly-xi >p) then p=y-xi end if (v)xi=i end for end while1.3 松弛法 1.3.1 松弛法及其串行算法 为了加快雅可比迭代与高斯-塞德尔迭代的收敛速度，可采用松弛法。以高斯-塞德尔迭 代为例，首先，由高斯-塞德尔迭代格式求得第 k+1 次迭代值 xi (k +1)，即： ( ) 1 1 ( ) 1 1 ( 1) ( 1)  = + − = + + = − − n j i k ij j i j k i ij j ii k i b a x a x a x 然后计算第 k+1 次迭代值与第 k 次迭代值之差；即： x i (k +1) -xi (k) 最后在第 k 次迭代值的基础上，加上这个差的一个倍数作为实际的第 k+1 次迭代值，即： xi (k +1)= xi (k)+w( x i (k +1) -xi (k) ) 其中 w 为一个常数。综合以上过程，可以得到如下迭代格式： ii n j i k ij j i j k i ij j k i k i a x w x w b a x a x 1 (1 ) ( ) 1 ( ) 1 1 ( 1) ( ) ( 1) = − + −  −  = + − = + + (i =1,2,  , n) 其中， w 称为松弛因子，为保证收敛，要求松弛因子 w 满足：0<w<2。当 w>1 时，称 之为超松弛法，此时， x i (k +1)的比重被加大；当 w=1 时，它就成了一般的高斯-塞德尔迭代。 实际应用时，可根据系数矩阵的性质及对其反复计算的经验来决定适合的松弛因子 w。若取 一次乘法和加法运算时间或一次比较运算时间为一个单位时间，则下述算法 20.5 一轮计算 时间计算为 n 2+n=O(n 2 )。 算法 20.5 单处理器上松弛法求解线性方程组的算法 输入：系数矩阵 An×n，常数向量 b n×1，ε，初始解向量 xn×1 输出：解向量 xn×1 Begin (1) for i=1 to n do xi=0 end for (2) p=ε+1 (3) while ( p ≥ ε) do (3.1) for i=1 to n do (i) s=0 (ii) for j= 1 to n do if (j ≠ i) then s= s+ aij xj end if end for (iii) yi= (1-w) xi +w(bi-s)/aii (iv) if (│yi - xi│>p) then p=│yi - xi│end if (v) xi =yi end for end while