數(shù)值分析復(fù)習(xí)

1、ReviewChap 1 數(shù)值計算中的誤差數(shù)值計算中的誤差 誤差誤差 誤差限誤差限 有效數(shù)字有效數(shù)字 用微分計算函數(shù)值誤差用微分計算函數(shù)值誤差 計算方法的數(shù)值穩(wěn)定性計算方法的數(shù)值穩(wěn)定性誤差誤差 誤差限誤差限 有效數(shù)字有效數(shù)字1) 定義 1.1：稱 為 的絕對誤差(簡稱誤差)。( )e xxxxx設(shè) 是準(zhǔn)確值， 是 的近似值xx2) 定義 1.2：若 ，則稱 是 x 的誤差限。|xx稱單位量上的誤差 為 x 的相對誤差。( )rxxe xx3) 定義 1.3： 定義 1.4：r 若 , 則稱 是 x 的相對誤差限。|( )|rre x4) 定義 1.5： 如果近似值 x 的誤差限是它的某一位的半

2、個單位，就稱它準(zhǔn)確到這一位。若該位到 x 左邊第一位非零數(shù)字共有n 位，則稱它有n 位有效數(shù)字。5)例1.5 題1.1 用微分計算函數(shù)值誤差用微分計算函數(shù)值誤差( )( )re yeyy相對誤差( )( )( )fxe xf x( )( )( )rfxxexf x( )()( )( ) ( )e yf xf xfx e x誤差例1.9 ()yf x已知 的近似值 x ，一元函數(shù)值 的近似值為x( )yf x1)2) 已知自變量誤差( ),( ), ( )re x ex e y和( ).re y求二元函數(shù)值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 計算方法的數(shù)值穩(wěn)定性計算方法的數(shù)值穩(wěn)定性1) 求根公式的數(shù)值穩(wěn)定性2) 遞推法的數(shù)值穩(wěn)定性數(shù)值計算中應(yīng)注意的幾個原則數(shù)值計算中應(yīng)注意的幾個原則避免相近數(shù)相減 ;避免小除

4、數(shù), 大乘數(shù) ;避免大數(shù)吃小數(shù) ;采用數(shù)值穩(wěn)定的算法 ;減少運(yùn)算次數(shù).題1.9, 題1.10 題1.7 Chap 2 插值法與最小二乘法插值法與最小二乘法 多項式插值多項式插值 Lagrange Lagrange插值公式插值公式 插值余項插值余項 Newton Newton插值公式插值公式 Hermite Hermite插值插值 分段插值分段插值 三次樣條函數(shù)三次樣條函數(shù)n 次多項式插值問題：次多項式插值問題：() (0,1, )iiyf xin求作一個次數(shù)不超過 n 的多項式 ，使之滿足( )nP x()(0,1, )(2.1)niiP xyin插值條件f (x)的滿足插值條件(2.1)的n

5、次插值多項式插值區(qū)間插值節(jié)點(diǎn)( )f x已知 上的函數(shù) 在點(diǎn) , a b01naxxxb上的函數(shù)值被插值函數(shù)Lagrange插值公式插值公式 插值余項插值余項010111(),( )yPyxP x求作一個1次已知函數(shù) 在點(diǎn) 上的函數(shù)值 ， 01,xx01,yy( )f x101( )P xaa x多項式 ，使得1) 線性插值0110101011001( )( )( )xxxxP xyyyxyxxxxxll2) 拋物插值001212222(),( ),()PPPxyxyxy已知函數(shù) 在點(diǎn) 上的函數(shù)值 ，求作 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插值基函數(shù) 的性質(zhì):( )klx()(0,1,2, )kjkjlxjn 是 n 次式;( )klx0( )1nkklx題2.1 題2.2 4) Lagrange插值余項 定理2.2 ：設(shè) 的 n+1階導(dǎo)數(shù) 在 上存在，則 , (0,1, ),( )ixa binf x(1)( )(

7、 )( ) , (1)!nnfR xw xxa bn (1)( )nfx , a b0( )(), , nkkw xxxa bx其中 與 有關(guān) 。1010111, ( )( )()(), , 2nR xfxxxxx x當(dāng)時20120212, ( )( )()()(), , 6nR xfxxxxxxx x當(dāng)時 例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 差商與微商的關(guān)系( )01( ),!nnff x xxnHermite插值插值3次Hermite插值300110011( )( )( )( )( )P xx yx yx yx y3次Hermite插值基函數(shù) (插值基函數(shù)的性質(zhì)) 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次樣條函數(shù)次樣條函數(shù)1) 什么是3次樣條函數(shù), 3次樣條插值2) 比較3次多項式插值(不含導(dǎo)數(shù)條件), 分段3次Hermite插值, 3次樣條插值Chap 3 數(shù)值積分與數(shù)值微分?jǐn)?shù)值積分與數(shù)值微分 機(jī)械求積公式機(jī)械求積公式 插值型求積公式插值型求積公式 復(fù)合求積公式復(fù)合求積公式 Gauss Gauss求積公式求積公式 數(shù)值微分?jǐn)?shù)值微分機(jī)械求積公式機(jī)械求積公式0( )()nbkkakf x dxA f x求積節(jié)點(diǎn)求積系數(shù)例3.1, 題3.1

