第6章 解线性方程组的迭代法.ppt

1、第6章 解线性方程组的迭代法,6.1 引 言,考虑线性方程组,（1.1）,其中A为非奇异矩阵，当A为低阶稠密矩阵时，第5章所讨 论的选主元消去法是有效方法.,但对于A的阶数n很大，零元素较多的大型稀疏矩阵 方程组，例如求某些偏微分方程数值解所产生的线性方程 组来说，利用迭代法求解则更为合适.,迭代法通常都可利用A中有大量零元素的特点.,从而得到简单迭代格式为,例 用简单迭代法解方程组,方程组的准确解是:,把方程组改写成,解,当k=0时,迭代格式为,代入得,选取初始迭代向量,当k=1时,迭代格式为,代入得,把,使用这种迭代格式，得到迭代结果如下表所示:,从表中看到，近似解向量序列收敛，且收敛到准

2、确解。,迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法，其具有需要计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点,由于迭代法是通过逐次迭代来逼近方程组的解的，因此收敛性和收敛速度是构造迭代法时要注意的问题,问题：是否可以构造一种适合于一般情况的迭代法呢？,一般如何构造迭代法的计算格式呢?,设方程组为 ,将其变形为 . 由此构造下面迭代格式:,对于给定方程组 ，,设有惟一解 ，,（1.3）,又设 为任取的初始向量，按上述迭代格式可构造向量序 列,（1.2）,其中 表迭代次数.,则,定义1:,(2) 如果 存在(记为 )，,显然 就是方程组的解，否则称此迭代法

3、发散.,称此迭代法收敛，,构造迭代格式(1),显然迭代格式(1)对任何的初始向量，得到的序列都不收敛.,如对方程组 ,构造迭代格式(2),6.2 基本迭代法,设有,（2.1）,其中， 为非奇异矩阵.,将 分裂为,（2.2）,其中， 为可选择的非奇异矩阵，且使 容易求解，,一般选择为 的某种近似，称 为分裂矩阵.,于是，求解 转化为求解 ，,即求解,可构造一阶定常迭代法,（2.3）,其中,称 为迭代法的迭代矩阵.,选取 阵，就得到解 的各种迭代法.,设 , 并将 写为三部分：,（2.4）,6.2.1 雅可比迭代法,由 ，选取 为 的对角元素部分，,即选取 (对角阵)， ，,（2.5）,其中,称

4、为解 的雅可比迭代法的迭代阵.,1 矩阵形式,研究雅可比迭代法(2.5)的分量计算公式.,记,由雅可比迭代公式(2.5), 有,或,于是，解 的雅可比迭代法的分量计算公式为,（2.6）,把,项留在左边,其它项移到右边得到,n阶线性代数方程组:,设,第i个方程两边除,得到,2 方程形式,令,再令,则有,则有,选取任意初始向量,得到一个新向量,把它代入(*)式右边,按这样做下去就会得到一个向量序列,把它代入(*)式右边又得到一个新向量,记为,它通常称为简单迭代序列或Jacobi迭代序列.,简单迭代序列中的向量可以表示为,它称为简单迭代格式或Jacobi迭代格式,称为初始迭代向量,称为简单迭代矩阵或

5、Jacobi迭代矩阵.,即有,记为,Jacobi迭代法算法, k = 1,则打印“求解失败”, 停机;否则,对 j = 1, 2, , n 计算,迭代 对 i = 1, 2, , n 计算, 若,， 输出X , k , 停机; 否则,做下一步.,输入A, b，初始向量Y，容许误差，容许最大迭代次数M,若,形成迭代矩阵B（存放在A中）,对 i = 1, 2, , n 循环,若k M , 则 k = k + 1 ，将X赋值给Y，转; 否则，输出求解失败信息，停机。,(下三角阵)，,6.2.2 高斯-塞德尔迭代法,选取分裂矩阵 为 的下三角部分，,即选取,（2.7）,其中,称 为解 的高斯-塞德尔迭

