1、计算方法计算方法总结总结1行业借鉴#目录目录第第1 1章章 绪论绪论第第2 2章章 线性代数方程组线性代数方程组第第3 3章章 数据近似数据近似第第4 4章章 数值微积分数值微积分第第5 5章章 非线性方程求解非线性方程求解第第6 6章章 常微分方程数值解法常微分方程数值解法第第7 7章章 最优化方法简介最优化方法简介(基本工具)(误差分析基础)(计算方法应用)2行业借鉴#第第1章章 绪论绪论1.1.误差误差:近似值与真正值之差近似值与真正值之差分为模型误差、数据误差、截断误差、舍入误差分为模型误差、数据误差、截断误差、舍入误差2.2.数制表示数制表示1212 (),1,0,2,3,ltjtx
2、tdddxddjt(1)实数 可以表示以下形式的 进制 位有效数字12120.10,0.10,0.5 10,llttl txd ddxd ddxxxt (2)有效数字:指一个近似数的有意义的数字的位数 若 如果 则称 有 位有效数字1(,)2(1)(1)1tFt L UUL(3)浮点数系:表示为数的个数:lU上溢:lL下溢:3行业借鉴#第第1章章 绪论绪论3.3.舍入误差舍入误差:对数进行舍入，得到有对数进行舍入，得到有t t位尾数的浮点数位尾数的浮点数():()xfl xxx相对舍入误差11()2tx123:()(1-)()()(1-)()()(1-)()fl xyxyfl xyxyxxfl
3、yy性质浮点运算的注意事项浮点运算的注意事项(1)避免产生大结果的运算，尤其是避免小数作为除数 参加运算；(2)避免“大”“小”数相加减；(3)避免相近数相减，防止大量有效数字损失；(4)尽可能简化运算步骤，减少运算次数。)(xfl4行业借鉴#第第1章章 绪论绪论5.5.方法的稳定性方法的稳定性数值稳定:若初始误差导致最终解的误差能被有效地控制6.6.算法算法由有限个无二义性法则组成的一个计算过程数值不稳定:若初始误差导致最终解的误差不能被有效地控制4.4.问题的性态问题的性态:问题的解对原始数据扰动的敏感性问题的解对原始数据扰动的敏感性病态问题:输入数据相对小的扰动引起解的相对大的变化良态问
4、题:输入数据相对小的扰动不会引起解的相对大的变化,()()()supxf xf xcond fx条件数:当输入数据具有的误差 引起问题的结果误差为则算法的特点,描述5行业借鉴#第第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 86行
5、业借鉴#第第1章章 绪论绪论1-(,),-()1()()2tFt L Uxfl xxxx例.证明在浮点数系中 浮点数的相对误差 满足,.)3,2(0,1 ,)(:11133221jddddddxjltt其中其中设设证明证明 211 td若若lttddddxfl )()(33221有有lttdxflx 11)(此时此时lt 121tl 21lxd 1,1 1有有由于由于txxflx 121)(7行业借鉴#第第1章章 绪论绪论 211 td，若若同理同理lttddddxfl )1()(33221有有lttdxflx 11)(lt 121tl 21lxd 1,1 1有有由于由于txxflx 121)
6、(8行业借鉴#第第1章章 绪论绪论2334610-1-1-1yxxx例.为了使计算的乘除法次数尽可 能少,应该式如何计算:_21610 xx 例.在浮点数系下,计算的两个根,应如何 计算才能使精度较高？(),()f xf x例.对于函数在某个区间上连续可微 则求的近似条件数9行业借鉴#第第2章章 线性代数方程组线性代数方程组,LULDUGGGauss解法列主元Gauss解法数值解法矩阵分解法:分解分解 分解 追赶法Jacobi迭代法迭代解法Gauss-Seide线性方l迭代法程组解法32:(),:()o nnsoGaus消去的时间复杂度回代消去法32:(),:()o nGasnsou消去的时间
7、复列主元消去法杂度回代3:,:,()LUoUnL:单位下三角阵上三角阵 时间复杂度分解3:,:,()3nLDULDUo:单位下三角阵对角阵,单位上三角阵 时间复杂度分解3(/6),oGnGn:分针对对称正定矩阵,加 个解开方运算:三对角阵分带状矩阵分解解,追赶法10行业借鉴#第第2章章 线性代数方程组线性代数方程组范数:方程组的条件数:*1*xxbbAAbx(1)当右端向量有扰动 *()xxxAACond AAxx(2)当系数矩阵有扰动 1,1()AbxxbAkAxbAkAkcond AAA(3)当系数矩阵有扰动右端向量有扰动 其中-1()mcond AA A定义,性质.向量与矩阵范数的相容性
8、,等价性11行业借鉴#第第2章章 线性代数方程组线性代数方程组(1)()kkxGxd迭代:构造,算法判断收敛-111()GDEFID AdD bJacobi:-11()()GDEFdDEbGauss-Seidel:收敛性判定定理,AJacobiTH2.7 为严格对角占优格式收敛,-AGauss SeidelTH2.8 为严格对角占优格式收敛,-;2-,AGauss SeidelD AJacobiTH2.9 对称正定收敛对称正定收敛(1)()1kkxGxdGTH2.10 迭代格式收敛的充要条件为(TH2.11 迭代格式的误差估计1,TH2.6 G则迭代格式收敛12行业借鉴#第第2章章 线性代数方
9、程组线性代数方程组11,_,_,_01004AAA11-12例:矩阵A=则113121:12,1,TAaGGGaaa例 若矩阵可以分解为的形式 其中 为下三角阵且对角元均为正问 的取值范围 并请按此要求将此 分解36,37PP13行业借鉴#第第2章章 线性代数方程组线性代数方程组1231231235210:242252465-xxxxxxxxxJacobiGauss Seidel 例 考查方程组 的迭代格式,格式的收敛性.123123123:(,),2323Txxxxxxxxxx例 设则是否是范数,是否是范数要证明是否是范数,应验证是否满足范数的三个条件.(P79,14题)要否定一个范数,只需
10、要举一个反例14行业借鉴#第第3章章 数据近似数据近似LagrangeNewtonHermit多项式插值插值连续多项式插值插值插值多项式插值分段一次插值分段多项式插值 分段二次插值分段三次样条插值最小二乘近似数据近似15行业借鉴#第第3章章 数据近似数据近似多项式插值0()()nniiiL xl x yLagrange 插值 0()()()()()()niiiiixl xxxxxxxTH 3.1 经过给定插值点的插值多项式唯一()()()nnf xpxR xLagrange插值基本多项式的性质0,()1,ijijl xij0()1niil x16行业借鉴#第第3章章 数据近似数据近似00100
11、1201012011 (),(),()()+,()()()nnnNxy xy x xxxy x x xxxxxy x x xxxxxxxx Newton值 插 1012011(),()()()nnnNxy x x xxxxxxxx差商性质1,对称性()1(),.,!kiii kii kyy x xxx xk差商性质2,Newton 计算带导数条件的插值多项式 利Herm用差商性质2,使用插值多项式的思想it插值进行构造()1(),.,!kiiiikyxy x xxk 个 17行业借鉴#第第3章章 数据近似数据近似插值多项式的误差 3.2 ()()-()nnTHR xy xP x(P97)(1)
12、0()(),(1)!nnyxx xn01,.,()ny x xxxx18行业借鉴#第第3章章 数据近似数据近似分段插值多项式2122113.3()max()max8iia x biTHE gMMy xxx 分段一次多项式的误差 3233113.4()max()max12iia x biTHE gMMyxxx 分段二次多项 式的误差 222113.5()-()max()max2iia x biTHy xs xMMy xxx 分段三次样条插值多项式的误差 19行业借鉴#第第3章章 数据近似数据近似最小二乘法1112111112112122222122221212()()()()()()()()()
13、nnnnnnnnnnmmnmTTaaabg xgxgxaaabg xgxgxGaaabg xgxgxG GaG y得到方程组或法方程 12,(1,2,.,)()(1,2,.,),.,(),iiknx yimgx knmn 给定数据点和一组函数求系数假定使函数1,.()TTaG GG y可以证明 最小二乘问题的法方程总有解存在QR分解 RQGO TRGQO22222Eh11221/2221()()()()()nnmiiip xg xgxgxEp xy 满足达到最小20行业借鉴#第第3章章 数据近似数据近似(4)(),()(),()(),()11,2,()12 ()13()11iiiip xp x
14、f xp xfxfxxp xxf xfx 例.求不超过三次的多项式满足条件若求的误差界01210101000122010101(),()(2)()()()()()()()()()()()()f xa bxxa bxxxxxxxxxxxp xf xfxf xxxxxxxR xf xp x 例.设在区间上有三阶连续导数,有相应的插值多项式试求此插值多项式的余项的表达式21行业借鉴#第第3章章 数据近似数据近似.(),0,1,2,.,(,()1(),()()()1(1)kkkknnnkkknxf xxnxf xxxpxpxpxf xxp n例设取以为插值数据点 做插值多项式则满足 试求534()20
15、09200720062005,2,1,0,1,2()_f xxxxL x例.设则以为 插值节点的不超过四次的插值多项式32()2001200220012000,3,4,550,3,5,1002,3,4,5,_f xxxxfmfmfm例.设则以则22行业借鉴#第第3章章 数据近似数据近似01010,.,(),.,()nniniix xxf xf x xxx例.设节点互异 试证明0100,.,()()()()()()()nnniiiiiiix xxLagrangexL xl x f xf xxxx解:由节点互异 则插值多项式为0()()()()niiiif xxxxx0()()niif xx因此,
16、该多项式最高项的系数为:0100100120101011,.,(),(),()(),()()()nnnx xxNewtonN xyy x xxxy x x xxxxxy x xxxxxxxx另一方面,由节点形成的插值多项式为01,ny x xx该多项式最高项的系数为:因此得证23行业借鉴#第第3章章 数据近似数据近似1010(0,1,),(0)(1)()nnniiiniix inlxx xxl xLagrange 例.设为互异实数 试证明其中为插值多项式0 ()()()()niinif xl x f xRx证明:构造lagrange插值多项式,有110(),(0)0(0)(0)nnniinif
17、 xxflxR取(1)01()()()()()()()(1)!nnnfR xxxxxxxxxn101(0)(1)nnnRx xx 得证()231234 ()1.50.20.30.7f xxf x例.给定以下的数据点,利用插值多项式,计算在 到 之间的根的近似值24行业借鉴#第第3章章 数据近似数据近似-4664()1.060.5671.43 1.77()sincosxf xp xAxBx例.已知函数f(x)有以下测试数据求形如最小二乘近似12()sin,()cosg xx gxx令0.7070.7071.060.50.8660.567,0.50.8661.430.7070.7071.77TTG
18、yGay得 得法方程GG25行业借鉴#第第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因此26行业借鉴#第第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相应的数据构造法方程.下略27行业借鉴#第第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.6PTh28行业借鉴#第第4章章 数值微积分数值微积分01001110102001221022011()()()()()2 (P178)11()()()()()21()3()4()()()231()()()()261
21、()(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待定系数法:利用公式可求得最高计算精度的微分公式29行业借鉴#第第4章章 数值微积分数值微积分.()()2baa
22、bf 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)30行业借鉴#第第4章章 数值微积分数值微积分 100.(),(),(0,1,2,.,)(),().()()().:(1)0,()()kiniinbkkaknikijiixa bxx inxl xxLagrangex f x dxA f xk jn kjAxx例例设设是是定
23、定义义在在区区间间上上的的关关于于权权函函数数的的正正交交多多项项式式族族 并并且且是是的的零零点点是是以以为为插插值值点点的的插插值值基基函函数数是是高高斯斯型型求求积积公公式式证证明明当当时时200 (2)()()()0,(3)()()()bkjanbbkaakx lx lx dxkjx lx dxx dx31行业借鉴#第第4章章 数值微积分数值微积分0001020.()()()(2)fxA f xA f xhA f xh例确定如下的数值微分公式的系数,使其对尽可能高次的多项式精确成立 并给出误差表达式1102488.()0.45675,0.47117,0.47446,0.47612,_f
24、 x dxSSSSS例按照复化Simpson公式计算的数值微分值为则 的误差近似为32行业借鉴#第第5章章 非线性方程求解非线性方程求解(1)()()(1)()()()(-1)(1)()()()(-1)()()-()-()()-()kkkkkkkkkkkkkxxf xNewtonxxfxxxxxf xf xf x简单迭代法迭代法迭代法非线性方程求解割线法区间法:二分法5.1(1),(),(2)()-()01 5.2 ()1THxa bxa bxyq xyqTHxs 简单迭代法的收敛性 *1(),()()1xxxx取构造收敛性的改善 33行业借鉴#第第5章章 非线性方程求解非线性方程求解Newt
25、on迭代格式的收敛性(1)*()*lim0,kpkkxxpxx若 则称收敛速度收敛速度 为 阶收敛005.4(1)()()0 (2)(),()0 (3)()(4)()()0THf a f bfxfxfxf xfx 不变号 且不变号 简单迭代格式收敛速度为线性收敛牛顿迭代格式收敛速度为二阶收敛割线法收敛速度为超线性收敛二分法收敛速度为线性收敛34行业借鉴#第第5章章 非线性方程求解非线性方程求解*()()0f xfx当两次可微且,迭代函数满足()*,kNewTonxx因此 当迭代序列收敛于 时,有()kkq 记lim()kk 由于0于是有*()(5-25)kxx称满足条件并收敛于 的序列为超线性
26、收敛的NewTon法为超线性收敛的(1)*()*()*(),kkkkkxxxxxx 是与 之间的某个数(1)*()*(5-25)lim0kkkkkxxq xxq*()x可知该格式的收敛速度要比简单迭代格式快一些方法方法Newton0)(*x 35行业借鉴#第第5章章 非线性方程求解非线性方程求解由于()()()()()()(-)kkkl xf xfxx x()()()()()(-)0kkkf xfxx x因此*()()*()*()210()()()(-)()(-)2kkkkkf xf xfxxxfxx()()(1)()0()()(-)kkkkf xfxxx两式相减()(1)*()21()(-)
27、()(-)2kkkkfxxxfxx*()()0,fxfx由于连续且()*,kxxk当收敛于 时 对充分大的()()0kfx总有从而(1)*()2()()1(-)2()kkkkfxxxxfx36行业借鉴#第第5章章 非线性方程求解非线性方程求解()()1max2()kkfqfx若令2(1)()()(*)(5-26)kkkxxq xx则有(*)()kxx称满足条件式(5-26)的收敛于的序列称为二阶收敛的Newton法为二阶收敛的同时,可以得出割线性是超线性收敛(1)*()2()()1(-)2()kkkkfxxxxfx37行业借鉴#第第5章章 非线性方程求解非线性方程求解322)(,/11)()1
28、(:xxxx 解解讨论迭代格式讨论迭代格式附近有根附近有根在在方程方程,5.101*23xxx 的收敛性的收敛性2)()1(/11kkxx 58.1,4.1取区间取区间41.1)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 构造构造迭代格式收敛迭代格式收敛38行业借鉴#第第5章章 非线性方程求解非线性方程求解lim222222k试
29、用迭代法明例原理证.(1)()(0)2,0()2,2()0kkxxxxxxx 解:构造迭代格式 则当时,1()0,()2 2xxx即单调增()202x5/21()04(2)xx*0,2,()0,2,()15.2xxxThx考虑区间有由知,对任何初始点 迭代格式都收敛于不动点*2,2xxx由方程知其不动点()x单调减()2kx因此,39行业借鉴#第第6章章 常微分方程数值解法常微分方程数值解法221 (,)(,)()()2iiiiiihEuleryyhf t yE t hyo h公式22111 (,)(,)()()2iiiiiihEuleryyhf tyE t hyo h后退公式11()(,()
30、()()(,()iitiity tf y y ty 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 40行业借鉴#第第6章章 常微分方程数值解法常微分方程数值解法2(2)1011 (,)()kkiiiiki kiihyyb fb f
31、b fE t hrhyA显示公式01*2(2)111 (,)()kkkiiiii kiihyyb fb fb fE t hr hyA 隐示公式11110 kkijijjijjjyyhf 1k 当时为单步法1k 当时为多步法00当时为显式公式00当时为隐式公式3.Adams3.Adams公式公式:利用高次插值多项式近似利用高次插值多项式近似f(t,y(t)f(t,y(t)4.4.待定系数法待定系数法1000kkjijjijjjyhf 000kkkjkjjjjjh 特征方程稳定性、稳定域稳定性、稳定域41行业借鉴#第第6章章 常微分方程数值解法常微分方程数值解法(1)利用两个同阶公式,相同步长_1
32、(1)1(1)111121_1111()-()()-()()()ppppiiiiiiiiy tyhyy tyhyy tyyy_1111 ()iiiiy tyyy(2)利用两个不同阶公式,相同步长_11111 ()()/1/piiiihhy tyyyh h(3)利用同一个公式,不同的步长 和计算5.5.预估预估校正方法校正方法精度更高精度更高使计算更方便使计算更方便隐式公式作校正隐式公式作校正利用显式公式作预估利用显式公式作预估，42行业借鉴#第第6章章 常微分方程数值解法常微分方程数值解法132112111(9375955)24(4)()(5199(,)24iiiiiiiiiiiiihpyff
33、ffABMhyyffff tp四阶精度1321111114(22)3Milne-Simpson()(4(,)3iiiiiiiiiiihpyfffhyyfff tp四阶精度1111(,)():(,)(,)2iiiiiiiiiipyhf t yhyyf t yf tp预估:Heun方法二阶精度校正43行业借鉴#第第6章章 常微分方程数值解法常微分方程数值解法132111111114(22)328Milne-Simpson()294(,)3iiiiiiiiiiiiiiihpyfffmpyphyyfff tm预估修正校正1321111211111114(22)3112()12113(9)2(,)889
34、()121iiiiiiiiiiiiiiiiiiiihpyfffmpypcyyhfff tmyccp:修正Hamming预估-校正公式44行业借鉴#第第6章章 常微分方程数值解法常微分方程数值解法1112212221111,11(,)(,)(,)iimmiiiimimimm mmyyKKKKhf t ymKhf th yKKhf th yKK一般的 级12121(,)(/2,/2)iiiiiiyyKEulerKhf t yKhf thyK变形方法1123412132431(22)6(,)4 (/2,/2)(/2,/2)(,)iiiiiiiiiiyyKKKKKhf t yRKKhf thyKKhf
35、 thyKKhf th yK6.6.RungeRungeKuttaKutta方法方法:构造高精度的单步法公式构造高精度的单步法公式45行业借鉴#第第6章章 常微分方程数值解法常微分方程数值解法)(83),(),23165(12 )2(,)1()(,)()(,()(.)4(41211110yhhtEfffhyy，fffhyybatyaytytftyiiiiiiiiiii公式公式校正校正修正修正预估预估组成组成合合请将公式与以下公式结请将公式与以下公式结截断误差截断误差并给出局部并给出局部精度精度使算法具有尽可能高的使算法具有尽可能高的确定系数确定系数的算法的算法解常微分方程初值问题解常微分方程初
36、值问题例例25.0,10,0)0(,1 .22 htyytyKuttaRunge取步长取步长法计算初值问题法计算初值问题用用例例46行业借鉴#第第6章章 常微分方程数值解法常微分方程数值解法使用待定系数法 234(4)51342(4)51321()23!4!()23!2iiiiiiiiiiiiiiiiiiiihhhy ty thyhyyyyO hy tyhhAhfAhyAh yAyAyO hBhfBhyhChfChyCh yCy4(4)5()3!ihCyO h125,128,12131211CBACACACBA1118512iiiiihyyfff4(4)54(4)511 15 11()()()
37、4!12 612 624iiEh yO hh yO h 47行业借鉴#第第6章章 常微分方程数值解法常微分方程数值解法 121(51623),12iiiiihpyfff4(4)113()()8iiiy tph y4(4)111()()24iiiy tyh y 由 及 4(4)4(4)11111012()()()245iiiiyph fh fyp得 因此 121111111(51623)129()1085(,)12iiiiiiiiiiiiiiihpyfffmpyphyyfff tm48行业借鉴#感谢大家感谢大家大自然是上帝用数学创造的大自然是上帝用数学创造的 -毕达哥拉斯计算方法主要研究数值算法的性能,通过对误差的评价实现对算法性能的评价49行业借鉴#
