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

《第七章解线性方程组的迭代法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第七章解线性方程组的迭代法PPT讲稿.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第1页，共70页，编辑于2022年，星期二主要知识点主要知识点雅可比迭代法雅可比迭代法高斯高斯-塞德尔迭代法塞德尔迭代法SOR方法方法迭代法的收敛性及误差估计迭代法的收敛性及误差估计2第2页，共70页，编辑于2022年，星期二解线性方程组的迭代法解线性方程组的迭代法直接法直接法:经过有限次运算后可求得方程组精确解的方经过有限次运算后可求得方程组精确解的方法法(不计舍入误差不计舍入误差!)!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）解的方法。（一般有限步内得不到精确解）直接法比

2、较适用于中小型方程组。对高阶方程组，既使系数矩直接法比较适用于中小型方程组。对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。复杂等不足。迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。程组。3第3页，共70页，编辑于2022年，星期二迭代法概述迭代法概述 迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计

3、算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。4第4页，共70页，编辑于2022年，星期二收敛性定理收敛性定理5第5页，共70页，编辑于2022年，星期二收敛性定理（续）收敛性定理（续）6第6页，共70页，编辑于2022年，星期二雅可比雅可比(Jacobi)迭代法迭代法7第7页，共70页，编辑于2022年，星期二雅可比雅可比(Jacobi)迭代法（续）迭代法（续）8第8页，共70页，编辑于2022年，星期二矩阵简化记法矩阵简化记法9第9页，共70页，编辑于2022年，星期二收敛与解收敛与解故如果序列收敛,则收敛到解。B称迭代矩阵。10第10页，共70页，编辑

4、于2022年，星期二雅可比雅可比(Jacobi)迭代法例子迭代法例子11第11页，共70页，编辑于2022年，星期二Jacobi迭代法的计算过程如下：迭代法的计算过程如下：12第12页，共70页，编辑于2022年，星期二高斯高斯塞德尔塞德尔（Gauss-Seidel)迭代法迭代法13第13页，共70页，编辑于2022年，星期二高斯高斯塞德尔迭代法（续塞德尔迭代法（续1）14第14页，共70页，编辑于2022年，星期二高斯高斯塞德尔迭代法（续塞德尔迭代法（续2）15第15页，共70页，编辑于2022年，星期二高斯高斯塞德尔迭代法（续塞德尔迭代法（续3）16第16页，共70页，编辑于2022年，星

5、期二高斯高斯塞德尔迭代法（续塞德尔迭代法（续4）17第17页，共70页，编辑于2022年，星期二高斯高斯塞德尔迭代法（续塞德尔迭代法（续5）18第18页，共70页，编辑于2022年，星期二Gauss-Seidel迭代法的计算过程如下迭代法的计算过程如下19第19页，共70页，编辑于2022年，星期二松弛法松弛法20第20页，共70页，编辑于2022年，星期二松弛法（续松弛法（续1）21第21页，共70页，编辑于2022年，星期二松弛法（续松弛法（续2）22第22页，共70页，编辑于2022年，星期二松弛法例子松弛法例子23第23页，共70页，编辑于2022年，星期二松弛法松弛法计算过程如下计算

6、过程如下24第24页，共70页，编辑于2022年，星期二迭代法的收敛条件矩阵的谱半径迭代法的收敛条件矩阵的谱半径25第25页，共70页，编辑于2022年，星期二矩阵的谱半径定理矩阵的谱半径定理26第26页，共70页，编辑于2022年，星期二矩阵的谱半径定理（续）矩阵的谱半径定理（续）27第27页，共70页，编辑于2022年，星期二迭代法的收敛条件迭代法的收敛条件28第28页，共70页，编辑于2022年，星期二迭代法的收敛条件（续迭代法的收敛条件（续1）29第29页，共70页，编辑于2022年，星期二迭代法的收敛条件（续迭代法的收敛条件（续2）30第30页，共70页，编辑于2022年，星期二迭代

7、法例题迭代法例题31第31页，共70页，编辑于2022年，星期二例子例子32第32页，共70页，编辑于2022年，星期二迭代法例题（续迭代法例题（续1）33第33页，共70页，编辑于2022年，星期二迭代法例题（续迭代法例题（续2）34第34页，共70页，编辑于2022年，星期二严格对角占优严格对角占优35第35页，共70页，编辑于2022年，星期二迭代法收敛条件迭代法收敛条件36第36页，共70页，编辑于2022年，星期二迭代法收敛性例题迭代法收敛性例题37第37页，共70页，编辑于2022年，星期二迭代法收敛性例题（续迭代法收敛性例题（续1）38第38页，共70页，编辑于2022年，星期二

8、迭代法收敛性例题（续迭代法收敛性例题（续2）39第39页，共70页，编辑于2022年，星期二迭代法收敛性例题（续迭代法收敛性例题（续3）40第40页，共70页，编辑于2022年，星期二误差估计误差估计41第41页，共70页，编辑于2022年，星期二误差估计（续误差估计（续1）42第42页，共70页，编辑于2022年，星期二误差估计（续误差估计（续2）43第43页，共70页，编辑于2022年，星期二误差估计（续误差估计（续3）44第44页，共70页，编辑于2022年，星期二线性代数方程组的表示线性代数方程组的表示45第45页，共70页，编辑于2022年，星期二高斯消去法的变形高斯消去法的变形二、

