第四章线性代数方程组的迭代解法.ppt
《第四章线性代数方程组的迭代解法.ppt》由会员分享,可在线阅读,更多相关《第四章线性代数方程组的迭代解法.ppt(55页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、Tel:86613747E-mail:授课授课:68学分:学分:4 在第二章中我们知道,凡是迭代法都有在第二章中我们知道,凡是迭代法都有一个收敛问题,有时某种方法对一类方程组一个收敛问题,有时某种方法对一类方程组迭代收敛,而对另一类方程组进行迭代时就迭代收敛,而对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设会发散。一个收敛的迭代法不仅具有程序设计简单,适于自动计算,而且较直接法更少计简单,适于自动计算,而且较直接法更少的计算量就可获得满意的解。因此,迭代法的计算量就可获得满意的解。因此,迭代法亦是求解线性方程组,尤其是求解具有大型亦是求解线性方程组,尤其是求解具有大型稀疏矩阵
2、的线性方程组的重要方法之一。稀疏矩阵的线性方程组的重要方法之一。第四章第四章 解线性方程组的迭代法解线性方程组的迭代法4.2 4.2 迭代法的基本思想迭代法的基本思想 迭代法的基本思想是将线性方程组转化迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组,对任选一组初始为便于迭代的等价方程组,对任选一组初始值值 ,按某种计算规则,不断地,按某种计算规则,不断地对所得到的值进行修正,最终获得满足精度对所得到的值进行修正,最终获得满足精度要求的方程组的近似解要求的方程组的近似解。设设 非奇异,非奇异,则线性方程组,则线性方程组 有惟一解有惟一解 ,经过变换构造,经过变换构造出一个等价同解方程组
3、出一个等价同解方程组将上式改写成迭代式将上式改写成迭代式选定初始向量选定初始向量 ,反复不断反复不断地使用迭代式逐步逼近方程组的精确解地使用迭代式逐步逼近方程组的精确解,直直到满足精度要求为止。这种方法称为迭代法到满足精度要求为止。这种方法称为迭代法 如果如果 存在极限存在极限则称迭代法是收敛的,否则就是发散的。则称迭代法是收敛的,否则就是发散的。收敛时,在迭代公式收敛时,在迭代公式中当中当 时,时,,则则,故故 是方程组是方程组 的解。的解。对于给定的方程组可以构造各种迭代公式。对于给定的方程组可以构造各种迭代公式。并非全部收敛并非全部收敛 例例4.1 4.1 用迭代法求解线性方程组用迭代法
4、求解线性方程组 解解 构造方程组的等价方程组构造方程组的等价方程组据此建立迭代公式据此建立迭代公式 取取 计算得计算得 迭代解离精确解迭代解离精确解 越来越远迭代不收敛越来越远迭代不收敛 4.3 雅可比(雅可比(Jacobi)迭代法迭代法4.3.14.3.1雅可比迭代法算法构造雅可比迭代法算法构造 例例4.2 4.2 用雅可比迭代法求解方程组用雅可比迭代法求解方程组 解:从方程组的三个方程中分离出解:从方程组的三个方程中分离出 和和 建立迭代公式建立迭代公式 取初始向量取初始向量进行迭代进行迭代,可以逐步得出一个近似解的序列:可以逐步得出一个近似解的序列:(k=1,2,)直到求得的近似解能达到
5、预先要求的精度,直到求得的近似解能达到预先要求的精度,则迭代过程终止,以最后得到的近似解作为线则迭代过程终止,以最后得到的近似解作为线性方程组的解。性方程组的解。当迭代到第当迭代到第10次有次有计算结果表明,此迭代过程收敛于方程组的精计算结果表明,此迭代过程收敛于方程组的精确解确解x*=(3,2,1)T。考察一般的方程组,将考察一般的方程组,将n n元线性方程组元线性方程组 写成写成 若若 ,分离出变量分离出变量 据此建立迭代公式据此建立迭代公式 上式称为解方程组的上式称为解方程组的JacobiJacobi迭代公式。迭代公式。4.3.4.3.2 雅可比迭代法的矩阵表示雅可比迭代法的矩阵表示 设
6、方程组设方程组 的系数矩阵的系数矩阵A A非奇异,且主对非奇异,且主对角元素角元素 ,则可将,则可将A A分裂成分裂成 记作记作 A=L+D+U 则则 等价于等价于即即因为因为 ,则则这样便得到一个迭代公式这样便得到一个迭代公式令令则有则有(k=0,1,2)称为雅可比迭代公式称为雅可比迭代公式,B称为雅可比迭代矩阵称为雅可比迭代矩阵其中其中 在例在例4.24.2中中,由迭代公式写出雅可比迭代矩阵为由迭代公式写出雅可比迭代矩阵为 雅可比迭代矩阵表示法,主要是用来讨论其收敛雅可比迭代矩阵表示法,主要是用来讨论其收敛性,实际计算中,要用雅可比迭代法公式的分量性,实际计算中,要用雅可比迭代法公式的分量
7、形式。即形式。即(k=0,1,2,)4 4.3 3.3 3 雅雅可可比比迭迭代代法法的的算算法法实实现现 4.4 高斯高斯-塞德尔(塞德尔(Gauss-Seidel)迭代法迭代法4.4.1 高斯高斯-塞德尔迭代法的基本思想塞德尔迭代法的基本思想 在在Jacobi迭迭代代法法中中,每每次次迭迭代代只只用用到到前前一一次次的的迭迭代代值值,若若每每次次迭迭代代充充分分利利用用当当前前最最新新的的迭迭代代值值,即在求即在求 时用新分量时用新分量代替旧分量代替旧分量 ,就得到高斯就得到高斯-赛德尔迭代法。其迭代法格式为:赛德尔迭代法。其迭代法格式为:(i=1,2,=1,2,n k=0,1,2,=0,1
8、,2,)例例4.3 用用GaussSeidel 迭代格式解方程组迭代格式解方程组 精确要求为精确要求为=0.005=0.005 解解 GaussGaussSeidel Seidel 迭代格式为迭代格式为取初始迭代向量取初始迭代向量 ,迭代结果为:迭代结果为:x*4.4.2 GaussSeidel 迭代法的矩阵表示迭代法的矩阵表示 将将A分裂成分裂成A=L+D+U,则则 等价于等价于 (L+D+U)L+D+U)x=b=b 于是于是,则高斯则高斯塞德尔迭代过程塞德尔迭代过程 因为因为 ,所以所以 则高斯则高斯-塞德尔迭代形式为:塞德尔迭代形式为:故故 令令 4.4.3 高斯高斯塞德尔迭代算法实现塞
9、德尔迭代算法实现 高高斯斯-塞塞德德尔尔迭迭代代算算法法的的计计算算步步骤骤与与流流程程图图与雅可比迭代法大致相同,只是一旦求出变元与雅可比迭代法大致相同,只是一旦求出变元的某个新值的某个新值 后后,就改用新值就改用新值 替代老值替代老值 进行这一步剩下的计算。进行这一步剩下的计算。高斯高斯-塞德尔迭代算法的塞德尔迭代算法的程序实现程序实现(见附录见附录A A-7 用高斯用高斯塞德尔迭代法求解线塞德尔迭代法求解线 性方程组性方程组)4.5.5 超松弛迭代法(超松弛迭代法(SOR方法)方法)使用迭代法的困难在于难以估计其计算使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛,但由于收敛速
10、量。有时迭代过程虽然收敛,但由于收敛速度缓慢,使计算量变得很大而失去使用价值度缓慢,使计算量变得很大而失去使用价值。因此,迭代过程的加速具有重要意义。逐。因此,迭代过程的加速具有重要意义。逐次超松弛迭代(次超松弛迭代(Successive Over Successive Over relaxatic relaxatic MethodMethod,简称简称SORSOR方法)法,可以看作是带参方法)法,可以看作是带参数的高斯数的高斯塞德尔迭代法,实质上是高斯塞德尔迭代法,实质上是高斯-塞塞德尔迭代的一种加速方法。德尔迭代的一种加速方法。4.5.1超松弛迭代法的基本思想超松弛迭代法的基本思想 超松弛
11、迭代法目的是为了提高迭代法的收敛速超松弛迭代法目的是为了提高迭代法的收敛速度,在高斯度,在高斯塞德尔迭代公式的基础上作一些修改。塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果这种方法是将前一步的结果 与高斯与高斯-塞德尔迭塞德尔迭代方法的迭代值代方法的迭代值 适当加权平均,期望获得更好适当加权平均,期望获得更好的近似值的近似值 。是解大型稀疏矩阵方程组的有效方。是解大型稀疏矩阵方程组的有效方法之一,有着广泛的应用。法之一,有着广泛的应用。其具体计算公式如下:其具体计算公式如下:用高斯用高斯塞德尔迭代法定义辅助量。塞德尔迭代法定义辅助量。把把 取为取为 与与 的加权平均,即的加权平均
12、,即 合并表示为:合并表示为:式中系数式中系数称为称为松弛因子松弛因子,当,当=1时,便为高斯时,便为高斯-塞德尔迭代法。为了保证迭代过程收敛,要求塞德尔迭代法。为了保证迭代过程收敛,要求0 2。当当0 1时,低松弛法;当时,低松弛法;当1 2时时称为超松弛法。但通常统称为超松弛法称为超松弛法。但通常统称为超松弛法(SOR)。4.5.2 超松弛迭代法的矩阵表示超松弛迭代法的矩阵表示设线性方程组设线性方程组 的系数矩阵的系数矩阵A非奇异非奇异,且主对且主对角元素角元素 ,则将则将A A分裂成分裂成A=L+D+U,A=L+D+U,则超松弛迭代公式用矩阵表示为则超松弛迭代公式用矩阵表示为或或 故故
13、显然对任何一个显然对任何一个值值,(,(D+L)D+L)非奇异非奇异,(,(因为假设因为假设 )于是超松弛迭代公式为于是超松弛迭代公式为 令令则超松弛迭代则超松弛迭代公式可写成公式可写成 例例4.4 用用SOR法求解线性方程组法求解线性方程组 取取=1.46,要求要求 解:解:SOR迭代公式迭代公式 k=0,1,2,,初值初值 该方程组的精确解该方程组的精确解只需迭代只需迭代20次便可达到精度要求次便可达到精度要求 如果取如果取=1(即高斯即高斯塞德尔迭代法塞德尔迭代法)和同一初和同一初值值 ,要达到同样精度要达到同样精度,需要迭代需要迭代110次次4.6 迭代法的收敛性迭代法的收敛性 我们知
14、道我们知道,对于给定的方程组可以构造成对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯简单迭代公式、雅可比迭代公式、高斯-塞德塞德尔迭代公式和超松弛迭代公式,但并非一定尔迭代公式和超松弛迭代公式,但并非一定收敛。现在分析它们的收敛性。收敛。现在分析它们的收敛性。对于方程组对于方程组 经过等价变换构造出的等价方程组经过等价变换构造出的等价方程组 在什么条件下迭代序列在什么条件下迭代序列 收敛?先引入收敛?先引入如下定理如下定理 定理定理4.1 对给定方阵对给定方阵G,若若 ,则则 为非奇异矩阵为非奇异矩阵,且且 证证:用反证法用反证法,若若 为奇异矩阵为奇异矩阵,则存在非零向则存在非
15、零向 量量x,使使 ,即有即有 由相容性条件得由相容性条件得 由于由于 ,两端消去两端消去 ,有有 ,与已知条件与已知条件矛盾矛盾,假设不成立假设不成立,命题得证。命题得证。又由于又由于 有有 即即 将将G分别取成分别取成G和和-G,再取范数再取范数 又已知又已知 ,有有 定理定理4.2 4.2 迭代公式迭代公式 收敛收敛的充分必要条件是迭代矩阵的充分必要条件是迭代矩阵G的谱半径的谱半径证证:必要性必要性 设迭代公式收敛设迭代公式收敛,当当kk时时,则在迭代公式两端同时取极限得则在迭代公式两端同时取极限得记记 ,则则 收敛于收敛于0(0(零向量零向量),),且有且有 于是于是 由于由于 可以是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 线性代数 方程组 解法
限制150内