《数值计算方法.ppt》由会员分享，可在线阅读，更多相关《数值计算方法.ppt（58页珍藏版）》请在三一文库上搜索。
1、重庆邮电大学,1,数值计算方法,第七章 解线性方程组的数值方法,重庆邮电大学,2,7.1 引言,7.2 Gauss消去法,第七章 解线性方程组的数值方法,7.3 选主元的Gauss消去法,7.4 矩阵的三角分解,7.5 向量和矩阵的范数,7.6 解线性方程组的迭代法,7.7 病态方程组和迭代改善法,重庆邮电大学,3,7.5 向量及矩阵的范数,“范数“是对向量和矩阵的一种度量,实际上是二维 和三维向量长度概念的一种推广,数域:,数的集合,对加法和乘法封闭,线性空间:,可简化为向量的集合,对向量的加法和 数量乘法封闭,二维向量和三维向量都可以度量其大小和长度,高维向量的“长度“能否定义呢?,也称为
2、向量空间,重庆邮电大学,4,定义1.,一、向量和矩阵的范数,重庆邮电大学,5,-(1),-(2),-(3),重庆邮电大学,6,显然,并且由于,-(4),重庆邮电大学,7,例4.求下列向量的各种常用范数,解:,定义（向量序列的极限）,则 称收敛于 ,记为,重庆邮电大学,8,定理6 设 是 上任一向量范数,则 是 的分量 的连续函数。,定理7 设 是 上向量的任意两种范数，则存在常数 ,使得对一切 有,（5.1）,定理8 设 是 中一上向量序列，且 则,重庆邮电大学,9,定义3.,重庆邮电大学,10,例5.,不难验证其满足定义2的4个条件,称为Frobenius范数,简称F-范数,而且可以验证,t
3、r为矩阵的迹,-(5),-(6),类似向量的 2-范数,重庆邮电大学,11,定义4.,-(7),简称为从属范数或算子范数,重庆邮电大学,12,显然，由定义不难推出,定义5.,由(8)式,可知算子范数和其对应的向量范数是相容的,-(8),-(9),重庆邮电大学,13,根据向量的常用范数可以得到常用的矩阵算子范数,-(10),-(11),-(12),重庆邮电大学,14,例6.,求矩阵A的各种常用范数,解:,由于,重庆邮电大学,15,特征方程为,重庆邮电大学,16,容易计算,计算较复杂,对矩阵元素的 变化比较敏感,不是从属范数,较少使用,使用最广泛,性质较好,重庆邮电大学,17,7.6 解线性方程组
4、的迭代法,在用直接法解线性方程组时要对系数矩阵不断变换,如果方程组的阶数很高,则运算量将会很大,并且大量占用计算机资源,因此对线性方程组,要求找寻更经济、适用的数值解法,-(1),重庆邮电大学,18,如果能将线性方程组(1)变换为,-(2),显然,(1)式和(2)式同解,我们称(1)(2)等价,对线性方程组(2),采用以下步骤:,依此类推,重庆邮电大学,19,-(3),这种方式就称为迭代法,以上过程称为迭代过程,迭代法产生一个序列,如果其极限存在,即,则称迭代法收敛,否则称为发散,重庆邮电大学,20,一、简单迭代法(基本迭代法),设线性方程组(1)的一般形式为,重庆邮电大学,21,依此类推,线
5、性方程组(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
6、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-004 x10 = 3.0000 1.9999 0.9999 d = 2.8918e-004 x11 = 3.0000 2.0000 1.0000 d = 1.7669e-004 x12 = 3.0000 2.0000 1.0000 d = 3.0647e-005,
7、重庆邮电大学,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.4825 x2=2.9773 2.0289 1.0041 d =0.5305 x3 =3.0098
8、1.9968 0.9959 d =0.0465 x4 =2.9998 1.9997 1.0002 d =0.0112 x5 =2.9998 2.0001 1.0001 d =3.9735e-004 x6 =3.0000 2.0000 1.0000 d =1.9555e-004 x7 =3.0000 2.0000 1.0000 d =1.1576e-005,从例6和例7可以看出,Gauss-Seidel迭代法的收敛速度比Jacobi迭代法要高.高斯-赛得尔迭代法与雅可比迭代法都具有算式简单、易在计算机上实现等优点,且每迭代依次一次秩只需计算一次矩阵与向量的乘法.且前者比后者需要的存储单元要少.对
9、于给定的矩阵线性方程组,用两种求解时,可能都收敛,也可能一个收敛另一个不收敛.在都收敛的情况下,有时前者收敛快,有时后者收敛快.二者统称为简单迭代法.,重庆邮电大学,35,二.解线性方程组的超松弛迭代法,逐次超松弛迭代法(Successive Over Relaxation Method),简称SOR方法是GS迭代法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一，它有着广泛的应用。,其中 为可选择的松弛因子。于是可得迭代矩阵,重庆邮电大学,36,于是得到解 的逐次超松弛迭代公式：,（6.11）,其中,超松弛迭代法（SOR）的分量形式：,设已知第k次近似 及第 次近似的分量 ,首先用GS迭
10、代法计算一个辅助量,（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有唯
11、一解.由定理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(
12、B)1;且当p(B)1时,迭代矩阵谱半径越小,收敛速度越快.,重庆邮电大学,44,例8 试考察用Jacobi方法,GS迭代法解下面方程组的收敛,解 由于,为严格对角占优阵，于是由定理6可知解方程组,Ax=b的Jacobi迭代法，GS迭代法均收敛。,重庆邮电大学,45,7.7 病态方程组和迭代法改善法,判断一个计算方法的好坏,可用算法的稳定性、解的精确程度以及计算量、存储量的大小等来衡量。然而，同一方法用于不同问题，效果却可以相差很远，这就涉及到问题本身的状态。,本节在分析方程组的初始数据A、b的小扰动（误差）对解的影响的基上，给出方程组“病态”、”良态“的概念及其衡量标准，并介绍判断近似解可靠
13、性以及提高计算结果精度的方法。,重庆邮电大学,46,引例 设有方程组,其解为,此例说明,方程组常数项分量只有微小变化(1/100),而方程组的解有较大的变化.也就是说这个方程组的解对于问题的数据b很灵敏.这样的方程组就是病态方程组。,重庆邮电大学,47,定义.,7.7.1 病态方程组及误差分析简介,即有,-(15),重庆邮电大学,48,-(16),-(17),-(18),所以,又因为,可得,(16)和(17)两式相乘,得,重庆邮电大学,49,(18)式表明,由常数项产生的误差,最多可将解的 相对误差放大 倍,所以,重庆邮电大学,50,定义7.,-(20),-(19),重庆邮电大学,51,显然,
14、即任意方阵的条件数必不小于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).,本章作业,