《数值计算方法》PPT课件.ppt

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