8线性方程组的迭代解法

1、1.8线性方程组的迭代解法线性方程组的迭代解法在阶数较大、系数阵为稀疏阵的情况下，可以采用迭代法求解线性方程组。用迭代法迭代法(IterativeMethod)求解线性方程组的优点是方法简单，便于编制计算机程序，但必须选取合适的迭代格式及初始向量，以使迭代过程尽快地收敛。迭代法根据迭代格式的不同分成雅可比可比(Jacobi)迭代、高斯高斯塞德尔塞德尔(GaussSeidel)迭代和松弛松弛(Relaxation)法等几种。在本节中，我们

2、假设系数矩阵A的主对角线元素，且按行严格对角占优对角占优(DiagonalDonimant)，0?iia即：)...21(1niaanjijijii?????1.1雅可比迭代雅可比迭代1.1.1雅可比迭代及其串行算法雅可比迭代及其串行算法雅可比迭代的原理是：对于求解n阶线性方程组Ax=b，将原方程组的每一个方程ai1x1ai2x2…ainxn=bi改写为未知向量x的分量的形式：)1()(1niaxabxiinijjjijii??????

3、?然后使用第k1步所计算的变量xi(k1)来计算第k步的xi(k)的值：)1()(1)1()(nkiaxabxiinijjkijikji????????这里，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)收敛于原

4、方程组的解x。实际计算中，一般认为，当相邻两次的迭代值xi(k1)与xi(k)i=(12…n)很接近时，xi(k1)与准确解x中的分量xi也很接近。因此，一般用判断迭代是否(k)i)(kixx1ni1max???收敛。如果取一次乘法和加法运算时间或一次比较运算时间为一个单位时间，则下述雅可比迭代算法20.1的一轮计算时间为n2n=O(n2)。算法算法20.1单处理器上求解线性方程组雅可比迭代算法单处理器上求解线性方程组雅可比迭代算法输入

5、：输入：系数矩阵Ann，常数向量bn1，ε，初始解向量xn1输出：输出：解向量xn1Begin(1)fi=1tondoendifendf(1.3)x1[i]=(b[i]sum)a[imy_rankmi]endf(2)求出本处理器计算的x的相应的分量的新值与原值的差的最大值localmaxlocalmax=│x1[0]x[0]│(3)fi=1tom1doif(│x1[i]x[i]│localmax)thenlocalmax=│x1[i]x

6、[i]│endifendf(4)用Allgather操作将x的所有分量的新值广播到所有处理器中(5)用Allreduce操作求出所有处理器中localmax值的最大值max并广播到所有处理器中endwhileEnd若取一次乘法和加法运算时间或一次比较运算时间为一个单位时间，则一轮迭代的计算时间为mnm；另外，各处理器在迭代中做一次归约操作，通信量为1，一次扩展收集操作，通信量为m，需要的通信时间为，因此算法20.2的一轮)1()1()1

7、(4????ptmptws并行计算时间为。mmnptmptTwsp???????)1()1()1(4MPI源程序请参见所附光盘。1.2高斯高斯塞德尔迭代塞德尔迭代1.2.1高斯高斯塞德尔迭代及其串行算法塞德尔迭代及其串行算法高斯塞德尔迭代的基本思想与雅可比迭代相似。它们的区别在于，在雅可比迭代中，每次迭代时只用到前一次的迭代值，而在高斯塞德尔迭代中，每次迭代时充分利用最新的迭代值。一旦一个分量的新值被求出，就立即用于后续分量的迭代计算，

8、而不必等到所有分量的新值被求出以后。设方程组Ax=b的第i个方程为：=??nj1ijajxib)21(ni??高斯塞德尔迭代公式为：)(11)(11)1()1(???????????nijkjijijkjijiiikixaxabax)21(ni??取适当的x(0)作为初始向量，由上述迭代格式可得出近似解向量x(k)。若原方程组的系数矩阵是按行严格对角占优的，则x(k)收敛于方程组的解x，若取一次乘法和加法运算时间或一次比较运算时间为一个