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

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

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

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

3、绍单步定常线性迭代法。4本讲稿第四页，共七十页收敛性定理收敛性定理5本讲稿第五页，共七十页收敛性定理（续）收敛性定理（续）6本讲稿第六页，共七十页雅可比雅可比(Jacobi)迭代法迭代法7本讲稿第七页，共七十页雅可比雅可比(Jacobi)迭代法（续）迭代法（续）8本讲稿第八页，共七十页矩阵简化记法矩阵简化记法9本讲稿第九页，共七十页收敛与解收敛与解故如果序列收敛,则收敛到解。B称迭代矩阵。10本讲稿第十页，共七十页雅可比雅可比(Jacobi)迭代法例子迭代法例子11本讲稿第十一页，共七十页Jacobi迭代法的计算过程如下：迭代法的计算过程如下：12本讲稿第十二页，共七十页高斯高斯塞德尔塞德尔（

4、Gauss-Seidel)迭代法迭代法13本讲稿第十三页，共七十页高斯高斯塞德尔迭代法（续塞德尔迭代法（续1）14本讲稿第十四页，共七十页高斯高斯塞德尔迭代法（续塞德尔迭代法（续2）15本讲稿第十五页，共七十页高斯高斯塞德尔迭代法（续塞德尔迭代法（续3）16本讲稿第十六页，共七十页高斯高斯塞德尔迭代法（续塞德尔迭代法（续4）17本讲稿第十七页，共七十页高斯高斯塞德尔迭代法（续塞德尔迭代法（续5）18本讲稿第十八页，共七十页Gauss-Seidel迭代法的计算过程如下迭代法的计算过程如下19本讲稿第十九页，共七十页松弛法松弛法20本讲稿第二十页，共七十页松弛法（续松弛法（续1）21本讲稿第二十一

5、页，共七十页松弛法（续松弛法（续2）22本讲稿第二十二页，共七十页松弛法例子松弛法例子23本讲稿第二十三页，共七十页松弛法松弛法计算过程如下计算过程如下24本讲稿第二十四页，共七十页迭代法的收敛条件矩阵的谱半径迭代法的收敛条件矩阵的谱半径25本讲稿第二十五页，共七十页矩阵的谱半径定理矩阵的谱半径定理26本讲稿第二十六页，共七十页矩阵的谱半径定理（续）矩阵的谱半径定理（续）27本讲稿第二十七页，共七十页迭代法的收敛条件迭代法的收敛条件28本讲稿第二十八页，共七十页迭代法的收敛条件（续迭代法的收敛条件（续1）29本讲稿第二十九页，共七十页迭代法的收敛条件（续迭代法的收敛条件（续2）30本讲稿第三十

6、页，共七十页迭代法例题迭代法例题31本讲稿第三十一页，共七十页例子例子32本讲稿第三十二页，共七十页迭代法例题（续迭代法例题（续1）33本讲稿第三十三页，共七十页迭代法例题（续迭代法例题（续2）34本讲稿第三十四页，共七十页严格对角占优严格对角占优35本讲稿第三十五页，共七十页迭代法收敛条件迭代法收敛条件36本讲稿第三十六页，共七十页迭代法收敛性例题迭代法收敛性例题37本讲稿第三十七页，共七十页迭代法收敛性例题（续迭代法收敛性例题（续1）38本讲稿第三十八页，共七十页迭代法收敛性例题（续迭代法收敛性例题（续2）39本讲稿第三十九页，共七十页迭代法收敛性例题（续迭代法收敛性例题（续3）40本讲稿

7、第四十页，共七十页误差估计误差估计41本讲稿第四十一页，共七十页误差估计（续误差估计（续1）42本讲稿第四十二页，共七十页误差估计（续误差估计（续2）43本讲稿第四十三页，共七十页误差估计（续误差估计（续3）44本讲稿第四十四页，共七十页线性代数方程组的表示线性代数方程组的表示45本讲稿第四十五页，共七十页高斯消去法的变形高斯消去法的变形二、平方根法二、平方根法46本讲稿第四十六页，共七十页平方根平方根(Cholesky分解法）法分解法）法47本讲稿第四十七页，共七十页平方根平方根(Cholesky分解法）法（续）分解法）法（续）48本讲稿第四十八页，共七十页例题分析例题分析例例 用平方根法求

8、解方程组用平方根法求解方程组解解 解毕故知故知解得解得49本讲稿第四十九页，共七十页改进平方根法改进平方根法50本讲稿第五十页，共七十页改进平方根法（续改进平方根法（续1）51本讲稿第五十一页，共七十页改进平方根法（续改进平方根法（续2）52本讲稿第五十二页，共七十页追赶法追赶法53本讲稿第五十三页，共七十页追赶法追赶法（续）（续）54本讲稿第五十四页，共七十页定理证明（定理证明（1）55本讲稿第五十五页，共七十页定理证明（定理证明（2）56本讲稿第五十六页，共七十页定理证明（定理证明（3）57本讲稿第五十七页，共七十页追赶法的计算公式追赶法的计算公式58本讲稿第五十八页，共七十页追赶法追赶法

9、事实上，追赶法的求解过程就是将系数矩阵分解事实上，追赶法的求解过程就是将系数矩阵分解两个简单的二对角矩阵，从而归结为求解两个简单方两个简单的二对角矩阵，从而归结为求解两个简单方程组的过程。程组的过程。上述定理也表明，追赶法的原理和高斯消去法相同，上述定理也表明，追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大量零元素撇开，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。从而大大节省计算量。59本讲稿第五十九页，共七十页追赶法例题追赶法例题例例 用追赶法解下面三对角方程组用追赶法解下面三对角方程组60本讲稿第六十页，共七十页追赶法例题（续追赶法例题（续1）解解

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

11、分解是唯一的。64本讲稿第六十四页，共七十页QR方法（续）方法（续）可证，在一定条件下，基本可证，在一定条件下，基本QR方法产生的矩阵序列方法产生的矩阵序列A(k)“基本基本”收敛于一个上三角阵（或分块上三角阵）。即主对角线收敛于一个上三角阵（或分块上三角阵）。即主对角线（或主对角线子块）及其以下元素均收敛，主对角线（或主对角（或主对角线子块）及其以下元素均收敛，主对角线（或主对角线子块）以上元素可以不收敛。特别的，如果线子块）以上元素可以不收敛。特别的，如果A是实对称阵，则是实对称阵，则A(k)“基本基本”收敛于对角矩阵。收敛于对角矩阵。因为上三角阵的主对角元（或分块上三角阵中，主对角线因为

12、上三角阵的主对角元（或分块上三角阵中，主对角线子块的特征值）即为该矩阵的特征值，故当子块的特征值）即为该矩阵的特征值，故当k充分大时，充分大时，A(k)的主对角元（或主对角线子块的特征值）就可以作为的主对角元（或主对角线子块的特征值）就可以作为A的特征值的近的特征值的近似。似。基本的基本的QR方法的主要运算是对矩阵方法的主要运算是对矩阵QR分解，分解的方法有分解，分解的方法有多种。介绍一种多种。介绍一种Schmit正交化方法。正交化方法。65本讲稿第六十五页，共七十页Schmit正交化方法正交化方法66本讲稿第六十六页，共七十页基本基本QR方法方法67本讲稿第六十七页，共七十页基本基本QR方法

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