第七章解线性方程组的迭代法精选PPT.ppt

1第1页，本讲稿共70页主要知识点主要知识点雅可比迭代法雅可比迭代法高斯高斯-塞德尔迭代法塞德尔迭代法SOR方法方法迭代法的收敛性及误差估计迭代法的收敛性及误差估计2第2页，本讲稿共70页解线性方程组的迭代法解线性方程组的迭代法直接法直接法:经过有限次运算后可求得方程组精确解的方经过有限次运算后可求得方程组精确解的方法法(不计舍入误差不计舍入误差!)!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）逼近精确解的方法。（一般有限步内得不到精确解）直接法比较适用于中小型方程组。对高阶方程组，既使系直接法比较适用于中小型方程组。对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。大，程序复杂等不足。迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。3第3页，本讲稿共70页迭代法概述迭代法概述 迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。4第4页，本讲稿共70页收敛性定理收敛性定理5第5页，本讲稿共70页收敛性定理（续）收敛性定理（续）6第6页，本讲稿共70页雅可比雅可比(Jacobi)迭代法迭代法7第7页，本讲稿共70页雅可比雅可比(Jacobi)迭代法（续）迭代法（续）8第8页，本讲稿共70页矩阵简化记法矩阵简化记法9第9页，本讲稿共70页收敛与解收敛与解故如果序列收敛,则收敛到解。B称迭代矩阵。10第10页，本讲稿共70页雅可比雅可比(Jacobi)迭代法例子迭代法例子11第11页，本讲稿共70页Jacobi迭代法的计算过程如下：迭代法的计算过程如下：12第12页，本讲稿共70页高斯高斯塞德尔塞德尔（Gauss-Seidel)迭代法迭代法13第13页，本讲稿共70页高斯高斯塞德尔迭代法（续塞德尔迭代法（续1）14第14页，本讲稿共70页高斯高斯塞德尔迭代法（续塞德尔迭代法（续2）15第15页，本讲稿共70页高斯高斯塞德尔迭代法（续塞德尔迭代法（续3）16第16页，本讲稿共70页高斯高斯塞德尔迭代法（续塞德尔迭代法（续4）17第17页，本讲稿共70页高斯高斯塞德尔迭代法（续塞德尔迭代法（续5）18第18页，本讲稿共70页Gauss-Seidel迭代法的计算过程如下迭代法的计算过程如下19第19页，本讲稿共70页松弛法松弛法20第20页，本讲稿共70页松弛法（续松弛法（续1）21第21页，本讲稿共70页松弛法（续松弛法（续2）22第22页，本讲稿共70页松弛法例子松弛法例子23第23页，本讲稿共70页松弛法松弛法计算过程如下计算过程如下24第24页，本讲稿共70页迭代法的收敛条件矩阵的谱半径迭代法的收敛条件矩阵的谱半径25第25页，本讲稿共70页矩阵的谱半径定理矩阵的谱半径定理26第26页，本讲稿共70页矩阵的谱半径定理（续）矩阵的谱半径定理（续）27第27页，本讲稿共70页迭代法的收敛条件迭代法的收敛条件28第28页，本讲稿共70页迭代法的收敛条件（续迭代法的收敛条件（续1）29第29页，本讲稿共70页迭代法的收敛条件（续迭代法的收敛条件（续2）30第30页，本讲稿共70页迭代法例题迭代法例题31第31页，本讲稿共70页例子例子32第32页，本讲稿共70页迭代法例题（续迭代法例题（续1）33第33页，本讲稿共70页迭代法例题（续迭代法例题（续2）34第34页，本讲稿共70页严格对角占优严格对角占优35第35页，本讲稿共70页迭代法收敛条件迭代法收敛条件36第36页，本讲稿共70页迭代法收敛性例题迭代法收敛性例题37第37页，本讲稿共70页迭代法收敛性例题（续迭代法收敛性例题（续1）38第38页，本讲稿共70页迭代法收敛性例题（续迭代法收敛性例题（续2）39第39页，本讲稿共70页迭代法收敛性例题（续迭代法收敛性例题（续3）40第40页，本讲稿共70页误差估计误差估计41第41页，本讲稿共70页误差估计（续误差估计（续1）42第42页，本讲稿共70页误差估计（续误差估计（续2）43第43页，本讲稿共70页误差估计（续误差估计（续3）44第44页，本讲稿共70页线性代数方程组的表示线性代数方程组的表示45第45页，本讲稿共70页高斯消去法的变形高斯消去法的变形二、平方根法二、平方根法46第46页，本讲稿共70页平方根平方根(Cholesky分解法）法分解法）法47第47页，本讲稿共70页平方根平方根(Cholesky分解法）法（续）分解法）法（续）48第48页，本讲稿共70页例题分析例题分析例例 用平方根法求解方程组用平方根法求解方程组解解 解毕故知故知解得解得49第49页，本讲稿共70页改进平方根法改进平方根法50第50页，本讲稿共70页改进平方根法（续改进平方根法（续1）51第51页，本讲稿共70页改进平方根法（续改进平方根法（续2）52第52页，本讲稿共70页追赶法追赶法53第53页，本讲稿共70页追赶法追赶法（续）（续）54第54页，本讲稿共70页定理证明（定理证明（1）55第55页，本讲稿共70页定理证明（定理证明（2）56第56页，本讲稿共70页定理证明（定理证明（3）57第57页，本讲稿共70页追赶法的计算公式追赶法的计算公式58第58页，本讲稿共70页追赶法追赶法事实上，追赶法的求解过程就是将系数矩阵分解两事实上，追赶法的求解过程就是将系数矩阵分解两个简单的二对角矩阵，从而归结为求解两个简单方程组个简单的二对角矩阵，从而归结为求解两个简单方程组的过程。的过程。上述定理也表明，追赶法的原理和高斯消去法相上述定理也表明，追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大量零元素同，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。撇开，从而大大节省计算量。59第59页，本讲稿共70页追赶法例题追赶法例题例例 用追赶法解下面三对角方程组用追赶法解下面三对角方程组60第60页，本讲稿共70页追赶法例题（续追赶法例题（续1）解解：先把系数矩阵分解成如下形式：先把系数矩阵分解成如下形式由递推公式可知由递推公式可知61第61页，本讲稿共70页追赶法例题（续追赶法例题（续2）又由递推公式（又由递推公式（4.274.27）可得：）可得：62第62页，本讲稿共70页追赶法例题（续追赶法例题（续3）再由递推公式（再由递推公式（4.284.28）可得：）可得：故所求的解向量为故所求的解向量为63第63页，本讲稿共70页QR方法方法60年代出现的QR算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法。实矩阵、非奇异。理论依据：任一非奇异实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是唯一的。64第64页，本讲稿共70页QR方法（续）方法（续）可证，在一定条件下，基本可证，在一定条件下，基本QR方法产生的矩阵序列方法产生的矩阵序列A(k)“基本基本”收敛于一个上三角阵（或分块上三角阵）。即主对角线收敛于一个上三角阵（或分块上三角阵）。即主对角线（或主对角线子块）及其以下元素均收敛，主对角线（或主对角（或主对角线子块）及其以下元素均收敛，主对角线（或主对角线子块）以上元素可以不收敛。特别的，如果线子块）以上元素可以不收敛。特别的，如果A是实对称阵，则是实对称阵，则A(k)“基本基本”收敛于对角矩阵。收敛于对角矩阵。因为上三角阵的主对角元（或分块上三角阵中，主对角线子块因为上三角阵的主对角元（或分块上三角阵中，主对角线子块的特征值）即为该矩阵的特征值，故当的特征值）即为该矩阵的特征值，故当k充分大时，充分大时，A(k)的主对角的主对角元（或主对角线子块的特征值）就可以作为元（或主对角线子块的特征值）就可以作为A的特征值的近似。的特征值的近似。基本的基本的QR方法的主要运算是对矩阵方法的主要运算是对矩阵QR分解，分解的方法分解，分解的方法有多种。介绍一种有多种。介绍一种Schmit正交化方法。正交化方法。65第65页，本讲稿共70页Schmit正交化方法正交化方法66第66页，本讲稿共70页基本基本QR方法方法67第67页，本讲稿共70页基本基本QR方法（续）方法（续）基本基本QR方法每次迭代都需作一次方法每次迭代都需作一次QR分解与矩阵乘法，计算量分解与矩阵乘法，计算量大，而且收敛速度慢。因此实际使用的大，而且收敛速度慢。因此实际使用的QR方法是先用一系列相似方法是先用一系列相似变换将变换将A化成拟上三角矩阵（称为上化成拟上三角矩阵（称为上Hessenberg矩阵），然后对此矩阵），然后对此矩阵用基本矩阵用基本QR方法。因为拟上三角矩阵具有较多零元素，故可减方法。因为拟上三角矩阵具有较多零元素，故可减少运算量。化少运算量。化A为相似的拟上三角阵的方法有多种。为相似的拟上三角阵的方法有多种。68第68页，本讲稿共70页例题分析例题分析69第69页，本讲稿共70页例题分析例题分析（续）（续）70第70页，本讲稿共70页