數(shù)值計(jì)算方法復(fù)習(xí)提綱

1、數(shù)值計(jì)算方法復(fù)習(xí)提綱第一章數(shù)值計(jì)算中的誤差分析1 了解誤差及其主要來源，誤差估計(jì);2 了解誤差(絕對誤差、相對誤差)和有效數(shù)字的概念及其關(guān)系;3 掌握算法及其穩(wěn)定性，設(shè)計(jì)算法遵循的原則。1、誤差的來源模型誤差觀測誤差截?cái)嗾`差舍入誤差2誤差與有效數(shù)字絕對誤差E (x) =x-x絕對誤差限XXX相對誤差Er (X) (X X*)/X (X X*)/X*有效數(shù)字x0.a1a2.an 10m*Im n*若x X -10 ，稱X有n位有效數(shù)字。2有效數(shù)字與誤差關(guān)系(1)m 一定時(shí)，有效數(shù)字n越多，絕對誤差限越小;(2)X有n位有效數(shù)字，則相對誤差限為Er(X)12a110(n 1)選擇算法應(yīng)遵循的原則1

2、、選用數(shù)值穩(wěn)定的算法，控制誤差傳播;例1 n11 n x .x e dxe 0In 1n 1 n 11011eXnn!叫1廠嚴(yán)脈二-列嚴(yán)-巴知“嚴(yán)aa j2、簡化計(jì)算步驟，減少運(yùn)算次數(shù)；3、避免兩個(gè)相近數(shù)相減，和接近零的數(shù)作分母;避免第二章線性方程組的數(shù)值解法1 了解Gauss消元法、主元消元法基本思想及算法；2 掌握矩陣的三角分解，并利用三角分解求解方程組；（Doolittle 分解；Crout分解；Cholesky 分解；追趕法）3 .掌握迭代法的基本思想，Jacobi迭代法與Gauss-Seidel迭代法;4 .掌握向量與矩陣的范數(shù)及其性質(zhì)，迭代法的收斂性及其判定。本章主要解決線性方程組

3、求解問題，假設(shè)n行n列線性方程組有唯一解，如何得到其解？a1 Xax?a1nXnb1a?1 xa?2 X2.a2n Xnb2an 1X1an2X2.annXnbn兩類方法，第一是直接解法，得到其精確解；第二是迭代解法，得到其近似解。Gauss消去法 1、順序G auss消去法記方程組為:(1)a；1 X1(1)a?1 X(1) a2 X2(1) a?2 X2a1(?Xna2n Xnbby(1)an1 X1(1)an2 X2(1)ann Xnbn1)a22)X2b1(1)b22)消元過程: 經(jīng)n-1步消元，化為上三角方程組小(1)a1 X1(2) a 21 X1an；）X1an；）X2ann)x

4、nbnn)若 akk)0(k)Jk 1)3aikJk)aijaijakk)akj回代過程:b(k 1)(k)b(k)爲(wèi)匕律akkk1,.n1 i, j k1,., nXi(n)(n)bn / ann(i)Xn(iin 1, n 2,.1)2、G auss Jordan 消去法避免回代，消元時(shí)上下同時(shí)消元3、G auss列主元消去法例：說明直接消元，岀現(xiàn)錯(cuò)誤0.00001x1X12x22x23由順序G auss消去法，得X21,X10 ;G auss列主元消去法原理： 每步消元前，選列主元，交換方程。算法：將方程組用增廣矩陣A Mbaij表示。n(n 1)(1)消元過程:對 k=1,2,n-1.

5、選主元，找ik k,k 1,n使得a,k max ak如果aik,k 0，則矩陣a奇異，程序結(jié)束；否則執(zhí)行 3如果ik k，則交換第k行與第ik行對應(yīng)的元素位置，akjaikj,j k,ggg n 1.消元，對i=k+1, L ,n,計(jì)算 likL ,n+1,計(jì)算aij aij lik akj(2)回代過程: 1 若ann 0,則矩陣a奇異，程序結(jié)束；否則執(zhí)行Xi,2,1,計(jì)算舉例說明。4、消元法應(yīng)用(1 )行列式計(jì)算;(2 )矩陣求逆二、利用矩陣三角分解求解線性方程組1、求解原理線性方程組寫成矩陣形式為：AX=b若 A=LU，貝U LUX= b，記 UX=Y則 LY= b若L、U為特殊矩陣，

6、則求解線性方程組變?yōu)榻鈨蓚€(gè)特殊線性方程組問題。2、Doolittle 分解L為下三角矩陣，U為上三角矩陣，不一定能分解，分解也不一定唯一；設(shè)L或U是單位三角矩陣，若能分解，則可分解唯一.L是單位下三角矩陣，稱為Doolittle 分解；U是單位上三角矩陣，稱為Crout分解；定理：n階矩陣A有唯一分解的充要條件為A的前n-1階主子式都不為0.Doolittle分解算法:a11a12 .a1n1U11 U12 .U1 na21a22 .a2nl211U22 .U2nan1an2.annl n1l n2.1Unn由矩陣乘法：naijlikUkjk 1得到：k 1Ukjakjl krUrjjr 1k

7、, k 1,.n;k 1l ik(aiklirUrk ) /Ukki k,k 1,.nr 1算法特點(diǎn)：先計(jì)算U的行，再計(jì)算L的列，交替進(jìn)行；存儲(chǔ)時(shí)可用緊湊格式。矩陣分解后，解兩個(gè)三角方程組：LY= b，UX=Yyibii 1yibi hyki 2,3,.nk 1nXi(yiUikXk)/Uiii n,n 1,1k i 13、Crout 分解若L為下三角矩陣，U是單位上三角矩陣，則稱 Crout分解；算法特點(diǎn)：先計(jì)算L的列，再計(jì)算U的行，交替進(jìn)行。4、正定對稱矩陣的平方根法(Cholesky分解)(1)正定對稱矩陣性質(zhì)與判定：定義：是n階對稱矩陣，若對任意非零向量XRn，有XT AX 0 ,則稱

8、A為正定對稱矩陣;判定：A為n階正定對稱矩陣充要條件 A的各階順序主子式大于 0。(2) Cholesky 分解定理：設(shè)A為n階正定對稱矩陣，則存在唯一主對角線元素都是正數(shù)的下三角陣L,使得A LLT.a11a12 .a1nl11a21a22 .a2nl 21l22Cholesky分解算法:ll 11 l121nl22. l2nan1 an2annl n1ln2l nnl nnj 11ljj (ajj l2k)2k 1j 1l ij (aijl ik l jk ) / l jjk 1j1,2,n;i j 1,j2,.n5、追趕法三對角矩陣的特殊分解b|c1a2 b2C2a3b3C3an 1bn

9、 1cn 1anbnXiXn(yi Ci Xi 1)/Uiyn / Un1 u1c11 21U2C2I31. un 1 Cn-1In 1Unu1b1li ai /ui 1 i2,3,.nUi b1 ici 1三對角方程組的追趕法: 追的過程LY=D% d1yidili yi 1 i2,3,.n趕的過程UX=Y2線性方程組的迭代解法例：11X1 x22211X1x222Jacobi迭代公式其解為 X11, X2方程變形得到迭代公式(k 1)1(k)1X1X2022給初值X(O)計(jì)算，觀察解的變化。x2k 1)1 v(k)10X122一般地，對線性方程組a1 X1&12X2a1nXnb1821X1

10、&22X2a2nXnb2an1 X1an2 x2ann xn若an0,則可從第i個(gè)方程中解出Xi,得到Jacobi迭代公式:x；k 1) (ba12x2k)amxnk)/aii(k 1) x( 1(bi(k) aiixainxn ) /aii(kxni)(bn(k)(k) 、 /an1 xi . annxn 1 ) / ann簡記為：n(k 1)(k)、斤)(biajXj )/aHi 1,2,.,nj ij iGauss-Seldel 迭代公式xi(k1)(bii 1(k 1)aij Xjj 1jnaij xj ) / aiii 1三、SOR迭代公式四、迭代公式的矩陣表示X(k 1) GX (

11、k) D3 迭代公式的收斂性一、向量與矩陣的范數(shù)與性質(zhì)1、向量范數(shù)定義：向量XRn，對應(yīng)非負(fù)實(shí)數(shù)|x|，滿足三條件:（1） 非負(fù)性| X0, X O,|x 0（2） 齊次性|kX|k|x|（3）三角不等式 l|X Y|X|Y|稱 |X| 為向量范數(shù)2、常見向量范數(shù)1 范數(shù)|xhx1x2.xn2 范數(shù)X 2: X；X；.X；a范數(shù) | XmaxXiI n3、矩陣范數(shù)定義：方陣A R n ,對應(yīng)非負(fù)實(shí)數(shù) A，滿足三條件:(1) 非負(fù)性| A 0, A 0,制 0(2) 齊次性 |k|k|A(3)三角不等式A B A |B(4)絕對值不等式AB A B稱| A為矩陣范數(shù);向量范數(shù)與矩陣范數(shù)相容性：|

12、 AX AX4、常見矩陣范數(shù)n1范數(shù)，列范數(shù)：| A1 max aIjj n I 18范數(shù)，行范數(shù)max1 I n jaij2范數(shù)，譜范數(shù) ：n nF 范數(shù)：IIAIfJa2V I 1 j 1舉例計(jì)算迭代公式收斂性的判定1、向量的極限2、矩陣的譜半徑：(A) max Ii為特征值；3、收斂性的判定收斂的充要條件：迭代公式X (k 1)GX (k) D收斂的充要條件為譜半徑判定定理1 :若IG 1,則迭代公式X (k 1) GX (k) D收斂。判定定理2 :(G)1。若對方程AX=b的系數(shù)矩陣A為對角占優(yōu)，則Jacobi迭代公式，Gauss-Seidel迭代公式收斂;判定定理3 :若對方程AX

13、=b的系數(shù)矩陣A為對稱正定，則 Gauss-Seidel迭代公式收斂；Jacobi迭代公式收斂與Gauss-Seidel迭代公式收斂關(guān)系舉例：第三章非線性方程的數(shù)值解法1 了解二分法的原理與算法；2 .掌握一般迭代法的基本思想及其收斂性判定；3 .掌握Newt on切線法、弦截法，并用它們求方程近似根的方法。本章問題：求方程f(x)=0的根 二分法一、根的存在性定理：函數(shù)f(x)在區(qū)間a，b連續(xù)，且f(a).f(b)0,則方程f(x)=0在區(qū)間a，b有根。方程的根存在，不一定唯一，若在區(qū)間a，b上有唯一根，稱區(qū)間a，b為根隔離區(qū)間。二、二分法(區(qū)間逐次分半法)原理：通過計(jì)算根隔離區(qū)間中點(diǎn)，將區(qū)

14、間分半，縮小區(qū)間，得到方程近似根數(shù)列Xn。ka,b ai ,bi.an,bn. bk ak （b a）/2取 x （an bn ）/2迭代法一、迭代原理迭代法是一種逐次逼近法，由提供的遞推公式計(jì)算，逐次精確，直到滿足精度要求。方程f（x）=0變形為x （X），得到遞推公式Xk 1 （Xk）簡單迭代公式稱（X）為迭代函數(shù)給初值計(jì)算，得到數(shù)列Xn，若 lim Xk X*，則稱迭代收斂，否則發(fā)散。K1例：X*求方程 10 X 20 X 0.3,0.4寫出兩個(gè)簡單迭代公式：（1）Xk 1 10Xk 2（2）Xk 1lg（Xk2）觀察計(jì)算得到數(shù)列Xn的收斂性。迭代法的幾何解釋：二、迭代收斂性判定收斂性定

15、理：設(shè)方程 X （X）的迭代函數(shù) （X）在a，b滿足：（1 ）當(dāng) X a,b時(shí)，（x）a,b；(2)(x)在a, b可導(dǎo)，且(x) L 1, x a,b,則(1)方程x (x)在a , b有唯一根x ;（2 ）迭代公式Xk 1(Xk)收斂，即 |jm Xk x ；（3 ）誤差估計(jì)XLkXk X1Xg。1 L說明可根據(jù)迭代函數(shù)（x）的導(dǎo)數(shù)判斷迭代收斂性。三、迭代公式的加速3 Newt on 迭代法Newt on 切線公式 幾何作法迭代公式Xk 1 Xkf(Xk)f(Xk)例：利用解二次方程x2 c 0,推導(dǎo)近似計(jì)算.c的公式。由Newton 切線公式 Xk 1cXk三、Newt on 弦截公式N

16、ewt on切線公式的缺點(diǎn)及改進(jìn)幾何作法迭代公式Xk 1 Xkf (Xk)f(Xk) f(Xk 1)(XkXk 1)Newton 弦截公式是兩步公式。第五章插值法1. 掌握代數(shù)插值問題及其解存在唯一性，Lagrange插值多項(xiàng)式構(gòu)造及其余項(xiàng)， 插值基函數(shù)性質(zhì)；2. 掌握差商的概念及其性質(zhì)，Newt on插值多項(xiàng)式構(gòu)造，兩種插值法之間的區(qū) 別與聯(lián)系；3 了解差分與等距節(jié)點(diǎn)插值多項(xiàng)式公式；4.掌握Hermite插值問題及其構(gòu)造方法。本章問題：函數(shù) f(x)復(fù)雜，或無表達(dá)式，構(gòu)造簡單函數(shù)P(x)來代替f(X)。 Lagrange 插值一、代數(shù)插值問題及插值多項(xiàng)式存在唯一條件1、代數(shù)插值問題：已知f

17、(x)在區(qū)間a,b中互異的n+1個(gè)點(diǎn)X0, X1, , Xn的函數(shù)值y0, y1,., yn，求次數(shù) n次多項(xiàng) 式 Pn (x)a.anXn且滿足Pn(xi)f (xi)yi，(i=0,1,n).2、插值多項(xiàng)式存在唯一條件：定理：Pn(x) a0 a1x . anxn存在唯一條件是n+1個(gè)節(jié)點(diǎn)互異。二、Lagrange 插值構(gòu)造1、線形插值(n=1 )幾何解釋；l1 (X)滿足利用插值基函數(shù)構(gòu)造：基函數(shù)：一次多項(xiàng)式 l0(X),1o(Xo)ili (xo) olo ( xi)oli(Xi)ilo(x)XXiXXoli(x)XoXiXiXoLi(x)yo lo(X)yili(x)-1次Lagra

18、nge 插值多項(xiàng)式例i :求f (X)、X過點(diǎn)(4，2)，( 9，3)的i次Lagrange 插值多項(xiàng)式,2、拋物插值(n=2)幾何解釋;利用插值基函數(shù)構(gòu)造:基函數(shù)：二次多項(xiàng)式lo(x),li (x),l2 (x)滿足并計(jì)算. 5近似值。lo(Xo)ili (Xo)olo (xi)oli (Xi)ilo ( X2 )oli (X2)olo(x)(xX-I )(x X2)(XoXi )(XoX2)Li(x)yol o(X) yili(x)例2 :求f(x)X過點(diǎn)(i，3、一般情形：利用插值基函數(shù)構(gòu)造：基函數(shù)：1n次多項(xiàng)式l o(X),li(Xj)iji i o ij jlk(x)(x Xo)(X

19、Xi)(XkXo )(XkXi).(xo)I 2 (xi)I 2 (x2)(xXo)(X x2)li(x)(XiXo)(Xi X2)y22(x)2次 LagrangeLn(X)I2(X) (X SX Xi)(X2 Xo)(X2 Xi)插值多項(xiàng)式1), (4 , 2), (9 , 3)的2次Lagrange插值多項(xiàng)式，并計(jì)算J5近似值。li(x),. ln(x)滿足(XXki)(XXki)(XXn) (XkXk i)(XkXk i).(Xk Xn)yolo(x)yili(x) . yn(x)nyk(x)k 0n 次Lagrange 插值多項(xiàng)式三、插值余項(xiàng)f(n)(x)在a,b連續(xù)，fni)(x)

20、在a,b存在，則 插 值誤差Rn(X)f(X)Ln(X):(n 1)()(TV (x)，其中a,b 依賴于x。分段插值一、分段線性插值在區(qū)間a, b，分為n個(gè)區(qū)間Xj,Xj訂，i=0,1,2n-1每個(gè)區(qū)間由直線代替曲線，形成分段線性插值函數(shù)(X)(X) li(x)yi li1(x)yi 1X Xi ,Xi1X Xi 1 li(x)li i(x)XxiXiXi 1Xi 1Xi二、分段拋物插值3一、差商及其性質(zhì)定義：Newton插值一階差商:fXi ,Xif (Xi 1) f (Xi)1Xi 1Xi二階差商:fXi ,Xi1,Xi2込3fXi,Xi 1Xi 2XiK階差商:fXi ,Xi1,，xi

21、 kf Xi 1,Xi 2,，Xi k fXi,Xi 1,Xi k 1Xi kXi性質(zhì)：（1）差商可由節(jié)點(diǎn)函數(shù)值表示;（2）差商值與節(jié)點(diǎn)次序無關(guān)。二、Newton 插值多項(xiàng)式由差商定義f (X) f (X0) f X0, x(xX0)fx,x fX0,X fX,X1,X(X X1)fX,X1,X fX,X1,X2 fX,X1,X2,X(X X2)fX0,X1,.Xn 1,xf X0,X1,.Xnf【X。，捲，.X. , X( X X.)依次帶入Nn(x) f(Xo)fXo,Xi(X Xo) . fXo, Xi,.Xn(X X).(X X. 1) Newton插值多項(xiàng)式計(jì)算時(shí)先造差商表；三、余項(xiàng)

22、fX,Xi，Xn,X(n 1)(n 1)!4 差分與等距節(jié)點(diǎn)插值多項(xiàng)式一、差分及其性質(zhì)：二、等距節(jié)點(diǎn)插值多項(xiàng)式5 Hermite 插值一、帶導(dǎo)數(shù)的插值多項(xiàng)式1、 問 題： 求 次 數(shù) 不 超 過 3 次 多 項(xiàng) 式IIHa（x）,滿足 H3（Xo）yo,H3（xJ y1,H3（Xo） m,H3（X1）mn ；2、利用基函數(shù)構(gòu)造H3(x)o(x)y1&)力o(x)m1(x)m)10(x)(1Xo X1 Xo X11(x)(1X1X1X0)(X1生)2X0X X-I 20(x) (X Xo)(-)XoX1X Xo 21(X) (X X1)(-)XI Xo二、一般情形2n+11、 問 題H2n1(x

23、),滿足 H2n1(Xi) yi,H2n1(xJmJ0,1,n;2、利用基函數(shù)構(gòu)造見教材第七章數(shù)值微積分1. 了解數(shù)值求積基本思想；2. 掌握Newton-Cotes公式(梯形公式，Simpson 公式，Cotes公式)推導(dǎo)及誤差；3. 了解Romberg求積公式原理；4了解數(shù)值微分的方法。本章問題：數(shù)值積分問題b求定積分 f(x)dx F(b) F(a)a不能使用微積分公式情形存在問題：(1) f(x)表達(dá)式復(fù)雜，原函數(shù)更復(fù)雜；(2) f(x)表達(dá)式不復(fù)雜，但原函數(shù)復(fù)雜；(3 )原函數(shù)不存在；(3) f(x)無表達(dá)式 Newton-Cotes 公式一、數(shù)值求積基本思想1、不利用原函數(shù)，直接利

24、用函數(shù)值積分中值定理：ba f(x)dx (b a)f()f()為平均高度;bn機(jī)械求積方法：If (x)dxAi f (xi)ai 0Xj為求積節(jié)點(diǎn)；Ai為求積系數(shù)2、幾個(gè)簡單求積公式左矩形公式1ba f (x)dx(ba) f (a)右矩形公式1bf (x)dx a(ba)f(b)中矩形公式1bf(x)dx a(ba b、a)f( 2 )梯形公式1bf(x)dxab a2(f(a)f(b)二、Newton-Cotes 公式1、公式推導(dǎo)由Lagrange插值多項(xiàng)式Ln(x)代替函數(shù)f(x)f(x)dx abLn(x)dxb nli(x) f (xjdx ai 0n b(a h(x)dx) f

25、 (xji 0ba li (x)dxba f(x)dxA f (xj求積系數(shù)A的計(jì)算:Ci(n)為 Cotes(1)nii!(n i)!n g j 0 (i j i(b a)C(n)系數(shù);bnI f (x)dxAi f (xi)ai 0(ba)nCi(n) f (xi )Newton-Cotes 求積公式i 02、Cotes系數(shù)性質(zhì)對稱性：Ci(n)(n) C n in權(quán)性：c,n)1i 03、常用公式n=1bb a梯形公式：| f(x)dx(f(a) f (b)a 2n=2bb aa bSimpson,拋物公式：I g f (x)dx( f (a)4 f () f (b)n=4bb aCot

26、es公式： I f(x)dx (7f(x。)32f(xj 12f(X2)32f (xa) 7f(X4) a90.b axia i -44誤差估計(jì)：見教材舉例說明。 Romberg求積公式、復(fù)化梯形公式將積分區(qū)間a,b，n等份，步長hhn 1Tn -f(a) 2 f (xi)f(b)2i i誤差估計(jì)：二、梯形公式遞推化2i三、Romberg由梯形公式修正,f(xiil)2求積公式41T2n-T33161S2n1515641C2n6363提高精度SnRnCnSnCn3Gauss型求積公式、代數(shù)精確度定義：若求積公式Iba f(x)dxnAi f (xi )對任意wm次代數(shù)多項(xiàng)式精確成立，而對m+1

27、次代數(shù)多項(xiàng)式不精確成立，稱求積公式具有m次代數(shù)精確度。判定：求積公式具有m次代數(shù)精確度 求積公式對f(x) 1,X,X2,.,xm精確成立；而對m 1f (x) X不精確成立。例：梯形公式具有1次代數(shù)精確度；定理1 : n+1個(gè)節(jié)點(diǎn)的插值型求積公式代數(shù)精確度至少為n ;定理2 ； Newton-Cotes 公式代數(shù)精確度至少為 n ；當(dāng)n為偶數(shù)時(shí)，可達(dá)n+1次代數(shù)精確度。二、Gauss型求積公式定義：若n+1個(gè)節(jié)點(diǎn)求積公式If(x)dxA f (Xj 具有 2n+1i 0次代數(shù)精確度，則稱為Gauss型求積公式，節(jié)點(diǎn)為 Gauss點(diǎn)Gauss點(diǎn)的特性：見教材第八章常微分方程數(shù)值解1. 掌握Eu

28、ler方法(Euler公式，梯形公式，Euler預(yù)估-校正公式)，局部截?cái)嗾`差，公式的階；2. 了解Runge-Kutta方法的基本思想及四階經(jīng)典 Runge-Kutta公式；3. 掌握線性多步方法的原理與公式推導(dǎo)。本章問題：一階常微分方程初值問題dy f (x, y)dxy(x) y。解的存在性定理：解析解的概念數(shù)值解的概念 Euler方法一、Euler 公式導(dǎo)數(shù)離散化y(Xn) f (Xn, y(Xn)由向前差商代替導(dǎo)數(shù),、y(Xn 1) y(Xn)y (Xn)h得y(Xn 1)y(Xn) hf(Xn,y(Xn)記為 yn 1 yn hf(Xn,yn)Euler 顯式公式y(tǒng) (Xn 1)得y(Xn 1)記為y n 1二、Euler梯形公式y(tǒng)(X