数值分析复习

1、ReviewChap 1 数值计算中的误差数值计算中的误差 误差误差 误差限误差限 有效数字有效数字 用微分计算函数值误差用微分计算函数值误差 计算方法的数值稳定性计算方法的数值稳定性误差误差 误差限误差限 有效数字有效数字1) 定义 1.1：称 为 的绝对误差(简称误差)。( )e xxxxx设 是准确值， 是 的近似值xx2) 定义 1.2：若 ，则称 是 x 的误差限。|xx称单位量上的误差 为 x 的相对误差。( )rxxe xx3) 定义 1.3： 定义 1.4：r 若 , 则称 是 x 的相对误差限。|( )|rre x4) 定义 1.5： 如果近似值 x 的误差限是它的某一位的半

2、个单位，就称它准确到这一位。若该位到 x 左边第一位非零数字共有n 位，则称它有n 位有效数字。5)例1.5 题1.1 用微分计算函数值误差用微分计算函数值误差( )( )re yeyy相对误差( )( )( )fxe xf x( )( )( )rfxxexf x( )()( )( ) ( )e yf xf xfx e x误差例1.9 ()yf x已知 的近似值 x ，一元函数值 的近似值为x( )yf x1)2) 已知自变量误差( ),( ), ( )re x ex e y和( ).re y求二元函数值u = f (x,y)( )( ).re ue u的误差 和( )( )( )uue ud

3、ue xe yxy( )( )( )( )rrre uu xu yeuexeyux uy u例1.10 ,例1.11 3) 和、差、积、商的误差()( )( )e xye xe y()( )( )rrrxye xye xe yxyxy()( )( )( )( )rrrrrre xye xe yxee xe yy2()( )( )1( )( )e xyye xxe yxxee xe yyyy例1.10 , 例1.11, 题1.5 计算方法的数值稳定性计算方法的数值稳定性1) 求根公式的数值稳定性2) 递推法的数值稳定性数值计算中应注意的几个原则数值计算中应注意的几个原则避免相近数相减 ;避免小除

4、数, 大乘数 ;避免大数吃小数 ;采用数值稳定的算法 ;减少运算次数.题1.9, 题1.10 题1.7 Chap 2 插值法与最小二乘法插值法与最小二乘法 多项式插值多项式插值 Lagrange Lagrange插值公式插值公式 插值余项插值余项 Newton Newton插值公式插值公式 Hermite Hermite插值插值 分段插值分段插值 三次样条函数三次样条函数n 次多项式插值问题：次多项式插值问题：() (0,1, )iiyf xin求作一个次数不超过 n 的多项式 ，使之满足( )nP x()(0,1, )(2.1)niiP xyin插值条件f (x)的满足插值条件(2.1)的n

5、次插值多项式插值区间插值节点( )f x已知 上的函数 在点 , a b01naxxxb上的函数值被插值函数Lagrange插值公式插值公式 插值余项插值余项010111(),( )yPyxP x求作一个1次已知函数 在点 上的函数值 ， 01,xx01,yy( )f x101( )P xaa x多项式 ，使得1) 线性插值0110101011001( )( )( )xxxxP xyyyxyxxxxxll2) 抛物插值001212222(),( ),()PPPxyxyxy已知函数 在点 上的函数值 ，求作 012,xxx012,yyy( )f x2( )P x一个2次多项式 ，使得001221

6、20120102101201102 22021( )( )( )( )xxxxxxxxxxxxP xyyyxxxxxxxxlllxxxxyxyxyx3) n 次Lagrange插值0( )( )nnk kkP xy lx满足(),0,1,2,knkPkxyn0,( )njkjjkkjxxlxxxn 次Lagrange插值基函数 的性质:( )klx()(0,1,2, )kjkjlxjn 是 n 次式;( )klx0( )1nkklx题2.1 题2.2 4) Lagrange插值余项 定理2.2 ：设 的 n+1阶导数 在 上存在，则 , (0,1, ),( )ixa binf x(1)( )(

7、 )( ) , (1)!nnfR xw xxa bn (1)( )nfx , a b0( )(), , nkkw xxxa bx其中 与 有关 。1010111, ( )( )()(), , 2nR xfxxxxx x当时20120212, ( )( )()()(), , 6nR xfxxxxxxx x当时 例2.4, 题2.5 Newton插值公式插值公式1) 差商、差商的计算例2.5 2) Newton插值公式0010012012101010011010( )(),(),()(),(),()( ),()nnnnjnjjjnnnjjP xf xf x xxxf x x xxxxxf xxxx

8、f x xxxxPxf x xxxx误差010( )( ), ()nnnjjf xP xf xxxxxx例2.7, 例2.8题2.6, 题2.7 差商与微商的关系( )01( ),!nnff x xxnHermite插值插值3次Hermite插值300110011( )( )( )( )( )P xx yx yx yx y3次Hermite插值基函数 (插值基函数的性质) 22012201112,32,1,1tttttttt tttt插值余项33(4)220101 ( )( )( )( ) () () , , 4!Rxf xP xfxxxxxx x 例2.9, 题2.8, 题2.10 混合型H

