18线性方程组的迭代解法.DOC

8 线性方程组的迭代解法 在阶数较大、系数阵为稀疏阵的情况下，可以采用迭代法求解线性方程组。用迭代法(Iterative Method)求解线性方程组的优点是方法简单，便于编制计算机程序，但必须选取合适的迭代格式及初始向量，以使迭代过程尽快地收敛。迭代法根据迭代格式的不同分成雅可比(Jacobi)迭代、高斯-塞德尔(Gauss-Seidel)迭代和松弛(Relaxation)法等几种。在本节中，我们假设系数矩阵A的主对角线元素，且按行严格对角占优(Diagonal Donimant)，即： 雅可比迭代 雅可比迭代及其串行算法 雅可比迭代的原理是：对于求解n阶线性方程组Ax=b，将原方程组的每一个方程ai1x1+ ai2x2+…+ ainxn= bi改写为未知向量x的分量的形式： 然后使用第k-1步所计算的变量xi(k -1)来计算第k步的xi(k)的值： 这里，xi(k)为第k次迭代得到的近似解向量x(k)= (x1 (k), x2(k) , …, xn(k) )T的第i个分量。取适当初始解向量x(0)代入上述迭代格式中，可得到x(1)，再由x(1)得到x(2)，依次迭代下去得到近似解向量序列{x(k)}。若原方程组的系数矩阵按行严格对角占优，则{x(k)}收敛于原方程组的解x。实际计算中，一般认为，当相邻两次的迭代值xi(k +1)与xi(k) i=(1,2, …,n)很接近时，xi(k +1)与准确解x中的分量xi也很接近。因此，一般用判断迭代是否收敛。如果取一次乘法和加法运算时间或一次比较运算时间为一个单位时间，则下述雅可比迭代算法20.1的一轮计算时间为n2+n=O(n2)。 算法20.1 单处理器上求解线性方程组雅可比迭代算法 输入：系数矩阵An×n，常数向量b n×1，ε，初始解向量xn×1 输出：解向量xn×1 Begin (1)for i=1 to n do xi=bi/aii end for (2)diff=ε (3)while (diff ≥ ε) do (3.1)diff=0 (3.2)for i=1 to n do (i)newxi= bi (ii)for j= 1 to n do if (j ≠ i) then newxi= newxi- aij xj end if end for (iii)newxi= newxi/ aii end for (3.3)for i=1 to n do (i)diff=max {diff, |newxi- xi|} (ii)xi=newxi end for end while End 雅可比迭代并行算法 A是一个n阶系数矩阵，b是n维向量，在求解线性方程组Ax=b时，若处理器个数为p，则可对矩阵A按行划分以实现雅可比迭代的并行计算。设矩阵被划分为p块，每块含有连续的m行向量，这里，编号为i的处理器含有A的第im至第(i+1)m-1行数据，同时向量b中下标为im至(i+1)m-1的元素也被分配至编号为i的处理器(i=0,1, …,p-1)，初始解向量x被广播给所有处理器。 在迭代计算中，各处理器并行计算解向量x的各分量值，编号为i的处理器计算分量xim至x(i+1)m-1的新值。并求其分量中前后两次值的最大差localmax，然后通过归约操作的求最大值运算求得整个n维解向量中前后两次值的最大差max并广播给所有处理器。最后通过扩展收集操作将各处理器中的解向量按处理器编号连接起来并广播给所有处理器，以进行下一次迭代计算，直至收敛。具体算法框架描述如下： 算法20.2 求解线性方程组的雅可比迭代并行算法 输入：系数矩阵An×n，常数向量b n×1，ε，初始解向量xn×1 输出：解向量xn×1 Begin 对所有处理器my_rank(my_rank=0,…, p-1)同时执行如下的算法: while (maxε) do (1)for i=0 to m-1 do /*各个处理器由所存的行计算出解x的相应的分量*/ (1.1)sum=0.0 (1.2)for j=0 to n-1 do if (j ≠ (my_rank*m+i)) then sum=sum+a[i,j]*x[j] end if end for (1.3)x1[i]=(b[i] - sum)/a[i,my_rank*m+i] end for (2)/*求出本处理器计算的x的相应的分量的新值与原值的差的最大值localmax */ localmax=│x1[0]-x[0]│ (3)for i=1 to m-1 do if (│x1[i]-x[i] │localmax) then localmax =│x1[i]-x[i] │ end if end for (4)用Allgather操作将x的所有分量的新值广