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