第5章_线性方程组的迭代解.ppt

* 计 算 方 法 课 件 结束 第5章 线性方程组的迭代解法 线性方程组的直接法，用于阶数不太高的线性方程组效果较好.实际工作中有的线性方程组阶数很高，但其中的大多数系数为0，这一类的线性方程组的系数阵称为稀疏矩阵.稀疏矩阵的存贮和计算有一套技术处理，可以节约大量的存贮空间和计算工作量.用直接法计算时，因一次消元就可以使系数阵丧失其稀疏性，不能有效利用其稀疏的特点.下文介绍的迭代法就有保持系数阵稀疏的优点，此外迭代法也常用来提高已知近似解的精度. 5.1 迭代法的一般形式 线性方程组 Ax=b (5.1) 其中A非奇异，b≠0，因而它有唯一非零解. * 构造与(5.1)等价的方程组 x=Bx+f (5.2) 即使得(5.2)与(5.1)同解，其中B是n×n矩阵，f是n维向量. 结束 任取一个向量x(0)作为x的近似解，用迭代公式 x(k+1)=Bx(k)+f, (k=0,1,2,?) (5.3) 产生一个向量序列{x(k)}，若 则有 x=Bx +f，即x是(5.2)的解，当然x也就是Ax=b的解. 从以上的讨论中，可以看出，迭代法的关键有： 1 如何构造迭代公式x(k+1)=Bx(k)+f ？这样的构造形式不止一种，它们各对应一种迭代法. 2 迭代法产生的向量序列{x(k)}的收敛条件是什么，收敛速度如何.后面将进行讨论. 5.2 几种常用的迭代法公式 5.2.1 简单迭代法 * 结束 先看一个算例： 例1 从以上三个方程中分别解出x1, x2, x3。 按下式进行迭代 (k=0,1,2, ?) * 结束 任取一初始向量，例如x(0)=(0,0,0)T，得到迭代序列{x(k)} (k=0,1,2,?)，列表如下表5-1。 容易验证，原方程组的精确解为 x = (1,2,3) T，从上面的计算可看出，{x(k)}收敛于精确解. 一般说来，对方程组： i=1,2,?，n (5.4) 并设aii≠0(i=1,2,?,n)，从第i个方程解出xi，得等价的方程组： 2.9997 2.9977 2.9938 2.9823 2.9540 2.9540 2.6600 2.0000 0 x3 1.9998 1.9986 1.9961 1.9897 1.9700 1.9260 1.7600 1.5000 0 x2 0.9998 0.9985 0.9962 0.9804 0.9716 0.9180 0.8000 0.3000 0 x1 8 7 6 5 4 3 2 1 0 k * 迭代公式为： 结束 i=1,2,?,n (5.5) (5.6) 这种迭代形式称为简单迭代法，也称雅可比(Jacobi)迭代法. 雅可比迭代法的矩阵迭代形式: (推导) * 结束 5.2.2 塞德尔 (Seidel) 迭代法 在简单迭代法的迭代形式(5.6)中，可以看出，在计算 时，要使用 .但此时 已计算出来.看来此时可提前使 用 代替 ，一般地，计算 (n≥i≥2)时，使 用 代替 (i p≥1)，这样可能收敛会快一些，这就形成一种新的迭代法，称为塞德尔迭代法。 例2 用塞德尔迭代法计算例1并作比较. 解 迭代公式为： (k=0,1,2, ?) * 结束 用它计算得到的序列{x(k)}列表如表5-2： 可见它对这一方程组比简单迭代法收敛快一些。 塞德尔迭代法的公式如下： (5.9) Seidel 迭代法的矩阵迭代形式： （推导） * k 0 1 2 3 4 5 6 x1 0 0.3000 0.8804 0.9843 0.9978 0.9997 1.0000 x2 0 1.5000 1.9448 1.9922 1.9989 1.9998 2.0000 x3 0 2.6840 2.9539 2.9938 2.9991 2.9999 3