9、ermite插值分段插值分段插值1) 分段线性插值2) 分段3次Hermite插值( 如何确定其解析式, 光滑性, 误差估计? )题2.11, 题2.12 3次样条函数次样条函数1) 什么是3次样条函数, 3次样条插值2) 比较3次多项式插值(不含导数条件), 分段3次Hermite插值, 3次样条插值Chap 3 数值积分与数值微分数值积分与数值微分 机械求积公式机械求积公式 插值型求积公式插值型求积公式 复合求积公式复合求积公式 Gauss Gauss求积公式求积公式 数值微分数值微分机械求积公式机械求积公式0( )()nbkkakf x dxA f x求积节点求积系数例3.1, 题3.1

10、, 题3.2 代数精度: 若一个机械求积公式对准确成立,但对1( )mf xx不准确成立, 就说它具( ),(0,1,)jf xxjm有m次代数精度.利用代数精度定义构造求积公式题3.11插值型求积公式插值型求积公式0( )()( )nbbkkaakf x dxf xlx dx1) 求积系数( ).bkkaAlx dx2) 求积系数具有 n+1个求积节点的插值型求积公式至少具 有 n 次代数精度.3) 中矩形公式、梯形公式、Simpson公式是插值型求积公式 (各自的代数精度).4) Newton-Cotes公式: 一类节点等距分布的插值型求积公式.( n为奇数时, 代数精度为n; n为偶数时

11、, 代数精度为n+1)梯形公式余项31()( ),12baITfa b1( )( ) ,2baTf af b12( )4( ) .6abbaSf aff b记Simpson公式余项5(4)1()( ),2880b aISfa b复合求积公式复合求积公式 (复合求积的思想)1) 复合梯形公式11( )( )2()( )2nbknakhf x dxf af xf bT复合梯形求积公式的余项为2( )( )12nhITfbfa 2) 复合Simpson公式121110( )( )2()4()( )6nnbknkakkhf x dxf af xf xf bS复合Simpson求积公式的余项为4(3)(

12、3)1( )( )1802nhISfbfa 题3.5, 题3.6Gauss求积公式求积公式1) 什么是Gauss求积公式?2) Gauss点的性质?1( )()nniiL xxx 定理定理3.4： 是Gauss点的充分必要条件是以 为零点 1nix的多项式 与所有次数不超过 n-1的多项式11( )0 (0,1,1).jnx Lx dxjn 1nix正交，即例3.7, 例3.8, 例3.9, 例3.10, 题3.9, 题3.10, 题3.11数值微分数值微分 在点 a 处以 h 为步长的向前差商 ()( )f ahf ah( )f x( )()f af ahh( )f x()()2f ahf

13、ahh 在点 a 处以 h 为步长的向后差商 ( )f x 在点 a 处以 2h 为步长的中心差商 例3.111) 中心差商公式2) Richardson外推例3.12Chap 4 方程求根方程求根 不动点迭代法不动点迭代法 Newton Newton迭代法迭代法 简化简化NewtonNewton迭代法迭代法 弦截法弦截法 NewtonNewton下山法下山法不动点迭代法不动点迭代法1)( )0( )f xxx( )0f x ( )xx求 的根等价于求 的不动点 2) 不动点迭代格式 1(),0,1,2,(4.5)kkxxk3) 迭代收敛条件 定理 4.1：设 是闭区间 上的压缩函数，则 在

14、中有唯一不动点 ，且对任意 , 迭 代公式(4.5)都收敛 . (全局收敛) , a b( )x , a b( )x*x0 , xa b 推论 ：设 ，且 1( ) , xC a b( ), , xLx ya b(0,1)L1) 总有 ; , xa b ( ) , xa b2) 存在 ，使则定理4.1结论成立 . (全局收敛) 定理 4.3：设 在其不动点 附近有连续一阶导数，且 则存在 的某个领域 ，( )x* :|xxx *|()| 1,x*x0 x*x使得 , 迭代(4.5)均收敛. (局部收敛)迭代不收敛的条件 题4.44) 迭代收敛速度记 , 若 ，且存在正常数 ，使*kkexx 定

15、义 4.3：1p 0ke 1lim(0)kpkkeCCe, 则称(4.5)为 p 阶收敛的.1p若 ，则称(4.5)是线性收敛的；若 , 则称(4.5)是平方收敛的.2p 定理 4.4：若 在 的根 邻近有连续的 1阶导数， 且 , 则当 时迭代公式(4.5)为线性收敛 . 若 在 邻近有连续的 2 阶导数，则当 时迭代公式(4.5)为平方收敛 .( )x*|()| 1x*x*()0 x( )xx( )x*x*()0,()0 xx例4.4, 例4.5, 例4.6, 题4.2, 题4.3, 题4.5Newton迭代迭代1()(0,1,2,)(4.11)()kkkkf xxxkfx( )0f x

