計算方法B總結

1、編輯ppt計算方法計算方法總結總結編輯ppt目錄目錄第第1 1章章 緒論緒論第第2 2章章 線性代數(shù)方程組線性代數(shù)方程組第第3 3章章 數(shù)據(jù)近似數(shù)據(jù)近似第第4 4章章 數(shù)值微積分數(shù)值微積分第第5 5章章 非線性方程求解非線性方程求解第第6 6章章 常微分方程數(shù)值解法常微分方程數(shù)值解法第第7 7章章 最優(yōu)化方法簡介最優(yōu)化方法簡介(基本工具)(誤差分析基礎)(計算方法應用)編輯ppt第第1章章 緒論緒論1.1.誤差誤差: :近似值與真正值之差近似值與真正值之差分為模型誤差、數(shù)據(jù)誤差、截斷誤差、舍入誤差分為模型誤差、數(shù)據(jù)誤差、截斷誤差、舍入誤差2.2.數(shù)制表示數(shù)制表示1212 (),1,0,2,3,

2、ltjtxtdddxddjt (1)實數(shù) 可以表示以下形式的 進制 位有效數(shù)字12120.10 ,0.10 , 0.5 10,llttl txd ddxd ddxxxt (2)有效數(shù)字: 指一個近似數(shù)的有意義的數(shù)字的位數(shù) 若 如果 則稱 有 位有效數(shù)字1( , , ,) 2(1)(1) 1tFt L UUL(3)浮點數(shù)系:表示為數(shù)的個數(shù):lU上溢:lL下溢:編輯ppt第第1章章 緒論緒論3.3.舍入誤差舍入誤差: :對數(shù)進行舍入，得到有對數(shù)進行舍入，得到有t t位尾數(shù)的浮點數(shù)位尾數(shù)的浮點數(shù)( ): ( )xfl xxx相對舍入誤差11( )2tx123:()(1-)() ()(1-)() (

3、)(1-)( )fl xyxyfl xyxyxxflyy性質浮點運算的注意事項浮點運算的注意事項(1)避免產(chǎn)生大結果的運算，尤其是避免小數(shù)作為除數(shù) 參加運算；(2)避免“大”“小”數(shù)相加減；(3)避免相近數(shù)相減，防止大量有效數(shù)字損失；(4)盡可能簡化運算步驟，減少運算次數(shù)。)(xfl編輯ppt第第1章章 緒論緒論5.5.方法的穩(wěn)定性方法的穩(wěn)定性數(shù)值穩(wěn)定:若初始誤差導致最終解的誤差能被有效地控制6.6.算法算法由有限個無二義性法則組成的一個計算過程數(shù)值不穩(wěn)定:若初始誤差導致最終解的誤差不能被有效地控制4.4.問題的性態(tài)問題的性態(tài): :問題的解對原始數(shù)據(jù)擾動的敏感性問題的解對原始數(shù)據(jù)擾動的敏感性病

4、態(tài)問題:輸入數(shù)據(jù)相對小的擾動引起解的相對大的變化良態(tài)問題:輸入數(shù)據(jù)相對小的擾動不會引起解的相對大的變化,( )( ) ( )supxf xf xcond fx條件數(shù):當輸入數(shù)據(jù)具有的誤差 引起問題的結果誤差為則算法的特點,描述編輯ppt第第1章章 緒論緒論112.718281828,2.71828325, 6 xxx例.則 的有位有效位數(shù)( )2.71828225,fl x 若則有 7 位有效位數(shù)(10,5,-2,3)F例.在中有多少個數(shù)?33661) ,)11 38,19601 6930 8,19601 6930 83833- 8例.下列各式均與等價,在浮點數(shù)系F(10,5,-10,10)中

