第2章线性方程组求解的数值方法精选文档.ppt

第2章线性方程组求解的数值方法本讲稿第一页，共八十五页第二章第二章 线性方程组求解的数值方法线性方程组求解的数值方法1.高斯消元法高斯消元法2.矩阵分解法矩阵分解法3.向量范数与矩阵范数向量范数与矩阵范数4.迭代法求解迭代法求解5.方程组的病态问题与误差分析方程组的病态问题与误差分析主要内容：主要内容：本讲稿第二页，共八十五页第二章第二章 线性方程组求解的数值方法线性方程组求解的数值方法1.理解各种线性方程组数值求解；理解各种线性方程组数值求解；2.掌握求解方法和解的误差分析方法；掌握求解方法和解的误差分析方法；3.能编程实现求解算法。能编程实现求解算法。特别强调：遇到问题养成用计算机编程求解的习惯，特别强调：遇到问题养成用计算机编程求解的习惯，不要习惯性的用笔算，而这是国内外学生的一个主不要习惯性的用笔算，而这是国内外学生的一个主要差距。要差距。教学要求：教学要求：本讲稿第三页，共八十五页 在自然科学和工程技术中，有很多问题的解决都需要用到在自然科学和工程技术中，有很多问题的解决都需要用到线性方程组的求解。因此，求解线性方程组的问题是一个在科线性方程组的求解。因此，求解线性方程组的问题是一个在科学技术中常见的普遍问题。学技术中常见的普遍问题。解线性方程组的数值解法：有直接法和迭代法两类。解线性方程组的数值解法：有直接法和迭代法两类。直接法：直接法：计算过程没有舍入误差，经过有限次四则运算可求得方程计算过程没有舍入误差，经过有限次四则运算可求得方程组得精确解。（实际计算有舍入误差）组得精确解。（实际计算有舍入误差）高斯消元法，矩阵分解法高斯消元法，矩阵分解法迭代法：迭代法：核心是迭代求解的收敛条件和收敛速度。核心是迭代求解的收敛条件和收敛速度。雅可比（雅可比（JacobiJacobi）迭代，高斯）迭代，高斯-赛德尔（赛德尔（Gauss-SeidelGauss-Seidel）迭代）迭代本讲稿第四页，共八十五页基本思想方法：基本思想方法：由由行初等变换行初等变换将系数矩阵约化为三角将系数矩阵约化为三角 矩阵；用矩阵；用回代回代的方法求解方程组。的方法求解方程组。例例1 1 用消去法（高斯消元法）解方程组用消去法（高斯消元法）解方程组高斯消元法高斯消元法是求解方程组的古典方法。是求解方程组的古典方法。(2.1)3.1 3.1 高斯消元法高斯消元法本讲稿第五页，共八十五页结论：结论：整个计算过程可分为两部分：整个计算过程可分为两部分：（1 1）消元消元：把原方程组转化为系数矩阵为上三角矩阵：把原方程组转化为系数矩阵为上三角矩阵的方程组；的方程组；（2 2）回代回代：由系数矩阵为上三角矩阵的方程组求解：由系数矩阵为上三角矩阵的方程组求解（2 2）回代求解，得：）回代求解，得：解：解：（1 1）消元：）消元：本讲稿第六页，共八十五页对于一般情形：对于一般情形：n n阶线性方程组的高斯消元法阶线性方程组的高斯消元法本讲稿第七页，共八十五页若记若记增广矩阵增广矩阵（2.2）本讲稿第八页，共八十五页（1 1）第）第1 1步步(k k=1)=1)，一般形式的高斯消元法一般形式的高斯消元法：设设 ，首先对行计算乘数，首先对行计算乘数对增广矩阵对增广矩阵 进进行行行初等变换：行初等变换：(即即用用 乘乘以以2.2式式的的第第1个个方方程程，加加到到第第i个个方方程程上上，消消去去2.2式的第二个方程直到第式的第二个方程直到第n个方程中的未知数个方程中的未知数 )(代表第代表第i行行)本讲稿第九页，共八十五页得到与原方程组得到与原方程组 等价的方程组等价的方程组 。记为记为（2）一般第）一般第k步消元步消元()设已完成上述消元过程第设已完成上述消元过程第1 1步，第步，第2 2步，步，第，第k k-1-1步，且步，且 本讲稿第十页，共八十五页其中：其中：设设 ，计算乘数，计算乘数本讲稿第十一页，共八十五页(即即用用 乘乘以以2.2式式的的第第k个个方方程程，加加到到第第i个个方方程程上上，消消去去2.2式式的的第第k+1个方程直到第个方程直到第n个方程中的未知数个方程中的未知数 )那么第那么第k步消元操作即：步消元操作即：(3)(3)继续这一过程，直到完成第继续这一过程，直到完成第n-1n-1次消元，最后我们得到与原方次消元，最后我们得到与原方程组等价的三角形方程组程组等价的三角形方程组(2.3)(2.3)消元过程结束消元过程结束本讲稿第十二页，共八十五页求解三角形方程组求解三角形方程组2.3，得到求解公式，得到求解公式这个过程称为这个过程称为回代过程。回代过程。本讲稿第十三页，共八十五页例题：例题：考虑方程组考虑方程组 GaussGauss消消去去法法中中每每步步用用来来消消去去其其他他元元素素的的 称称为为该该步步的的主主元元素素。GaussGauss消消去去法法作作为为数数值值方方法法，主主元元素素的的选选择择是是否否会会影影响响计算的结果呢？计算的结果呢？则该方程的精确解为则该方程的精确解为而采用而采用(，1)1)作为主元素，利用高斯消去法得到的解为作为主元素，利用高斯消去法得到的解为显然结果是错误的。显然结果是错误的。本讲稿第十四页，共八十五页 错误在哪个地方呢？错误在哪个地方呢？原原因因是是我我们们在在消消元元时时，利利用用了了小小主主元元 ，使使得得约约化化后后的的方方程程组组元元素素数数量量级级大大大大增增长长，再再经经舍舍入入，而而计计算算机机的的有有效效位位数有限，造成消元后的三角形方程组就不准确了。数有限，造成消元后的三角形方程组就不准确了。结结论论：在在消消元元过过程程中中可可能能出出现现主主元元素素为为零零的的情情况况，这这时时消消去去法法将将无无法法进进行行；即即使使不不为为零零，在在主主元元素素很很小小时时，用用其其做做除除数数，也也会会导导致致其其他他元元素素数数量量级级的的严严重重增增长长和和舍舍入入误误差差的的扩扩散散，最最后也使得计算解不可靠。后也使得计算解不可靠。解解决决方方法法：对对一一般般的的矩矩阵阵来来说说，最最好好每每一一步步选选取取系系数数矩矩阵阵（或或消消元元后后的的低低阶阶矩矩阵阵）的的该该列列中中绝绝对对值值最最大大的的元元素素作作为为主主元元素素，以以使使高高斯斯消消去法具有较好的数字稳定性。去法具有较好的数字稳定性。(高斯列主元素消去法高斯列主元素消去法)本讲稿第十五页，共八十五页1.1.列主元法列主元法第一列中绝对值最大是第一列中绝对值最大是1010，取，取1010为主元为主元n n阶方程组第阶方程组第k k轮消元时，选第轮消元时，选第k k列的后列的后(n-k+1)(n-k+1)个元素中绝对值最个元素中绝对值最大作主元。大作主元。本讲稿第十六页，共八十五页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本讲稿第十七页，共八十五页2 2 完全主元素消去法完全主元素消去法整个矩阵中绝对值最大是整个矩阵中绝对值最大是1010，取，取1010为主元为主元n n阶方程组第阶方程组第k k轮消元时，选消元后元素中绝对值最大作主元。轮消元时，选消元后元素中绝对值最大作主元。本讲稿第十八页，共八十五页x1=0 x2=-1x3=1方框中方框中6 6最大，交换行列，交换列的时候要做记录（即最大，交换行列，交换列的时候要做记录（即x3x3和和x2x2交换了位置）：交换了位置）：本讲稿第十九页，共八十五页 完全主元素消除法与列主元素消除法完全主元素消除法与列主元素消除法的优缺点比较：的优缺点比较：优点：优点：数值更加稳定；数值更加稳定；缺点：缺点：计算量大；计算量大；本讲稿第二十页，共八十五页 对对矩矩阵阵A A实实行行初初等等行行变变换换相相当当于于用用初初等等矩矩阵阵左左乘乘A A，于于是是对对(2 2.2 2)做做 第第 一一 次次 消消 元元 后后，化化 为为 化化 为为 ，即即 ，其中，其中 3.1 矩阵的三角分解矩阵的三角分解 LULU分解分解本讲稿第二十一页，共八十五页第第k k步的初等矩阵为步的初等矩阵为并且并且重复这一过程，最后得到重复这一过程，最后得到将上三角矩阵将上三角矩阵 记为记为U U，则，则 本讲稿第二十二页，共八十五页将上三角矩阵将上三角矩阵 记为记为U U，则，则 ，其中其中则，则，L L为单位下三角矩阵。为单位下三角矩阵。高斯消去法实质上是产生了一个将高斯消去法实质上是产生了一个将A A分解为两个三角形矩阵相分解为两个三角形矩阵相乘的因式分解。如果乘的因式分解。如果A A是非奇异阵，则是非奇异阵，则LULU分解是唯一的，否则分解分解是唯一的，否则分解不唯一。不唯一。本讲稿第二十三页，共八十五页消元法：消元法：消元法与三角分解法间的关系：消元法与三角分解法间的关系：三角分解法：三角分解法：讨论讨论本讲稿第二十四页，共八十五页直接三角分解法解线性方程组（直接三角分解法解线性方程组（）的具体流程：）的具体流程：1.2.2.计算计算U U的第的第r r行，行，L L的第的第r r列元素列元素 r=2,3,n3.(一一)LU分解分解本讲稿第二十五页，共八十五页再求解再求解Ly=b,Ux=yLy=b,Ux=y计算公式：计算公式：(二二)x的的计算计算本讲稿第二十六页，共八十五页例例 用直接三角分解法解方程组用直接三角分解法解方程组 解解:(一一)矩阵矩阵LU分解分解(1)(1)故：故：本讲稿第二十七页，共八十五页(2)经计算：经计算：本讲稿第二十八页，共八十五页(二二)求解求解x：从而从而本讲稿第二十九页，共八十五页 3.2 3.2 矩阵的矩阵的CholeskyCholesky分解分解 对称正定矩阵对称正定矩阵A A：AT=A,A的各阶顺序主子式大于零的各阶顺序主子式大于零.前前 面面 指指 出出 非非 奇奇 异异 的的 矩矩 阵阵 可可 以以 有有 三三 角角 分分 解解，当当A A是是 某某 些些 特特 殊殊矩矩阵阵时时，它它的的L L U U 分分 解解 会会 有有 更更 加加 简简 洁洁 的的 形形 式式。A A的的LULU分解分解(2.4)本讲稿第三十页，共八十五页uii 0(i=1,n)由于由于A A是对称正定的，则有是对称正定的，则有将将U U进一步分解：进一步分解：本讲稿第三十一页，共八十五页根据根据A A的对称性：的对称性：故：故：由分解的唯一性知：由分解的唯一性知：故：故：其中其中P P为上三角矩阵，这种对称正定矩阵的分解称为为上三角矩阵，这种对称正定矩阵的分解称为CholeskyCholesky分分解。解。在在MatlabMatlab中函数中函数“cholchol”给出对称正定矩阵的给出对称正定矩阵的CholeskyCholesky分解。分解。本讲稿第三十二页，共八十五页经过经过n n步可直接求得步可直接求得思路思路:(1)(1)分解对称正定矩阵分解对称正定矩阵设设n n阶对称正定矩阵阶对称正定矩阵A A有分解有分解 ,先用待定系数法求先用待定系数法求L L的的元素元素Cholesky分解的具体步骤分解的具体步骤(平方根法平方根法)：(2)(2)分解分解求解方程组求解方程组本讲稿第三十三页，共八十五页Cholesky方法方法具体计算公式：具体计算公式：分解计算：分解计算：求解：求解：本讲稿第三十四页，共八十五页 3.3 3.3 向量范数与矩向量范数与矩阵范数范数向量、向量、矩阵与线性方程组有着密切的关系，矩阵与线性方程组有着密切的关系，向量、矩阵范数是向量、矩阵范数是解方程解方程组以及研究与探讨方程组本身性质的工具。组以及研究与探讨方程组本身性质的工具。一、向量范数的定义一、向量范数的定义定义定义 范数为范数为其中的其中的 ，最常用的范数是，最常用的范数是 ，以及，以及本讲稿第三十五页，共八十五页容易证明向量范数满足如下性质：容易证明向量范数满足如下性质：(1)如果如果 ，则，则 ；而且；而且 ，当且，当且仅当仅当 (2)对任何的数对任何的数c，都有，都有 (3)范数也称为范数也称为2-2-范数或范数或EuclideanEuclidean函数；函数；范数也称为范数也称为 -范数范数或一致范数。在或一致范数。在MatlabMatlab中用函数中用函数 用来计算向量用来计算向量x x的的 范数。范数。由性质由性质(3),还容易得到：还容易得到：本讲稿第三十六页，共八十五页二二 矩阵范数的定义矩阵范数的定义在向量范数的基础上可以进一步定义矩阵范数在向量范数的基础上可以进一步定义矩阵范数 如果上式中的向量范数取为如果上式中的向量范数取为 范数，则可以证明定义出的矩阵范范数，则可以证明定义出的矩阵范数（称为矩阵数（称为矩阵 范数或者列范数）为范数或者列范数）为 如果向量范数取为如果向量范数取为2-范数，则范数，则 其中其中 （模），称为矩阵（模），称为矩阵B的谱半的谱半径。径。(为为B的任意特征值。的任意特征值。)本讲稿第三十七页，共八十五页 类似地，类似地，Matlab函数函数norm(A,p)给出矩阵给出矩阵p=1,2或或 范数范数 如果向量范数取如果向量范数取为为 ，则可以证明定义出的矩阵范数，则可以证明定义出的矩阵范数（称为矩阵的（称为矩阵的 范数或者行范数）为范数或者行范数）为 容易证明矩阵范数满足如下性质：容易证明矩阵范数满足如下性质：(1)(1)如果如果 ，则，则 ；而且；而且 ，而且仅当，而且仅当 (2)(2)对任何的数对任何的数 ，(3)(3)(4)(4)而且由矩阵范数的定义还有而且由矩阵范数的定义还有称之为矩阵范数与相应的向量范数是相容的。称之为矩阵范数与相应的向量范数是相容的。本讲稿第三十八页，共八十五页39 3.4 古典迭代法的构造古典迭代法的构造求解线性代数方程组的方法求解线性代数方程组的方法中小规模中小规模问题问题直接法直接法迭代法迭代法 大规模，大规模，超大规模问题超大规模问题 古典方法古典方法现代方法现代方法本讲稿第三十九页，共八十五页40线性方程组的一般形式为：线性方程组的一般形式为：如果如果 是非奇异的，则上式有唯一解。是非奇异的，则上式有唯一解。我们将通过一个具体线性方程组的例子来讲解迭代法。我们将通过一个具体线性方程组的例子来讲解迭代法。取：取：即线性方程组为：即线性方程组为：方程的精确解方程的精确解 (直接法计算直接法计算)本讲稿第四十页，共八十五页41 如果对该方程组进行变形，将变量如果对该方程组进行变形，将变量 分别从分别从三个方程中分离出来：三个方程中分离出来：(1)(1)令令初初值值本讲稿第四十一页，共八十五页所以所以(1)式可以表示为迭代形式：式可以表示为迭代形式：所以我们可以得到一个向量的序列所以我们可以得到一个向量的序列 ，只要该序列当，只要该序列当 时有极限，那么这个极限就是该线性方程组的解。时有极限，那么这个极限就是该线性方程组的解。上面这种迭代求解线性方程组的方法称为上面这种迭代求解线性方程组的方法称为Jacobi迭代法迭代法。本讲稿第四十二页，共八十五页考虑线性方程组的一般形式：考虑线性方程组的一般形式：其中矩阵其中矩阵A为为nn阶方阵，则方程的分量形式为：阶方阵，则方程的分量形式为：改写成：改写成：本讲稿第四十三页，共八十五页从而得到迭代公式：从而得到迭代公式：上面式子就是一般形式的上面式子就是一般形式的Jacobi迭代法，也可也记做：迭代法，也可也记做：本讲稿第四十四页，共八十五页在在Jacobi迭代法中充分利用新值，可得到下面迭代：迭代法中充分利用新值，可得到下面迭代：上面这种迭代方法也叫做上面这种迭代方法也叫做Gauss-Seidel迭代，也可以记为：迭代，也可以记为：本讲稿第四十五页，共八十五页方程组的精确解为方程组的精确解为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法求解线性方程组法求解线性方程组本讲稿第四十六页，共八十五页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.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636可见可见,迭代序列逐次收敛于方程组的解迭代序列逐次收敛于方程组的解,而且迭代而且迭代7 7次得到精确到小数点后两位次得到精确到小数点后两位的近似解的近似解.计算结果列表如下计算结果列表如下:本讲稿第四十七页，共八十五页Gauss-SeidelGauss-Seidel迭代法的计算公式为迭代法的计算公式为:同样取初始向量同样取初始向量x x(0)(0)=(0,0,0)=(0,0,0)T T,计算结果为计算结果为 由计算结果可见由计算结果可见,Gauss-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 本讲稿第四十八页，共八十五页为了进一步研究为了进一步研究,从矩阵角度来讨论上述迭代法从矩阵角度来讨论上述迭代法.对线性方程组对线性方程组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 本讲稿第四十九页，共八十五页由此建立由此建立JacobiJacobi迭代法迭代公式迭代法迭代公式 x x(k+1)(k+1)=D=D-1-1(L+U)x(L+U)x(k)(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,其中其中本讲稿第五十页，共八十五页所以所以Gauss-SeidelGauss-Seidel迭代法可以写成迭代法可以写成其中其中Gauss-SeidelGauss-Seidel迭代法迭代公式为迭代法迭代公式为写成矩阵形式为：写成矩阵形式为：本讲稿第五十一页，共八十五页 3.5 3.5 迭代法的分析迭代法的分析 构造迭代法的途径可以有很多，那么是不是所有的方法都构造迭代法的途径可以有很多，那么是不是所有的方法都能收敛呢？收敛速度的快慢与什么有关系呢？能收敛呢？收敛速度的快慢与什么有关系呢？它的精确解为它的精确解为例：例：本讲稿第五十二页，共八十五页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)收敛速度也是不同的收敛速度也是不同的.计算结果列表如下计算结果列表如下:本讲稿第五十三页，共八十五页 设设 是矩阵是矩阵B任意一个特征值，任意一个特征值，是相应的特征向量，是相应的特征向量，即即 再假设再假设 为任意的向量范数及与之相融的矩阵范数，则有：为任意的向量范数及与之相融的矩阵范数，则有：首先引入几个定义、引理：首先引入几个定义、引理：所以对矩阵所以对矩阵B任意一个特征值任意一个特征值 ，都有，都有记记 ，称之为矩阵，称之为矩阵B的的谱半径谱半径，则，则本讲稿第五十四页，共八十五页先引入两个引理（详细证明见附录）：先引入两个引理（详细证明见附录）：引理引理3.1 矩阵矩阵 ，则，则 的充分必要条的充分必要条件是件是 引理引理3.2 矩阵矩阵 ，若，若 ，则，则 是是非奇异的。非奇异的。本讲稿第五十五页，共八十五页 定理定理3.1 对任意的对任意的 和任意的初始向量和任意的初始向量 ，迭代法收敛的，迭代法收敛的充分必要条件是充分必要条件是证明：证明：必要性必要性 设迭代法产生的序列设迭代法产生的序列 收敛，记收敛，记 是该序列的极限点，所以是该序列的极限点，所以 满满足足又由迭代关系又由迭代关系 ，可以得到，可以得到本讲稿第五十六页，共八十五页由由 的任意性，知：的任意性，知：由引理由引理3.1知：知：充分性充分性 由由 及引理及引理2知知 （即（即 ）有唯一解，记为有唯一解，记为 类似于必要性的证明，得到类似于必要性的证明，得到再由第一步知再由第一步知 ，故，故本讲稿第五十七页，共八十五页 定理定理3.1给出了迭代收敛的充要条件，但给出了迭代收敛的充要条件，但 不宜计算，不宜计算，所以在实际使用中通常并不好用。由所以在实际使用中通常并不好用。由 知，只要对某种知，只要对某种相容的矩阵范数有相容的矩阵范数有 那那么么当当然然 ，所所以以这这常常常常是是实实际际中中很很有有效效的的收收敛敛判判别别准准则。则。严格对角占优矩阵：严格对角占优矩阵：考虑考虑 ，设，设 ，当，当 时的矩阵。时的矩阵。本讲稿第五十八页，共八十五页定理定理3.2 如果如果A是严格对角占优的矩阵，则它一定非奇异。是严格对角占优的矩阵，则它一定非奇异。由于由于A是对角占优矩阵，所以是对角占优矩阵，所以 ，故矩阵，故矩阵是可逆的。考虑是可逆的。考虑本讲稿第五十九页，共八十五页 矩阵的矩阵的 范数为范数为由由A是对角占优矩阵，得是对角占优矩阵，得 由引理由引理3.2知知 是非奇异的，又由于是非奇异的，又由于 是非奇异的，所以是非奇异的，所以A是非奇是非奇异的。异的。得证！得证！引理引理3.2 矩阵矩阵 ，若，若 ，则，则 是是非奇异的。非奇异的。本讲稿第六十页，共八十五页 定理定理3.3 系数矩阵为严格对角占优的线性代数方程组，它的系数矩阵为严格对角占优的线性代数方程组，它的Jacobi迭迭代法和代法和Gauss-Seidel迭代都是收敛的。迭代都是收敛的。证明：证明：Jacobi方法的迭代矩阵为方法的迭代矩阵为由定理由定理3.2中的证明知，严格对角占优矩阵满足：中的证明知，严格对角占优矩阵满足：再由定理再由定理3.1，得，得Jacobi迭代法收敛。迭代法收敛。(a)Jocobi的证明的证明1本讲稿第六十一页，共八十五页再考虑再考虑Gauss-Seidel方法，其迭代矩阵为方法，其迭代矩阵为用反证法，假设用反证法，假设Gauss-Seidel迭代不收敛，则由定理迭代不收敛，则由定理3.1知：知：所以存在模大于所以存在模大于1的特征值的特征值.设有设有 ，使得行列式：，使得行列式：(b)Gauss-Seidel的证明的证明本讲稿第六十二页，共八十五页 故，只有故，只有才能使得才能使得 成立。成立。由于由于A是对角占优的，所以矩阵是对角占优的，所以矩阵 也是对角占优的，那么该矩阵一定非奇异，这与上面该矩阵也是对角占优的，那么该矩阵一定非奇异，这与上面该矩阵 的行列式等于的行列式等于0矛盾。矛盾。由于由于 可逆，所以可逆，所以得证！得证！本讲稿第六十三页，共八十五页定理定理3.4 若迭代矩阵若迭代矩阵B满足满足 ，则迭代生成的序列，则迭代生成的序列 满足满足收敛速度问题收敛速度问题其中其中 表示精确解。表示精确解。证明：证明：先证明先证明(b),然后证明然后证明(a)本讲稿第六十四页，共八十五页而而所以所以故，本页第一个式子可写为故，本页第一个式子可写为本讲稿第六十五页，共八十五页由于由于 ，故，故(b)得证得证显然对于任意的正整数显然对于任意的正整数p，都有，都有那么在本页第一个式子中反复利用上式就可以得到那么在本页第一个式子中反复利用上式就可以得到(a)(a)得证得证本讲稿第六十六页，共八十五页 给出的关系可以作为计算终止的判别准则。即只要给出的关系可以作为计算终止的判别准则。即只要 和和 已足够接近，表明已足够接近，表明 与与 便已足够靠近。便已足够靠近。定理定理3.4(a)给出的是迭代收敛速度的一个估计。显然给出的是迭代收敛速度的一个估计。显然 越接近越接近0，生成序列，生成序列 收敛得越快。收敛得越快。定理定理3.14(b)定理定理3.4的讨论的讨论本讲稿第六十七页，共八十五页 3.6 超松弛迭代超松弛迭代(SOR)及分块迭代方法及分块迭代方法 对于给定的迭代法，每步迭代所需的工作量是确定的。对于给定的迭代法，每步迭代所需的工作量是确定的。如果迭代法收敛速度缓慢，则需要比较多的迭代次数，由如果迭代法收敛速度缓慢，则需要比较多的迭代次数，由此导致算法工作量太大而失去使用价值，因此各种迭代法此导致算法工作量太大而失去使用价值，因此各种迭代法的加速技术具有重要意义。的加速技术具有重要意义。假设假设 是已经得到的迭代值，以是已经得到的迭代值，以 为初值进行一步为初值进行一步Gauss-Seidel迭代得：迭代得：本讲稿第六十八页，共八十五页将这一迭代值与将这一迭代值与 的值组合作为新一步的迭代值的值组合作为新一步的迭代值其中其中 为待定的参数，写成矩阵形式为：为待定的参数，写成矩阵形式为：这时迭代矩阵：这时迭代矩阵：本讲稿第六十九页，共八十五页 新新的的迭迭代代每每步步的的计计算算代代价价与与Gauss-Seidel方方法法相相差差无无几几，如如果果能能取取得得恰恰当当的的 值值，使使新新构构造造的的方方法法比比Gauss-Seidel方方法法收收敛敛得得更更快快，松松弛就起到了加速的作用。弛就起到了加速的作用。在在实实际际上上真真正正使使用用的的 值值通通常常的的范范围围为为 ，被被统统称称为为超超松松弛弛方法方法，简称，简称SOR(Successive Over-Relaxation)方法。方法。上面的这个方法就叫做松弛方法，它可以视为上面的这个方法就叫做松弛方法，它可以视为Gauss-Seidel方法的加方法的加速。显然速。显然 时，上面这个方法就是时，上面这个方法就是Gauss-Seidel方法。方法。本讲稿第七十页，共八十五页定理定理3.5 SOR方法收敛的必要条件是：方法收敛的必要条件是：证明：证明：假设假设SOR方法收敛，所以方法收敛，所以设设 为为 的特征值，则的特征值，则另一方面，经过计算不难得到另一方面，经过计算不难得到故故 ，结论得证。，结论得证。本讲稿第七十一页，共八十五页分块矩阵以及分块迭代方法分块矩阵以及分块迭代方法在许多实际应用中，矩阵可以写成如下分块的形式：在许多实际应用中，矩阵可以写成如下分块的形式：其中其中 是是 阶的方阵，而且阶的方阵，而且 据此可以构造分块形式的迭代法，考虑据此可以构造分块形式的迭代法，考虑 其中其中本讲稿第七十二页，共八十五页求解方程组求解方程组 ，分块的，分块的Jacobi迭代法为：迭代法为：分块的分块的Gauss-Seidel迭代法为：迭代法为：本讲稿第七十三页，共八十五页分块的超松弛迭代法分块的超松弛迭代法(BSOR)为为本讲稿第七十四页，共八十五页 3.7 线性方程组的条件数线性方程组的条件数 对于线性方程组对于线性方程组 如如果果解解x关关于于问问题题（即即矩矩阵阵A和和向向量量b）的的“微微小小”变变化化(来来源源可可能能是是模模型型误误差差或或数数据据上上的的误误差差，也也可可能能是是数数值值计计算算中中的的舍舍入入误误差差)不不敏敏感感，那那么么这这个个问问题题即即是是一一个个“好好”问问题题，反之就是反之就是“坏坏”问题或者病态的问题。问题或者病态的问题。关于病态的例子，我们在第一章中已经包含了一个，这一章主要用关于病态的例子，我们在第一章中已经包含了一个，这一章主要用范数作为工具来分析线性方程组的好坏。范数作为工具来分析线性方程组的好坏。本讲稿第七十五页，共八十五页例例 设有方程组设有方程组已知系数已知系数测量数据测量数据待求数据待求数据其中其中A为为 ，若测量数据为准确数据，若测量数据为准确数据，即即 ，那么很容易计算，那么很容易计算如果测量数据不够精确，即测量数据仅保留了如果测量数据不够精确，即测量数据仅保留了2 2位有效数字，即位有效数字，即 ，计算结果为，计算结果为本讲稿第七十六页，共八十五页如果测量数据和系数矩阵的数据都仅保留了如果测量数据和系数矩阵的数据都仅保留了2 2位有效数字，即位有效数字，即，则计算结果为，则计算结果为以上问题称为病态的问题，病态是问题本身固有的。以上问题称为病态的问题，病态是问题本身固有的。本讲稿第七十七页，共八十五页(1)考虑由于右端的扰动所引起的解的变化，考虑由于右端的扰动所引起的解的变化，已知已知两式相减得两式相减得利用范数关系可以得到：利用范数关系可以得到：综合上述两式有：综合上述两式有：本讲稿第七十八页，共八十五页 这个式子给出了右端的扰动可能引起解扰动的上界，显然这个式子给出了右端的扰动可能引起解扰动的上界，显然 越小，方程右端的变化引起解的变化就越小。越小，方程右端的变化引起解的变化就越小。(2)考虑由于矩阵考虑由于矩阵A有扰动时所引起的解的变化有扰动时所引起的解的变化可以得到：可以得到：其中利用了其中利用了本讲稿第七十九页，共八十五页经过整理可以得到经过整理可以得到(3)考虑更一般的情形所引起的解的变化考虑更一般的情形所引起的解的变化假设满足如下的特殊形式：假设满足如下的特殊形式：又又Tylor展开，展开，可以写成可以写成本讲稿第八十页，共八十五页对对 求导得求导得令令 ，并考虑到，并考虑到 ，则，则记记 ，从而有，从而有本讲稿第八十一页，共八十五页 从上面三种情况可见，问题扰动所引起解的扰动是被同一从上面三种情况可见，问题扰动所引起解的扰动是被同一个因子个因子 控制的控制的 定义定义3.1 设设A为可逆矩阵，为可逆矩阵，是与某种向量范数相容的矩是与某种向量范数相容的矩阵范数，称阵范数，称 为线性方程组为线性方程组 相应于该矩阵范数的条件数。相应于该矩阵范数的条件数。由前面的分析可见，条件数大的就是病态的矩阵，反之是良态的矩阵。由前面的分析可见，条件数大的就是病态的矩阵，反之是良态的矩阵。求解线性方程时了解它的条件数大小是必要的，它可以帮助你判断所求解线性方程时了解它的条件数大小是必要的，它可以帮助你判断所得数值解的可信性及模型的合理性。得数值解的可信性及模型的合理性。在在Matlab中可以用中可以用cond（A）来计算条件数或者用）来计算条件数或者用rcond(A)来估计来估计其量级的倒数其量级的倒数。本讲稿第八十二页，共八十五页设设 ，则，则 ，即对于该函数，误差会被放大，即对于该函数，误差会被放大n n倍。倍。二、病态问题与条件数（针对问题本身）二、病态问题与条件数（针对问题本身）定义：输入数据的微小变动导致输出数据的较大误差，就被称定义：输入数据的微小变动导致输出数据的较大误差，就被称为病态问题。为病态问题。衡量是否病态的标准：条件数衡量是否病态的标准：条件数 对于函数值计算问题，条件数定义为：对于函数值计算问题，条件数定义为：不同的问题，条件数具体定义不同。不同的问题，条件数具体定义不同。一般情况下，条件数大于一般情况下，条件数大于1010，就认为问题病态。，就认为问题病态。通过构造特殊算法来解决本讲稿第八十三页，共八十五页条件数的重要性质：条件数的重要性质：定理定理3.6 (a)对任意的非奇异矩阵对任意的非奇异矩阵A，cond(A)是由任意的矩阵是由任意的矩阵 范数定义的条件范数定义的条件数，则数，则 (b)如果如果Q是正交矩阵，则对于任意的非奇异矩阵是正交矩阵，则对于任意的非奇异矩阵A，都有，都有其中其中本讲稿第八十四页，共八十五页证明：证明：(a)中的各条性质是显然的，例如，对任意的非奇异矩阵中的各条性质是显然的，例如，对任意的非奇异矩阵A，有，有 (b)由于由于Q是正交矩阵，所以是正交矩阵，所以 另外，另外，本讲稿第八十五页，共八十五页