6、代法的迭 代阵.,于是由(2.3)式得到解,的高斯-塞德尔(Gauss-Seidel)迭代法,1 矩阵形式,研究高斯-塞德尔迭代法的分量计算公式.,由(2.7)式有,或,即,记,于是解 的高斯-塞德尔迭代法计算公式为,（2.8）,或,（2.9）,而由高斯-塞德尔迭代公式可知，,雅可比迭代法不使用变量的最新信息计算 ，,计算 的第 个分量,时，,利用了已经计算出的最新分量,由(2.8)可知，高斯-塞德尔迭代法每迭代一次只需计算 一次矩阵与向量的乘法.,高斯-塞德尔迭代法可看作雅可比迭代法的一种改进.,称为Seidel迭代格式.,2 方程形式,对上面式子归纳得到如下计算公式:,从而得到Seidel

7、迭代格式为,例 用Seidel迭代法解方程组,方程组的准确解是:,把方程组改写成,解,当k=0时,迭代格式为,代入得,选取初始迭代向量,当k=1时,迭代格式为,代入得,把,例 用雅可比迭代法和高斯塞德尔迭代法解线性方程组：,精确至三位有效数字。,解 雅可比迭代格式：,计算结果：,高斯塞德尔迭代格式,计算结果：,有上述结果可看出：高斯塞德尔迭代法比雅可比迭代法收 敛得快。,Seidel迭代法算法, k = 1 ,对 i = 1, 2, , n 做,则打印“求解失败”, 停机，否则,对 j = 1, 2, , n 计算,迭代 对 i = 1, 2, , n 计算, 若,， 输出X , k , 停机

8、; 否则,做下一步.,输入A, b，初始向量Y，容许误差，容许最大迭代次数M,若,形成迭代矩阵B（存放在A中）,对 i = 1, 2, , n 循环,若k M , 则 k = k + 1 ，将X赋值给Y，转，否则，输出求解失败信息，停机。,例 用Jacobi迭代法解方程组,它的准确解是:,取初始迭代向量 X (0) = (0, 0, 0)T , 利用Jacobi迭代格式，迭代计算结果如下表：,这说明:迭代序列收敛是有条件的。,从表中可以看到，迭代序列发散.,6.3 迭代法的收敛性,Jacobi迭代格式:,Seidel迭代格式:,上面几种迭代格式都具有如下形式:,定义 设 n 阶方阵A的特征值为

9、j (j=1,2,n), 则 称为A的谱半径.,定理6.1 对任何初始向量 X (0) 和常数项f ，由迭代格式,产生的向量序列,收敛的充分必要条件是迭代矩阵的谱半径,可以看到，迭代格式是否收敛与迭代矩阵的谱半径有关,而迭代矩阵是由方程组的系数矩阵演变而来的,所以迭代格式是否收敛与系数矩阵和演变方式有关,与方程组的常数项b和初始迭代向量X (0)无关.,6.3.1 迭代法收敛性的讨论,从而得到简单迭代格式为,补充例 考察用简单迭代法和Seidel迭代法解方程组,的收敛性.,把方程组改写成,解,因而得到简单迭代矩阵为,又因M的特征方程为,所以M的特征值为,从而得知,据定理6.1, 使用简单迭代法

10、解此方程组是收敛的.,从而得到Seidel迭代矩阵为,又因M的特征方程为,所以M的特征值为,从而得知,据定理6.1,使用Seidel迭代法解此方程组是不收敛的.,求矩阵的谱半径是比较困难的,但由前面证明得知,故由,就能保证有,所以可以用,来判别迭代,法的收敛性.,需注意的是:,不能保证有,故不能用,判别不收敛.,从而得到简单迭代格式为,补充例 考察用简单迭代法解方程组,的收敛性.,把方程组改写成,解,因而得到简单迭代矩阵为,所以使用简单迭代法解此方程组是收敛的.,定理6. 2 若迭代矩阵 M的范数,，则迭代格式,对任何初始向量 X (0) 一定收敛.,定理6. 3 Jacobi迭代法收敛的充分必要条件是,的所有根 i ( i = 1 , 2 , , n )的绝对值（复数理解为模）,小于1。,从而得到,补充例 考察用简单迭代法(Jacobi迭代法)解方程组,的收敛性.,由6.3式得,解,解方程得,因而,据定理6