《数值分析-第6章-线性代数方程组的迭代法PPT课件》由会员分享，可在线阅读，更多相关《数值分析-第6章-线性代数方程组的迭代法PPT课件（54页珍藏版）》请在金锄头文库上搜索。
1、6.1 迭代法的基本概念迭代法的基本概念6.2 雅可比迭代法与高斯雅可比迭代法与高斯-塞德尔迭代法塞德尔迭代法6.3 超松弛迭代法超松弛迭代法6.4 共轭梯度法共轭梯度法第第6 6章章 解线性方程组的迭代法解线性方程组的迭代法/* Iterative Techniques for Solving Linear Systems */4/22/20221第6章 解线性方程组的迭代法6.1 迭代法的基本概念迭代法的基本概念 考虑线性方程组考虑线性方程组 （1.1）其中其中 为非奇异矩阵。为非奇异矩阵。 迭代法通常都可利用迭代法通常都可利用 中有大量零元素的特点中有大量零元素的特点. . 6.1.1
2、引言引言 当当 为低阶稠密矩阵时，选主元消去法是有效方法为低阶稠密矩阵时，选主元消去法是有效方法. . 迭代法适用于求解大型稀疏的线性方程组。迭代法适用于求解大型稀疏的线性方程组。基本思想：基本思想：通过构造迭代格式产生迭代序列，由迭代序列通过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组的解。来逼近原方程组的解。要解决的基本问题：要解决的基本问题：1. 如何构造迭代格式如何构造迭代格式 2.迭代序列是否收敛迭代序列是否收敛4/22/20222第6章 解线性方程组的迭代法 6.1.2 向量序列与矩阵序列的极限向量序列与矩阵序列的极限 则称向量序列则称向量序列 收敛于收敛于 ，记为，记为 定
3、义定义2 设有向量序列设有向量序列 如果存在如果存在 ，使，使其中其中 为任一种向量范数为任一种向量范数. . 定义定义3 设有矩阵序列设有矩阵序列 及及 , ,如果如果 个数列极限存在且有个数列极限存在且有 则称则称 收敛于收敛于 ，记为记为 4/22/20223第6章 解线性方程组的迭代法 解解由于，当由于，当 时，有时，有 所以所以 例例1 设有矩阵序列设有矩阵序列 且设且设 ，考查其极限，考查其极限. . 证明证明范数的等价性范数的等价性 定理定理1 其中其中为矩阵的任意一种算子范数为矩阵的任意一种算子范数. . 4/22/20224第6章 解线性方程组的迭代法 证明证明 定理定理2
4、的充分必要条件是的充分必要条件是（1.7）若若 ，则，则 ，取取 为第为第 个坐标向量个坐标向量 ，则，则必要性。必要性。故对一切故对一切 ，有，有 . .表示表示 的第的第 列元素极限均为零，列元素极限均为零，当当 时，时，就得到就得到矩阵的算子范数满足矩阵的算子范数满足 充分性。充分性。4/22/20225第6章 解线性方程组的迭代法 定理定理3 设设 ，下面下面3个命题等价：个命题等价：（1 1） ；证明证明与迭代矩阵相关的结论与迭代矩阵相关的结论（2 2） ；（3 3）至少存在一种从属的矩阵范数）至少存在一种从属的矩阵范数 ，使，使反证法。反证法。假定假定 有一个特征值有一个特征值 ，
5、满足满足 , , 则存在则存在 ，使，使 ，由此由此,由由定理定理2 2知（知（1）不成立，从而知）不成立，从而知 ，即（，即（2）成立）成立.对任意对任意 ，存在一种从属范数，存在一种从属范数 ，使，使 ，适当选择适当选择 ，可使，可使 ，即（，即（3 3）成立）成立. .由矩阵范数由矩阵范数 ，可得可得 ，从而有，从而有又又4/22/20226第6章 解线性方程组的迭代法 将将 分裂为分裂为 （1.9）其中，其中， 为可选择的为可选择的非奇异矩阵非奇异矩阵，且使，且使 容易求解，容易求解，称称 为为分裂矩阵分裂矩阵. . 即求解即求解一阶定常迭代法一阶定常迭代法 （1.11）即即（1.10
6、）迭代的构造迭代的构造其中其中 迭代矩阵迭代矩阵4/22/20229第6章 解线性方程组的迭代法6.1.4 迭代法的收敛性迭代法的收敛性 研究研究 的收敛性的收敛性. . 引进误差向量引进误差向量 得得 ，递推得递推得 研究研究 在什么条件下有在什么条件下有是初始误差向量，是一个确定的值。是初始误差向量，是一个确定的值。对任意的初始向量对任意的初始向量 ，序列，序列 收敛收敛4/22/202210第6章 解线性方程组的迭代法 定理定理5 给定线性方程组给定线性方程组 及一阶定常迭代法及一阶定常迭代法 对任意选取初始向量对任意选取初始向量 ，迭代法收敛的充要条件是矩阵，迭代法收敛的充要条件是矩阵
7、 的谱半径的谱半径（1）迭代法是否收敛取决于迭代矩阵的迭代法是否收敛取决于迭代矩阵的谱半径谱半径，与初，与初始向量和常数项无关。始向量和常数项无关。（2）而对于同一个方程组，不同的迭代法对应的迭代而对于同一个方程组，不同的迭代法对应的迭代矩阵的矩阵的谱半径谱半径一般不会相同，因而收敛性也不同。一般不会相同，因而收敛性也不同。注：注：注：注：至少存在一种从属的矩阵范数至少存在一种从属的矩阵范数 ，使，使迭代法收敛的判别准则迭代法收敛的判别准则4/22/202211第6章 解线性方程组的迭代法 例例2 求解方程组求解方程组 （1.2）记为记为 , , 方程组的精确解是方程组的精确解是 . . 其中
8、其中 现将现将(1.2)改写为改写为 （1.3）或写为或写为 , , 其中其中 4/22/202212第6章 解线性方程组的迭代法 任取初始值，例如取任取初始值，例如取 . . 得到新的值得到新的值 （1.4）简写为简写为 其中其中 表示迭代次数表示迭代次数 迭代到第迭代到第10次有次有 4/22/202213第6章 解线性方程组的迭代法 对于任何由对于任何由 变形得到的等价方程组变形得到的等价方程组 ，迭代法产生的向量序列迭代法产生的向量序列 是否都能逐步逼近方程组是否都能逐步逼近方程组的解的解 ？ 如方程组如方程组构造迭代法构造迭代法对任何的初始向量，得到的序列都不收敛对任何的初始向量，得
9、到的序列都不收敛. .4/22/202214第6章 解线性方程组的迭代法例例3 考察线性方程组（考察线性方程组（1.21.2）给出的迭代法（给出的迭代法（1.4）的收敛性）的收敛性 （1.2）（1.4） 先求迭代矩阵先求迭代矩阵 的特征值的特征值. . 由特征方程由特征方程可得可得解得解得所以迭代法（所以迭代法（1.41.4）是收敛的是收敛的. .解解4/22/202215第6章 解线性方程组的迭代法例例4 考察用迭代法解方程组考察用迭代法解方程组 的收敛性，的收敛性，解解其中其中特征方程为特征方程为特征根特征根 即即 . . 这说明用此迭代法解此方程组不收敛这说明用此迭代法解此方程组不收敛.
10、 . 4/22/202216第6章 解线性方程组的迭代法 定理定理6及一阶定常迭代法及一阶定常迭代法 如果有如果有 的某种算子范数的某种算子范数 ，则，则 ( (迭代法收敛的充分条件迭代法收敛的充分条件) ) 设有方程组设有方程组 (1) 迭代法收敛，即对任取迭代法收敛，即对任取 有有 利用利用矩阵的范数判定迭代收敛只是一个充分条矩阵的范数判定迭代收敛只是一个充分条件，通常采用矩阵的件，通常采用矩阵的1- -范数、范数、 - -范数来判定。范数来判定。事后估计事后估计估计迭代次数估计迭代次数4/22/202217第6章 解线性方程组的迭代法 证明证明(2)(2)反复递推即得反复递推即得(2).
11、 (2). (1) (1) 是显然的是显然的. . 有有 (3) (3) 即即 (3)(3)反复利用反复利用( (a) )由关系式由关系式由由 4/22/202218第6章 解线性方程组的迭代法 定理定理6 6只给出迭代法（只给出迭代法（1.111.11）收敛的充分条件，即使条）收敛的充分条件，即使条件件 对任何常用范数均不成立，迭代序列仍可能收敛对任何常用范数均不成立，迭代序列仍可能收敛. . 例例5 迭代法迭代法 , ,其中其中 的各种范数均大于的各种范数均大于1 1，但但 ，故此迭代法产生的迭代序列故此迭代法产生的迭代序列 是收敛的是收敛的. .4/22/202219第6章 解线性方程组
12、的迭代法 下面考察迭代法下面考察迭代法的收敛速度的收敛速度.6.1.4 迭代法的收敛速度迭代法的收敛速度/* Rate of Average Convergence */ 假定迭代法是收敛的，即假定迭代法是收敛的，即 ，于是于是根据从属范数定义，有根据从属范数定义，有 迭代迭代 次后误差向量次后误差向量 的范数与初始误差向量的范数与初始误差向量 的范数之比的最大值的范数之比的最大值. .由由 ，得，得4/22/202220第6章 解线性方程组的迭代法平均每次迭代误差向量范数的压缩率平均每次迭代误差向量范数的压缩率其中其中 ，可取，可取 . . 因为因为 ，故，故 ，即即（1.12）它表明迭代次
13、数它表明迭代次数 与与 成反比成反比. .若要求迭代若要求迭代 次后有次后有由由 两边取对数得两边取对数得越大越大越小越小收敛越快收敛越快4/22/202221第6章 解线性方程组的迭代法 定义定义4 迭代法（迭代法（1.111.11）的）的平均收敛速度平均收敛速度定义为定义为（1.13） 定义定义5 迭代法迭代法(1.11)(1.11)的的渐近收敛速度渐近收敛速度定义为定义为 由由 ，（1.14）（1.15）估计迭代次数估计迭代次数所以所以 与迭代次数及与迭代次数及 取何种范数无关，它反映了迭代次数趋取何种范数无关，它反映了迭代次数趋于无穷时迭代法的渐近性质。于无穷时迭代法的渐近性质。当当
14、越小时越小时 越大，迭代法收敛越快越大，迭代法收敛越快。4/22/202222第6章 解线性方程组的迭代法迭代矩阵迭代矩阵 的谱半径的谱半径 即取即取 即可达到要求即可达到要求. .若要求若要求 ， 则由则由于是于是几种实用的基本迭代法几种实用的基本迭代法几种实用的基本迭代法几种实用的基本迭代法应用实例应用实例应用实例应用实例4/22/202223第6章 解线性方程组的迭代法（2.1）6.2.1 雅可比迭代法雅可比迭代法 6.2 雅可比迭代法与高斯雅可比迭代法与高斯-塞尔迭代法塞尔迭代法（1.1）设设 ，选取选取 ( (对角阵对角阵) )，（2.2）解解 的雅可比的雅可比(Jacobi)迭代法
15、迭代法其中其中 雅可比迭代法的迭代阵雅可比迭代法的迭代阵4/22/202224第6章 解线性方程组的迭代法记记 雅可比迭代雅可比迭代或或 （2.2）其中其中 （2.3）解解 的雅可比迭代法的的雅可比迭代法的分量计算公式分量计算公式 Jacobi方法是由方程组第方法是由方程组第i个方程解出个方程解出xi得到的等价方程组。得到的等价方程组。4/22/202225第6章 解线性方程组的迭代法 每迭代一次只需计算一次矩阵和向量的乘法且计算过程中每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵原始矩阵 始终不变始终不变. . 6.2.2 高斯高斯-塞德尔迭代法塞德尔迭代法 分裂矩阵分裂矩阵 取
16、为取为 的下三角部分，即的下三角部分，即 ( (下三角阵下三角阵) )，解解 的的高斯高斯-塞德尔塞德尔(Gauss-Seidel)迭代法迭代法（2.4）其中其中 高斯高斯- -塞德尔迭代法的迭代阵塞德尔迭代法的迭代阵研究高斯研究高斯- -塞德尔迭代法的分量计算公式塞德尔迭代法的分量计算公式. . 4/22/202226第6章 解线性方程组的迭代法记记 高斯高斯- -塞德尔迭代塞德尔迭代或或 即即 解解 的高斯的高斯- -塞德尔迭代法的分量计算公式塞德尔迭代法的分量计算公式 （2.5）雅可比迭代法的一种改进雅可比迭代法的一种改进4/22/202227第6章 解线性方程组的迭代法或或 （2.6）4/22/202228第6章 解线性方程组的迭代法 迭代一次，这个算法需要的运算次数至多与矩阵迭代一次，这个算法需要的运算次数至多与矩阵 的的非零元素的个数一样多非零元素的个数一样多. . 算法算法1 1 ( (高斯高斯- -塞德尔迭代法塞德尔迭代法) ) 设设 ，其中，其中 为非奇异矩阵且为非奇异矩阵且 本算法用高斯本算法用高斯- -塞德尔迭代法解塞德尔迭代法解 ，数组数组 开始存放开始存放 ,
