数值分析期末考试复习提纲13级

1、一、绝对误差一、绝对误差(限限)和相对误差和相对误差(限限)、有效数字位数、有效数字位数例1.,28718. 2,82281718. 2*reee和相对误差限的绝对误差限求其近似值为已知解:eeE*绝对误差82001000. 082001000. 0|E002000. 061026102|*er28718. 2102628718. 2102661071. 0绝对误差限:相对误差限:knaaax10. 021*|xx0.5 10kn因此,可根据上述分析对有效数字有如下结果:01a定义：定义：设设x*是是x的一个近似数，可表示为的一个近似数，可表示为k为整数为整数, ,如果如果则称则称x*为为x的

2、具有的具有n位有效数字的近似值位有效数字的近似值. .有效数字例4*.:1000效数字位数的下面两个近似值的有判断 x9 .999*1x1 .1000*2x30.9999 1040.10001 10*11| |xx1 . 03 30.5 10*22| |xx1 . 04 40.5 10位有效数字有所以3*1x位有效数字却有而4*2xk0.510k-n (n为有效数字个数)例2.求下列四舍五入近似值的有效数字个数.218.0*1x18002.0*2x180.2*3x0.218*4x2*51018.2x6*51000218.0 x3个3个4个4个3个5个 注：注：四舍五入的近似值其有效数字位数等于

3、左起第一位四舍五入的近似值其有效数字位数等于左起第一位非零数字到末位数字的位数。非零数字到末位数字的位数。叙述误差的种类与来源P2 ，避免误差危害的原则P10。其它其它：例例 3.3少取几位有效数字？，应至的相对误差不超过要使%1 . 020 解解:.*.位位有有效效数数字字有有的的近近似似值值设设的的首首位位数数是是nxa204201 11|*|1|100.1%| *|2nrxxxa则由定理则由定理3.3,相对误差满足相对误差满足001. 0104211n097. 3n即应取即应取4位有效数字位有效数字,近似值的近似值的相对相对误差不超过误差不超过0.1%.相关习题相关习题 P21:4Tnn