16、求 近似根的Newton迭代公式:1kkxx1) 迭代控制条件2) 收敛性x()0fx单根，则当 时(4.11)平方收敛 .( )f xx 定理 4.5：设 在 邻近二次连续可微， 是 的( )0f x 3) Newton迭代与开方法例4.7, 题4.8例4.8, 题4.7简化简化Newton迭代法迭代法 弦截法弦截法 Newton下山法下山法10()(0,1,2,)()kkkf xxxkfx111()()()()kkkkkkkf xxxxxf xf x1()()kkkkf xxxfx1) 简化Newton迭代法2) 弦截法3) Newton下山法例4.9例4.10例4.11Chap 5 线性

17、代数方程组数值解法线性代数方程组数值解法 迭代法迭代法 迭代法的收敛性迭代法的收敛性 Gauss Gauss消去法消去法 矩阵的矩阵的LULU分解及应用分解及应用 方程组的条件数与误差分析方程组的条件数与误差分析迭代法迭代法111122133121122223323113223333a xa xa xba xa xa xba xa xa xb考虑线性方程组Jacobi迭代112233( )(1)(1)111221331( )(1)(1)122112332( )(1)(1)133113223kkkakkkakkkaxa xa xbxa xa xbxa xa xbGauss-Seidel迭代112

18、233( )(1)(1)111221331( )( )(1)122112332( )( )( )133113223kkkakkkakkkaxa xa xbxa xa xbxa xa xb考虑线性方程组 A x = b , 将 A 进行分解 A = D + L + U , ( )1(1)1(),1,2,kkxDL U xD bk Jacobi迭代的矩阵表示 :Gauss-Seidel迭代的矩阵表示 :( )1(1)1()(),1,2,kkxDLUxDLbk ( )1( )(1)1(),1,2,kkkxDLxUxD bk 或SOR迭代的矩阵表示 :()1(1)1()(1)()kkxDLDUxDLb

19、 定理：定理：SOR方法收敛的必要条件是 .02证明：假设SOR方法收敛，则有()1BB12,n 设 的特征值为 ，则12det()()1nnBB 而1()1BDLDUA =-L-UD1det()det()det(1)BDLDUnDD)1 ()1det(det11102det()1B迭代法的收敛性迭代法的收敛性AxbxGxd( )(1),0,1,2,(5.18)kkxGxdk迭代收敛基本定理：迭代收敛基本定理：对任意 和任意的初始向量 , 迭代公式(5.18)收敛的充要条件是 .()1GndR(0)nxR例5.6, 题5.3定理5.3 ：设G 是(5.18)的迭代矩阵，且它的某一种范数满足 ,

20、 则对任意的初值 ，迭代公式(5.18)均收敛 .| 1G (0)nxR例5.5定理5.4 ：设 A 严格对角占优，则其 Jacobi 迭代公式和Gauss- Seidel 迭代公式均收敛 .例5.7 题5.2 定理：定理：设 对称正定,且 ,则解 的SOR方法收敛.02n nARAxb1()(1)GDLDU证明：SOR迭代法的迭代矩阵为设 是G的一个特征值，相应的特征向量为 x , 则(1)()DUxDL x()TALU对称 (1)(, )(, )(, )(, )Dx xUx xDx xLx x(, )pDx x记 , 则 p 0. (因为 A 正定, D 亦正定)又记 , 则有 . (,

21、)Lx xi(, )Ux xi*(, )()20Ax xx Axx DLU xp且于是(1),pipi而22222()()|,()()ppp22()()( 2)(2)0ppppp故当 时 , SOR方法收敛.02| 1特别的, 当 时 , SOR方法就是GS方法, 从而当A是对称正定矩阵时, GS方法收敛.1Gauss消去法消去法1) 顺序Gauss消去法2) 列主元Gauss消去法例5.8 题5.7例5.10 题5.7矩阵的矩阵的LU分解及应用分解及应用 A = L U , 其中L是单位下三角阵, U是上三角阵1) 计算矩阵行列式2) 解方程组3) 求矩阵的逆例5.11 题5.9方程组的条件

22、数与误差分析方程组的条件数与误差分析 定义5.7: 称数 为矩阵 A 的关于解方程 1 组 的条件数.1( ) | |cond AAAAxb11111( )| | ,( )| |condAAAcondAAA例5.13 题5.10 设 x 是方程组 的精确解, y 是其近似解. 称Axb为y 的剩余向量, 则成立不等式rbAy| |( ).| | |xyrcond Axb(定理5.7)当方程组良态时, 可以用 来估计近似解 y 的误差.| |rChap 7 常微分方程初值问题数值解法常微分方程初值问题数值解法 Euler Euler法法 改进改进EulerEuler法法 Runge-Kutta Runge-Kutta法法 收敛性与稳定性收敛性与稳定性(7.1)(7.2)数值求解一阶常微分方程的初值问题 :000( ,)()dyf x yxxbdxy xy1(,)nnnnyyh f xyEuler公式 :(步进式, 单步方法, 显式格式)记 , 则Euler公式的*1()(,()nnnnyy xhf xy x局部截断误差 :2*2111()( )(),2nnnnhy xyyO hxx总体截断误差 :11()( )nny xyO h(Euler法是1阶方法)Euler法的三种分析解释: 差商逼近微商,数值积分