10、, 題3.2 代數(shù)精度: 若一個機(jī)械求積公式對準(zhǔn)確成立,但對1( )mf xx不準(zhǔn)確成立, 就說它具( ),(0,1,)jf xxjm有m次代數(shù)精度.利用代數(shù)精度定義構(gòu)造求積公式題3.11插值型求積公式插值型求積公式0( )()( )nbbkkaakf x dxf xlx dx1) 求積系數(shù)( ).bkkaAlx dx2) 求積系數(shù)具有 n+1個求積節(jié)點(diǎn)的插值型求積公式至少具 有 n 次代數(shù)精度.3) 中矩形公式、梯形公式、Simpson公式是插值型求積公式 (各自的代數(shù)精度).4) Newton-Cotes公式: 一類節(jié)點(diǎn)等距分布的插值型求積公式.( n為奇數(shù)時, 代數(shù)精度為n; n為偶數(shù)時

11、, 代數(shù)精度為n+1)梯形公式余項31()( ),12baITfa b1( )( ) ,2baTf af b12( )4( ) .6abbaSf aff b記Simpson公式余項5(4)1()( ),2880b aISfa b復(fù)合求積公式復(fù)合求積公式 (復(fù)合求積的思想)1) 復(fù)合梯形公式11( )( )2()( )2nbknakhf x dxf af xf bT復(fù)合梯形求積公式的余項為2( )( )12nhITfbfa 2) 復(fù)合Simpson公式121110( )( )2()4()( )6nnbknkakkhf x dxf af xf xf bS復(fù)合Simpson求積公式的余項為4(3)(

12、3)1( )( )1802nhISfbfa 題3.5, 題3.6Gauss求積公式求積公式1) 什么是Gauss求積公式?2) Gauss點(diǎn)的性質(zhì)?1( )()nniiL xxx 定理定理3.4： 是Gauss點(diǎn)的充分必要條件是以 為零點(diǎn) 1nix的多項式 與所有次數(shù)不超過 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數(shù)值微分?jǐn)?shù)值微分 在點(diǎn) a 處以 h 為步長的向前差商 ()( )f ahf ah( )f x( )()f af ahh( )f x()()2f ahf

13、ahh 在點(diǎn) a 處以 h 為步長的向后差商 ( )f x 在點(diǎn) a 處以 2h 為步長的中心差商 例3.111) 中心差商公式2) Richardson外推例3.12Chap 4 方程求根方程求根 不動點(diǎn)迭代法不動點(diǎn)迭代法 Newton Newton迭代法迭代法 簡化簡化NewtonNewton迭代法迭代法 弦截法弦截法 NewtonNewton下山法下山法不動點(diǎn)迭代法不動點(diǎn)迭代法1)( )0( )f xxx( )0f x ( )xx求 的根等價于求 的不動點(diǎn) 2) 不動點(diǎn)迭代格式 1(),0,1,2,(4.5)kkxxk3) 迭代收斂條件 定理 4.1：設(shè) 是閉區(qū)間 上的壓縮函數(shù)，則 在

14、中有唯一不動點(diǎn) ，且對任意 , 迭 代公式(4.5)都收斂 . (全局收斂) , a b( )x , a b( )x*x0 , xa b 推論 ：設(shè) ，且 1( ) , xC a b( ), , xLx ya b(0,1)L1) 總有 ; , xa b ( ) , xa b2) 存在 ，使則定理4.1結(jié)論成立 . (全局收斂) 定理 4.3：設(shè) 在其不動點(diǎn) 附近有連續(xù)一階導(dǎo)數(shù)，且 則存在 的某個領(lǐng)域 ，( )x* :|xxx *|()| 1,x*x0 x*x使得 , 迭代(4.5)均收斂. (局部收斂)迭代不收斂的條件 題4.44) 迭代收斂速度記 , 若 ，且存在正常數(shù) ，使*kkexx 定

