《第六章线性方程组的数值解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第六章线性方程组的数值解优秀PPT.ppt（180页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章线性方程组的数值解第一页，本课件共有180页本章解决的问题：线性代数方程组的基本解法。本章解决的问题：线性代数方程组的基本解法。1 引言第二页，本课件共有180页 矩阵形式表示为矩阵形式表示为:AX=b,其中其中当当A A非奇异时，非奇异时，detdet A A00，方程组有唯一解。，方程组有唯一解。n n个未知量个未知量n n个方程的线性代数方程组个方程的线性代数方程组第三页，本课件共有180页解线性方程组的解线性方程组的两类方法两类方法：直接法直接法:经过有限次运算后可求得方程组精确解的方法经过有限次运算后可求得方程组精确解的方法(不计不计舍入误差舍入误差!)!)迭代法迭代法：从解的
2、某个近似值出发，通过构造一个无穷序列：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）去逼近精确解的方法。（一般有限步内得不到精确解）第四页，本课件共有180页一一.Gauss 消去法过程消去法过程:1.消元消元:2.Gauss 消去法第五页，本课件共有180页=思思路路首先将方程组首先将方程组Ax=b 化为上三角方程组，化为上三角方程组，此过程称为此过程称为消去过程消去过程，再求解上三角方程，再求解上三角方程组，此过程称为组，此过程称为回代过程回代过程.第六页，本课件共有180页2.回代过程回代过程:第七页，本课件共有180页 矩阵形式表示为矩阵形式
3、表示为:AX=b,其中其中当当A A非奇异时，非奇异时，detdet A A00，方程组有唯一解。，方程组有唯一解。n n个未知量个未知量n n个方程的线性代数方程组个方程的线性代数方程组二二.一般线性方程组的一般线性方程组的Gauss 消去法计算过程消去法计算过程第八页，本课件共有180页第一步：记乘数为:第九页，本课件共有180页相当于第一个方程(-乘数mi1)加到第i方程上去得到等价方程:第十页，本课件共有180页第十一页，本课件共有180页 上述消元过程除第一个方程不变以外,第2至第 n 个方程全消去了变量x1，而系数 和常数项全得到新值.第十二页，本课件共有180页第十三页，本课件共
4、有180页第十四页，本课件共有180页第k-1次消元得到第十五页，本课件共有180页k次消元第十六页，本课件共有180页第十七页，本课件共有180页系数矩阵与常数项：第十八页，本课件共有180页回代过程算法第十九页，本课件共有180页问题问题1.消元过程能按顺序进行到底的充要条件是什么？消元过程能按顺序进行到底的充要条件是什么？答：答：问题问题2.在原方程组的系数矩阵中如何反映出这个条件呢在原方程组的系数矩阵中如何反映出这个条件呢?称为消元过程的称为消元过程的主元素主元素。第二十页，本课件共有180页A的的k阶顺序主子矩阵阶顺序主子矩阵Ak的行列式值是的行列式值是:就是要求就是要求A的所有顺序
5、主子式均不为的所有顺序主子式均不为0，第二十一页，本课件共有180页定理定理1 (高斯消去法高斯消去法)设设Ax=b，其中，其中ARnn。如果约化的主元素如果约化的主元素a kk0(k=1,2,n)，则可通过，则可通过高斯消去法高斯消去法(不进行交换两行的初等交换不进行交换两行的初等交换)将方将方程组程组Ax=b约化为三角形矩阵方程组且消元和求约化为三角形矩阵方程组且消元和求解公式为解公式为(1)消元计算消元计算k=1,2,n-1第二十二页，本课件共有180页(2)(2)回代回代第二十三页，本课件共有180页四、Gauss消去法乘法计算量(1)消元计算：在第消元计算：在第k步步(k=1,2.n
6、-1)1、计算乘数：需作、计算乘数：需作n-k次除法运算；次除法运算；2、消元：需作有、消元：需作有(n-k)2次乘法运算次乘法运算 3、计算、计算b(k):需作需作(n-k)次乘法运算；次乘法运算；第二十四页，本课件共有180页高斯消去法解方程组高斯消去法解方程组Ax=b的计算量即总共为的计算量即总共为 除法运算次数为除法运算次数为n次次.乘法运算次数为乘法运算次数为(n-1)+1=n(n-1)/2次；共需要作次；共需要作n(n1)/2次乘除法运算。次乘除法运算。（2）回代过程的计算）回代过程的计算通常也说通常也说GaussGauss消去法的运算次数与消去法的运算次数与n n3 3同阶同阶,
7、记为记为O(nO(n3 3)第二十五页，本课件共有180页第二十六页，本课件共有180页第二十七页，本课件共有180页第二十八页，本课件共有180页6.3 选主元高斯消去法选主元高斯消去法第二十九页，本课件共有180页 为避免这种情况的发生,可通过交换方程的次序，选取绝对值大的元素作主元.基于这种思想导出了主元素法在高斯消去法消去过程中可能出现 的情况，这时高斯消去法将无法进行；即使主因素 但很小，其作除数，也会导致其它元素数量级的严重增长和舍误差的扩散第三十页，本课件共有180页例：例：单精度解方程组单精度解方程组/*精确解为精确解为 和和 */8个个8个个用用Gaussian 消元法计算：
8、消元法计算：8个个小主元可能导致计算失小主元可能导致计算失败。败。第三十一页，本课件共有180页选主元高斯消去法选主元高斯消去法基本思想：基本思想：每次消元前按一定的范围选取绝对值最大的元素作为主元每次消元前按一定的范围选取绝对值最大的元素作为主元素素,以便减少舍入误差的影响。以便减少舍入误差的影响。主要有主要有列主元高斯消去法列主元高斯消去法和和全主元高斯消去法全主元高斯消去法.第三十二页，本课件共有180页1.列主元消元法思想列主元消元法思想若交换k行和j行行的交换，不改变方程组的解，同时又有效地克服了Gauss消元地缺陷,这种方法称为这种方法称为列主元列主元Gauss消去法。消去法。例：
9、例：一、列主元消元法思想列主元消元法思想在第在第k k步消元前，在系数矩阵第步消元前，在系数矩阵第k k列的对角线以下的列的对角线以下的元素中找出绝对值最大的元。元素中找出绝对值最大的元。第三十三页，本课件共有180页交换2.列主元消元法步骤列主元消元法步骤:第一步第一步:从第一列中选出绝对值最大的元素从第一列中选出绝对值最大的元素第三十四页，本课件共有180页第第k步步 从从 的第的第k列列 ，中选取绝对值最大项，中选取绝对值最大项，记录所在行，即记录所在行，即 若若 交换第交换第k行与行与 行的所有对应元素，再进行行的所有对应元素，再进行顺序消元。顺序消元。具体如下具体如下:第三十五页，本
10、课件共有180页当当k-1列消元后增广矩阵为列消元后增广矩阵为 第第k次消元时，先选列主元素，即在第次消元时，先选列主元素，即在第k列列 以下的各元素中寻以下的各元素中寻找绝对值最大的元素作为主元素找绝对值最大的元素作为主元素,即确定即确定ik，使，使中之最大者。中之最大者。为为第三十六页，本课件共有180页第三十七页，本课件共有180页第三十八页，本课件共有180页二、全主元高斯消去法二、全主元高斯消去法全主元消去法，在第全主元消去法，在第k k列列(k=1,2,(k=1,2,，n-1)n-1)消元时，从系消元时，从系数矩阵的右下角数矩阵的右下角(n-k+1)(n-k+1)阶子矩阵中，选取绝
11、对值最大的阶子矩阵中，选取绝对值最大的元素元素作为主元素。作为主元素。1 1、全主元高斯消去法基本思想、全主元高斯消去法基本思想:第三十九页，本课件共有180页设有线性方程组设有线性方程组Ax=b，其中，其中A为非奇异矩阵。方程为非奇异矩阵。方程组的增广矩阵为组的增广矩阵为2 2、全主元高斯消去法步骤、全主元高斯消去法步骤:第四十页，本课件共有180页第1步(k=1)：首先在A中选主元素，即选择i1,j1使 再交换(A,b)的第1行 与第i1行元素，交换A的第1列与第j1列元 素，将ai1 j1调到(1,1)位置(交换后增广阵为简 单起见仍记为(A,b)；然后,进行消元计算。第四十一页，本课件
12、共有180页第四十二页，本课件共有180页第四十三页，本课件共有180页 Gauss Gauss 全主元消去法：全主元消去法：优点优点-计算结果更可靠；计算结果更可靠；缺点缺点-挑主元花机时更多，挑主元花机时更多，次序有变动，程序复杂。次序有变动，程序复杂。第四十四页，本课件共有180页矩阵的三角分解矩阵的三角分解第四十五页，本课件共有180页4 4 三角分解法三角分解法 一一.高斯消元法的矩阵形式高斯消元法的矩阵形式 从矩阵理论来看Gauss消元法的第k步消去过程相当于左乘初等变换矩阵Lk第四十六页，本课件共有180页第四十七页，本课件共有180页第四十八页，本课件共有180页第四十九页，本
13、课件共有180页A 的的 LU 分解分解第五十页，本课件共有180页第五十一页，本课件共有180页证明：由证明：由1中定理可知，中定理可知，LU 分解存在。下面证明唯一性。分解存在。下面证明唯一性。若不唯一，则可设若不唯一，则可设 A=L1U1=L2U2，推出，推出上三角矩阵上三角矩阵对角线上为对角线上为1 1的下的下三角矩阵三角矩阵注注注注：（1 1）L 为单位下三角阵而为单位下三角阵而 U 为为一般一般上三角阵的分解上三角阵的分解称为称为Doolittle 分解分解（2）L 为一般下三角阵而为一般下三角阵而 U 为为单位单位上三角阵的分解称为上三角阵的分解称为Crout 分解分解。定理定理
14、2 2 (矩阵的矩阵的LULU分解分解)设设ARnn。如果。如果A A的顺序主子式的顺序主子式det(Ai)0,(,(i=1,2,n-1)，则，则A可分解为一个单位下三角可分解为一个单位下三角阵阵L与一个上三角阵与一个上三角阵U U的乘积，即的乘积，即A=LU，且分解是惟一的。且分解是惟一的。第五十二页，本课件共有180页杜利特尔分解杜利特尔分解(Doolittle)常用的另一种三角分解：常用的另一种三角分解：克劳特分解克劳特分解(Crout)第五十三页，本课件共有180页通过比较法直接导出通过比较法直接导出L 和和 U 的计算公式。的计算公式。1.思思路路二二.Doolittle.Dooli
15、ttle分解法分解法 ：第五十四页，本课件共有180页第五十五页，本课件共有180页第五十六页，本课件共有180页2.一般计算公式一般计算公式比较第1行：比较第1列：第五十七页，本课件共有180页第五十八页，本课件共有180页第五十九页，本课件共有180页第六十页，本课件共有180页第六十一页，本课件共有180页 设设A非奇异，并有三角分解非奇异，并有三角分解A=LU，则方程组，则方程组 Ax=b 就就化为化为 LUx=b 只须求解两个简单的三角形方程组：只须求解两个简单的三角形方程组：（1）解）解Ly=b 求出求出 y，(2)解解Ux=y，求出，求出x.三三.LU.LU 分解求解线性方程组分
16、解求解线性方程组第六十二页，本课件共有180页(1).解解Ly=b 求出求出 y，第六十三页，本课件共有180页展开方程组展开方程组Ly=b,得得第六十四页，本课件共有180页(2).解解Ux=y，求出，求出x.展开方程组展开方程组Ux=y,得得第六十五页，本课件共有180页第六十六页，本课件共有180页总运算量为：第六十七页，本课件共有180页四四.例题例题第六十八页，本课件共有180页第六十九页，本课件共有180页第七十页，本课件共有180页第七十一页，本课件共有180页第七十二页，本课件共有180页练习练习1：试求矩阵试求矩阵的杜利特尔分解，克劳特分解的杜利特尔分解，克劳特分解练习练习2
17、:用杜利特尔分解法求解方程组用杜利特尔分解法求解方程组第七十三页，本课件共有180页定理定理3：设A为非奇异阵，则必存在置换矩阵P，使得其中L为单位下三角阵，U为非奇异的上三角阵。第七十四页，本课件共有180页5 求解三对角方程组的追赶法求解三对角方程组的追赶法第七十五页，本课件共有180页在实际问题中如样条插值及常微分方程边值问题的数值解中，会遇到求解三对角线形线组：b1x1+c1x2=f1a2x1+b2x2+c2x3=f2 a3x2+b3x3 +c3x4=f3 an-1xn-2+bn-1xn-1+cn-1xn=fn-1 an xn-1+bnxn=fn5 求解三对角方程组的追赶法求解三对角方
18、程组的追赶法第七十六页，本课件共有180页 A 为三对角阵，且满足为三对角阵，且满足对于具有以上条件的方程组，我们介绍下述的追赶法求解。追赶法具有计算量少，方法简单，算法稳定等特点。第七十七页，本课件共有180页第七十八页，本课件共有180页第七十九页，本课件共有180页第八十页，本课件共有180页第八十一页，本课件共有180页第八十二页，本课件共有180页第一步第一步:对对 A 作作Crout 分解分解第八十三页，本课件共有180页直接比较等式两边的元素，可得到计算公式（直接比较等式两边的元素，可得到计算公式（p.184）可得到计算公式可得到计算公式第八十四页，本课件共有180页第二步第二步
19、:追追即解即解 ：第三步第三步:赶赶即解即解 ：第八十五页，本课件共有180页追赶法公式实际上就是把高斯消元法用到求解三对角线方程组上去的结果，这时由于A特别简单，因此使得求解的计算公式非常简单，而且计算量仅有5n-4次乘除法。3n-3次加减法，工作量小，电算时，需要3个一维数组存储A的系数，两个一维数组保存中间结果。第八十六页，本课件共有180页例6 用追赶法解方程组第八十七页，本课件共有180页练习:用追赶法解线组第八十八页，本课件共有180页66对称正定阵的平方根法对称正定阵的平方根法第八十九页，本课件共有180页设有方程组设有方程组Ax=b，其中，其中，ARnn。若。若A A满满足下述
20、条件，则称足下述条件，则称A A为对称正定矩阵。为对称正定矩阵。一一.对称正定阵对称正定阵对任意非零向量对任意非零向量xRn，则有则有(Ax,x)=xTAx0。A对称，即对称，即AT=A；第九十页，本课件共有180页回顾：回顾：对称正定阵对称正定阵A的几个重要性质的几个重要性质（1）A 1 亦对称正定，且亦对称正定，且 aii 0（2）A 的顺序主子阵的顺序主子阵 Ak 亦对称正定亦对称正定（3）A 的特征值的特征值 i 0(i=1,2,n)（4）A 的全部顺序主子式的全部顺序主子式 det(Ak)0(i=1,2,n)二二.对称正定阵对称正定阵重要性质重要性质第九十一页，本课件共有180页三三
21、 对称正定阵的对称正定阵的LDLT分解分解 设设A A为对称正定矩阵，则由定理知，为对称正定矩阵，则由定理知，A A有有惟一的三角分解惟一的三角分解为利用为利用A的对称性的对称性,将将U分解为分解为U=DU0其中其中第九十二页，本课件共有180页于是，（6.6.2）第九十三页，本课件共有180页第九十四页，本课件共有180页由矩阵三角分解的惟一性，则由矩阵三角分解的惟一性，则从而对称正定矩阵从而对称正定矩阵A有惟一分解式有惟一分解式（6.6.3）由式由式(6.6.2)可知可知第九十五页，本课件共有180页于是，对角阵于是，对角阵D还可以分解为还可以分解为代入式代入式(6.6.3)，则有，则有第
22、九十六页，本课件共有180页定理定理6(对称正定阵的三角分解对称正定阵的三角分解)设设A为为n阶对称正定矩阵，则有三角分解：阶对称正定矩阵，则有三角分解：A=LDLT，其其中中L为为单单位位下下三三角角阵阵，D为为对角阵，或对角阵，或 A=LLT，其其中中，L为为下下三三角角阵阵且且当当限限定定L的的对对角角元元素素为为正正时时，这这种种分分解解是是惟惟一一的的，这种矩阵分解称为这种矩阵分解称为(Cholesky)分解。分解。第九十七页，本课件共有180页下面推导实现分解计算下面推导实现分解计算A=LLT的递推公式及求解公式。的递推公式及求解公式。设有设有Ax=b，其中，其中ARnn为对称正定
23、矩阵，于是有三角分解为对称正定矩阵，于是有三角分解 四四.计算计算A=LLT的递推公式，及求解公式。的递推公式，及求解公式。其中，其中，lii0(i=1,2,n)。第九十八页，本课件共有180页由矩阵乘法，则有L的第1列元素同理，可确定L的第j列元素lij(i=j,n)。(当 jk时，则ljk=0)第九十九页，本课件共有180页第一百页，本课件共有180页第一百零一页，本课件共有180页Cholesky分解法缺点及优点分解法缺点及优点 优点：可以减少存储单元。优点：可以减少存储单元。缺点：存在开方运算，可能会出现根号下负数。缺点：存在开方运算，可能会出现根号下负数。第一百零二页，本课件共有18
24、0页由分解公式有所以说明说明ljk是有界的是有界的,数量级不会增长数量级不会增长,因此平方根法因此平方根法计计算算是是数值稳定的数值稳定的第一百零三页，本课件共有180页例7:用平方根法求以下方程组的解.求得x=(1.0,-1.0,2.0)第一百零四页，本课件共有180页Cholesky分解法要用到开方运算，为避免开方运算，可将A分解为A=LDLT(其中L为单位下三角矩阵)，再分别解方程组LY=b及DLTX=Y或，这种方法称为改进平方根法.第一百零五页，本课件共有180页7.向量和矩阵的范数向量和矩阵的范数第一百零六页，本课件共有180页为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们
25、需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，向量和矩阵的范数。第一百零七页，本课件共有180页定义7.1 (向量范数)如果向量xRn的某个实值函数N(x)x满足条件正定条件：x0且x=0 x=0向量;齐次性：x=x，为实数或复数;三角不等式：x+yx+y，对任意向量x,yRn。称N(x)x是Rn上的一个向量范数(或向量的模)。一:向量范数向量范数1.向量范数定义向量范数定义第一百零八页，本课件共有180页利用三角不等式可推得(见图6.2)|x-y|x-y第一百零九页，本课件共有180页定义7.2 设x=(x1,x2,xn)TRn，定义Rn上3种常用的向量范数2:几
26、种常用的向量范数几种常用的向量范数向量的向量的“2”范数范数向量的向量的“”范数范数 向量的向量的“1”范数范数 第一百一十页，本课件共有180页第一百一十一页，本课件共有180页第一百一十二页，本课件共有180页定义3 (向量序列的极限)设x(k)为向量序列，记x(k)=(x1(k),x2(k),xn(k)TRn及x*=(x1*,xn*)T Rn。如果n个数列极限存在且则称x(k)收敛于x*，记为 3:向量序列的极限向量序列的极限第一百一十三页，本课件共有180页定理7 设x(k)是Rn中一向量序列，且x*Rn，则证只就=证明。显然有第一百一十四页，本课件共有180页1.定义定义7.4 (矩
27、阵的范数矩阵的范数)如果矩阵ARnn的某个非负实值函数N(A)=A满足下述条件正定性：A0，且A=0A=0矩阵；齐次性：A=A，为实数或复数；三角不等式：A+BA+B，对任意矩阵A,BRnn；ABAB。则称N(A)=A是Rnn上一个矩阵范数(或模)。二二:矩阵的范数矩阵的范数第一百一十五页，本课件共有180页2.相容范数相容范数第一百一十六页，本课件共有180页3.算子范数算子范数注:|A|满足相容性的条件第一百一十七页，本课件共有180页定理8 (矩阵范数计算公式)设xRn，AR nn，则其中max(ATA)表示ATA的最大特征值。4.(矩阵范数计算公式矩阵范数计算公式)对应于对应于3种常见
28、的向量范数，有种常见的向量范数，有3种矩阵范数种矩阵范数第一百一十八页，本课件共有180页三三 例题例题第一百一十九页，本课件共有180页第一百二十页，本课件共有180页8 线性代数方程组的迭代解法线性代数方程组的迭代解法 迭代法亦是求解线性方程组，尤其是求解具有大型迭代法亦是求解线性方程组，尤其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。稀疏矩阵的线性方程组的重要方法之一。第一百二十一页，本课件共有180页一一.迭代法的基本思想迭代法的基本思想 (1)将线性方程组转化为便于迭代的等价方程组，将线性方程组转化为便于迭代的等价方程组，线性方程组线性方程组迭代法的思想迭代法的思想:A非奇异非
29、奇异,方程组有惟一解方程组有惟一解(2)改写成迭代格式改写成迭代格式(3)对任选一组初始值对任选一组初始值 ，按迭代，按迭代格式逐步迭代格式逐步迭代,得到向量序列得到向量序列x(k)第一百二十二页，本课件共有180页(4)如果如果 存在极限存在极限则称迭代法是收敛的，否则就是发散的。则称迭代法是收敛的，否则就是发散的。即即:这种方法称为迭代法这种方法称为迭代法第一百二十三页，本课件共有180页当当 时，时，,则则 ,故故 是是方程组方程组 的解。的解。收敛时，在迭代公式收敛时，在迭代公式第一百二十四页，本课件共有180页实例分析实例分析例题例题10求求解解方方程程组组矩阵形式：第一百二十五页，
30、本课件共有180页首先将首先将Ax=b转化为等价方程组转化为等价方程组解：有精确解解：有精确解第一百二十六页，本课件共有180页第一百二十七页，本课件共有180页迭代公式迭代公式如果取初始向量如果取初始向量第一百二十八页，本课件共有180页迭代结果分析迭代结果分析：并不是每一个迭代公式所：并不是每一个迭代公式所构造的迭代序列都收敛。于是，计算方法构造的迭代序列都收敛。于是，计算方法的目的就是要寻求一个使得构造序列收敛的目的就是要寻求一个使得构造序列收敛的方法。因此产生了各种各样的迭代方法，的方法。因此产生了各种各样的迭代方法，根据迭代矩阵的不同构造方法，形成了不根据迭代矩阵的不同构造方法，形成
31、了不同的迭代方法。这里介绍两种迭代方法：同的迭代方法。这里介绍两种迭代方法：雅可比迭代方法、高斯雅可比迭代方法、高斯-塞德尔迭代方法以塞德尔迭代方法以及超松弛迭代方法及超松弛迭代方法。并有记：。并有记：第一百二十九页，本课件共有180页设方程组的系数矩阵设方程组的系数矩阵A A非奇异，可将非奇异，可将A A分裂成分裂成 记作记作 A=D -L-U 第一百三十页，本课件共有180页Ax=b线性方程组：线性方程组：A=D-L-U或或A=M-N记记等价线性方程组：等价线性方程组：Mx=Nx+bM可选择为一个非奇异矩阵，且使可选择为一个非奇异矩阵，且使Mx=f容易求解，一般选择为容易求解，一般选择为A
32、的某种近似的某种近似构造迭代过程：构造迭代过程：第一百三十一页，本课件共有180页雅可比迭代的矩阵形式为雅可比迭代的矩阵形式为J为为雅可比迭代矩阵雅可比迭代矩阵。第一百三十二页，本课件共有180页考察一般的方程组，将考察一般的方程组，将n n元线性方程组元线性方程组 写成写成 2.2.雅可比迭代的分量形式雅可比迭代的分量形式第一百三十三页，本课件共有180页据此建立迭代公式据此建立迭代公式 上式称为解方程组的上式称为解方程组的JacobiJacobi迭代公式分量形式。迭代公式分量形式。若若 ,分离出变量分离出变量 第一百三十四页，本课件共有180页展开为：展开为：(k=0,1,2,)第一百三十
33、五页，本课件共有180页如上例的雅可比迭代公式为如上例的雅可比迭代公式为第一百三十六页，本课件共有180页8.2 高斯高斯-塞德尔（塞德尔（Gauss-Seidel）迭代法）迭代法一一.高斯高斯-塞德尔迭代法的基本思想塞德尔迭代法的基本思想 在在Jacobi迭迭代代法法中中，每每次次迭迭代代只只用用到到前前一一次次的的迭迭代代值值，若若每每次次迭迭代代充充分分利利用用当当前前最最新新的的迭迭代代值值，即即在在求求 时用新分量时用新分量代替旧分量代替旧分量 ,就得到高斯就得到高斯-赛德尔迭代法。其迭代法格式为：赛德尔迭代法。其迭代法格式为：(i=1,2,=1,2,n k=0,1,2,)=0,1,
34、2,)第一百三十七页，本课件共有180页 思想：设想把思想：设想把x1(k+1)算出后立即代替算出后立即代替x1(k)用于后面分量的计算，用于后面分量的计算，当当x2(k+1)算出后立即代替算出后立即代替x2(k)用于后面分量的计算，用于后面分量的计算，期望这样会，期望这样会收敛得快些。收敛得快些。第一百三十八页，本课件共有180页二二.GaussSeidel 迭代法的矩阵表示迭代法的矩阵表示 将将A分裂成分裂成A=D-L-U，则，则 等价于等价于(D-L-U)(D-L-U)x=b=b，如果取如果取M=DL（下三角矩阵），于是：（下三角矩阵），于是：N=M-A=U,于是：于是：因为因为 ,所以
35、所以 则高斯则高斯-塞德尔迭代形式为：塞德尔迭代形式为：故故 令令 G称为称为高斯高斯-塞德尔塞德尔迭代矩阵迭代矩阵第一百三十九页，本课件共有180页三三.高斯高斯-赛德尔赛德尔(Seidel)(Seidel)迭代公式分量形式迭代公式分量形式迭代公式即迭代公式即令令第一百四十页，本课件共有180页例题例题11：用高斯：用高斯-塞德尔迭代公式塞德尔迭代公式(GS)解方程解方程组组第一百四十一页，本课件共有180页高斯高斯-塞德尔迭代公式塞德尔迭代公式(GS)第一百四十二页，本课件共有180页GSGS迭代法和迭代法和JacobiJacobi迭代法的迭代法的比较比较：通常当两种方法都收敛时，通常当两
36、种方法都收敛时，GSGS迭代法往往收敛快一些。但有迭代法往往收敛快一些。但有时时JacobiJacobi迭代法收敛而迭代法收敛而GSGS迭代法发散；有时又相反。迭代法发散；有时又相反。例如方程组例如方程组雅可比迭代公式雅可比迭代公式方程组方程组收敛而收敛而GS迭代公式发散。迭代公式发散。发散，发散，但但GS迭代公式收敛。迭代公式收敛。的雅可比迭代公式的雅可比迭代公式第一百四十三页，本课件共有180页8.3超松弛迭代法（超松弛迭代法（SOR方法）方法）使用迭代法的困难在于难以估计其计算量。有使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛，但由于收敛速度缓慢，使计时迭代过程虽然收敛，但
37、由于收敛速度缓慢，使计算量变得很大而失去使用价值。因此，迭代过程的算量变得很大而失去使用价值。因此，迭代过程的加速具有重要意义。逐次超松弛迭代（加速具有重要意义。逐次超松弛迭代（Successive Successive Over relaxatic MethodOver relaxatic Method，简称，简称SORSOR方法）法，可以方法）法，可以看作是带参数的高斯看作是带参数的高斯塞德尔迭代法，实质上是高塞德尔迭代法，实质上是高斯斯-塞德尔迭代的一种加速方法。塞德尔迭代的一种加速方法。第一百四十四页，本课件共有180页一一.超松弛迭代法的基本思想超松弛迭代法的基本思想 超松弛迭代法目
38、的是为了提高迭代法的收敛速度，超松弛迭代法目的是为了提高迭代法的收敛速度，在高斯在高斯塞德尔迭代公式的基础上作一些修改。这种塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果方法是将前一步的结果 与高斯与高斯-塞德尔迭代方法塞德尔迭代方法的迭代值的迭代值 适当加权平均，期望获得更好的近似值适当加权平均，期望获得更好的近似值 。是解大型稀疏矩阵方程组的有效方法之一，有着广。是解大型稀疏矩阵方程组的有效方法之一，有着广泛的应用。泛的应用。其具体计算公式如下：其具体计算公式如下：用高斯用高斯塞德尔迭代法定义辅助量。塞德尔迭代法定义辅助量。第一百四十五页，本课件共有180页把把 取为取为 与与
39、 的加权平均，即的加权平均，即 合并表示为：合并表示为：式中系数式中系数称为称为松弛因子松弛因子，当，当=1时，便为高斯时，便为高斯-塞塞德尔迭代法。为了保证迭代过程收敛，要求德尔迭代法。为了保证迭代过程收敛，要求0 2。当当0 1时，低松弛法；当时，低松弛法；当1 2时称为超松时称为超松弛法。但通常统称为超松弛法弛法。但通常统称为超松弛法(SOR)。第一百四十六页，本课件共有180页二二.超松弛迭代法的矩阵表示超松弛迭代法的矩阵表示设线性方程组设线性方程组 AX=b AX=b 的系数矩阵的系数矩阵A非奇异非奇异,且主对角元素且主对角元素 ,则将则将A A分裂成分裂成A=D-L-U,A=D-L
40、-U,则超松弛迭代公式用矩阵表示为则超松弛迭代公式用矩阵表示为或或 故故 显然对任何一个显然对任何一个值值,(D-L),(D-L)非奇异非奇异,(,(因为假设因为假设 )于是超松弛迭代公式为于是超松弛迭代公式为 第一百四十七页，本课件共有180页令令则超松弛迭代公式可写成则超松弛迭代公式可写成 第一百四十八页，本课件共有180页例例12 用用SOR法求解线性方程组法求解线性方程组 k=0,1,2,，初值初值 第一百四十九页，本课件共有180页8.4 迭代法的收敛性迭代法的收敛性 我们知道我们知道,对于给定的方程组可以构造成简单迭代公对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯式
41、、雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代塞德尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。公式，但并非一定收敛。现在分析它们的收敛性。对于方程组对于方程组 经过等价变换构造出的等价方程组经过等价变换构造出的等价方程组 在什么条件下迭代序列在什么条件下迭代序列 收敛？先引入如下定理收敛？先引入如下定理 第一百五十页，本课件共有180页设有方程组设有方程组x=Bx+f,x*=Bx*+f,迭代公式迭代公式于是于是 由于由于 可以是任意向量可以是任意向量,故故 收敛于收敛于0 0当且仅当且仅当当 收敛于零矩阵，即当收敛于零矩阵，即当 时时 于是于是 当迭代矩阵当迭代矩阵B
42、 B满足满足 引入误差向量引入误差向量所以必有所以必有 迭代法收敛迭代法收敛则则第一百五十一页，本课件共有180页迭代公式迭代公式 ,若迭代矩阵若迭代矩阵B B的一种范数的一种范数 (2)(3)且有误差估计式且有误差估计式(1)x(k)收敛于方程的唯一解收敛于方程的唯一解X*则则定理定理10(10(迭代法收敛的充分条件迭代法收敛的充分条件)一、迭代收敛的充分条件一、迭代收敛的充分条件第一百五十二页，本课件共有180页因为因为 ,则则det(I-B)0,I-B为非奇异矩阵为非奇异矩阵,故故xBxf有惟一解有惟一解 ,即即与迭代过程与迭代过程 相比较相比较,有有两边取范数两边取范数 第一百五十三页
43、，本课件共有180页由迭代格式，有由迭代格式，有 两边取范数，代入上式，得两边取范数，代入上式，得 证毕证毕 由定理知，当由定理知，当 时，其值越小，迭代收敛越时，其值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代快，在程序设计中通常用相邻两次迭代 （为给定的精度要求）作为为给定的精度要求）作为控制迭代结束的条件控制迭代结束的条件 第一百五十四页，本课件共有180页例例13：已知方程组：已知方程组考察用考察用Jacobi迭代法求解时的收敛性迭代法求解时的收敛性第一百五十五页，本课件共有180页例题例题14：求：求 的谱半径的谱半径 第一百五十六页，本课件共有180页第一百五十七页，本课件共
44、有180页定理定理12 12(迭代法的基本定理迭代法的基本定理)迭代公式迭代公式 收敛收敛的充分必要条件是迭代矩阵的充分必要条件是迭代矩阵B的谱半径的谱半径推论推论(1)(1)雅可比迭代法雅可比迭代法 (2)(2)高斯高斯塞德尔迭代法塞德尔迭代法 (3)(3)超松弛迭代法超松弛迭代法它们收敛的充要条件是其迭代矩阵的谱半径它们收敛的充要条件是其迭代矩阵的谱半径 。定理定理11第一百五十八页，本课件共有180页例例15：已知方程组：已知方程组考察用考察用Jacobi迭代和迭代和G-S迭代求解时的收敛性迭代求解时的收敛性第一百五十九页，本课件共有180页练习：练习：已知线性方程组已知线性方程组 考察
45、用考察用JacobiJacobi迭代和迭代和G-SG-S迭代求解时的收敛性迭代求解时的收敛性第一百六十页，本课件共有180页定义7：设 ，如果其主对角线元素的绝对值大于同行其他元素绝对值之和。称 A是严格对角占优的。即：二、对角占优二、对角占优第一百六十一页，本课件共有180页定理定理13 设设n阶方阵阶方阵 为对角占优阵为对角占优阵,则则 非奇异非奇异证证:因因A A为对角占优阵为对角占优阵,其主对角元素的绝对值大于同其主对角元素的绝对值大于同行其它元素绝对值之和行其它元素绝对值之和,且主对角元素全不为且主对角元素全不为0,0,故故对角阵对角阵 为非奇异。为非奇异。作矩阵作矩阵 第一百六十二
46、页，本课件共有180页利用对角占优知利用对角占优知 由定理由定理4.14.1知知 非奇异非奇异,从而从而A A非奇异非奇异,证毕证毕 系数矩阵为对角占优阵的线性方程组称作对角系数矩阵为对角占优阵的线性方程组称作对角占优方程组。占优方程组。第一百六十三页，本课件共有180页考察用考察用Jacobi迭代和迭代和G-S迭代求解时的收敛性迭代求解时的收敛性例例16：设有方程组：设有方程组第一百六十四页，本课件共有180页定理定理14 若若Ax=b的系数矩阵的系数矩阵A为严格对角占优矩阵，为严格对角占优矩阵，则解此方程组的雅可比迭代法和高斯则解此方程组的雅可比迭代法和高斯-塞德尔迭塞德尔迭代法都收敛。代
47、法都收敛。定理定理15 若若Ax=b的系数矩阵的系数矩阵A为对称正定矩阵，则解为对称正定矩阵，则解此方程组的高斯此方程组的高斯-塞德尔迭代法都收敛。塞德尔迭代法都收敛。定理定理16 若若Ax=b的系数矩阵的系数矩阵A为对称正定矩阵，为对称正定矩阵，且，且，则解，则解Ax=b的的SOR方法收敛。方法收敛。三、收敛定理三、收敛定理第一百六十五页，本课件共有180页10 病态方程组和迭代法的改善第一百六十六页，本课件共有180页第一百六十七页，本课件共有180页此例说明方程的系数项此例说明方程的系数项,常数项等只有微小的变化常数项等只有微小的变化,而方程组的而方程组的解有较大的变化解有较大的变化.这样的方程组就是病态方程组。这样的方程组就是病态方程组。第一百六十八页，本课件共有180页第一百六十九页，本课件共有180页第一百七十页，本课件共有180页第一百七十一页，本课件共有180页注意到注意到因为：第一百七十二页，本课件共有180页第一百七十三页，本课件共有180页第一百七十四页，本课件共有180页第一百七十五页，本课件共有180页条件数的性质条件数的性质:第一百七十六页，本课件共有180页第一百七十七页，本课件共有180页第一百七十八页，本课件共有180页补充:第一百七十九页，本课件共有180页第一百八十页，本课件共有180页