西交计算方法总结

1、计算方法总结计算方法总结目录目录第第1 1章章 绪论绪论第第2 2章章 线性代数方程组线性代数方程组第第3 3章章 数据近似数据近似第第4 4章章 数值微积分数值微积分第第5 5章章 非线性方程求解非线性方程求解第第6 6章章 常微分方程数值解法常微分方程数值解法第第7 7章章 最优化方法简介最优化方法简介(基本工具)(误差分析基础)(计算方法应用)第第1章章 绪论绪论1.1.误差误差: :近似值与真正值之差近似值与真正值之差分为模型误差、数据误差、截断误差、舍入误差分为模型误差、数据误差、截断误差、舍入误差2.2.数制表示数制表示1212 (),1,0,2,3,ltjtxtdddxddjt

2、实数 可以表示以下形式的 进制 位有效数字12120.10 ,0.10 , 0.5 10,llttl txd ddxd ddxxxt 有效数字: 指一个近似数的有意义的数字的位数 若 如果 则称 有 位有效数字1( , , ,), 2(1)(1) 1tFt L UUL数系:表示为个数:lU上溢:lL下溢:第第1章章 绪论绪论3.3.舍入误差舍入误差: :对数进行舍入，得到有对数进行舍入，得到有t t位尾数的浮点数位尾数的浮点数( ): ( )xfl xxx相对舍入误差11( )2tx123:()(1-)() ()(1-)() ( )(1-)( )fl xyxyfl xyxyxxflyy性质浮点