15、義 4.3：1p 0ke 1lim(0)kpkkeCCe, 則稱(4.5)為 p 階收斂的.1p若 ，則稱(4.5)是線性收斂的；若 , 則稱(4.5)是平方收斂的.2p 定理 4.4：若 在 的根 鄰近有連續(xù)的 1階導(dǎo)數(shù)， 且 , 則當(dāng) 時迭代公式(4.5)為線性收斂 . 若 在 鄰近有連續(xù)的 2 階導(dǎo)數(shù)，則當(dāng) 時迭代公式(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單根，則當(dāng) 時(4.11)平方收斂 .( )f xx 定理 4.5：設(shè) 在 鄰近二次連續(xù)可微， 是 的( )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、代數(shù)方程組數(shù)值解法線性代數(shù)方程組數(shù)值解法 迭代法迭代法 迭代法的收斂性迭代法的收斂性 Gauss Gauss消去法消去法 矩陣的矩陣的LULU分解及應(yīng)用分解及應(yīng)用 方程組的條件數(shù)與誤差分析方程組的條件數(shù)與誤差分析迭代法迭代法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 進(jìn)行分解 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證明：假設(shè)SOR方法收斂，則有()1BB12,n 設(shè) 的特征值為 ，則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 ：設(shè)G 是(5.18)的迭代矩陣，且它的某一種范數(shù)滿足 ,

20、 則對任意的初值 ，迭代公式(5.18)均收斂 .| 1G (0)nxR例5.5定理5.4 ：設(shè) A 嚴(yán)格對角占優(yōu)，則其 Jacobi 迭代公式和Gauss- Seidel 迭代公式均收斂 .例5.7 題5.2 定理：定理：設(shè) 對稱正定,且 ,則解 的SOR方法收斂.02n nARAxb1()(1)GDLDU證明：SOR迭代法的迭代矩陣為設(shè) 是G的一個特征值，相應(yīng)的特征向量為 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故當(dāng) 時 , SOR方法收斂.02| 1特別的, 當(dāng) 時 , SOR方法就是GS方法, 從而當(dāng)A是對稱正定矩陣時, GS方法收斂.1Gauss消去法消去法1) 順序Gauss消去法2) 列主元Gauss消去法例5.8 題5.7例5.10 題5.7矩陣的矩陣的LU分解及應(yīng)用分解及應(yīng)用 A = L U , 其中L是單位下三角陣, U是上三角陣1) 計算矩陣行列式2) 解方程組3) 求矩陣的逆例5.11 題5.9方程組的條件

22、數(shù)與誤差分析方程組的條件數(shù)與誤差分析 定義5.7: 稱數(shù) 為矩陣 A 的關(guān)于解方程 1 組 的條件數(shù).1( ) | |cond AAAAxb11111( )| | ,( )| |condAAAcondAAA例5.13 題5.10 設(shè) x 是方程組 的精確解, y 是其近似解. 稱Axb為y 的剩余向量, 則成立不等式rbAy| |( ).| | |xyrcond Axb(定理5.7)當(dāng)方程組良態(tài)時, 可以用 來估計近似解 y 的誤差.| |rChap 7 常微分方程初值問題數(shù)值解法常微分方程初值問題數(shù)值解法 Euler Euler法法 改進(jìn)改進(jìn)EulerEuler法法 Runge-Kutta Runge-Kutta法法 收斂性與穩(wěn)定性收斂性與穩(wěn)定性(7.1)(7.2)數(shù)值求解一階常微分方程的初值問題 :000( ,)()dyf x yxxbdxy xy1(,)nnnnyyh f xyEuler公式 :(步進(jìn)式, 單步方法, 顯式格式)記 , 則Euler公式的*1()(,()nnnnyy xhf xy x局部截斷誤差 :2*2111()( )(),2nnnnhy xyyO hxx總體截斷誤差 :11()( )nny xyO h(Euler法是1階方法)Euler法的三種分析解釋: 差商逼近微商,數(shù)值積分