8线性方程组的迭代解法 在阶数较大、系数阵为稀疏阵的情况下,可以采用迭代法求解线性方程组。用迭代法 ( Iterative Method)求解线性方程组的优点是方法简单,便于编制计算机程序,但必须选取合 适的迭代格式及初始向量,以使迭代过程尽快地收敛。迭代法根据迭代格式的不同分成雅可 比 Jacobi)迭代、高斯塞德尔( Gauss-Seidel迭代和松弛 Relaxation)法等几种。在本节中,我 们假设系数矩阵A的主对角线元素an≠0,且按行严格对角占优 Diagonal Donimant),即: la>∑nl(=12…,n) 1.1雅可比迭代 111雅可比选代及其串行算法 雅可比迭代的原理是:对于求解n阶线性方程组Ac=b,将原方程组的每一个方程anx1+ x2+…+ aint=b改写为未知向量x的分量的形式: x=(b-∑ajxj)/ai(≤i≤n) 然后使用第k-1步所计算的变量x1)来计算第k步的x的值: =(b 人9(k-)a(sk≤n) 这里,x为第k次迭代得到的近似解向量x=(x(,x2,…,x)的第i个分量。取 适当初始解向量x0代入上述迭代格式中,可得到x1),再由x)得到x2),依次迭代下去得到 近似解向量序列{x)}。若原方程组的系数矩阵按行严格对角占优,则{x)}收敛于原方程组 的解x。实际计算中,一般认为,当相邻两次的迭代值x+与x=(1,2,…,n)很接近时, x*+)与准确解x中的分量x也很接近。因此,一般用max+x,判断迭代是否收敛 如果取一次乘法和加法运算时间或一次比较运算时间为一个单位时间,则下述雅可比迭代算 法20.1的一轮计算时间为m2+n=O(n2) 算法201单处理器上求解线性方程组雅可比选代算法 输入:系数矩阵Anxn,常数向量bnx1,ε,初始解向量xx 输出:解向量xn× (I)for i=l to n do end for1. 8 线性方程组的迭代解法 在阶数较大、系数阵为稀疏阵的情况下，可以采用迭代法求解线性方程组。用迭代法 (Iterative Method)求解线性方程组的优点是方法简单，便于编制计算机程序，但必须选取合 适的迭代格式及初始向量，以使迭代过程尽快地收敛。迭代法根据迭代格式的不同分成雅可 比(Jacobi)迭代、高斯-塞德尔(Gauss-Seidel)迭代和松弛(Relaxation)法等几种。在本节中，我 们假设系数矩阵 A 的主对角线元素 aii  0 ，且按行严格对角占优(Diagonal Donimant)，即： ( 1,2,..., ) 1 a a i n n j j i ii   ij = =  1.1 雅可比迭代 1.1.1 雅可比迭代及其串行算法 雅可比迭代的原理是：对于求解 n 阶线性方程组 Ax=b，将原方程组的每一个方程 ai1x1+ ai2x2+…+ ainxn= bi 改写为未知向量 x 的分量的形式： ( ) / (1 ) 1, x b a x aii i n n j j i i = i −  ij j   =  然后使用第 k-1 步所计算的变量 xi (k -1)来计算第 k 步的 xi (k)的值： ( ) / (1 , ) 1, ( ) ( 1) x b a x aii i k n n j j i k i ij k i j = −    =  − 这里，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 也很接近。因此，一般用 (k) i (k ) i x -x 1 1 i n max +   判断迭代是否收敛。 如果取一次乘法和加法运算时间或一次比较运算时间为一个单位时间，则下述雅可比迭代算 法 20.1 的一轮计算时间为 n 2+n=O(n 2 )。 算法 20.1 单处理器上求解线性方程组雅可比迭代算法 输入：系数矩阵 An×n，常数向量 b n×1，ε，初始解向量 xn×1 输出：解向量 xn×1 Begin (1)for i=1 to n do xi=bi/aii end for