5、3+ 8 哪個公式能獲得最準確的結果:(17-6 8(17+6 8編輯ppt第第1章章 緒論緒論1-( , , ,),-( )1( )( )2tFt L Uxfl xxxx例.證明在浮點數(shù)系中 浮點數(shù)的相對誤差 滿足,.)3 , 2(0 ,1 ,)(:11133221jddddddxjltt其其中中設設證證明明 211 td若若lttddddxfl )()(33221有有l(wèi)ttdxflx 11)(此時此時lt 121tl 21lxd 1,1 1有有由由于于txxflx 121)( 編輯ppt第第1章章 緒論緒論 211 td，若若同理同理lttddddxfl )1()(33221有有l(wèi)ttdx

6、flx 11)(lt 121tl 21lxd 1,1 1有有由由于于txxflx 121)( 編輯ppt第第1章章 緒論緒論2334610-1-1-1yxxx例.為了使計算的乘除法次數(shù)盡可 能少,應該式如何計算:_21610 xx 例.在浮點數(shù)系下,計算的兩個根,應如何 計算才能使精度較高？( ),( )f xf x例.對于函數(shù)在某個區(qū)間上連續(xù)可微 則求的近似條件數(shù)編輯ppt第第2章章 線性代數(shù)方程組線性代數(shù)方程組,LULDUGGGauss解法列主元Gauss解法數(shù)值解法矩陣分解法:分解分解 分解 追趕法Jacobi迭代法迭代解法Gauss-Seide線性方l迭代法程組解法32:(),: ()

7、o nnsoGaus消去的時間復雜度回代消去法32:(),: ()o nGasnsou消去的時間復列主元消去法雜度回代3:,:,()LUoUnL:單位下三角陣上三角陣 時間復雜度分解3:,:,()3nLDULDUo:單位下三角陣對角陣,單位上三角陣 時間復雜度分解3(/6),oGnGn:分針對對稱正定矩陣,加 個解開方運算:三對角陣分帶狀矩陣分解解,追趕法編輯ppt第第2章章 線性代數(shù)方程組線性代數(shù)方程組范數(shù):方程組的條件數(shù):*1*xxbbAAbx(1)當右端向量有擾動 *( )xxxAACond AAxx(2)當系數(shù)矩陣有擾動 1, 1( )AbxxbAkAxbAkAkcond AAA(3)

8、當系數(shù)矩陣有擾動右端向量有擾動 其中-1( )mcond AA A定義,性質.向量與矩陣范數(shù)的相容性,等價性編輯ppt第第2章章 線性代數(shù)方程組線性代數(shù)方程組(1)( )kkxGxd迭代:構造,算法判斷收斂-111()GDEFID AdD bJacobi:-11()()GDEFdDEbGauss-Seidel:收斂性判定定理,AJacobiTH2.7 為嚴格對角占優(yōu)格式收斂,-AGauss SeidelTH2.8 為嚴格對角占優(yōu)格式收斂,-;2-,AGauss SeidelD AJacobiTH2.9 對稱正定收斂對稱正定收斂(1)( )1kkxGxdGTH2.10 迭代格式收斂的充要條件為

9、(TH2.11 迭代格式的誤差估計1,TH2.6 G則迭代格式收斂編輯ppt第第2章章 線性代數(shù)方程組線性代數(shù)方程組11,_,_,_01004AAA11-12例:矩陣A=則113121:12,1,TAaGGGaaa例 若矩陣可以分解為的形式 其中 為下三角陣且對角元均為正 問 的取值范圍 并請按此要求將此 分解36, 37PP編輯ppt第第2章章 線性代數(shù)方程組線性代數(shù)方程組1231231235210:242252465-xxxxxxxxxJacobiGauss Seidel 例 考查方程組 的迭代格式,格式的收斂性.123123123:(,) ,2323Txxxxxxxxxx例 設則是否是范

10、數(shù), 是否是范數(shù)要證明是否是范數(shù),應驗證是否滿足范數(shù)的三個條件.(P79,14題)要否定一個范數(shù),只需要舉一個反例編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似LagrangeNewtonHermit多項式插值插值連續(xù)多項式插值插值插值多項式插值分段一次插值分段多項式插值 分段二次插值分段三次樣條插值最小二乘近似數(shù)據(jù)近似編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似多項式插值0( )( )nniiiL xl x yLagrange 插值 0( )( ) ( )()()( )niiiiixl xxxxxxxTH 3.1 經(jīng)過給定插值點的插值多項式唯一( )( )( )nnf xpxR xLagrange插值基本

11、多項式的性質0, ()1, ijijl xij0( )1niil x編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似001001201012011 ( ),(),()() + ,()()()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 計算帶導數(shù)條件的插值多項式 利Herm用差商性質2,使用插值多項式的思想it插值進行構造( )1( ) ,.,!kiiiikyxy

12、x xxk 個 編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似插值多項式的誤差 3.2 ( )( )-( )nnTHR xy xP x(P97)(1)0( )( ) , (1)!nnyxx xn01,., ( )ny x xxxx編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似分段插值多項式2122113.3() max( ) max8iia x biTHE gMMyxxx 分段一次多項式的誤差 3233113.4() max( ) max12iia x biTHE gMMyxxx 分段二次多項 式的誤差 222113.5( )- ( ) max( ) max2iia x biTHy xs xMMy xxx 分

13、段三次樣條插值多項式的誤差 編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似最小二乘法1112111112112122222122221212( )( )( )()()() ()()()nnnnnnnnnnmmnmTTaaabg xgxgxaaabg xgxgxGaaabg xgxgxG GaG y得到方程組或法方程 12,(1,2,.,)( )(1,2,., ),.,(),iiknx yimgx knmn 給定數(shù)據(jù)點和一組函數(shù)求系數(shù)假定使函數(shù)1,.()TTaG GG y可以證明 最小二乘問題的法方程總有解存在QR分解 RQGO TRGQO22222Eh11221/2221( )( )( )( ) (

14、( )nnmiiip xg xgxgxEp xy 滿足達到最小編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似(4)( ),( )( ),( )( ),( )11, 2,( )12 ( )13( )11iiiip xp xf xp xfxfxxp xxf xfx 例.求不超過三次的多項式滿足條件若求的誤差界01210101000122010101( ) , ,()(2)()()() ( )()()( )()()( )( )( )f xa bxxa bxxxxxxxxxxxp xf xfxf xxxxxxxR xf xp x 例.設在區(qū)間上有三階連續(xù)導數(shù),有相應的插值多項式試求此插值多項式的余項的表達式編

15、輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似.( ),0,1,2,., ,(,()1( ),( )()()1(1)kkkknnnkkknxf xxnxf xxxpxpxpxf xxp n例設取以為插值數(shù)據(jù)點 做插值多項式則滿足 試求534( )2009200720062005,2, 1,0,1,2( )_f xxxxL x例.設則以為 插值節(jié)點的不超過四次的插值多項式32( )2001200220012000,3,4,550,3,5,1002,3,4,5,_f xxxxfmfmfm例.設則以則編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似01010,.,( ) ,.,( )nniniix xxf xf x x

16、xx例.設節(jié)點互異 試證明0100,.,( )( )( ) ( )( )()( )nnniiiiiiix xxLagrangexL xl x f xf xxxx解:由節(jié)點互異 則插值多項式為0( )( )()( )niiiif xxxxx0( )( )niif xx因此,該多項式最高項的系數(shù)為:0100100120101011,.,( ),(),()(),()()()nnnx xxNewtonN xyy x xxxy x x xxxxxy x xxxxxxxx另一方面,由節(jié)點形成的插值多項式為01,ny x xx該多項式最高項的系數(shù)為:因此得證編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似1010(0

17、,1, ),(0)( 1)( )nnniiiniixinlxx xxl xLagrange 例.設為互異實數(shù) 試證明其中為插值多項式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例.給定以下的數(shù)據(jù)點,利用插值多項式,計算在 到 之間的根的近似值編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似-

18、4664( )1.060.5671.43 1.77( )sincosxf xp xAxBx例.已知函數(shù)f(x)有以下測試數(shù)據(jù)求形如最小二乘近似12( )sin ,( )cosg xx gxx令0.7070.7071.060.50.8660.567,0.50.8661.430.7070.7071.77TTGyGay得 得法方程GG編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似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.43

19、1.77AB1.500302.501.25AB即 2.00 .500AB解得( )2sin0.5cosf xxx因此編輯ppt第第3章章 數(shù)據(jù)近似數(shù)據(jù)近似( )01.4452.8904.3355.780 1.84192.963318.23698.7410529.2178( )xf xxyp xe例.已知函數(shù)有以下測試數(shù)據(jù)求形如的最小二乘近似函數(shù)( ) ln( )lnp xp xx解:對兩邊求對數(shù),有( )ln( ),ln, ( )f xp xABf xABx令則最小二乘函數(shù)變?yōu)?1.4452.8904.3355.780 ln0.61071.08632.90344.59256.2714xy相應的

20、數(shù)據(jù)構造法方程. 下略編輯ppt第第4章章 數(shù)值微積分數(shù)值微積分(1)-(3)(5)()()()mNewton CotesSimpsonmCotesmSimpsonCotes梯形公式 公式公式公式 等距結點復化梯形公式 二階復化求積公式 復化公式 四階復化公式 六階不等距結點:GaTh 數(shù)值積4.9uss型求(構造方法積公式,利用正交多項) TH 4.11 式進行構TH4.造 12 分 Romberg積分:利用低精度的求積公式,構造高精度的公式待定系數(shù)法:利用代數(shù)精度的定義求得最 4-39計算系數(shù) 4-4高代數(shù)精度的求積公式0計算誤差135.47 4.1PTh136.48 4.2PTh136.

21、49 4.3PTh140.4 13 4.4PTh140.4 14 4.5PTh140.4 15 4.6PTh編輯ppt第第4章章 數(shù)值微積分數(shù)值微積分01001110102001221022011()()()( )()2 (P178)11()()()( )()21()3 ()4 ()()( )231()()()( )261()(2fxf xf xfxxhfxf xf xfxxhhfxf xf xf xfhhfxf xf xfhfxf xh兩點公式一階導數(shù)公式三點式微公數(shù)值分2122(4)00121222(4)101222(4)2012122 (P179)4 ()3 ()( )31()()2 (

22、)()()()61()()2 ()()( )121()()2 ()()()()6hf xf xfhfxf xf xf xhffhhfxf xf xf xfhhfxf xf xf xhffh二階導數(shù)公式 (P180)Taylor待定系數(shù)法:利用公式可求得最高計算精度的微分公式編輯ppt第第4章章 數(shù)值微積分數(shù)值微積分.( )()2baabf x dxba f例試導出中矩形公式,并給出其誤差公式 20120.( )(0)( )(2 )hf x dxA fA f hA fh例確定以下公式中的系數(shù),使其具有盡可能高的代數(shù)精度 (1) 1123111( )()(0)( )22f x dxA fA fA

23、f (2) 111221( )()()f x dxA f xA f x (3) 編輯ppt第第4章章 數(shù)值微積分數(shù)值微積分 100.( ) , ( ),(0,1,2,., )( ), ( ). ( ) ( )().: (1) 0,()()kiniinbkkaknikijiixa bxx inxl xxLagrangex f x dxA f xk jn kjAxx例例設設是是定定義義在在區(qū)區(qū)間間上上的的關關于于權權函函數(shù)數(shù)的的正正交交多多項項式式族族 并并且且是是的的零零點點是是以以為為插插值值點點的的插插值值基基函函數(shù)數(shù)是是高高斯斯型型求求積積公公式式證證明明當當時時200 (2) ( ) (

24、 ) ( )0, (3) ( ) ( )( )bkjanbbkaakx lx lx dxkjx lx dxx dx編輯ppt第第4章章 數(shù)值微積分數(shù)值微積分0001020.()()()(2 )fxA f xA f xhA f xh例確定如下的數(shù)值微分公式的系數(shù),使其對盡可能高次的多項式精確成立 并給出誤差表達式1102488.( )0.45675,0.47117,0.47446,0.47612,_f x dxSSSSS例按照復化Simpson公式計算的數(shù)值微分值為則 的誤差近似為編輯ppt第第5章章 非線性方程求解非線性方程求解(1)( )( )(1)( )( )( )( -1)(1)( )(

25、 )( )( -1) ()() -()- -()()-()kkkkkkkkkkkkkxxf xNewtonxxfxxxxxf xf xf x簡單迭代法迭代法迭代法非線性方程求解割線法區(qū)間法:二分法5.1 (1) , , ( ) , (2) ( )- ( ) 01 5.2 ( )1THxa bxa bxyq xyqTHxs 簡單迭代法的收斂性 *1(),( )( )1xxxx取構造收斂性的改善 編輯ppt第第5章章 非線性方程求解非線性方程求解Newton迭代格式的收斂性(1)*( )*lim0,kpkkxxpxx若 則稱收斂速度收斂速度 為 階收斂005.4(1)( ) ( )0 (2) (

26、),( )0 (3) ( )(4)()()0THf a f bfxfxfxf xfx 不變號 且不變號 簡單迭代格式收斂速度為線性收斂牛頓迭代格式收斂速度為二階收斂割線法收斂速度為超線性收斂二分法收斂速度為線性收斂編輯ppt第第5章章 非線性方程求解非線性方程求解*( )()0f xfx當兩次可微且,迭代函數(shù)滿足( )*,kNewTonxx因此 當?shù)蛄惺諗坑?時,有()kkq 記lim()kk 由于0于是有*( )(5-25)kxx稱滿足條件并收斂于 的序列為超線性收斂的NewTon法為超線性收斂的(1)*( )*( )*(),kkkkkxxxxxx 是與 之間的某個數(shù)(1)*( )* (

27、5-25)lim0kkkkkxxq xxq*()x可知該格式的收斂速度要比簡單迭代格式快一些方法方法Newton0)(* x 編輯ppt第第5章章 非線性方程求解非線性方程求解由于( )( )( )( )()()( -)kkkl xf xfxx x( )( )( )()()( -)0kkkf xfxx x因此*( )( )*( )*( )210()()()(-)()(-)2kkkkkf xf xfxxxfxx( )( )(1)( )0()()(-)kkkkf xfxxx兩式相減( )(1)*( )21()(-)()(-)2kkkkfxxxfxx*( )()0,fxfx由于連續(xù)且( )*,kxx

28、k當收斂于 時 對充分大的( )()0kfx總有從而(1)*( )2( )()1(-)2()kkkkfxxxxfx編輯ppt第第5章章 非線性方程求解非線性方程求解( )()1max2()kkfqfx若令2(1)( )( )(*) (5-26)kkkxxq xx則有 (*)( )kxx稱滿足條件式(5-26)的收斂于的序列稱為二階收斂的Newton法為二階收斂的同時,可以得出割線性是超線性收斂(1)*( )2( )()1(-)2()kkkkfxxxxfx編輯ppt第第5章章 非線性方程求解非線性方程求解322)(,/11)()1(: xxxx 解解討討論論迭迭代代格格式式附附近近有有根根在在方

29、方程程,5 . 101*23xxx 的收斂性的收斂性2)()1(/11kkxx 58. 1 , 4 . 1取取區(qū)區(qū)間間41. 1)58. 1(,51. 1)4 . 1( 0)( x， 在在此此區(qū)區(qū)間間上上單調減單調減則則)(x 06)(4 xx 5071. 0)58. 1(,7288. 0)4 . 1( 1)( x 可知可知迭代格式收斂迭代格式收斂改善迭代格式改善迭代格式)2(59259. 0)5 . 1( 取取 xxxxx59259. 01159259. 011)(11)(2 構構造造迭代格式收斂迭代格式收斂編輯ppt第第5章章 非線性方程求解非線性方程求解lim222222k試用迭代法明例

30、原理證 .(1)( )(0)2,0( )2,2( )0kkxxxxxxx 解: 構造迭代格式 則當時,1( )0,( )2 2xxx即單調增( )202x5/21( )04(2)xx *0,2,( )0,2,( )15.2xxxThx考慮區(qū)間有由知,對任何初始點 迭代格式都收斂于不動點*2,2xxx由方程知其不動點( )x單調減( )2kx因此,編輯ppt第第6章章 常微分方程數(shù)值解法常微分方程數(shù)值解法221 ( ,) ( , )( )()2iiiiiihEuleryyhf t yE t hyo h公式22111 (,) ( , )( )()2iiiiiihEuleryyhf tyE t hy

31、o h后退公式11( )( , ( )( )()( , ( )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.數(shù)值微分法數(shù)值微分法2.2.數(shù)值積分法數(shù)值積分法5(5)5( , )( )()90iihE t hyo h 編輯ppt第第6章章 常微分方程數(shù)值解法常微分方程數(shù)值解法2(

32、2)1011 ( , )( )kkiiiiki kiihyyb fb fb 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.待定系數(shù)法待定系數(shù)法1000kkjijjijjjyhf 000kkkjkjjjjjh 特征方程穩(wěn)定性、穩(wěn)定域穩(wěn)定性、穩(wěn)定域編輯ppt第第6

33、章章 常微分方程數(shù)值解法常微分方程數(shù)值解法(1)利用兩個同階公式,相同步長_1(1)1(1)111121_1111()-( ) ()-()()()ppppiiiiiiiiy tyhyy tyhyy tyyy_1111 ()iiiiy tyyy(2)利用兩個不同階公式,相同步長_11111 ()()/ 1/piiiihhy tyyyh h(3)利用同一個公式,不同的步長 和計算5.5.預估預估校正方法校正方法精精度度更更高高使使計計算算更更方方便便隱隱式式公公式式作作校校正正利利用用顯顯式式公公式式作作預預估估， 編輯ppt第第6章章 常微分方程數(shù)值解法常微分方程數(shù)值解法132112111( 9

34、375955 )24(4)()(5199 (,)24iiiiiiiiiiiiihpyffffABMhyyffff tp四階精度1321111114(22 ) 3Milne-Simpson()(4(,)3iiiiiiiiiiihpyfffhyyfff tp四階精度1111( ,)():( ,)(,)2iiiiiiiiiipyhf t yhyyf t yf tp預估:Heun方法二階精度校正編輯ppt第第6章章 常微分方程數(shù)值解法常微分方程數(shù)值解法132111111114(22)328Milne-Simpson()294(,)3iiiiiiiiiiiiiiihpyfffmpyphyyfff tm預估修正校正1321111211111114(22)3112()12113(9)2(,)889()121iiiiiiiiiiiiiiiiiiiihpyfffmpypcyyhfff tmyccp:修正Hamming預估-校正公式編輯ppt第第6章章 常微分方程數(shù)值解法常微分方程數(shù)值解法1112212221111,11( ,)(,)(,)