数值分析期末试卷2006-2011及课件信二学生会学习部

1、1课程内容第一章 数值计算中的误差第二章 方程（组）的迭代解法第三章 解线性方程组的直接解法第四章 解线性方程组的迭代法第五章 插值法第六章 数值积分与数值微分第三章 解线性方程组的直接法关于线性方程组3简记为AX=B，其中这里假定|A|0，方程组的解唯一。根据系数矩阵A分类：低阶稠密矩阵方程组大型稀疏矩阵方程组求解线性方程组的数值方法：直接法在不考虑舍入误差的情况下，经过有限步运算后能求得方程组准确解。2. 迭代法用某种极限过程去逐步逼近线性方程组精确解。4低阶稠密矩阵方程组大型稀疏矩阵方程组关于线性方程组本章内容1 消元法2 选主元的高斯消元法3 关于结果精度的检验561 消 元 法71.

2、1 方法的一般描述1.2 高斯消元法1.3 克劳特消元法1.4 平方根法1.5 追赶法1.6 消元法的应用条件1 消元法思路: 通过组合方程的方法实现逐步消元，达到将原方程简化为三角形方程组，然后用回代法解三角形方程组即可获得原方程组的解。8u11x1+u12x2+u1nxn=z1 u22x2+u2nxn=z2 . (2) unnxn=zn消元x1=x2=xn=回代1 消元法 1.1 方法的一般描述例：用消元法解方程组9消去(2) (3)式中的x1项：(2)- (1):0+(4-1) x2+(-1-1)x3=6-6(3)-2(1):0+(-4-21)x2+(1-21)x3=-3-263x2-2

3、x3=0 (4)-6x2-x3=-15 (5)消去(5) 式中的x2项：(5)+2(4): 0+(-1-22)x3=-15-2 01 消元法 1.1 方法的一般描述 举例-5x3=-15 (6)10 x1+x2 +x3 =6 (1) 3x2-2x3=0 (4) -5x3=-15 (6)x1=1x2=2x3=3得到以下方程组消元回代1 消元法 1.1 方法的一般描述 举例11用l11除(1)式得u11u12u13z1消去(2)式中x1l21(2)-l21(4)0+(a22-l21u12) x2+(a23-l21u13)x3 =b2-l21z11 消元法 1.1 方法的一般描述 1.1.1 消元计

4、算过程120+(a22-l21u12) x2+(a23-l21u13)x3 =b2-l21z1 (5)0+(a32-l31u12) x2+(a33-l31u13)x3=b3-l31z1 (6)a22(1)a23(1)用l22除(5)u22u23z2消去(6)中x2消去(2)(3)式中的x1a32(1)a33(1)b2 (1)b3 (1)1 消元法 1.1 方法的一般描述 1.1.1 消元计算过程130+(a33(1)-l32u23)x3 =b3(1)-l32z2 (8)a33(2)消去(3)式中的x2b3 (2)用l33除(8)u33z3u22u23z21 消元法 1.1 方法的一般描述 1.

5、1.1 消元计算过程u11u12u13z114以上的计算过程称为消元过程。1 消元法 1.1 方法的一般描述 1.1.2 消元过程的计算公式l33(择定)l11(择定)l22(择定)15u11x1+u12x2+u13x3=z1 u22x2+u23x3=z2 (10) u33x3=z3简记为UX=Z，其中消元后得：1 消元法 1.1 方法的一般描述 1.1.2 消元过程的计算公式16简记为LZ=B，其中z由下列公式确定：1 消元法 1.1 方法的一般描述 1.1.2 消元过程的计算公式17u11x1+u12x2+u13x3=z1 u22x2+u23x3=z2 u33x3=z3由LZ=B、 UX=

6、Z，得LUX=B与AX=B比较知 A=LUL为下三角矩阵，U为上三角矩阵1 消元法 1.1 方法的一般描述 1.1.2 消元过程的计算公式将A分解为LU逐次求出x3、x2、x1，称为回代过程。18u11x1+u12x2+u13x3=z1 u22x2+u23x3=z2 u33x3=z31 消元法 1.1 方法的一般描述 1.1.3 回代计算过程消元法计算公式19lii选值的不同会影响到计算量及舍入误差的大小20高斯消元法：lii =1克劳特消元法l11= a11(0)= a11 , l22= a22(1) , l33= a33(2), lnn= ann(n-1)uii =1平方根法(系数矩阵为对

7、称矩阵)lii= uiilij= uji 消元法计算公式211.1 方法的一般描述1.2 高斯消元法1.3 克劳特消元法1.4 平方根法1.5 追赶法1.6 消元法的应用条件1 消元法取lii =1(i=1,2,n)221 消元法 1.2 高斯消元法消元和回代运算复杂度：乘除次数： 加减次数：例3.1用高斯消元法解右面线性方程组解：按高斯消元法的计算公式计算如下：23-23x1 + 11x2 + x3 =0 2.26086x2 -1.52174x3=3 1.01924x3=1.01921x1 =0.99999x2=1.99999x3=0.999971 消元法 1.2 高斯消元法u11=-23u

