[经济学]第六章解线性方程组的迭代法.ppt

1,第6章 解线性方程组的迭代法,2,6.1 迭代法的基本概念,6.2 Jacobi迭代法与Gauss-Seidel迭代法,6.3 超松弛迭代法,6.4 共轭梯度法,3,6.1 迭代法的基本概念,考虑线性方程组,（1.1）,其中 为非奇异矩阵，当 为低阶稠密矩阵时，第5章所讨 论的选主元消去法是有效方法.,但对于 的阶数 很大，零元素较多的大型稀疏矩阵 方程组，例如求某些偏微分方程数值解所产生的线性方程 组来说，利用迭代法求解则更为合适.,迭代法通常都可利用 中有大量零元素的特点.,4,例1,（1.2）,记为 ,方程组的精确解是 .,求解方程组,其中,现将(1.2)改写为,5,（1.3）,或写为 ,其中,6,将这些值代入(1.3) 式右边 (若(1.3)式为等式即求得方程组的解，但一般不满足).,任取初始值，例如取 .,再将 分量代入(1.3)式右边得到 ，反复利用这个计 算程序，得到一向量序列和一般的计算公式(迭代公式),得到新的值,7,（1.4）,简写为,其中 表示迭代次数,迭代到第10次有,8,从此例看出，由迭代法产生的向量序列 逐步逼近,方程组的精确解 .,对于任何由 变形得到的等价方程组 ，,迭代法产生的向量序列 不一定都能逐步逼近方程组 的解 .,如对方程组,9,构造迭代法,则对任何的初始向量，得到的序列都不收敛.,对于给定方程组 ，,设有唯一解 ，,（1.5）,又设 为任取的初始向量，,（1.6）,其中 表迭代次数.,则,按下述公式构造向量序列,10,定义1,(1) 对于给定的方程组 ，,逐步代入求近似解的方法称为迭代法(或称为一阶定常迭代 法，这里 与 无关).,(2) 如果 存在(记为 )，,显然 就是方程组的解，否则称此迭代法发散.,用公式(1.6),称此迭代法收敛，,研究 的收敛性.,引进误差向量,由(1.6)减去(1.5)式，,得 ，,11,要考察 的收敛性, 就要研究 在什么条件下有,亦即要研究 满足什么条件时有,递推得,12,6.2 Jacobi迭代法与Gauss-Seidel迭代法,设有,（2.1）,其中， 为非奇异矩阵.,将 分裂为,（2.2）,其中， 为可选择的非奇异矩阵，且使 容易求解，,一般选择为 的某种近似，称 为分裂矩阵.,13,于是，求解 转化为求解 ，,即求解,可构造一阶定常迭代法,（2.3）,其中,称 为迭代法的迭代矩阵.,14,选取 阵，就得到解 的各种迭代法.,设 , 并将 写为三部分,（2.4）,15,6.2.1 雅可比迭代法,由 ，选取 为 的对角元素部分，,解 的雅可比(Jacobi)迭代法,即选取 (对角阵)， ，,（2.5）,其中,称 为解 的雅可比迭代法的迭代阵.,由(2.3)式得到,16,研究雅可比迭代法(2.5)的分量计算公式.,记,由雅可比迭代公式(2.5), 有,或,于是，解 的雅可比迭代法的分量计算公式为,17,（2.6）,18,(下三角阵)，,6.2.2 高斯-塞德尔迭代法,选取分裂矩阵 为 的下三角部分，,即选取,于是由(2.3)式得到解,（2.7）,其中,称 为解 的高斯-塞德尔迭代法的迭 代阵.,的高斯-塞德尔(Gauss-Seidel)迭代法,19,研究高斯-塞德尔迭代法的分量计算公式.,由(2.7)式有,或,即,记,20,于是解 的高斯-塞德尔迭代法计算公式为,（2.8）,或,（2.9）,21,而由高斯-塞德尔迭代公式可知，,雅可比迭代法不使用变量的最新信息计算 ，,计算 的第 个分量,时，,利用了已经计算出的最新分量 .,由(2.8)可知，高斯-塞德尔迭代法每迭代一次只需计算 一次矩阵与向量的乘法.,高斯-塞德尔迭代法可看作雅可比迭代法的一种改进.,算法1,(高斯-塞德尔迭代法),设 ，,其中 为非奇异矩阵且,本算法用高斯-塞德尔迭代法解 ，,22,迭代一次，这个算法需要的运算次数至多与矩阵 的 非零元素的个数一样多.,数组 开始存放 ,后存放,为最大迭代次数.,23,例2,按高斯-塞德尔迭代公式,迭代7次，得 ，,（1.2）,用高斯-塞德尔迭代法解线性方程组(1.2).,取 ，,24,由此例可知，用高斯-塞德尔迭代法，雅可比迭代法解 线性方程组(1.2)(且取 )均收敛.,而高斯-塞德尔迭代法比雅可比迭代法收敛较快(即取 相同，达到同样精度所需迭代次数较少).,但这结论只当 满足一定条件时才是对的.,且,25,6.3.1 解大型稀疏线性方程组的逐次超松弛迭代法,选取分裂矩阵 为带参数的下三角阵,其中 为可选择的松弛因子.,于是，由(2.3)可构造一个迭代法，其迭代矩阵为,从而得到解 的逐次超松弛迭代法(Successive Over Relaxation Method, 简称SOR方法).,6.3 逐次超松弛迭代法,26,解 的SOR方法为,（2.10）,其中,研究解 的SOR迭代法的分量计算公式.,记,27,或,由(2.10)式可得,由此，得到解 的SOR方法的计算公式,（2.11）,28,或,（2.12）,关于SOR迭代法 ， 有,(1) 显然，当 时，SOR方法即为高斯-塞德尔迭 代法.,29,(2) SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法.,(3) 当 时，称为超松弛法；当 时，称为低 松弛法.,(4) 在计算机实现时可用,控制迭代终止，或用 控制迭代 终止.,SOR迭代法是高斯-塞德尔迭代法的一种修正.,30,设已知 及已计算 的分量,(1) 首先用高斯-塞德尔迭代法定义辅助量,（2.13）,(2) 再由 与 加权平均定义 ，,将(2.13)代入(2.14)得到解 的SOR迭代(2.11)式.,即,（2.14）,31,例3,它的精确解为,取 ，迭代公式为,用SOR方法解方程组,解,32,取 ，,取其他 值，迭代次数如下表.,第11次迭代结果为,33,从此例看到，松弛因子选择得好，会使SOR迭代法的 收敛大大加速. 本例中 是最佳松弛因子.,34,6.3 迭代法的收敛性,6.3.1 一阶定常迭代法的基本定理,设,（3.1）,其中 为非奇异矩阵，,记 为(3.1)精确解，,于是,（3.2）,且设有等价的方程组,35,设有解 的一阶定常迭代法,（3.3）,问题是： 迭代矩阵 满足什么条件时，由迭代法产生 的向量序列 收敛到,引进误差向量,由(3.3)式减(3.2)式得到误差向量的递推公式,36,由6.1节可知，研究迭代法(3.3)收敛性问题就是要研究,迭代矩阵 满足什么条件时，有,定义2,设有矩阵序列 及 ,如果 个数列极限存在且有,则称 收敛于 ，,记为,37,例4,且设 ，考查其极限.,解,由于，当 时，有,设有矩阵序列,所以,38,矩阵序列极限概念可以用矩阵算子范数来描述.,定理1,证明,再利用矩阵范数的等价性，可证定理对其他算子范数亦对.,定理2,对任何向量 都有,其中为矩阵的任意一种算子范数.,显然有,（证明略）,39,定理3,设 ,则 (零矩阵)的,充分必要条件是矩阵 的谱半径,证明,由矩阵 的若当标准型，存在非奇异矩阵 使,其中若当块,40,且 ，,其中,于是,下面考查 的情况.,显然有,引进记号,41,显然有，,由于 ,因此,42,其中,利用极限 ，,所以 的充要条件是 ，,得到,即,43,定理4,（3.4）,(迭代法基本定理),设有方程组,及一阶定常迭代法,（3.5）,对任意选取初始向量 ，,矩阵 的谱半径,迭代法(3.5)收敛的充要条件是,证明,设 ，,易知,)有唯一解，,记为 ，,充分性.,(其中,则,44,误差向量,由设 ，,应用定理3，有,于是对任意 ,有 ，,必要性.,设对任意 有,其中,即,显然，极限 是方程组(3.4)的解，,且对任意 有,45,由定理2知,再由定理3，即得,推论,设 ，,其中 为非奇异矩阵,且 非奇异，则,(1) 解方程组的雅可比迭代法收敛的充要条件是 ，,其中,(2) 解方程组的高斯-塞德尔迭代法收敛的充要条件是,其中,(3) 解方程组的SOR方法收敛的充要条件是 ，,其中,46,例5,迭代矩阵 的特征方程为,解得,考察用雅可比方法解方程组（1.2）的收敛性.,（1.2）,即 .,所以用雅可比迭代法解方程组(1.2)是收敛的. ,47,例6,的收敛性，,解,考察用迭代法解方程组,其中,特征方程为,特