计算方法B课程总结

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

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

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

4、变化良态问题:数据相对小的扰动不会引起解的相对大的变化,( )( ) ( )supxf xf xcond fx条件数:当输入数据具有的误差 引起问题的结果误差为则算法的特点,描述第第1章章 绪论绪论112.718281828,2.71828325,6xxx例.则 的有 位有效位数( )2.71828225,fl x若则有7位有效位数(10,5,-2,3)F例.在中有多少个数?例.若桌子长为100cm,宽为50cm,实测长为102cm,宽为51cm, 求面积的相对误差33661) ,)11 38,19601 6930 8,19601 6930 83833- 8例.下列各式均与等价,在浮点数系F(

5、10,5,-10,10)中3+ 8 哪个公式能获得最准确的结果:(17-6 8(17+6 8第第1章章 绪论绪论1-( , , ,),-( )1( )( )2tFt L Uxfl xxxx例.证明在浮点数系中 浮点数的相对误差 满足,.)3 , 2(0 ,1 ,)(11133221 jddddddxjltt 其其中中设设 211 td若若lttddddxfl )()(33221有有lttdxflx 11)(此此时时lt 121tl 21lxd 1,1 1有有由由于于tlxxflx 21)(第第1章章 绪论绪论 211 td，若若同理同理lttddddxfl )1()(33221有有lttdxf

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

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

8、AxbAkAkcond AAA(3)当系数矩阵有扰动右端向量有扰动 其中第第2章章 线性代数方程组线性代数方程组xGxd迭代算:构造,法判断收敛-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 迭代格式的误

9、差估计第第2章章 线性代数方程组线性代数方程组11,_,_,_01004AAA11-12例:矩阵A=则113121:12,1,TAaGGGaaa例 若矩阵可以分解为的形式 其中 为下三角阵且对角元均为正问 的取值范围 并请按此要求将此 分解36, 37PP第第2章章 线性代数方程组线性代数方程组1231231235210:242252465-xxxxxxxxxJacobiGauss Seidel 例 考查方程组 的迭代格式,格式的收敛性.123123123:(,) ,2323Txxxxxxxxxx例 设则是否是范数, 是否是范数第第3章章 数据近似数据近似LagrangeNewtonHermi

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

11、 xx 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 xxx(P97)第第3章章 数据近似数据近似分段插值多项式2122113.3() max( ) max8iia x biTHE gM

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

13、2,., ),.,(),( )( )( )( ) ( ( )iiknnnmiiix yimgx knmnp xg xgxgxEp xy 给定数据点和一组函数求系数假定使函数 满足达到最小1,.()TTaG GG y可以证明 最小二乘问题的法方程总有解存在QR分解 RQGO TRGQO第第3章章 数据近似数据近似0120121)( )xxxxf xyyy例.求满足以下插值条件的插值多项式 ( 01201212)( )( )xxxxf xyyyfxy ( 0120213)( )( )xxxxf xyyfxy ( 第第3章章 数据近似数据近似 (0)(0)0,(1)(1)1,(2)1ppppp例.求

14、不超过四次的插值多项式,满足条件(4)( ),( )( ),( )( ),( )11, 2,( )12 ( )13( )11iiiip xp xf xp xfxfxxp xxf xfx 例.求不超过三次的多项式满足条件若求的误差界.( ),0,1,2,., ,(,()1( ),( )()()1(1)kkkknnnkkknxf xxnxf xxxpxpxpxf xxp n例设取以为插值数据点 做插值多项式则满足 试求第第3章章 数据近似数据近似01010,.,( ) ,.,( )nniniix xxf xf x xxx例.设节点互异 试证明0100,.,( )( )( ) ( )( )()( )

15、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该多项式最高项的系数为:因此得证第第3章章 数据近似数据近似1010(0,1, ),(0)( 1)( )nnniiiniix inlxx xxl xLagrange

16、 例.设为互异实数 试证明其中为插值多项式0 ( )( ) ( )( )niinif xl x f xR x证明:构造lagrange插值多项式,有110( ),(0)0(0)(0)nnniinif xxflxR取(1)01( )( )( )( )()()()(1)!nnnfR xxxxxxxxxn101(0)( 1)nnnRx xx 得证第第3章章 数据近似数据近似3( )234(),1,2,3_, 0,1,2,3_, 0,1,2,3,4_f xxaxafff例.设为实数 则差商32( )25( , ,),1,2,0, 0,1,_f xxpxqxc p q cfmfm例.设均为实数 若差商则

17、534( )2009200720062005,2, 1,0,1,2( )_f xxxxL x例.设则以为 插值节点的不超过四次的插值多项式( )231234 ( )0.7f xxf x例.给定以下的数据点,利用插值多项式,计算在 到 之间的根的 近似值第第3章章 数据近似数据近似01210101000122010101( ) , ,()(2)()()() ( )()()()()()( )( )( )f xa bxxa bxxxxxxxxxxxp xf xfxf xxxxxxxR xf xp x 例.设在区间上有三阶连续导数,有相应的插值多项式试求此插值多项式的余项的表达式00

18、1100()() ,()() ,()()p xf xp xf xp xfx解:由于因此插值多项式的余项公式为:200101201( )( )( ), () ()1( )() () , 6R xf xp xf xxx x xxxxfxxxxa b第第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.

19、43660.7070.7071.77sin()cos()1.7744ABABABABAB 0.7070.7071.060.50.8660.567,0.50.8661.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 .500( )2sin0.5cosABf xxx解得因此第第3章章 数

20、据近似数据近似( )01.4452.8904.3355.780 1.84192.963318.23698.7410529.2178( )xf xxyp xe例.已知函数有以下测试数据求形如的最小二乘近似函数( ) 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 CotesSimpsonmCotesm

21、SimpsonCotes梯形公式 公式公式公式 等距结点复化梯形公式 二阶复化求积公式 复化公式 四阶复化公式 六阶不等距结点:GaTh 数值积4.9uss型求(构造方法积公式,利用正交多项) 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章章 数值微积分数值微积分01001

22、11010200122102201211()()()( )()211()()()( )()21()3 ()4 ()()( )231()()()( )261()()4 ()3 ()2fxf xf xfxxhfxf xf xfxxhhfxf xf xf xfhhfxf xf xfhfxf xf xf xh数两点公式一阶导数公式三点式分公值微22(4)00121222(4)101222(4)2012122( )31()()2 ()()( )()61()()2 ()()( )121()()2 ()()( )()6hfhfxf xf xf xhffhhfxf xf xf xfhhfxf xf xf xh

23、ffh二阶导数公式待定系Taylor数法:利用公式可求得最高计算精度的微分公式第第4章章 数值微积分数值微积分.( )()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章章 数值微积分数值微积分 1111.( ) , ( ),(1,2,.,1)( ), ( ). ( ) ( )().:

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

25、.( )0.45675,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

26、(),( )( )1xxxx取构造收敛性的改善 第第5章章 非线性方程求解非线性方程求解005.4(1)( ) ( )0 (2) ( ),( )0 (3) ( )(4)()()0THfNewtona f bfxfxfxf xfx 不变号 且不变号 迭代格式的收敛性 (1)*( )*lim0,kpkkxxpxx若 则称收敛速度收敛速度 为 阶收敛第第5章章 非线性方程求解非线性方程求解32*(1)( )-1/2 -101.5,(-1)kkxxxxx方程在邻近有根讨论迭例.代格式的收敛性-1/2( )( -1)xx解: 令-3/21( )( -1)2xx 1.4,1.6取区间*1.4,1.6 (1

27、.4)1.5811, (1.6)1.29099x有 ( )0,( )xx且在此区间上即单调减-5/23( )( -1)04xx又( )x单调增( )(1.4)1.9761x*( )( )()( )xxxxxxxx 可知( )x迭代格式不收敛(1.5)1.414 取1/21(1)1.414( )( )12.414xxxxx构造则此迭代格式收敛第第5章章 非线性方程求解非线性方程求解lim222222k试用迭代法明例原理证 .(1)( )(0)2,0( )2,2( )0kkxxxxxxx 解: 构造迭代格式 则当时,1( )0,( )2 2xxx即单调增( )202x5/21( )04(2)xx

28、*0,2,( )0,2,( )15.2xxxThx考虑区间有由知,对任何初始点 迭代格式都收敛于不动点*2,2xxx由方程知其不动点( )x单调减( )2kx因此,第第6章章 常微分方程数值解法常微分方程数值解法0( )( , ( ) , ( )y tf t y tta by ay初值问题 1.数值微分法221 ( ,) ( , )( )()2iiiiiihEuleryyhf t yE t hyo h公式22111 (,) ( , )()()2iiiiiihEuleryyhf tyE t hyo h后退公式2.数值积分法1111( )( , ( )( )( , ( ) ( )()( , ( )

29、iiiiiitttttiity tf y y ty t dtf y y t dty ty tf t y t dt33111 ( ,)(,) ( , )( )()212iiiiiiiihhyyf t yf tyE t hyo h 梯形公式1111115(5)5 (,)4 ( ,)(,) 3 ( , )( )()90iiiiiiiiiihyyf tyf t yf tyhE t hyo h Simpson公式第第6章章 常微分方程数值解法常微分方程数值解法Adams公式2(2)1011 ( , )( )kkiiiiki kiihyyb fb fb fE t hrhyA显示公式01*2(2)111 (

30、 , )( )kkkiiiii kiihyyb fb fb fE t hr hyA 隐示公式3.待定系数法11110 kkijijjijjjyyhf 1k 当时为单步法1k 当时为多步法00当时为显式公式00当时为隐式公式第第6章章 常微分方程数值解法常微分方程数值解法4.预估-校正公式(1)利用两个同阶公式,相同步长_1(1)1(1)111121_1111()-( ) ()-()()()ppppiiiiiiiiy tyhyy tyhyy tyyy_1111 ()iiiiy tyyy(2)利用两个不同阶公式,相同步长_11111()()/ 1/piiiihhy tyyyh h(3)利用同一个公

31、式,不同的步长 和计算第第6章章 常微分方程数值解法常微分方程数值解法132112111( 9375955 )24(4)(5199 (,)24iiiiiiiiiiiiihpyffffABMhyyffff tp1321111114(22) 3Milne-Simpson(4(,)3iiiiiiiiiiihpyfffhyyfff tp1111( ,):( ,)(,)2iiiiiiiiiipyhf t yhyyf t yf tp预估:Heun方法校正第第6章章 常微分方程数值解法常微分方程数值解法132111111114(22)328Milne-Simpson()294(,)3iiiiiiiiiiiiiiihpyfffm