8、22=-3-(-0.47826)11=2.26086u13=1z1=0u12=11u23=-2-(-0.47826)1=-1.52174z2=3- (-0.47826)0 =3U33=2-(-0.04348)1-(-0.67307)(-1.52174)=1.01924z3=-1- (-0.04348)0-(-0.67307)3 =1.01921-23111011-3-231-22-1241.1 方法的一般描述1.2 高斯消元法1.3 克劳特消元法1.4 平方根法1.5 追赶法1.6 消元法的应用条件1 消元法l11= a11(0)= a11 , l22= a22(1) , l33= a33(2

9、), lnn= ann(n-1)251 消元法 1.3克劳特消元法26例3.2用克劳特消元法求解。解：按克劳特消元法的计算公式计算如下：x1 + 1.5x2 +2x3 = 3 x2 - 8x3 = -8 x3 = 2x1 =3-1.5*8-2*2=-13x2=-8+8*2=8x3=21 消元法 1.3克劳特消元法u11=1l11=2u22=1l22=5-31.5=0.5u13=4/2=2z1=6/2=3u12=3/2=1.5u23=(2-32)/0.5=-8z2=(5-33)/0.5 =-8u33=1L33=30-42-(-3)(-8)=-2z3=(32-43-(-3)(-8)/(-2) =2

10、l21=3l31=4l32=3-41.5=-323463525433032271.1 方法的一般描述1.2 高斯消元法1.3 克劳特消元法1.4 平方根法1.5 追赶法1.6 消元法的应用条件1 消元法28l33= u33l11= u11l22= u221 消元法 1.4 平方根法适合对称的系数矩阵 取lii= uii(i=1,2,n)291 消元法 1.4 平方根法30计算公式：1 消元法 1.4 平方根法31例3.3 用平方根法求解x1 + 0.42x2 + 0.54x3 =0.3 0.90752x2 +0.10270 x3 =0.41211 0.83537x3 =0.59336x1 =-

11、0.24052x2=0.37372x3=0.710301 消元法 1.4 平方根法10.30.4210.50.540.3210.7321.1 方法的一般描述1.2 高斯消元法1.3 克劳特消元法1.4 平方根法1.5 追赶法1.6 消元法的应用条件1 消元法33l11=b1 u12=c1/l11 0 0.0l21=a2 l22=b2-a2u12 u23=c2/l22 0.00 l32=a3 l33=b3-a3u23 u34=c3/l33 0.0三对角方程组用克劳特消元法求解 00 ln-1n-2=an-1 ln-1 n-1=bn-1-an-1un-2 n-1 un-1 n=cn-1/ln-1

12、n-1 00 0 ln n-1=an lnn= bn- anun-1 n 1 消元法 1.5追赶法34(1) li i-1=ai (i=2,3,n) li i=bi ai ui-1 i (i=1,2, ,n) a1=0, u01 =0 ui i+1 = ci/ li i (i=1,2, ,n-1) 1 消元法 1.5追赶法(2)zi (i=1,2, ,n)(3)xi (i=n,n-1, ,2,1)351 消元法 1.5追赶法解：按公式计算结果如下：36例3.4 用追赶法求解x1 - 0.5x2 =1 x2 -0.66667x3 =0 x3 =3.00001x1 =2.00001x2=2.000

13、02x3=3.000011 消元法 1.5追赶法-2-21-2111-2-41371.1 方法的一般描述1.2 高斯消元法1.3 克劳特消元法1.4 平方根法1.5 追赶法1.6 消元法的应用条件1 消元法381 消元法 1. 6 消元法的应用条件定理3.1: A的各阶主子式均不为0，即|A1| =|a11|0,|An|=|A| 0,是消元法中lii 0,uii 0的充要条件。391 消元法 1. 6 消元法的应用条件40证明：因为A=LU1 消元法 1. 6 消元法的应用条件41|A1| =l11.u11 0 ,所以l110, u1101 消元法 1. 6 消元法的应用条件|A2| =l11

14、.u11. l22.u22 = |A1|. l22.u22 0 ,所以l220, u220|Ai| =l11.u11 .l22.u22 lii.uii = |Ai-1|. lii.uii 0 ,所以lii0, uii0|An| =l11.u11 .l22.u22 lnn.unn = |An-1|. lnn.unn 0 , lnn0, unn042定理3.2 若A为实对称正定矩阵，则 lii0，uii0 (i=1,2, ,n)证明：因实对称矩阵为正定的必要且充分条件是其所有的主子式都大于零，即|A1|0,|A2|0,|An|0显然满足定理3.1中|Ai|0的条件，因此定理3.2得证。1 消元法

15、1. 6 消元法的应用条件A为实对称正定矩阵，如果采用平方根法进行求解，则必有lii20 (i=1,2, ,n)，这是因为43不必进行复数计算。1 消元法 1. 6 消元法的应用条件阿达马定理 r阶主子式|Ar|0的一个充分条件是下述严格对角占优条件成立。441 消元法 1. 6 消元法的应用条件证明：用反证法，假设|Ar|=0，则线性方程组ArX=0有非零解x1, x2, xr。45此结论与条件矛盾，故假设|Ar|=0不对，定理得证。设xk=max(|x1|, |x2|, |xr|)在第k个方程中， xk处于对角线位置上。这时有如下等式与不等式成立：1 消元法 1. 6 消元法的应用条件46

16、证明：严格对角占优矩阵:对角线上元素的绝对值大于同行上其余元素绝对值之和的矩阵，即A的各阶主子矩阵A1、A2An均是严格对角占优矩阵根据阿达马定理，其各阶主子式均不等于零，按定理3.1知lii0,uii0 (i=1,2, ,n)。定理3.3 若A为严格对角占优矩阵，则lii0,uii0 (i=1, 2,n)1 消元法 1. 6 消元法的应用条件47本章内容1 消元法2 选主元的高斯消元法3 关于结果精度的检验482 主元素法消元法缺点线性方程组解唯一只需要|A|0消元法：消元过程中分母不能为零lij=分子/ujj，uij=分子/lii，zi=分子/lii，xi=分子/uii定理3.1(消元法应

17、用条件)要求各阶主子式均不为0。误差可能很大492 主元素法例如 50高斯消元法求解，取五位有效数字。2 主元素法51消去第二个方程中的x12 主元素法采用交换的方法使u110。52 x3 =1 (1) x1 x2 + x3 =2 (2)2x1 + x2 + 2x3=3 (3) x1 x2 + x3 =2 (1) x3 =1 (2)2x1 + x2 + 2x3=3 (3)(2)和(1) 交换 2x1 + x2 +2x3=3 (1) x1 x2 + x3 =2 (2) x3 =1 (3)(3)和(1) 交换这时u11=0，l21=1/0，l31=2/0u11=1，l21=0/1，l31=2/1u

18、11=2，l21=1/2，l31=0/2结论如果lij的算式中分母较小(1,用它做乘数会使被乘方程中的误差扩大回代过程中用较大数值的uii为分母可减少除法的舍入误差2 主元素法53交换原则：使在对角线位置上获得绝对值尽可能大的系数uij，称这样的uij为主元素，并称使用主元素的消元法为主元素法根据主元素选取范围分为：列主元素法全主元素法2 主元素法542.1 列主元素法2.2 全主元素法2主元素法列主元素法就是在待消元的所在列中选取主元例3.5 用列主元素法解下列方程组55 10 x1 - 19x2 - 2x3=3 (1)-20 x1 +40 x2 + x3 =4 (2) x1 + 4x2 +

19、 5x3=5 (3)解：2 主元素法 2.1 列主元素法-0.51-1.55-0.0565.055.20.16667-2.341684.13332消元后的方程-20 x1 +40 x2 + x3 =4 (4) 6x2 + 5.05x3=5.2 (9) -2.34168x3=4.13332 (11)进行回代x3 =-1.76511x2=2.35230 x1=4.41634562.1 列主元素法2.2 全主元素法2主元素法在全体待选系数中选取主元素，是全主元素法。例3.6 用全主元素法解下列线性方程组57 10 x1 - 19x2 - 2x3=3 (1)-20 x1 +40 x2 + x3 =4

20、(2) x1 + 4x2 + 5x3=5 (3)解：2 主元素法 2.2 全主元素法-0.4750. 5-1.5254.90.134.94.6-0.311221.433666.33161213231消元后的方程5840 x2 + x3 20 x1 =4 4.9x3 + 3x1=4.6 1.43366x1=6. 33161进行回代x1=4.41634 x3 =-1.76511x2=2.352302 主元素法 2.2 全主元素法59全主元素法与列主元素法比较全主元素法精度高：在全体元素中选择主元。对控制舍入误差十分有效计算时间长：需要同时作行列的互换，程序复杂列主元素法精度稍低于全主元素法计算简单

21、，工作量大大减少结论列主元素法是求解中小型稠密线性方程组的最好方法之一2主元素法60本章作业3.1 3.2 3.4 3.6 3.7 611 消元法 1.2 高斯消元法Bool Guass(int n,double aMAXMINE,double b)if(对角元为0，分解失败） return false； for(j=1;jn;j+) lji=aji/u00; for(i=1;in;i+) if(对角元为0，分解失败） return false； if(对角元uii为0，分解失败） return false；求解Ly=b;求解Ux=y;return true;Bool Guass(int n,double aMAXMINEint i,j,k; double sum;if(IS_ZERO(a00) return false; for(i=1,in,i+) ai0/=a00for(i=1,in,i+) if(IS_ZERO(aii