《第2章线性方程组求解的数值方法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第2章线性方程组求解的数值方法优秀PPT.ppt（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章线性方程组求解的数值方法现在学习的是第1页，共85页第二章第二章 线性方程组求解的数值方法线性方程组求解的数值方法1.高斯消元法高斯消元法2.矩阵分解法矩阵分解法3.向量范数与矩阵范数向量范数与矩阵范数4.迭代法求解迭代法求解5.方程组的病态问题与误差分析方程组的病态问题与误差分析主要内容：主要内容：现在学习的是第2页，共85页第二章第二章 线性方程组求解的数值方法线性方程组求解的数值方法1.理解各种线性方程组数值求解；理解各种线性方程组数值求解；2.掌握求解方法和解的误差分析方法；掌握求解方法和解的误差分析方法；3.能编程实现求解算法。能编程实现求解算法。特别强调：遇到问题养成用计算机
2、编程求解的习惯，特别强调：遇到问题养成用计算机编程求解的习惯，不要习惯性的用笔算，而这是国内外学生的一个主不要习惯性的用笔算，而这是国内外学生的一个主要差距。要差距。教学要求：教学要求：现在学习的是第3页，共85页 在自然科学和工程技术中，有很多问题的解决都需要用到线在自然科学和工程技术中，有很多问题的解决都需要用到线性方程组的求解。因此，求解线性方程组的问题是一个在科学技性方程组的求解。因此，求解线性方程组的问题是一个在科学技术中常见的普遍问题。术中常见的普遍问题。解线性方程组的数值解法：有直接法和迭代法两类。解线性方程组的数值解法：有直接法和迭代法两类。直接法：直接法：计算过程没有舍入误差
3、，经过有限次四则运算可求得方程组得计算过程没有舍入误差，经过有限次四则运算可求得方程组得精确解。（实际计算有舍入误差）精确解。（实际计算有舍入误差）高斯消元法，矩阵分解法高斯消元法，矩阵分解法迭代法：迭代法：核心是迭代求解的收敛条件和收敛速度。核心是迭代求解的收敛条件和收敛速度。雅可比（雅可比（JacobiJacobi）迭代，高斯）迭代，高斯-赛德尔（赛德尔（Gauss-SeidelGauss-Seidel）迭代）迭代现在学习的是第4页，共85页基本思想方法：基本思想方法：由由行初等变换行初等变换将系数矩阵约化为三角将系数矩阵约化为三角 矩阵；用矩阵；用回代回代的方法求解方程组。的方法求解方程
4、组。例例1 1 用消去法（高斯消元法）解方程组用消去法（高斯消元法）解方程组高斯消元法高斯消元法是求解方程组的古典方法。是求解方程组的古典方法。(2.1)3.1 3.1 高斯消元法高斯消元法现在学习的是第5页，共85页结论：结论：整个计算过程可分为两部分：整个计算过程可分为两部分：（1 1）消元消元：把原方程组转化为系数矩阵为上三角矩阵：把原方程组转化为系数矩阵为上三角矩阵的方程组；的方程组；（2 2）回代回代：由系数矩阵为上三角矩阵的方程组求解：由系数矩阵为上三角矩阵的方程组求解（2 2）回代求解，得：）回代求解，得：解：解：（1 1）消元：）消元：现在学习的是第6页，共85页对于一般情形：
5、对于一般情形：n n阶线性方程组的高斯消元法阶线性方程组的高斯消元法现在学习的是第7页，共85页若记若记增广矩阵增广矩阵（2.2）现在学习的是第8页，共85页（1 1）第）第1 1步步(k k=1)=1)，一般形式的高斯消元法一般形式的高斯消元法：设设 ，首先对行计算乘数，首先对行计算乘数对增广矩阵对增广矩阵 进进行行行初等变换：行初等变换：(即即用用 乘乘以以2.2式式的的第第1个个方方程程，加加到到第第i个个方方程程上上，消消去去2.2式式的的第第二二个个方方程程直直到到第第n个个方方程程中中的的未未知知数数 )(代表第代表第i行行)现在学习的是第9页，共85页得到与原方程组得到与原方程组
6、 等价的方程组等价的方程组 。记为记为（2）一般第）一般第k步消元步消元()设已完成上述消元过程第设已完成上述消元过程第1 1步，第步，第2 2步，步，第，第k k-1-1步，且步，且 现在学习的是第10页，共85页其中：其中：设设 ，计算乘数，计算乘数现在学习的是第11页，共85页(即即用用 乘乘以以2.2式式的的第第k个个方方程程，加加到到第第i个个方方程程上上，消消去去2.2式式的的第第k+1个方程直到第个方程直到第n个方程中的未知数个方程中的未知数 )那么第那么第k步消元操作即：步消元操作即：(3)(3)继续这一过程，直到完成第继续这一过程，直到完成第n-1n-1次消元，最后我们得到与
7、原次消元，最后我们得到与原方程组等价的三角形方程组方程组等价的三角形方程组(2.3)(2.3)消元过程结束消元过程结束现在学习的是第12页，共85页求解三角形方程组求解三角形方程组2.3，得到求解公式，得到求解公式这个过程称为这个过程称为回代过程。回代过程。现在学习的是第13页，共85页例题：例题：考虑方程组考虑方程组 GaussGauss消消去去法法中中每每步步用用来来消消去去其其他他元元素素的的 称称为为该该步步的的主主元元素素。GaussGauss消消去去法法作作为为数数值值方方法法，主主元元素素的的选选择择是是否否会会影响计算的结果呢？影响计算的结果呢？则该方程的精确解为则该方程的精确
8、解为而采用而采用(，1)1)作为主元素，利用高斯消去法得到的解为作为主元素，利用高斯消去法得到的解为显然结果是错误的。显然结果是错误的。现在学习的是第14页，共85页 错误在哪个地方呢？错误在哪个地方呢？原原因因是是我我们们在在消消元元时时，利利用用了了小小主主元元 ，使使得得约约化化后后的的方方程程组组元元素素数数量量级级大大大大增增长长，再再经经舍舍入入，而而计计算算机机的的有有效效位位数数有有限限，造成消元后的三角形方程组就不准确了。造成消元后的三角形方程组就不准确了。结结论论：在在消消元元过过程程中中可可能能出出现现主主元元素素为为零零的的情情况况，这这时时消消去去法法将将无无法法进进
9、行行；即即使使不不为为零零，在在主主元元素素很很小小时时，用用其其做做除除数数，也也会会导导致致其其他他元元素素数数量量级级的的严严重重增增长长和和舍舍入入误误差差的的扩扩散散，最最后后也也使使得得计计算算解不可靠。解不可靠。解解决决方方法法：对对一一般般的的矩矩阵阵来来说说，最最好好每每一一步步选选取取系系数数矩矩阵阵（或或消消元元后后的的低低阶阶矩矩阵阵）的的该该列列中中绝绝对对值值最最大大的的元元素素作作为为主主元元素素，以以使高斯消去法具有较好的数字稳定性。使高斯消去法具有较好的数字稳定性。(高斯列主元素消去法高斯列主元素消去法)现在学习的是第15页，共85页1.1.列主元法列主元法第
10、一列中绝对值最大是第一列中绝对值最大是1010，取，取1010为主元为主元n n阶方程组第阶方程组第k k轮消元时，选第轮消元时，选第k k列的后列的后(n-k+1)(n-k+1)个元素中绝对值最个元素中绝对值最大作主元。大作主元。现在学习的是第16页，共85页x3=6.2/6.2=1x2=(2.5-5x3)/2.5=-1x1=(7+7x2-0 x3)/10=0 x1=0 x2=-1x3=1第二列的后两个数中选出主元第二列的后两个数中选出主元 2.52.5现在学习的是第17页，共85页2 2 完全主元素消去法完全主元素消去法整个矩阵中绝对值最大是整个矩阵中绝对值最大是1010，取，取1010为
11、主元为主元n n阶方程组第阶方程组第k k轮消元时，选消元后元素中绝对值最大作主元。轮消元时，选消元后元素中绝对值最大作主元。现在学习的是第18页，共85页x1=0 x2=-1x3=1方框中方框中6 6最大，交换行列，交换列的时候要做记录（即最大，交换行列，交换列的时候要做记录（即x3x3和和x2x2交换了位置）：交换了位置）：现在学习的是第19页，共85页 完全主元素消除法与列主元素消除法完全主元素消除法与列主元素消除法的优缺点比较：的优缺点比较：优点：优点：数值更加稳定；数值更加稳定；缺点：缺点：计算量大；计算量大；现在学习的是第20页，共85页 对对矩矩阵阵A A实实行行初初等等行行变变
12、换换相相当当于于用用初初等等矩矩阵阵左左乘乘A A，于于是是对对(2 2.2 2)做做 第第 一一 次次 消消 元元 后后，化化 为为 化化 为为 ，即即 ，其中，其中 3.1 矩阵的三角分解矩阵的三角分解 LULU分解分解现在学习的是第21页，共85页第第k k步的初等矩阵为步的初等矩阵为并且并且重复这一过程，最后得到重复这一过程，最后得到将上三角矩阵将上三角矩阵 记为记为U U，则，则 现在学习的是第22页，共85页将上三角矩阵将上三角矩阵 记为记为U U，则，则 ，其中其中则，则，L L为单位下三角矩阵。为单位下三角矩阵。高斯消去法实质上是产生了一个将高斯消去法实质上是产生了一个将A A
13、分解为两个三角形矩阵相乘的分解为两个三角形矩阵相乘的因式分解。如果因式分解。如果A A是非奇异阵，则是非奇异阵，则LULU分解是唯一的，否则分解不分解是唯一的，否则分解不唯一。唯一。现在学习的是第23页，共85页消元法：消元法：消元法与三角分解法间的关系：消元法与三角分解法间的关系：三角分解法：三角分解法：讨论讨论现在学习的是第24页，共85页直接三角分解法解线性方程组（直接三角分解法解线性方程组（）的具体流）的具体流程：程：1.2.2.计算计算U U的第的第r r行，行，L L的第的第r r列元素列元素 r=2,3,n3.(一一)LU分解分解现在学习的是第25页，共85页再求解再求解Ly=b
14、,Ux=yLy=b,Ux=y计算公式：计算公式：(二二)x的的计算计算现在学习的是第26页，共85页例例 用直接三角分解法解方程组用直接三角分解法解方程组 解解:(一一)矩阵矩阵LU分解分解(1)(1)故：故：现在学习的是第27页，共85页(2)经计算：经计算：现在学习的是第28页，共85页(二二)求解求解x：从而从而现在学习的是第29页，共85页 3.2 3.2 矩阵的矩阵的CholeskyCholesky分解分解 对称正定矩阵对称正定矩阵A A：AT=A,A的各阶顺序主子式大于零的各阶顺序主子式大于零.前前面面指指出出非非奇奇异异的的矩矩阵阵可可以以有有三三角角分分解解，当当A A是是某某
15、些些特特殊殊矩矩阵阵时时，它它的的L L U U分分解解会会有有更更加加简简洁洁的的形形式式。A A的的LULU分解分解(2.4)现在学习的是第30页，共85页uii 0(i=1,n)由于由于A A是对称正定的，则有是对称正定的，则有将将U U进一步分解：进一步分解：现在学习的是第31页，共85页根据根据A A的对称性：的对称性：故：故：由分解的唯一性知：由分解的唯一性知：故：故：其中其中P P为上三角矩阵，这种对称正定矩阵的分解称为为上三角矩阵，这种对称正定矩阵的分解称为CholeskyCholesky分解。分解。在在MatlabMatlab中函数中函数“cholchol”给出对称正定矩阵的
16、给出对称正定矩阵的CholeskyCholesky分解。分解。现在学习的是第32页，共85页经过经过n n步可直接求得步可直接求得思路思路:(1)(1)分解对称正定矩阵分解对称正定矩阵设设n n阶对称正定矩阵阶对称正定矩阵A A有分解有分解 ,先用待定系数法求先用待定系数法求L L的的元素元素Cholesky分解的具体步骤分解的具体步骤(平方根法平方根法)：(2)(2)分解分解求解方程组求解方程组现在学习的是第33页，共85页Cholesky方法方法具体计算公式：具体计算公式：分解计算：分解计算：求解：求解：现在学习的是第34页，共85页 3.3 3.3 向量范数与矩向量范数与矩阵范数范数向量
17、、向量、矩阵与线性方程组有着密切的关系，矩阵与线性方程组有着密切的关系，向量、矩阵范数是向量、矩阵范数是解方解方程组以及研究与探讨方程组本身性质的工具。程组以及研究与探讨方程组本身性质的工具。一、向量范数的定义一、向量范数的定义定义定义 范数为范数为其中的其中的 ，最常用的范数是，最常用的范数是 ，以及，以及现在学习的是第35页，共85页容易证明向量范数满足如下性质：容易证明向量范数满足如下性质：(1)如果如果 ，则，则 ；而且；而且 ，当且，当且仅当仅当 (2)对任何的数对任何的数c，都有，都有 (3)范数也称为范数也称为2-2-范数或范数或EuclideanEuclidean函数；函数；范
18、数也称为范数也称为 -范范数或一致范数。在数或一致范数。在MatlabMatlab中用函数中用函数 用来计算向量用来计算向量x x的的 范数。范数。由性质由性质(3),还容易得到：还容易得到：现在学习的是第36页，共85页二二 矩阵范数的定义矩阵范数的定义在向量范数的基础上可以进一步定义矩阵范数在向量范数的基础上可以进一步定义矩阵范数 如果上式中的向量范数取为如果上式中的向量范数取为 范数，则可以证明定义出的范数，则可以证明定义出的矩阵范数（称为矩阵矩阵范数（称为矩阵 范数或者列范数）为范数或者列范数）为 如果向量范数取为如果向量范数取为2-范数，则范数，则 其中其中 （模），称为矩阵（模），
19、称为矩阵B的谱半的谱半径。径。(为为B的任意特征值。的任意特征值。)现在学习的是第37页，共85页 类似地，类似地，Matlab函数函数norm(A,p)给出矩阵给出矩阵p=1,2或或 范数范数 如果向量范数取如果向量范数取为为 ，则可以证明定义出的矩阵范数，则可以证明定义出的矩阵范数（称为矩阵的（称为矩阵的 范数或者行范数）为范数或者行范数）为 容易证明矩阵范数满足如下性质：容易证明矩阵范数满足如下性质：(1)(1)如果如果 ，则，则 ；而且；而且 ，而且仅当，而且仅当 (2)(2)对任何的数对任何的数 ，(3)(3)(4)(4)而且由矩阵范数的定义还有而且由矩阵范数的定义还有称之为矩阵范数
20、与相应的向量范数是相容的。称之为矩阵范数与相应的向量范数是相容的。现在学习的是第38页，共85页39 3.4 古典迭代法的构造古典迭代法的构造求解线性代数方程组的方法求解线性代数方程组的方法中小规模中小规模问题问题直接法直接法迭代法迭代法 大规模，大规模，超大规模问题超大规模问题 古典方法古典方法现代方法现代方法现在学习的是第39页，共85页40线性方程组的一般形式为：线性方程组的一般形式为：如果如果 是非奇异的，则上式有唯一解。是非奇异的，则上式有唯一解。我们将通过一个具体线性方程组的例子来讲解迭代法。我们将通过一个具体线性方程组的例子来讲解迭代法。取：取：即线性方程组为：即线性方程组为：方
21、程的精确解方程的精确解 (直接法计算直接法计算)现在学习的是第40页，共85页41 如果对该方程组进行变形，将变量如果对该方程组进行变形，将变量 分别从三分别从三个方程中分离出来：个方程中分离出来：(1)(1)令令初初值值现在学习的是第41页，共85页所以所以(1)式可以表示为迭代形式：式可以表示为迭代形式：所以我们可以得到一个向量的序列所以我们可以得到一个向量的序列 ，只要该序列当，只要该序列当 时有极限，那么这个极限就是该线性方程组的解。时有极限，那么这个极限就是该线性方程组的解。上面这种迭代求解线性方程组的方法称为上面这种迭代求解线性方程组的方法称为Jacobi迭代法迭代法。现在学习的是
22、第42页，共85页考虑线性方程组的一般形式：考虑线性方程组的一般形式：其中矩阵其中矩阵A为为nn阶方阵，则方程的分量形式为：阶方阵，则方程的分量形式为：改写成：改写成：现在学习的是第43页，共85页从而得到迭代公式：从而得到迭代公式：上面式子就是一般形式的上面式子就是一般形式的Jacobi迭代法，也可也记做：迭代法，也可也记做：现在学习的是第44页，共85页在在Jacobi迭代法中充分利用新值，可得到下面迭代：迭代法中充分利用新值，可得到下面迭代：上面这种迭代方法也叫做上面这种迭代方法也叫做Gauss-Seidel迭代，也可以记为：迭代，也可以记为：现在学习的是第45页，共85页方程组的精确解
23、为方程组的精确解为x x*=(1,1,1)=(1,1,1)T T.解解 JacobiJacobi迭代法计算公式为迭代法计算公式为取初始向量取初始向量x x(0)(0)=(0,0,0)=(0,0,0)T T,迭代可得迭代可得例例1：利用：利用Jacobi法和法和Gauss-Seidel法求解线性方程组法求解线性方程组现在学习的是第46页，共85页kx1(k)x2(k)x3(k)x(k)-x*0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9
24、290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636可见可见,迭代序列逐次收敛于方程组的解迭代序列逐次收敛于方程组的解,而且迭代而且迭代7 7次得到精确到小数点后次得到精确到小数点后两位的近似解两位的近似解.计算结果列表如下计算结果列表如下:现在学习的是第47页，共85页Gauss-SeidelGauss-Seidel迭代法的计算公式为迭代法的计算公式为:同样取初始向量同样取初始向量x x(0)(0)=(0,0,0)=(0,0,0)T T,计算结果为计算结果为 由计算结果可见由计算结果可见,Gaus
25、s-Seidel,Gauss-Seidel迭代法收敛较快迭代法收敛较快.取精确到小数点后取精确到小数点后两位的近似解两位的近似解,Gauss-Seidel,Gauss-Seidel迭代法只需迭代迭代法只需迭代3 3次次,而而JacobiJacobi迭代法需要迭代迭代法需要迭代7 7次次.kx1(k)x2(k)x3(k)x(k)-x*012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956 现在学习的是第48页，共85页为了进一步研究为了进一步研究,从矩阵角度来讨论上述迭代法从
26、矩阵角度来讨论上述迭代法.对线性方程组对线性方程组Ax=b,Ax=b,记记D=diag(aD=diag(a1111,a,a2222,a,annnn)则有则有 A=D-L-UA=D-L-U于是线性方程组于是线性方程组 Ax=b Ax=b 可写成可写成 (D-L-U)x=b(D-L-U)x=b等价于等价于 Dx=(L+U)x+b Dx=(L+U)x+b 或或 x=Dx=D-1-1(L+U)x+D(L+U)x+D-1-1b b 现在学习的是第49页，共85页由此建立由此建立JacobiJacobi迭代法迭代公式迭代法迭代公式 x x(k+1)(k+1)=D=D-1-1(L+U)x(L+U)x(k)(
27、k)+D+D-1-1b k=0,1,2,b k=0,1,2,或写成或写成 x x(k+1)(k+1)=Bx=Bx(k)(k)+f k=0,1,2,+f k=0,1,2,其中其中现在学习的是第50页，共85页所以所以Gauss-SeidelGauss-Seidel迭代法可以写成迭代法可以写成其中其中Gauss-SeidelGauss-Seidel迭代法迭代公式为迭代法迭代公式为写成矩阵形式为：写成矩阵形式为：现在学习的是第51页，共85页 3.5 3.5 迭代法的分析迭代法的分析 构造迭代法的途径可以有很多，那么是不是所有的方法都能构造迭代法的途径可以有很多，那么是不是所有的方法都能收敛呢？收敛
28、速度的快慢与什么有关系呢？收敛呢？收敛速度的快慢与什么有关系呢？它的精确解为它的精确解为例：例：现在学习的是第52页，共85页kx1(k)x2(k)x3(k)x(k)-x*0123401416.792.8168104.7-41.4-52.4-254.30-1.74.56-151-238.211342.41521680可见可见,并不是所有的方程组都收敛，即使收敛对于不同的方法并不是所有的方程组都收敛，即使收敛对于不同的方法(例如例如JacobiJacobi与与Gauss-Seidel)Gauss-Seidel)收敛速度也是不同的收敛速度也是不同的.计算结果列表如下计算结果列表如下:现在学习的是第
29、53页，共85页 设设 是矩阵是矩阵B任意一个特征值，任意一个特征值，是相应的特征向量，是相应的特征向量，即即 再假设再假设 为任意的向量范数及与之相融的矩阵范数，则有：为任意的向量范数及与之相融的矩阵范数，则有：首先引入几个定义、引理：首先引入几个定义、引理：所以对矩阵所以对矩阵B任意一个特征值任意一个特征值 ，都有，都有记记 ，称之为矩阵，称之为矩阵B的的谱半径谱半径，则，则现在学习的是第54页，共85页先引入两个引理（详细证明见附录）：先引入两个引理（详细证明见附录）：引理引理3.1 矩阵矩阵 ，则，则 的充分必要条的充分必要条件是件是 引理引理3.2 矩阵矩阵 ，若，若 ，则，则 是是
30、非奇异的。非奇异的。现在学习的是第55页，共85页 定理定理3.1 对任意的对任意的 和任意的初始向量和任意的初始向量 ，迭代法收敛的，迭代法收敛的充分必要条件是充分必要条件是证明：证明：必要性必要性 设迭代法产生的序列设迭代法产生的序列 收敛，记收敛，记 是该序列的极限点，所以是该序列的极限点，所以 满满足足又由迭代关系又由迭代关系 ，可以得到，可以得到现在学习的是第56页，共85页由由 的任意性，知：的任意性，知：由引理由引理3.1知：知：充分性充分性 由由 及引理及引理2知知 （即（即 ）有唯一解，记为有唯一解，记为 类似于必要性的证明，得到类似于必要性的证明，得到再由第一步知再由第一步
31、知 ，故，故现在学习的是第57页，共85页 定理定理3.1给出了迭代收敛的充要条件，但给出了迭代收敛的充要条件，但 不宜计算，所以在不宜计算，所以在实际使用中通常并不好用。由实际使用中通常并不好用。由 知，只要对某种相容的矩阵范数知，只要对某种相容的矩阵范数有有 那那么么当当然然 ，所所以以这这常常常常是是实实际际中中很很有有效效的的收收敛敛判判别别准准则。则。严格对角占优矩阵：严格对角占优矩阵：考虑考虑 ，设，设 ，当，当 时的矩阵。时的矩阵。现在学习的是第58页，共85页定理定理3.2 如果如果A是严格对角占优的矩阵，则它一定非奇异。是严格对角占优的矩阵，则它一定非奇异。由于由于A是对角占
32、优矩阵，所以是对角占优矩阵，所以 ，故矩阵，故矩阵是可逆的。考虑是可逆的。考虑现在学习的是第59页，共85页 矩阵的矩阵的 范数为范数为由由A是对角占优矩阵，得是对角占优矩阵，得 由引理由引理3.2知知 是非奇异的，又由于是非奇异的，又由于 是非奇异的，所以是非奇异的，所以A是非奇异的。是非奇异的。得证！得证！引理引理3.2 矩阵矩阵 ，若，若 ，则，则 是是非奇异的。非奇异的。现在学习的是第60页，共85页 定理定理3.3 系数矩阵为严格对角占优的线性代数方程组，它的系数矩阵为严格对角占优的线性代数方程组，它的Jacobi迭代法和迭代法和Gauss-Seidel迭代都是收敛的。迭代都是收敛的
33、。证明：证明：Jacobi方法的迭代矩阵为方法的迭代矩阵为由定理由定理3.2中的证明知，严格对角占优矩阵满足：中的证明知，严格对角占优矩阵满足：再由定理再由定理3.1，得，得Jacobi迭代法收敛。迭代法收敛。(a)Jocobi的证明的证明1现在学习的是第61页，共85页再考虑再考虑Gauss-Seidel方法，其迭代矩阵为方法，其迭代矩阵为用反证法，假设用反证法，假设Gauss-Seidel迭代不收敛，则由定理迭代不收敛，则由定理3.1知：知：所以存在模大于所以存在模大于1的特征值的特征值.设有设有 ，使得行列式：，使得行列式：(b)Gauss-Seidel的证明的证明现在学习的是第62页，
34、共85页 故，只有故，只有才能使得才能使得 成立。成立。由于由于A是对角占优的，所以矩阵是对角占优的，所以矩阵 也是对角占优的，那么该矩阵一定非奇异，这与上面该矩阵也是对角占优的，那么该矩阵一定非奇异，这与上面该矩阵 的行列式等于的行列式等于0矛盾。矛盾。由于由于 可逆，所以可逆，所以得证！得证！现在学习的是第63页，共85页定理定理3.4 若迭代矩阵若迭代矩阵B满足满足 ，则迭代生成的序列，则迭代生成的序列 满足满足收敛速度问题收敛速度问题其中其中 表示精确解。表示精确解。证明：证明：先证明先证明(b),然后证明然后证明(a)现在学习的是第64页，共85页而而所以所以故，本页第一个式子可写为
35、故，本页第一个式子可写为现在学习的是第65页，共85页由于由于 ，故，故(b)得证得证显然对于任意的正整数显然对于任意的正整数p，都有，都有那么在本页第一个式子中反复利用上式就可以得到那么在本页第一个式子中反复利用上式就可以得到(a)(a)得证得证现在学习的是第66页，共85页 给出的关系可以作为计算终止的判别准则。即只要给出的关系可以作为计算终止的判别准则。即只要 和和 已足够接近，表明已足够接近，表明 与与 便已足够靠近。便已足够靠近。定理定理3.4(a)给出的是迭代收敛速度的一个估计。显然给出的是迭代收敛速度的一个估计。显然 越接近越接近0，生成序列，生成序列 收敛得越快。收敛得越快。定
36、理定理3.14(b)定理定理3.4的讨论的讨论现在学习的是第67页，共85页 3.6 超松弛迭代超松弛迭代(SOR)及分块迭代方法及分块迭代方法 对于给定的迭代法，每步迭代所需的工作量是确定的。如果对于给定的迭代法，每步迭代所需的工作量是确定的。如果迭代法收敛速度缓慢，则需要比较多的迭代次数，由此导致算法迭代法收敛速度缓慢，则需要比较多的迭代次数，由此导致算法工作量太大而失去使用价值，因此各种迭代法的加速技术具有重工作量太大而失去使用价值，因此各种迭代法的加速技术具有重要意义。要意义。假设假设 是已经得到的迭代值，以是已经得到的迭代值，以 为初值进行一步为初值进行一步Gauss-Seidel迭
37、代得：迭代得：现在学习的是第68页，共85页将这一迭代值与将这一迭代值与 的值组合作为新一步的迭代值的值组合作为新一步的迭代值其中其中 为待定的参数，写成矩阵形式为：为待定的参数，写成矩阵形式为：这时迭代矩阵：这时迭代矩阵：现在学习的是第69页，共85页 新新的的迭迭代代每每步步的的计计算算代代价价与与Gauss-Seidel方方法法相相差差无无几几，如如果果能能取取得得恰恰当当的的 值值，使使新新构构造造的的方方法法比比Gauss-Seidel方方法法收收敛敛得得更更快快，松松弛就起到了加速的作用。弛就起到了加速的作用。在在实实际际上上真真正正使使用用的的 值值通通常常的的范范围围为为 ，被
38、被统统称称为为超超松松弛弛方方法法，简称，简称SOR(Successive Over-Relaxation)方法。方法。上面的这个方法就叫做松弛方法，它可以视为上面的这个方法就叫做松弛方法，它可以视为Gauss-Seidel方法方法的加速。显然的加速。显然 时，上面这个方法就是时，上面这个方法就是Gauss-Seidel方法。方法。现在学习的是第70页，共85页定理定理3.5 SOR方法收敛的必要条件是：方法收敛的必要条件是：证明：证明：假设假设SOR方法收敛，所以方法收敛，所以设设 为为 的特征值，则的特征值，则另一方面，经过计算不难得到另一方面，经过计算不难得到故故 ，结论得证。，结论得证
39、。现在学习的是第71页，共85页分块矩阵以及分块迭代方法分块矩阵以及分块迭代方法在许多实际应用中，矩阵可以写成如下分块的形式：在许多实际应用中，矩阵可以写成如下分块的形式：其中其中 是是 阶的方阵，而且阶的方阵，而且 据此可以构造分块形式的迭代法，考虑据此可以构造分块形式的迭代法，考虑 其中其中现在学习的是第72页，共85页求解方程组求解方程组 ，分块的，分块的Jacobi迭代法为：迭代法为：分块的分块的Gauss-Seidel迭代法为：迭代法为：现在学习的是第73页，共85页分块的超松弛迭代法分块的超松弛迭代法(BSOR)为为现在学习的是第74页，共85页 3.7 线性方程组的条件数线性方程
40、组的条件数 对于线性方程组对于线性方程组 如如果果解解x关关于于问问题题（即即矩矩阵阵A和和向向量量b）的的“微微小小”变变化化(来来源源可可能能是是模模型型误误差差或或数数据据上上的的误误差差，也也可可能能是是数数值值计计算算中中的的舍舍入入误误差差)不不敏敏感感，那那么么这这个个问问题题即即是是一一个个“好好”问问题题，反之就是反之就是“坏坏”问题或者病态的问题。问题或者病态的问题。关于病态的例子，我们在第一章中已经包含了一个，这一章主关于病态的例子，我们在第一章中已经包含了一个，这一章主要用范数作为工具来分析线性方程组的好坏。要用范数作为工具来分析线性方程组的好坏。现在学习的是第75页，
41、共85页例例 设有方程组设有方程组已知系数已知系数测量数据测量数据待求数据待求数据其中其中A为为 ，若测量数据为准确数据，若测量数据为准确数据，即即 ，那么很容易计算，那么很容易计算如果测量数据不够精确，即测量数据仅保留了如果测量数据不够精确，即测量数据仅保留了2 2位有效数字，即位有效数字，即 ，计算结果为，计算结果为现在学习的是第76页，共85页如果测量数据和系数矩阵的数据都仅保留了如果测量数据和系数矩阵的数据都仅保留了2 2位有效数字，即位有效数字，即，则计算结果为，则计算结果为以上问题称为病态的问题，病态是问题本身固有的。以上问题称为病态的问题，病态是问题本身固有的。现在学习的是第77
42、页，共85页(1)考虑由于右端的扰动所引起的解的变化，考虑由于右端的扰动所引起的解的变化，已知已知两式相减得两式相减得利用范数关系可以得到：利用范数关系可以得到：综合上述两式有：综合上述两式有：现在学习的是第78页，共85页 这个式子给出了右端的扰动可能引起解扰动的上界，显然这个式子给出了右端的扰动可能引起解扰动的上界，显然 越小，方程右端的变化引起解的变化就越小。越小，方程右端的变化引起解的变化就越小。(2)考虑由于矩阵考虑由于矩阵A有扰动时所引起的解的变化有扰动时所引起的解的变化可以得到：可以得到：其中利用了其中利用了现在学习的是第79页，共85页经过整理可以得到经过整理可以得到(3)考虑
43、更一般的情形所引起的解的变化考虑更一般的情形所引起的解的变化假设满足如下的特殊形式：假设满足如下的特殊形式：又又Tylor展开，展开，可以写成可以写成现在学习的是第80页，共85页对对 求导得求导得令令 ，并考虑到，并考虑到 ，则，则记记 ，从而有，从而有现在学习的是第81页，共85页 从上面三种情况可见，问题扰动所引起解的扰动是被同一从上面三种情况可见，问题扰动所引起解的扰动是被同一个因子个因子 控制的控制的 定义定义3.1 设设A为可逆矩阵，为可逆矩阵，是与某种向量范数相容的矩阵范是与某种向量范数相容的矩阵范数，称数，称 为线性方程组为线性方程组 相应于该矩阵范数的条件数。相应于该矩阵范数
44、的条件数。由前面的分析可见，条件数大的就是病态的矩阵，反之是良态的矩由前面的分析可见，条件数大的就是病态的矩阵，反之是良态的矩阵。求解线性方程时了解它的条件数大小是必要的，它可以帮助你阵。求解线性方程时了解它的条件数大小是必要的，它可以帮助你判断所得数值解的可信性及模型的合理性。判断所得数值解的可信性及模型的合理性。在在Matlab中可以用中可以用cond（A）来计算条件数或者用）来计算条件数或者用rcond(A)来估计其来估计其量级的倒数量级的倒数。现在学习的是第82页，共85页设设 ，则，则 ，即对于该函数，误差会被放大，即对于该函数，误差会被放大n n倍。倍。二、病态问题与条件数（针对问
45、题本身）二、病态问题与条件数（针对问题本身）定义：输入数据的微小变动导致输出数据的较大误差，就定义：输入数据的微小变动导致输出数据的较大误差，就被称为病态问题。被称为病态问题。衡量是否病态的标准：条件数衡量是否病态的标准：条件数 对于函数值计算问题，条件数定义为：对于函数值计算问题，条件数定义为：不同的问题，条件数具体定义不同。不同的问题，条件数具体定义不同。一般情况下，条件数大于一般情况下，条件数大于1010，就认为问题病态。，就认为问题病态。通过构造特殊算法来解决现在学习的是第83页，共85页条件数的重要性质：条件数的重要性质：定理定理3.6 (a)对任意的非奇异矩阵对任意的非奇异矩阵A，cond(A)是由任意的矩阵是由任意的矩阵 范数定义的条件范数定义的条件数，则数，则 (b)如果如果Q是正交矩阵，则对于任意的非奇异矩阵是正交矩阵，则对于任意的非奇异矩阵A，都有，都有其中其中现在学习的是第84页，共85页证明：证明：(a)中的各条性质是显然的，例如，对任意的非奇异矩阵中的各条性质是显然的，例如，对任意的非奇异矩阵A，有，有 (b)由于由于Q是正交矩阵，所以是正交矩阵，所以 另外，另外，现在学习的是第85页，共85页