9、平方根法二、平方根法46第46页，共70页，编辑于2022年，星期二平方根平方根(Cholesky分解法）法分解法）法47第47页，共70页，编辑于2022年，星期二平方根平方根(Cholesky分解法）法（续）分解法）法（续）48第48页，共70页，编辑于2022年，星期二例题分析例题分析例例 用平方根法求解方程组用平方根法求解方程组解解 解毕故知故知解得解得49第49页，共70页，编辑于2022年，星期二改进平方根法改进平方根法50第50页，共70页，编辑于2022年，星期二改进平方根法（续改进平方根法（续1）51第51页，共70页，编辑于2022年，星期二改进平方根法（续改进平方根法（续

10、2）52第52页，共70页，编辑于2022年，星期二追赶法追赶法53第53页，共70页，编辑于2022年，星期二追赶法追赶法（续）（续）54第54页，共70页，编辑于2022年，星期二定理证明（定理证明（1）55第55页，共70页，编辑于2022年，星期二定理证明（定理证明（2）56第56页，共70页，编辑于2022年，星期二定理证明（定理证明（3）57第57页，共70页，编辑于2022年，星期二追赶法的计算公式追赶法的计算公式58第58页，共70页，编辑于2022年，星期二追赶法追赶法事实上，追赶法的求解过程就是将系数矩阵分解事实上，追赶法的求解过程就是将系数矩阵分解两个简单的二对角矩阵，从

11、而归结为求解两个简单方两个简单的二对角矩阵，从而归结为求解两个简单方程组的过程。程组的过程。上述定理也表明，追赶法的原理和高斯消去法相上述定理也表明，追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大量零元素同，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。撇开，从而大大节省计算量。59第59页，共70页，编辑于2022年，星期二追赶法例题追赶法例题例例 用追赶法解下面三对角方程组用追赶法解下面三对角方程组60第60页，共70页，编辑于2022年，星期二追赶法例题（续追赶法例题（续1）解解：先把系数矩阵分解成如下形式：先把系数矩阵分解成如下形式由递推公式可知

12、由递推公式可知61第61页，共70页，编辑于2022年，星期二追赶法例题（续追赶法例题（续2）又由递推公式（又由递推公式（4.274.27）可得：）可得：62第62页，共70页，编辑于2022年，星期二追赶法例题（续追赶法例题（续3）再由递推公式（再由递推公式（4.284.28）可得：）可得：故所求的解向量为故所求的解向量为63第63页，共70页，编辑于2022年，星期二QR方法方法60年代出现的QR算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法。实矩阵、非奇异。理论依据：任一非奇异实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是唯一的。6

13、4第64页，共70页，编辑于2022年，星期二QR方法（续）方法（续）可证，在一定条件下，基本可证，在一定条件下，基本QR方法产生的矩阵序列方法产生的矩阵序列A(k)“基本基本”收敛于一个上三角阵（或分块上三角阵）。即主对角收敛于一个上三角阵（或分块上三角阵）。即主对角线（或主对角线子块）及其以下元素均收敛，主对角线（或主对线（或主对角线子块）及其以下元素均收敛，主对角线（或主对角线子块）以上元素可以不收敛。特别的，如果角线子块）以上元素可以不收敛。特别的，如果A是实对称阵，是实对称阵，则则A(k)“基本基本”收敛于对角矩阵。收敛于对角矩阵。因为上三角阵的主对角元（或分块上三角阵中，主对角线因

14、为上三角阵的主对角元（或分块上三角阵中，主对角线子块的特征值）即为该矩阵的特征值，故当子块的特征值）即为该矩阵的特征值，故当k充分大时，充分大时，A(k)的主对角元（或主对角线子块的特征值）就可以作为的主对角元（或主对角线子块的特征值）就可以作为A的特征值的特征值的近似。的近似。基本的基本的QR方法的主要运算是对矩阵方法的主要运算是对矩阵QR分解，分解的方法有多分解，分解的方法有多种。介绍一种种。介绍一种Schmit正交化方法。正交化方法。65第65页，共70页，编辑于2022年，星期二Schmit正交化方法正交化方法66第66页，共70页，编辑于2022年，星期二基本基本QR方法方法67第6

15、7页，共70页，编辑于2022年，星期二基本基本QR方法（续）方法（续）基本基本QR方法每次迭代都需作一次方法每次迭代都需作一次QR分解与矩阵乘法，分解与矩阵乘法，计算量大，而且收敛速度慢。因此实际使用的计算量大，而且收敛速度慢。因此实际使用的QR方法是先方法是先用一系列相似变换将用一系列相似变换将A化成拟上三角矩阵（称为上化成拟上三角矩阵（称为上Hessenberg矩阵），然后对此矩阵用基本矩阵），然后对此矩阵用基本QR方法。因为拟方法。因为拟上三角矩阵具有较多零元素，故可减少运算量。化上三角矩阵具有较多零元素，故可减少运算量。化A为相为相似的拟上三角阵的方法有多种。似的拟上三角阵的方法有多种。68第68页，共70页，编辑于2022年，星期二例题分析例题分析69第69页，共70页，编辑于2022年，星期二例题分析例题分析（续）（续）70第70页，共70页，编辑于2022年，星期二