3、运算的注意事项浮点运算的注意事项(1)避免产生大结果的运算，尤其是避免小数作为除数 参加运算；(2)避免“大”“小”数相加减；(3)避免相近数相减，防止大量有效数字损失；(4)尽可能简化运算步骤，减少运算次数。)(xfl第第1章章 绪论绪论5.5.方法的稳定性方法的稳定性数值稳定:若初始误差导致最终解的误差能被有效地控制6.6.算法算法由有限个无二义性法则组成的一个计算过程数值不稳定:若初始误差导致最终解的误差不能被有效地控制4.4.问题的性态问题的性态: :问题的解对原始数据扰动的敏感性问题的解对原始数据扰动的敏感性病态问题:数据相对小的扰动引起解的相对大的变化良态问题:数据相对小的扰动不会

4、引起解的相对大的变化,( )( ) ( )supxf xf xcond fx条件数:当输入数据具有的误差 引起问题的结果误差为则算法的特点,描述第第1章章 绪论绪论112.718281828,2.71828325, 6 xxx例.则 的有位有效位数( )2.71828225,fl x若则有7位有效位数(10,5,-2,3)F例.在中有多少个数?33661) ,)11 38,19601 6930 8,19601 6930 83833- 8例.下列各式均与等价,在浮点数系F(10,5,-10,10)中3+ 8 哪个公式能获得最准确的结果:(17-6 8(17+6 8第第1章章 绪论绪论1-( ,

5、, ,),-( )1( )( )2tFt L Uxfl xxxx例.证明在浮点数系中 浮点数的相对误差 满足,.)3 , 2(0 ,1 ,)(11133221 jddddddxjltt 其中其中设设 211 td若若lttddddxfl )()(33221有有lttdxflx 11)(此时此时lt 121tl 21lxd 1,1 1有有由于由于txxflx 121)( 第第1章章 绪论绪论 211 td，若若同理同理lttddddxfl )1()(33221有有lttdxflx 11)(lt 121tl 21lxd 1,1 1有有由于由于txxflx 121)( 第第1章章 绪论绪论23346

6、10-1-1-1yxxx例.为了使计算的乘除法次数尽可 能少,应该式如何计算:_21610 xx 例.在浮点数系下,计算的两个根,应如何 计算才能使精度较高？( ),( )f xf x例.对于函数在某个区间上连续可微 则求的近似条件数第第2章章 线性代数方程组线性代数方程组,LULDUGGGauss解法列主元Gauss解法数值解法矩阵分解法:分解分解 分解 追赶法Jacobi迭代法迭代解法Gauss-Seide线性方l迭代法程组解法32:(),: ()o nnsoGaus消去的时间复杂度回代消去法32:(),: ()o nGasnsou消去的时间复列主元消去法杂度回代3:,:,()LUoUnL

7、:单位下三角阵上三角阵 时间复杂度分解3:,:,()3nLDULDUo:单位下三角阵对角阵,单位上三角阵 时间复杂度分解3(/6),oGnGn:分针对对称正定矩阵,加 个解开方运算:三对角阵分带状矩阵分解解,追赶法第第2章章 线性代数方程组线性代数方程组:定义,性质.向量与矩阵范数的相范数容性,等价性-1( )mcond AA A方程组的条:件数*1*xxbbAAbx(1)当右端向量有扰动 *( )xxxAACond AAxx(2)当系数矩阵有扰动 1, 1( )AbxxbAkAxbAkAkcond AAA(3)当系数矩阵有扰动右端向量有扰动 其中第第2章章 线性代数方程组线性代数方程组(1)

8、( )kkxGxd迭代:构造,算法判断收敛-111()GDEFID AdD bJacobi:-11()()GDEFdDEbGauss-Seidel:1, TH2.6收敛 G则迭代性判定定理格式收敛,AJacobiTH2.7 为严格对角占优格式收敛,-AGauss SeidelTH2.8 为严格对角占优格式收敛,-;2-,AGauss SeidelD AJacobiTH2.9 对称正定收敛对称正定收敛(1)( )1kkxGxdGTH2.10 迭代格式收敛的充要条件为 (TH2.11 迭代格式的误差估计第第2章章 线性代数方程组线性代数方程组11,_,_,_01004AAA11-12例:矩阵A=则

9、113121:12,1,TAaGGGaaa例 若矩阵可以分解为的形式 其中 为下三角阵且对角元均为正问 的取值范围 并请按此要求将此 分解36, 37PP第第2章章 线性代数方程组线性代数方程组1231231235210:242252465-xxxxxxxxxJacobiGauss Seidel 例 考查方程组 的迭代格式,格式的收敛性.123123123:(,) ,2323Txxxxxxxxxx例 设则是否是范数, 是否是范数要证明是否是范数,应验证是否满足范数的三个条件.(P79,14题)要否定一个范数,只需要举一个反例第第3章章 数据近似数据近似LagrangeNewtonHermit多

10、项式插值插值连续多项式插值插值插值多项式插值分段一次插值分段多项式插值 分段二次插值分段三次样条插值最小二乘近似数据近似第第3章章 数据近似数据近似( )( )( )nnf xpxR x TH 3.1 经过给定插值点的插值多项式唯一 多项式插值 0( )( )nniiiL xl x yLagrange 插值 0( )( ) ( )()()( )niiiiixl xxxxxxx001001201012011 ( ),(),()() + ,()()()nnnNxy xy x xxxy x x xxxxxy x x xxxxxxxx Newton值 插 1012011( ),()()()nnnNxy

11、 x x xxxxxxxx差商性质1,对称性( )1( ) ,., ,!kiii kii kyy x xxx xk差商性质2,第第3章章 数据近似数据近似( )1( ) ,.,!kiiiikNewtonyxy x xxk 个 计算带导数条件的插值多项式 利用差商性质2,使用插值多项式的思想进行构造 Hermit 插值 插值多项式的误差(1)001 3.2 ( )( )-( )( )( ) , (1)!,., ( )nnnnnTHR xy xP xyxx xny x xxxx(P97)第第3章章 数据近似数据近似分段插值多项式2122113.3() max( ) max8iia x biTHE

12、gMMy xxx 分段一次多项式的误差 3233113.4() max( ) max12iia x biTHE gMMyxxx 分段二次多项 式的误差 222113.5( )- ( ) max( ) max2iia x biTHy xs xMMy xxx 分段三次样条插值多项式的误差 第第3章章 数据近似数据近似最小二乘法1112111112112122222122221212()()()()()() ()()()nnnnnnnnnnmmnmTTaaabg xgxgxaaabg xgxgxGaaabg xgxgxG GaG y得到方程组或法方程 1211221/2221,(1,2,.,)( )

13、(1,2,., ),.,(),( )( )( )( ) ( ( )iiknnnmiiix yimgx knmnp xg xgxgxEp xy 给定数据点和一组函数求系数假定使函数 满足达到最小1,.()TTaG GG y可以证明 最小二乘问题的法方程总有解存在QR分解 RQGO TRGQO22222Eh第第3章章 数据近似数据近似(4)( ),( )( ),( )( ),( )11, 2,( )12 ( )13( )11iiiip xp xf xp xfxfxxp xxf xfx 例.求不超过三次的多项式满足条件若求的误差界01210101000122010101( ) , ,()(2)()(

14、)() ( )()()()()()( )( )( )f xa bxxa bxxxxxxxxxxxp xf xfxf xxxxxxxR xf xp x 例.设在区间上有三阶连续导数,有相应的插值多项式试求此插值多项式的余项的表达式第第3章章 数据近似数据近似.( ),0,1,2,., ,(,()1( ),( )()()1(1)kkkknnnkkknxf xxnxf xxxpxpxpxf xxp n例设取以为插值数据点 做插值多项式则满足 试求534( )2009200720062005,2, 1,0,1,2( )_f xxxxL x例.设则以为 插值节点的不超过四次的插值多项式第第3章章 数据近

15、似数据近似01010,.,( ) ,.,( )nniniix xxf xf x xxx例.设节点互异 试证明0100,.,( )( )( ) ( )( )()( )nnniiiiiiix xxLagrangexL xl x f xf xxxx解:由节点互异 则插值多项式为0( )( )()( )niiiif xxxxx0( )( )niif xx因此,该多项式最高项的系数为:0100100120101011,.,( ),(),()(),()()()nnnx xxNewtonN xyy x xxxy x x xxxxxy x xxxxxxxx另一方面,由节点形成的插值多项式为01,ny x xx

16、该多项式最高项的系数为:因此得证第第3章章 数据近似数据近似1010(0,1, ),(0)( 1)( )nnniiiniix inlxx xxl xLagrange 例.设为互异实数 试证明其中为插值多项式0 ( )( ) ()( )niinif xl x f xRx证明:构造lagrange插值多项式,有110( ),(0)0(0)(0)nnniinif xxflxR取(1)01( )( )( )( )()()()(1)!nnnfR xxxxxxxxxn101(0)( 1)nnnRx xx 得证( )231234 ( )1.50.20.30.7f xxf x例.给定以下的数据点,利用插值多项

17、式,计算在 到 之间的根的近似值第第3章章 数据近似数据近似- 4664( )1.060.5671.43 1.77( )sincosxf xp xAxBx例.已知函数f(x)有以下测试数据求形如最小二乘近似解:构造法方程sin()cos()1.06440.7070.7071.06sin()cos()0.5670.50.8660.567660.50.8661.43sin()cos()1.43660.7070.7071.77sin()cos()1.7744ABABABABAB 12( )sin ,( )cosg xx gxx令0.7070.7071.060.50.8660.567,0.50.866

18、1.430.7070.7071.77Gy得 得法方程第第3章章 数据近似数据近似0.7070.7070.707.500.500.7070.50.866.707.866.866.7070.50.8660.7070.7071.060.707.500.500.7070.567 .707.866.866.7071.431.77AB1.500302.501.25AB即 2.00 .500AB解得( )2sin0.5cosf xxx因此第第3章章 数据近似数据近似( )01.4452.8904.3355.780 1.84192.9633 18.23698.7410529.2178( )xf xxyp xe

19、例.已知函数有以下测试数据求形如的最小二乘近似函数( ) ln( )lnp xp xx解:对两边求对数,有( )ln( ),ln, ( )f xp xABf xABx令则最小二乘函数变为01.4452.8904.3355.780 ln0.61071.08632.90344.59256.2714xy相应的数据构造法方程. 下略第第4章章 数值微积分数值微积分(1)-(3)(5)()()()mNewton CotesSimpsonmCotesmSimpsonCotes梯形公式 公式公式公式 等距结点复化梯形公式 二阶复化求积公式 复化公式 四阶复化公式 六阶不等距结点:GaTh 数值积4.9uss

20、型求(构造方法积公式,利用正交多项) TH 4.11 式进行构TH4.造 12 分 Romberg积分:利用低精度的求积公式,构造高精度的公式待定系数法:利用代数精度的定义求得最 4-39计算系数 4-4高代数精度的求积公式0计算误差135.47 4.1PTh136.48 4.2PTh136.49 4.3PTh140.4 13 4.4PTh140.4 14 4.5PTh140.4 15 4.6PTh第第4章章 数值微积分数值微积分01001110102001221022011()()()( )()2 (P178)11()()()( )()21()3 ()4 ()()( )231()()()(

21、)261()(2fxf xf xfxxhfxf xf xfxxhhfxf xf xf xfhhfxf xf xfhfxf xh两点公式一阶导数公式三点式微公数值分2122(4)00121222(4)101222(4)2012122 (P179)4 ()3 ()( )31()()2 ()()()()61()()2 ()()( )121()()2 ()()()()6hf xf xfhfxf xf xf xhffhhfxf xf xf xfhhfxf xf xf xhffh二阶导数公式 (P180)Taylor待定系数法:利用公式可求得最高计算精度的微分公式第第4章章 数值微积分数值微积分.( )(

22、)2baabf x dxba f例试导出中矩形公式,并给出其误差公式 20120.( )(0)( )(2 )hf x dxA fA f hA fh例确定以下公式中的系数,使其具有尽可能高的代数精度 (1) 1123111( )()(0)( )22f x dxA fA fA f (2) 111221( )()()f x dxA f xA f x (3) 第第4章章 数值微积分数值微积分 100.( ) , ( ),(0,1,2,., )( ), ( ). ( ) ( )().: (1) 0,()()kiniinbkkaknikijiixa bxx inxl xxLagrangex f x dxA

23、 f xk jn kjAxx例例设设是是定定义义在在区区间间上上的的关关于于权权函函数数的的正正交交多多项项式式族族 并并且且是是的的零零点点是是以以为为插插值值点点的的插插值值基基函函数数是是高高斯斯型型求求积积公公式式证证明明当当时时200 (2) ( ) ( ) ( )0, (3) ( ) ( )( )bkjanbbkaakx lx lx dxkjx lx dxx dx第第4章章 数值微积分数值微积分0001020.()()()(2 )fxA f xA f xhA f xh例确定如下的数值微分公式的系数,使其对尽可能高次的多项式精确成立 并给出误差表达式1102488.( )0.4567

24、5,0.47117,0.47446,0.47612,_f x dxSSSSS例按照复化Simpson公式计算的数值微分值为则 的误差近似为第第5章章 非线性方程求解非线性方程求解(1)( )( )(1)( )( )( )( -1)(1)( )( )( )( -1) ()() -()- -()()-()kkkkkkkkkkkkkxxf xNewtonxxfxxxxxf xf xf x简单迭代法迭代法迭代法非线性方程求解割线法区间法:二分法5.1 (1) , , ( ) , (2) ( )- ( ) 01 5.2 ( )1THxa bxa bxyq xyqTHxs 简单迭代法的收敛性 *1(),(

25、 )( )1xxxx取构造收敛性的改善 第第5章章 非线性方程求解非线性方程求解005.4(1)( ) ( )0 (2) ( ),( )0 (3) ( )(4)()()0THfNewtona f bfxfxfxf xfx 不变号 且不变号 迭代格式的收敛性 (1)*( )*lim0,kpkkxxpxx若 则称收敛速度收敛速度 为 阶收敛第第5章章 非线性方程求解非线性方程求解322)(,/11)()1(: xxxx 解解讨论迭代格式讨论迭代格式附近有根附近有根在在方程方程,5 . 101*23xxx 的收敛性的收敛性2)()1(/11kkxx 58. 1 , 4 . 1取区间取区间41. 1)

26、58. 1(,51. 1)4 . 1( 0)( x， 在此区间上在此区间上单调减单调减则则)(x 06)(4 xx 5071. 0)58. 1(,7288. 0)4 . 1( 1)( x 可知可知迭代格式收敛迭代格式收敛改善迭代格式改善迭代格式)2(59259. 0)5 . 1( 取取 xxxxx59259. 01159259. 011)(11)(2 构造构造迭代格式收敛迭代格式收敛第第5章章 非线性方程求解非线性方程求解lim222222k试用迭代法明例原理证 .(1)( )(0)2,0( )2,2( )0kkxxxxxxx 解: 构造迭代格式 则当时,1( )0,( )2 2xxx即单调增

27、( )202x5/21( )04(2)xx *0,2,( )0,2,( )15.2xxxThx考虑区间有由知,对任何初始点 迭代格式都收敛于不动点*2,2xxx由方程知其不动点( )x单调减( )2kx因此,第第6章章 常微分方程数值解法常微分方程数值解法221 ( ,) ( , )( )()2iiiiiihEuleryyhf t yE t hyo h公式22111 (,) ( , )( )()2iiiiiihEuleryyhf tyE t hyo h后退公式1111( )( , ( )( )( , ( )( )()( , ( )iiiiiitttiittty tf y y ty t dtf

28、y y t dty ty tf t y t dt33111 ( ,)(,) ( , )( )()212iiiiiiiihhyyf t yf tyE t hyo h 梯形公式111111 (,)4 ( ,)(,)3iiiiiiiihyyf tyf t yf tySimpson公式, )()(,()( 0batyaytytfty 初值问题初值问题1.1.数值微分法数值微分法2.2.数值积分法数值积分法5(5)5( , )( )()90iihE t hyo h 第第6章章 常微分方程数值解法常微分方程数值解法2(2)1011 ( , )( )kkiiiiki kiihyyb fb fb fE t h

29、rhyA显示公式01*2(2)111 ( , )( )kkkiiiii kiihyyb fb fb fE t hr hyA 隐示公式11110 kkijijjijjjyyhf 1k 当时为单步法1k 当时为多步法00当时为显式公式00当时为隐式公式3.Adams3.Adams公式公式4.4.待定系数法待定系数法1000kkjijjijjjyhf 000kkkjkjjjjjh 特征方程5.5.稳定性、稳定域稳定性、稳定域第第6章章 常微分方程数值解法常微分方程数值解法(1)利用两个同阶公式,相同步长_1(1)1(1)111121_1111()-( ) ()-()()()ppppiiiiiiiiy

30、 tyhyy tyhyy tyyy_1111 ()iiiiy tyyy(2)利用两个不同阶公式,相同步长_11111 ()()/ 1/piiiihhy tyyyh h(3)利用同一个公式,不同的步长 和计算6.6.预估预估校正方法校正方法精度更高精度更高使计算更方便使计算更方便隐式公式作校正隐式公式作校正利用显式公式作预估利用显式公式作预估， 第第6章章 常微分方程数值解法常微分方程数值解法132112111( 9375955 )24(4)(5199 (,)24iiiiiiiiiiiiihpyffffABMhyyffff tp1321111114(22) 3Milne-Simpson(4(,)

31、3iiiiiiiiiiihpyfffhyyfff tp1111( ,):( ,)(,)2iiiiiiiiiipyhf t yhyyf t yf tp预估:Heun方法校正第第6章章 常微分方程数值解法常微分方程数值解法132111111114(22)328Milne-Simpson()294(,)3iiiiiiiiiiiiiiihpyfffmpyphyyfff tm预估修正校正1321111211111114(22)3112()12113(9)2(,)889()121iiiiiiiiiiiiiiiiiiiihpyfffmpypcyyhfff tmyccp:修正Hamming预估-校正公式第第6章章 常微分方程数值解法常微分方程数值解法1112212221111,11( ,