资源描述
第七章 解线性方程组的数值方法重庆邮电大学1第七章 解线性方程组的数值方法重庆邮电大学2 7.5 向量及矩阵的范数向量及矩阵的范数范数是对向量和矩阵的一种度量,实际上是二维和三维向量长度概念的一种推广数域:数的集合,对加法和乘法封闭线性空间:可简化为向量的集合,对向量的加法和数量乘法封闭,二维向量和三维向量都可以度量其大小和长度高维向量的长度能否定义呢?也称为向量空间重庆邮电大学3定义1.一、向量和矩阵的范数重庆邮电大学4-(1)-(2)-(3)重庆邮电大学5显然并且由于-(4)重庆邮电大学6例4.求下列向量的各种常用范数解:定义定义（向量序列的极限）设 为向量序列，记 及 如果n个数列极限存在且则 称收敛于 ,记为 重庆邮电大学7定理定理6 设 是 上任一向量范数,则 是 的分量 的连续函数。定理定理7 设 是 上向量的任意两种范数，则存在常数 ,使得对一切 有（5.1）定理定理8 设 是 中一上向量序列，且 则重庆邮电大学8定义3.重庆邮电大学9例5.不难验证其满足定义2的4个条件称为Frobenius范数,简称F-范数而且可以验证tr为矩阵的迹-(5)-(6)类似向量的 2-范数重庆邮电大学10定义4.-(7)简称为从属范数或算子范数重庆邮电大学11显然，由定义不难推出定义5.由(8)式,可知算子范数和其对应的向量范数是相容的-(8)-(9)重庆邮电大学12根据向量的常用范数可以得到常用的矩阵算子范数-(10)-(11)-(12)重庆邮电大学13例6.求矩阵A的各种常用范数解:由于重庆邮电大学14特征方程为重庆邮电大学15容易计算计算较复杂对矩阵元素的变化比较敏感不是从属范数较少使用使用最广泛性质较好重庆邮电大学16 7.6 解线性方程组的迭代法解线性方程组的迭代法在用直接法解线性方程组时要对系数矩阵不断变换如果方程组的阶数很高,则运算量将会很大并且大量占用计算机资源因此对线性方程组要求找寻更经济、适用的数值解法-(1)重庆邮电大学17如果能将线性方程组(1)变换为-(2)显然,(1)式和(2)式同解,我们称(1)(2)等价对线性方程组(2),采用以下步骤:依此类推重庆邮电大学18-(3)这种方式就称为迭代法,以上过程称为迭代过程迭代法产生一个序列如果其极限存在,即则称迭代法收敛,否则称为发散重庆邮电大学19一、简单迭代法(基本迭代法)设线性方程组(1)的一般形式为重庆邮电大学20依此类推,线性方程组(1)可化为-(4)重庆邮电大学21-(5)对(4)作迭代过程则(5)式转化为矩阵形式-(6)重庆邮电大学22令重庆邮电大学23故迭代过程(6)化为等价线性方程组为-(7)称(5)式和(7)式为解线性方程组(1)的Jacobi迭代法(J法)重庆邮电大学24例6.用Jacobi迭代法求解方程组,误差不超过1e-4解:重庆邮电大学25重庆邮电大学26重庆邮电大学27依此类推,得方程组满足精度的解为x12迭代次数为12次 x4=3.0241 1.9478 0.9205 d=0.1573 x5=3.0003 1.9840 1.0010 d=0.0914 x6=2.9938 2.0000 1.0038 d=0.0175 x7=2.9990 2.0026 1.0031 d=0.0059 x8=3.0002 2.0006 0.9998 d=0.0040 x9=3.0003 1.9999 0.9997 d=7.3612e-004x10=3.0000 1.9999 0.9999 d=2.8918e-004x11=3.0000 2.0000 1.0000 d=1.7669e-004x12=3.0000 2.0000 1.0000 d=3.0647e-005重庆邮电大学28分析Jacobi迭代法(5)的迭代过程,将(5)式细化重庆邮电大学29考虑迭代式(7)即将上式改为-(8)重庆邮电大学30-(9)上式称为Gauss-Seidel迭代法,简称G-S法利用(8)式展开Gauss-Seidel迭代法也可表示成重庆邮电大学31重庆邮电大学32例7.用Gauss-Seidel迭代法求解例6.解:通过迭代,至第7步得到满足精度的解x7重庆邮电大学33x1=2.5000 2.0909 1.2273 d=3.4825x2=2.9773 2.0289 1.0041 d=0.5305x3=3.0098 1.9968 0.9959 d=0.0465x4=2.9998 1.9997 1.0002 d=0.0112x5=2.9998 2.0001 1.0001 d=3.9735e-004x6=3.0000 2.0000 1.0000 d=1.9555e-004x7=3.0000 2.0000 1.0000 d=1.1576e-005 从例6和例7可以看出,Gauss-Seidel迭代法的收敛速度比Jacobi迭代法要高.高斯-赛得尔迭代法与雅可比迭代法都具有算式简单、易在计算机上实现等优点,且每迭代依次一次秩只需计算一次矩阵与向量的乘法.且前者比后者需要的存储单元要少.对于给定的矩阵线性方程组,用两种求解时,可能都收敛,也可能一个收敛另一个不收敛.在都收敛的情况下,有时前者收敛快,有时后者收敛快.二者统称为简单迭代法.重庆邮电大学34二二.解线性方程组的超松弛迭代法解线性方程组的超松弛迭代法 逐次超松弛迭代法(Successive Over Relaxation Method),简称SOR方法是GS迭代法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一，它有着广泛的应用。设有方程组 为非奇异矩阵.选取分裂矩阵 为带参数的下三角阵 其中 为可选择的松弛因子。于是可得迭代矩阵 重庆邮电大学35于是得到解 的逐次超松弛迭代公式：（6.11）其中 超松弛迭代法（SOR）的分量形式：设已知第k次近似 及第 次近似的分量 ,首先用GS迭代法计算一个辅助量 （6.12）重庆邮电大学36再由 的第 个分量 与 加权平均,定义（6.13）将(6.12)代入(6.13),得到解 的SOR方法：（6.14）重庆邮电大学37或写成 在SOR方法(6.14)中取 就是GS迭代法.当松弛因子 满足 时,迭代法(6.14)称为低松弛方法;当 时迭代法(6.14)称为超松弛方法超松弛方法。SOR方法每迭代一次主要计算量时计算一次矩阵乘向量.计算时可用迭代,这时SOR方法只需一组工作单元存放 来控制或 也可用剩余向量 来控制迭代终止。重庆邮电大学38定理12.三、迭代法的收敛条件与误差估计定义5.-(9)定理10.矩阵A的谱半径不超过矩阵A的任何一种算子范数.定理11.重庆邮电大学39定理13.-(10)-(11)证明:(1)先证明X=BX+f有唯一解.由定理4,B的特征值的模下证迭代序列收敛于唯一解.因为重庆邮电大学40-(12)(2)由范树的性质及上面的不等式(12)因此,结论成立.重庆邮电大学41(3)由不等式(10)及因此,结论成立.于是重庆邮电大学42(10)可以用来估计迭代法的精度,理论上只要在计算时,迭代终止的时间可以用上式判别另外,给出系数矩阵对角占优线性方程组的一个结论定理6.定理7.若方程组AX=b的系数矩阵为对称正定矩阵,则对任意初始向量X(0),高斯赛德尔迭代法收敛.定理8.迭代过程X(k+1)=BX(k)+f对任意初始向量X(0)收敛的充分必要条件是迭代局阵的谱半径p(B)1;且当p(B)1时,迭代矩阵谱半径越小,收敛速度越快.重庆邮电大学43例8 试考察用Jacobi方法,GS迭代法解下面方程组的收敛 解解 由于为严格对角占优阵，于是由定理6可知解方程组Ax=b的Jacobi迭代法，GS迭代法均收敛。重庆邮电大学44 7.7 病态方程组和迭代法改善法病态方程组和迭代法改善法 判断一个计算方法的好坏,可用算法的稳定性、解的精确程度以及计算量、存储量的大小等来衡量。然而，同一方法用于不同问题，效果却可以相差很远，这就涉及到问题本身的状态。本节在分析方程组的初始数据A、b的小扰动（误差）对解的影响的基上，给出方程组“病态”、”良态“的概念及其衡量标准，并介绍判断近似解可靠性以及提高计算结果精度的方法。重庆邮电大学45引例 设有方程组 其解现考虑常数项有微小的误差，即其中，得到一个扰动方程组其解为 此例说明,方程组常数项分量只有微小变化(1/100),而方程组的解有较大的变化.也就是说这个方程组的解对于问题的数据b很灵敏.这样的方程组就是病态方程组。重庆邮电大学46定义.7.7.1 病态方程组及误差分析简介即有-(15)重庆邮电大学47-(16)-(17)-(18)所以又因为可得(16)和(17)两式相乘,得相对误差重庆邮电大学48(18)式表明,由常数项产生的误差,最多可将解的相对误差放大 倍所以重庆邮电大学49定义7.-(20)-(19)重庆邮电大学50显然即任意方阵的条件数必不小于1根据算子范数的不同也有不同的条件数:重庆邮电大学51-(18)-(19)根据定义7的定义,(18)式和(19)式可表示为重庆邮电大学52定理定理17 （b扰动对解的影响）则有（7.4）重庆邮电大学537.7.2 迭代改善(可靠性判别)法定理19.-(21)定理定理18 （A扰动对解的影响）重庆邮电大学54设 为用高斯法求得的计算解，计算剩余向量-(22)求解-(23)且计算-(24).显然,如果计算 及 没有误差,则 是方程组 的精确解。事实上，但实际计算时,由于有舍入误差,得到 的只是一个近似解.于是,重复上述过程(22)(24),可求得方程组的一个近似解序列 .当 不是过分病态时,通常 很快收敛到方程组的解 。重庆邮电大学55例9 设线性方程组为解解 (1)因为(1)求系数矩阵的条件数 (2)若右端向量有扰动 ,试估计解的相对误差.所以,系数矩阵A的条件数重庆邮电大学56(2)本例是讨论方程组右端有扰动时对解的相对误差的国际,由解向量的精度估计式:得此即为解的相对误差.重庆邮电大学571.掌握两种基本迭代法;2.掌握迭代法收敛的条件及误差估计;3.会求矩阵的条件数,并根据其判断对应线性方程组的性态及误差估计.小结小结:作业:P.7,9,10(2).本章要点线性方程组的解法类型之一:直接解法主要归结为三角形方程组的求解包括一般线性方程组的Gauss消去法、Gauss列主元法、对称正定方程组的平方根法、三对角方程组的追赶法等涉及到一些三角分解：主要有Doolittle分解、Cholesky分解等本章作业重庆邮电大学58
展开阅读全文