第三章 线性代数方程组数值解法（迭代法）迭代法是解线性方程组的另一类方法，特别是适用于解大型稀疏线性方程组，如由某些偏微分方程数值解法中转化来的高阶线性代数方程组。

事实上，迭代法是求解多种数值问题的基本方法。

迭代法作为一种求解数值问题的通用方法，其基本思想是针对求解问题预先设计好某种迭代格式，从而产生求解问题的近似解的迭代序列，在迭代序列收敛于精确解的情况下，按精度要求取某个迭代值作为问题解的近似值，这就是求解数值问题的迭代法。

在这一章，我们的求解问题是线性方程组，下一章是非线性方程和非线性方程组，在不少其他问题中还会用到。

迭代法的内容包括下述两个主要方面： ① 针对具体问题构造具体的迭代格式。

② 研究迭代格式(序列)的收敛性并作误差分析。

3.1 解线性方程组迭代法的基本概念和基本迭代公式解线性代数方程组 b Ax = （3.1.1） (nn RA ⨯∈非奇异,0),,,(21≠=T n b b b b , Tn x x x x ),,,(21 =为解向量 )的迭代法的具体做法是： 把方程组(3.1.1)变形为等价形式)(x F x =我们这里只研究如上式的线性的形式 f Bx x +=(其中nn R B ⨯∈，nR f ∈ )例如把A分解为nn R M N M A ⨯∈-=,则（ b M Nx Mx b x N M 11)(--+=→=- ）如果令 N M B 1-=， b M f 1-= 这就是前面的迭代格式 f Bx x +=。

（对应的迭代公式是： ),,2,1,0()()1(n k f Bx xk k =+=+ 其中每一步迭代值仅依赖于前一步的迭代值。

称为单步迭代。

） 如果{)(k x }当 ∞→k 时有极限*x 存在， *)(lim x xk k =∞→则称迭代公式是收敛的；3.2 Jacobi 迭代法/Gauss —Seidel 迭代法这是解线性方程组的两种基本的方法。

1. Jacobi 迭代公式设方程组b Ax =中 nn ij Ra A ⨯∈=)(，ni R b b ∈=且 ),,2,1(0n i a ii =≠。

从方程组的分量形式来构造迭代格式，改写的迭代格式如下：1111113132121//)(a b a x a x a x a x n n +----= 2222223231212//)(a b a x a x a x a x n n +----=nn n nn n nn n n n a b a x a x a x a x //)(1122112+----=-- 或记为向量—矩阵形式 f x B x J +=于是对选定的初始向量 Tn x x x x ),,,()0()1(2)0(1)0( =构造迭代公式(格式)： ⎪⎪⎩⎪⎪⎨⎧+----=+----=+----=--+++nn n nn k n nn k n k n k nk n n k k k k n n k k k ab a x a x a x a x a b a x a x a x a x a b a x a x a x a x //)(//)(//)()(11)(22)(11)1(22222)(2)(323)(121)1(211111)(1)(313)(212)1(1或记成 ),,2,1,0()()1(n k f x B xk J k =+=+这就是解方程组b Ax =的Jacobi 迭代公式，J B 为迭代矩阵。

迭代公式也可写成),2,1,0(,,2,1/)(),,,(1)(11)()1()0()0(2)0(1)0( =⎪⎪⎩⎪⎪⎨⎧=--==∑∑+=-=+k ni a x a x a b x x x x x ii n i j k j ij i j k j ij i k i T n⎢⎢⎢⎢⎢⎢⎢⎣⎡--=nn n J a a a a B 122210nn n a a a a 211120-- ⎥⎥⎥⎥⎥⎥⎥⎦⎤--0222111 a a a a n n ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=nn n a b a b a b f 222111 也可一般地推导如下：将A 分裂为⎢⎢⎢⎢⎣⎡=11a A 22a⎥⎥⎥⎥⎦⎤nn a +⎢⎢⎢⎢⎣⎡1120n a a 20n a ⎥⎥⎥⎥⎦⎤0+⎢⎢⎢⎢⎣⎡0012a ⎥⎥⎥⎥⎦⎤021 n n a a 由于),,2,1(0n i a ii =≠即D 非奇异，1-D 存在，故有 b x U L D b Ax =--⇒=)(b x U L Dx ++=)(b D Ux D Lx D x 111---++=b D x U L D x 11)(--++= 即得Jacobi 迭代矩阵和常数项)(1U L D B J +=- （或 A D I B J 1--=） b D f 1-=2. Gauss —Seidel 迭代公式Gauss 迭代公式是Jocobi 迭代公式的改进版。

容易看到，上面的公式是)1()1(2)1(1+++→→→k nk k x x x 的次序计算的。

其实，当计算)1(+k i x 时，前面1-i 个)1(1+k x ，)1(2+k x ,, )1(1+-k i x 已经计算出，但Jacobi 并没有及时利用这些最新算出的近似值，而仍用)(1k x ，)(2k x ,, )(1k i x -。

为此，改造Jacobi 迭代公式为⎪⎪⎩⎪⎪⎨⎧+----=+----=+----=+--++++++nn n nn k n nn k n k n k nk n n k k k k n n k k k ab a x a x a x a x a b a x a x a x a x a b a x a x a x a x //)(//)(//)()1(11)1(22)1(11)1(22222)(2)(323)1(121)1(211111)(1)(313)(112)1(1或写成),2,1,0(,,2,1/)(),,,(1)(11)1()1()0()0(2)0(1)0( =⎪⎪⎩⎪⎪⎨⎧=--==∑∑+=-=++k ni a x a x a b x x x x x ii n i j k j ij i j k j ij i k iTn 或写成增量形式：),2,1,0(,,2,1/)(),,,()(11)1()()1()0()0(2)0(1)0( =⎪⎪⎪⎩⎪⎪⎪⎨⎧=--=∆∆+==∑∑=-=++k ni a x a x a b x x x x x x x x iin ij k j ij i j k j ij i i i k i k i Tn类似地，Gauss —Seidel 迭代公式可以表述成基本格式),2,1,0()()1( =+=+k f x B x k GS k它的推倒过程如下：b x U L D b Ax =--⇒=)(b Ux Lx Dx ++=b D Ux D Lx D x 111---++=从而可得 b D Ux D Lx D xk k k 1)(1)1(1)1(--+-+++=或由假设可知1)(--L D 存在，故有b Ux x L D k k +=-+)()1()(b L D Ux L D x k k 1)(1)1()()(--+-+-=从而可得Gauss —Seidel 迭代矩阵和常数项：U L D B GS 1)(--= b L D f 1)(--=3 Jacobi 迭代法与Gauss-Seidel 迭代法上述两种迭代公式，如果是收敛（即∞→k 当时有极限，且极限就是方程组的解），则按精度要求，取某个迭代向量{}kx作为解的近似值，这就是解方程组（3.1.1）的Jacobi 迭代法(简称J 法)和Gauss-Seidel 迭代法（简称GS 法）。

例3.2.1 已知方程组⎪⎩⎪⎨⎧=++=-+=+-12423311420238321321321x x x x x x x x x 分别用（1）J 法和（2）GS 法以T x )0,0,0()0(=为初始向量，计算其前3个迭代值。

并精确解T x )1,2,3(*=比较。

解（1）J 法迭代公式为⎪⎪⎩⎪⎪⎨⎧+--==++-=+-=+++4/)122(),.1,0(11/)334(8/)2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1k k k k k k k k k x x x k x x x x x x 前3个迭代值为：T(3)T (2)T (1)59)0455,0.971(3.1364,2.=x 0)3636,1.000(2.8750,2.=x 0)0000,3.000(2.5000,3.=x(2)GS 法的迭代公式为⎪⎪⎩⎪⎪⎨⎧+--==++-=+-=++++++4/)122(),.1,0(11/)334(8/)2023()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1k k k k k k k k k x x x k x x x x x x 前3个迭代值为：T(3)T (2)T(1)9)9968,0.995(3.0098,1.=x 3)0289,1.004(2.9772,2.=x3)0909,1.227(2.5000,2.=x在实践上，Jacobi 方法似乎比Gauss —Seidel 迭代法收敛速度快，但没有理论支持。

甚至有这样的方程组，使用J 法收敛，使用GS 法反而发散。

几点说明：① 一般计算是在没有肯定迭代法收敛的情况下进行的。

② 实际计算总是用迭代法的分量形式，迭代法的矩阵形式则用于研究收敛性理论。

③Jacobi 公式简单，每次迭代只需做矩阵与向量的一次乘法，特别适合于并行计算，缺点是需要存储两个向量)1()(,+k k x x . 4. Gauss —Seidel 迭代法的计算机算法 假定Tn x x x x),,,()0()0(2)0(1)0( =作为初值，以ε<-=-=∆=∞++)()1()1(0||max ||max ||k k k i k i ii ix x x x x P控制迭代终止，ε为精度要求，k 记录迭代次数，N 为允许的迭代次数最大值，n 为方程组的阶数，二维数组{}1,1,1+==n n j i ij a , 存放A 和b ，一维数组n i i x 1}{=开始存放初值，迭代过程中存放迭代值，最后存放近似值；算法使用工作单元0P 和P 以及循环变量i ;输入数据包括n ,A ,b , ε, N . [GS 算法] ① 0=k② 对 ,,,2,1n i =置初值 0=i x ③ 1+=k k④ 如果 N k >，则 输出当前迭代值i x （n i ,,2,1 =）和 k 值，并停机。