4、nxxxxCR),(,)(21设中在向量空间的的范范数数有有常常用用的的向向量量 x21222212)xxx(xn 范数或欧氏范数的 2x1xnxxx21范数的1xxinix1max范数或最大范数的x-(1)-(2)-(3)pxppnppxxx121)(-(4)1,ppx范数的求下列向量的各种常用范数求下列向量的各种常用范数Tx)1,3 ,4 , 1(:1x421xxx92x21242221)(xxx3327 xiix41max4常用的矩阵范数常用的矩阵范数1(1)Aniijnja11max,大值的每列绝对值之和的最A的列范数称A A(2)njijnia11max,大值的每行绝对值之和的最A的

5、行范数称A2(3)A)(maxAAT大大值值的的特特征征值值的的绝绝对对值值的的最最为为其其中中AA)AA(TTmax范范数数的的称称 2A-(5)-(6)-(7)21112)4(ninjijFaA1，2掌握；3，4了解110121021A求矩阵求矩阵A A的各种常用范数的各种常用范数1Aniijnja11max25234252 ,5 ,2max1njAnjijnia11max42 ,4 ,3max1ni2A)(maxAAT由于由于的特征值因此先求AATAAT110121021110122011211190102特征方程为特征方程为)det(AAIT2111901020的特征值为可得AAT93

6、61. 0,9211. 2,1428. 93211428. 9)(maxAAT2A)(maxAAT0237. 3FA2926056. 3参考参考P18例例1.4.1Ca,b上的三种常用范数：1范数 badxxff| )(|12范数 2122)(badxxff | )(|maxxffbxa范数 1( ),2f xx( )0,1f xC( )1x,f1f2f12f11121100211112224fxdxxdxxdx21201122 3fxdx例：例：设函数，权函数试计算和解解 此外：课本p21：12(1)(2),13,15(1)(3),18且满足上连续在设迭代函数,)(bax;)(,)1(bxa

7、bax时当有且满足存在一正数,10,)2(baxLLLx|)(|*,)(.1xbaxxo内有唯一解在方程则*)(,.210 xxxbaxkko均收敛于迭代法对于任意初值11*.3kkkoxxLLxx011*.4xxLLxxkko方程方程 f(x)=0 化为迭代公式化为迭代公式 x=(x). 定定理理 设( )x在( )xx的根*x 附近连续，且有 ()1x 则迭代格式1()kkxx在根*x 附近具有局部收敛性。 由于在实际应用中根 x* 事先不知道，故条件 | (x* )| 1无法验证。但已知根的初值x0在根 x*邻域，又根据 (x)的连续性，则可采用 | (x0 )| 1 来代替| (x*

8、)| 1，判断迭代的收敛性。 定理指出，只要构造的迭代函数满足1|)(|Lx就收敛迭代法)(1kkxx，比不动点定理易用。例例： 迭代过程)5(21kkkxcxx， 当局部收敛到5时，确定c的值。 解：迭代函数 )5()(2xcxx，cxx21)(，当局部收敛到5*x时，1521)5(c， 15211c，有051c。 定理. 附近满足：在根如果迭代法迭代函数*)(xx阶导数且连续；存在px)() 1 (,0*)()1(xp *)(*)()2(xx0*)()(xp而收敛阶的。的邻近是在则迭代法pxxxkk*1)()(211kkkxcxx),(21)(xcxx例例：迭代过程3，当至少平方收敛到时，

9、确定c的值。解：迭代函数),1 (21)(2xcx至少平方收敛，当, 0)3(于是. 3, 0)31 (21)3(cc得牛顿牛顿(Newton)迭代法：迭代法：1()()kkkkf xxxfx0,1,k 说明：说明：若若 x*是是 f(x)=0的一个单根，即的一个单根，即 f (x*)=0, f(x*) 0 ,则则牛顿法在牛顿法在 x* 的邻近是平方收敛的的邻近是平方收敛的 。证明:令)()()(xfxfxx)(x则22)()()()(1xfxfxfxf 2)()()(xfxfxf 0)(* x所以该迭代法恰是平方收敛的.进一步计算，)()()(*xfxfx 必有0)(* x否则，得 这与x*

10、是单根矛盾.0)(* xf其它其它：熟悉：熟悉斯特芬森斯特芬森迭代法加速公式迭代法加速公式P32(2-3-2), 割线法割线法公式公式P40.例例 设函数23)()(axxf，写出解0)(xf的牛顿迭代格式，并证明此格式的收敛阶。 解解 将23)()(axxf，23)(6)( xaxxf，代入牛顿迭代法，有 223231665)(6)(kkkkkkkxaxxaxaxxx 迭代函数25( )66axxx ，35( )66axx，又已知3*ax ， 015 . 0)( 3a，所以该牛顿迭代法为线性收敛。 注：此题中x*并不是单根。例例 证明方程155xx在区间( 1,0)内有唯一的实根，并用牛顿迭

11、代法求这个根的近似值，使误差不超过0.01。 解 令5( )51f xxx，则( )f x在 1,0上连续，又 ( 1)50,(0)10ff 故由介值定理知至少存在一个*( 1,0)x 使*()0f x，又由 4( )550fxx，知( )f x在 1,0上单调增加，因而方程5510 xx在区间( 1,0)内有唯一实根。 下面用牛顿迭代法求这个根的近似值。 牛顿迭代法为 1()()kkkkf xxxfx，则它为平方收敛的， 取, 10 x则 1510.0555x ，2( 0.5)0.50.26( 0.5)fxf 3( 0.26)0.260.20( 0.26)fxf ，4( 0.20)0.200

12、.20( 0.20)fxf 所以*0.20 x 。 例 对方程xex-1=0 ，说明方程在0,1上有唯一根,并构造一 种收敛的求根迭代格式，说明收敛理由。取x0 =0.5，求 这个根的近似值。解：解：令f(x)=xex-1,由于f(0)=-10, f(0) f(1) 0，于是f(x)在(0,1)内至少有一根，又由于 ,f(x)在0,1上是单调函数，于是原方程在0,1上有唯一根,0)1 ()(xexfx)1 (11kxxkkkxeexxxkk构造牛顿迭代法 因为在根x*处,必有 ， x*为单根时,它具有二阶收10.57102044x 敛性.取x0=0.5 ,经计算可得0.567143x30.56

13、714329x 40.56714329x 20.567165569x 这是迭代18次得到的计算结果。.另：习题二作业另：习题二作业 2, 7(1)(3),该迭代法一定收敛，10| )(|* x紧凑格式分解A=LU：（掌握）1.先确定U中第一行元素（即等于A中第一行元素）. 2.再确定L中第一列元素： ).(1111111aaualiii即3.确定U中第r行元素:中元素。已算出的中元素对应乘上它上边它左边已算出的ULrjrjau4.再确定L中第r列元素:。中元素上方已算出的中元素对应乘上它左边已算出的rrrririruualUL三、解线性方程组的数值解法三、解线性方程组的数值解法0 0, ,d

14、de et t A A子子式式D D若若n n阶阶方方阵阵A A的的顺顺序序主主k kk k nk, 2 , 1且且唯唯一一. . .则则A A的的L LU U分分解解存存在在111213212223313233 2 1 21 4 3 1 , 1, 65 (2) 2 (1) 1 (2)uuuALlUuullu 1 1 2 (4) 2 (3) 1 (1) -3 (6) 3 (1) -2 (5) -7 1 2 1 2 2 1, 13LU -21 -3 -7用紧凑格式分解A=LU：例：判断下矩阵A能否分解为LU形式（其中L为单 位下三角阵，U为上三角阵）？若能，将其分解.(P88:4(3)46156

15、1552621A提示：验证A的所有顺序主子式都不等于零.用紧凑格式分解.1 0 03 1 06 2 11 3 60 1 20 0 101det, 015 22 1, 01321LUAAAAA解：例： 用多利特尔分解求解方程组（掌握）解 设 A=LU，即 123123123242 1 1326 1 3 2 .2251 2 2xxxxxxAxxx1112132122233132332 1 110 01 3 21 00,1 2 2100uuuluullu100211 0.5100 2.5 1.5 .0.5 0.6 1000.6LU解下三角方程组 Ly = b，即解上三角方程组 Ux= y，即Thus

16、 . Let , then .AxbLUxbUxyLyb11223310044 0.5106 4 0.5 0.6 150.6yyyyyy 132231211410 2.5 1.54 1000.60.61xxxxxx掌握高斯消去法解方程组：掌握高斯消去法解方程组：P49例例3.1.1，P87:1计算A条件数(P67)1( ) | | Cond AAAp 常用的条件数有：常用的条件数有：1( ) | Cond AAA1222( ) | Cond AAAp 条件数的性质（了解）：条件数的性质（了解）：(1) Cond(A) 1(2) Cond(cA) = Cond(A)，其中，其中 c 为非零常数为

17、非零常数(3) 当当 A 是正交矩阵时，是正交矩阵时，Cond2(A) = 1(4) Cond2(PA) = Cond2(AP)=Cond2(A)， 其中其中 P 为正交矩阵为正交矩阵重点重点1031)(ACond 例例:已知A=,则条件数 = 16 .解线性方程组的迭代法重点掌握重点掌握雅可比迭代，高斯雅可比迭代，高斯-赛德尔迭代。赛德尔迭代。 对线性方程组 作分解 bAx )(ULDULDAP72(1)1( )1()kkxDLU xD bk = 0, 1, 2, 雅可比 (Jacobi) 迭代格式迭代格式:1()JBDLU称为称为雅可比雅可比 (Jacobi) 迭代矩阵迭代矩阵(1)()(

18、)()11122133111(1)()()()22211233222(1)()()()1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xaxaxba xa xaxaxbaxaxaxaJacobi 迭代的分量形式：迭代的分量形式：初始向量：Tnxxxx),.,()0()0(2)0(1)0(q G-S 迭代格式迭代格式11(1)( )kkxDLUxDLb1(1)(1)( )11inkkkiiijjijjiijj ixba xa xa ULDBG1)(其中 为迭代矩阵。 q SOR 算法算法11(1)( )(1)kkxDLDU xDLb1(1)( )(1)( )1i

19、nkkkkiiiijjijjiijj ixxba xa xa（了解）设解线性方程组Ax=b的迭代格式fBxxkk)()1(定理2.迭代格式 收敛的充要条件为1)(BfBxxkk)()1(收敛为迭代矩阵的迭代法则以若) 1 (, 1BB 定理3因BB )(（1）（注：判断简单，但仅是充分而不必要）定理.法均收敛法和则阵或不可约弱对角占优矩为严格对角占优的系数矩阵若线性方程组SGJacobiAbAx,例：设方程组1231231238322041133631236xxxxxxxxx 分别写出 J 法和 G-S 法的迭代格式，并判别迭代的收敛性。 解解 方法 1：雅可比迭代 (1)( )( )123(

20、1)( )( )213(!)( )( )312322088841311116361112kkkkkkkkkxxxxxxxxx 迭代矩阵J=3208841011116301212 因为故雅可比迭代收敛。1129J(1)( )( )123(1)( )( )223(!)( )( )3223220888322322111127751768888kkkkkkkkkxxxxxxxxx 320883202211277017688G,故高斯-塞德尔迭代收敛。又，G-S迭代 (1)( )( )123(1)(1)( )213(!)(1)(1)312322088841311116361112kkkkkkkkkxxx

21、xxxxxx 将1式代入2式，1、2式代入3式，有(1)(2)(3)185G13208841011116301212JID A 1J 方法2：雅可比迭代矩阵因为故雅可比迭代收敛。1180032()114001126300GDLU3208832022112770176881G高斯-塞德尔迭代矩阵：故高斯-塞德尔迭代收敛。)(1ULDJ即方法3：系数矩阵12361114238 A1|,1,2,niiijjj iaainA的元素满足A为严格对角占优矩阵,故雅可比迭代和塞德尔迭代都收敛.其它：掌握作业P89：16, 17(1)注：若A的特征值为，则A-1的特征值为1/ ， Am的特征 值为m，I kA

22、的特征值为1 k .相关题：掌握相关题：掌握P90: 20题的第题的第1问问.四、插值法四、插值法1、Lagrange插值(1) 过两个节点x0 , x1的线性（一次）插值：01010110( ), ( ),xxxxlxl xxxxxL1(x) = l0(x) y0 + l1(x) y11101( )( )( )( )()()(1.3)2!fR xf xL xxxxx余项：(2)过3个互异插值点(xi, f (xi), i = 0,1,2，二次插值：02011210122021()()()()( ),( ).()()()()x xx xx xx xl xl xxxxxxxxx220011220

23、( )( ) ()( ) ()( ) ()( ) ()(1.4)iiiLxlx f xl x f xlx f xl x f x 二次Lagrange插值多项式为：1200102()()( ).()()xxxxlxxxxx22012( )( )( )( )()()()(1.5)3!fRxf xLxxxxxxx余项：0110111()()()()( )()()()(),1,2,(1.7)iiniiiiiinnjijjj ixxxxxxxxl xxxxxxxxxxxinxx00110( )( ) ()( ) ()( ) ()( ) ()(1.8)nnnniiiLxlx f xl x f xlx f

24、xl x f x(3)过n个互异插值点n 次Lagrange插值多项式：(1)01( )( )()()()(1.9)(1)!nnnfRxxxxxxxn插值余项：插值余项：注：注：3点插值和点插值和4点插值为重点。点插值为重点。例例1 ：已知插值点 (-2.00,17.00), (0.00,1.00), (1.00,2.00), (2.00,17.00), 求三次插值，并计算 f (0.6)。并写出截断误差表示式.解解 先计算4个节点上的基函数：1230010203()()()( )()()()(0)(1.00)(2.00)( 2.000)( 2.00 1.00)( 2.002.00)1(1)(

25、2),24xxxxxxlxxxxxxxxxxx xx 0231101213()()()1( )(2)(1)(2),()()()4xxxxxxl xxxxxxxxxx0132202123()()()1( )(2) (2),()()()3xxxxxxlxxx xxxxxxx 三次Lagrange插值多项式为： f (0.6) L3(0.6) = -0.472.0123303132()()()1( )(2) (1).()()()8xxxxxxlxxx xxxxxxx3171( )(1)(2)(2)(1)(2)244217(2) (2)(2) (1).38L xx xxxxxxx xxx x ) 2

26、, 2(, | )(|0364. 0| )6 . 0)(6 . 0)(6 . 0)(6 . 0 ()!13 ()(| | ) 6 . 0 (|)4(3210) 13(3fxxxxfR误差：误差：例例 2 2： 设设 4)(xxf，用用拉拉格格朗朗日日余余项项定定理理写写出出以以1,0,1,3为为节节点点的的三三次次插插值值多多项项式式。 解解 (1)( )4!( )( )( )( )(1)(0)(1)(3)(1)!4!nfR xf xP xxxxxxn 443( )(1)(1)(3)()(3)P xxx xxxxxx x 三三次次插插值值多多项项式式32( )33P xxxx 练习：已知函数y

27、=f(x)的数值如右x0 1 2 5 y-1 1 7 17求y=f(x)的三次Lagrange插值多项式并写出截断误差表示式。此题显然可以用上述例题此题显然可以用上述例题1方法求解方法求解2、 Newton插值插值函数f的一阶差商：ijijjixxxfxfxxf )()(,二阶差商：ikjikjkjixxxxfxxfxxxf ,例如 设则 9)4(, 5)2(, 1)0( fff2)02()0()2(2 , 0 fff2)24()2()4(4 , 2 fff0)04()2 , 04 , 2(4 , 2 , 0 fff函数f的k阶差商： 2,4,50,2,40,2,4,550fff例如01011

28、10,.,.,.,xxxxxfxxxfxxxfkkkkk（2） 差商具有差商具有对称性对称性：任意改变节点的次序差商值不：任意改变节点的次序差商值不变。例如变。例如 f0,2,4 = f2,0,4 = f4,2,0等等。 (3) 差商和导数差商和导数 若若 f(x) 在在a,b 上存在上存在n 阶导数，且节点阶导数，且节点xi a,b,由余项由余项表达式可得，表达式可得，n 阶差商与导数有如下关系阶差商与导数有如下关系( )010( ) , , , ( , ) !nnnff x xxx xn 差商的性质 性质(1) k 阶差商 f x0, x1, xk可表成节点上函数值 f(x0), f(x1

29、), , f(xk) 的线性组合，即 0101101,().()()()()kkiiiiiiikif xxxf xxxxxxxxx)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四阶差商三阶差商二阶差商一阶差商差商的计算方法(表格法):,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf差商表经计算得 (xi, f(xi): (0, -1), (1, 1), (2, 7), (3, 17)。差商表如下 3 17x3 2 7 2 10 x2 1 1 2

30、 6 0 x1 0 -1 2x0 xi f (xi) f xi 1, xi f xi 2, xi 1, xi f xi 3, xi 2, xi 1, xii解解 由表易知， f x0, x1 = f 0, 1 = 2 f x0, x1, x2 = f 0, 1, 2 =6 2 )/2-0 = 2 f x0, x1, x2, x3 = f 0, 1, 2, 3 =(2 2)/3 0 ) = 0例例5 设f(x)=2x2-1,求差商 f 0,1,2,3= 0 . 可用性质可用性质3 3 由差商与导数的关系（由差商与导数的关系（性质性质3）例例6 对 f (x) = x7x4+3x+1， 求 f 2

31、0,21， f x,20,21,26 和 f x,20,21,27。解解 显然， f (7) (x) = 7!, f (8) (x) = 0, 由性质3得(7)016( ) ,2 ,2 ,2 1,7!ff x(8)017( ) ,2 ,2 ,2 0.8!ff x01(1)(2)4 1192 ,2 115,1 21fff00010101201101( )()() ,()() ,()()() ,nnnNxf xxxf xxxxxxf xx xxxxxxxf xxx0101010( )()()() , ,().nnnnniiRxxxxxxxf x xxxf x xxxxxn次次Newton插值公式：

32、插值公式：插值余项为：的近似值。插值公式求用例题数值表如下：已知例)596. 0( 02652. 188811. 069675. 057815. 041075. 0)(90. 080. 065. 055. 040. 0)432()( . fNewtonxfxPxfkk：先造差商表：先造差商表 )iixfx( (.) (.) (.) 4ffff的 阶差商).)(.)(.)(.).)(.)(.).)(.).(.)(8006505504000.034( 6505504000.197( 5504000.2800( 400116014107504 xxxxxxxxxxxN 由由Newton公式得四次插值

33、多项式为：公式得四次插值多项式为：) 9 . 0 , 4 . 0 (|,)( )()()()!14 ()(| | )(|43210) 14(4xxxxxxxxxxfxR6319205960596059604.).().(. Nfx代入得：代入得：将将练习练习：函数值表如下，求不超过三次的Newton插值多项式. x0 1 2 3f(x) -1 1 7 17差商表见例5. 误差：P123作业：1，7，8举例：验证多项式： 在 上带权 (x) = 1两两正交。解： 容易验证 而31, 12xx 1, 11101 xdx1120311dxx11113203131dxxxdxxx11201 dx112

34、0dxx1122031dxx由定义知结论成立。明确函数内积 概念，正交多项式概念. P126)(),(xgxf五、函数逼近与曲线拟合函数逼近与曲线拟合 )(),()(),()(),()()()()()()()()()(1010,1,0, 11, 10, 1,01,00,0 xxfxxfxxfaaannnnnnnn 先求法方程 即如下形式：njkkjkfa0),(),(的最佳平方逼近多项式上关于在求,.,)(10na,bxf具体解法（重点）记为 nddd10解出a0 , a1 , an ,则f(x)的最佳平方逼近多项式为：bannnndadadadxxfxfxsxfxfxaaaxs.)()(),

35、()(),()(,.)(11002*221100*平方误差为：作业P153：5(1)，6, 21* （掌握）1021011002220026.0609.0426.0147.1934.0)1 ()()(dxxdadadxxfx平方误差为：( 见P68例6)定定义义 0( )d()nbkkakR ffxxA fx 为求积公式 0( )d()nbkkakf xxA f x 的余项（或截断误差） 。 定定 义义 对 于 一 个 不 超 过m次 的 多 项 式 ， 求 积 公 式0( )d()nbkkakf xxA f x准确成立，即0R f，而对于m+1 次的多项式求积公式0( )d()nbkkakf

36、 xxA f x不能准确成立，则称该求积公式具有m次的代数精度。 1. 代数精度代数精度六、数值微分和数值积分六、数值微分和数值积分1 在a,b上选节点kx。 2 求()kf x和 （1） 利用( )dbkkaAlxx，或 （2） 解关于kA的线性方程组 求出kA，得到 0( )()nbkkakf x dxA f x 3 用1( ),nf xx，验证精度。 2.2.构造插值求积公式的步骤构造插值求积公式的步骤0( )d()nbkkakf xxA f x 定理定理 n+1个节点的求积公式至少具有 n次代数精度的充要条件是该公式是插值求积公式。例例 对30( )df xx，构造一个至少有 3 次代

37、数精度的求积公式。 解 4 个节点至少有 3 次代数精度，在0,3上选 0，1，2，3。 求kA（1）利用( )dbkkaAlxx，有 330000(1)(2)(3)3( )dd(0 1)(02)(03)8xxxAlxxx，12393,88AAA （2）解关于kA的线性方程组，将23( )1, ,f xx xx代入 01233AAAA，123239/ 2AAA，123499AAA，12382781/ 4AAA，解之038A ，123993,888AAA 30( )d(3/8)(0)3 (1)3 (2)(3)f xxffff 3030)()(kkkxfAdxxf4( ),f xx340d48.6xx 4444