1、數(shù)值計算方法復(fù)習(xí)提綱第一章數(shù)值計算中的誤差分析1 .理解誤差及其主要來源，誤差估計；2 .理解誤差(絕對誤差、相對誤差)和有效數(shù)字的概念及其關(guān)系;3 .掌握算法及其穩(wěn)定性，設(shè)計算法遵循的原那么。1、誤差的來源模型誤差觀測誤差截斷誤差舍入誤差2誤差與有效數(shù)字絕對妖差 Ex=x-x絕對誤差限xX X相對誤差 Er (x) (x x )/x (x x )/x有效數(shù)字x0.a1a2.an 10m*1”一*假設(shè)x x - 10 ，稱x有n位有效數(shù)字。2有效數(shù)字與誤差關(guān)系(1) m一定時，有效數(shù)字n越多，絕對誤差限越?。灰?* 一，、1 一(n 1)(2) x有n位有效數(shù)字，那么相對誤差限為 Er(x)

2、1002 al選擇算法應(yīng)遵循的原那么1、選用數(shù)值穩(wěn)定的算法，控制誤差傳播;1 1 n x ,例 I n x e dx e 0,/ 11 n 1 n| n 1101e xn n! Ax0 2、簡化計算步驟，減少運(yùn)算次數(shù)；3、防止兩個相近數(shù)相減，和接近零的數(shù)作分母;防止第二章線性方程組的數(shù)值解法1.理解Gauss消元法、主元消元法根本思想及算法；2,掌握矩陣的三角分解，并利用三角分解求解方程組；C Doolittle分解；Crout分解；Cholesky分解；追趕法3 .掌握迭代法的根本思想，Jacobi迭代法與Gauss-Seidel迭代法;4 .掌握向量與矩陣的范數(shù)及其性質(zhì)，迭代法的收斂性及其

3、斷定 。本章主要解決線性方程組求解問題，假設(shè)n行n列線性方程組有唯一解，如何得到其解?a11X1a 12 X2a1n Xnb1a21 X1a 22 X2.a2nXnb2an1X1.an2X2.a nn Xnbn兩類方法，第一是直接解法，得到其準(zhǔn)確解； 第二是迭代解法，得到其近似解。Gauss消去法(1)an Xi(2)a 21 Xi(2)a22 X2b1(1)b22)(n)an1 X1(n)an2 X2-(n)ann xn(n) bn1、 順序G auss消去法記方程組為:(1)an Xi八a12 X2(1)a1 n xnb1(1)J) a21 Xi八a 22 X2a2nxnb21)(i)an

4、1 X1.(1) an2X2(1)ann xnbn1)消元過程：經(jīng)n - 1步消元，化為上三角方程組假設(shè)akk) kk-(k 1) J)aijaija(kk)(k)(k) akj akk(k 1)bi(k)bia(k)b(k)k1,n1 i, j k 1,.akk.,n回代過程:Xn(n) (n)bn/ annXi(i)(bi(i)(i)aj Xj)/a(i11,n 2,1)2、G auss- Jordan 消去法防止回代，消元時上下同時消元3、G auss列主元消去法例：說明直接消元，出現(xiàn)錯誤0.00001x1 2x22x1 x2 3由順序G auss消去法，得x21, x10 ；Gauss

5、列主元消去法原理：每步消元前，選列主元，交換方程。算法：將方程組用增廣矩陣A小aj表示。lj n(n 1)1消元過程：對 k=1,2,n-1,選主元，找ik k,k 1, ,n使得aik，kmax aik假設(shè)aj k 0,那么矩陣a奇異，程序完畢；否那么執(zhí)行3。k ,假設(shè)ikk ,那么交換第k行與第ik行對應(yīng)的元素位置，akjakj,jk,n消元，對i=k+1, ,n，計算1.l ikai/, 對 j=L+1, ,n+1,計算akk2回代過程:1 .假設(shè)ann 0,那么矩陣A奇異，程序完畢；否那么執(zhí)行2 xn：2,1，計算舉例說明。4、消元法應(yīng)用1行列式計算;2矩陣求逆。二、利用矩陣三角分解求

6、解線性方程組1、求解原理線性方程組寫成矩陣形式為：AX=b假設(shè)A=LU ,那么LUX= b ,記 UX=Y那么LY= b假設(shè)L、U為特殊矩陣，那么求解線性方程組變?yōu)榻鈨蓚€特殊線性方程組問題。2、 Doolittle 分解L為下三角矩陣，U為上三角矩陣，不一定能分解，分解也不一定唯一；設(shè)L或U是單位三角矩陣，假設(shè)能分解，那么可分解唯一.L是單位下三角矩陣，稱為Doolittle分解；U是單位上三角矩陣，稱為Crout分解；定理：n階矩陣A有唯一分解的充要條件為A的前n-1階主子式都不為0.Doolittle分解算法:a11a12a1nU11U12U1 na21a22a2nl 21U22U2na

7、n1an2annln1ln2Unn由矩陣乘法:aijl ik Ukj得到:Ukja kjl kr Urj1k, k1,.n;l ik(aik1l ir Urk ) / U kk1k, k 1,.n算法特點(diǎn)：先計算U的行，再計算 矩陣分解后，解兩個三角方程組：交替進(jìn)展；存儲時可用緊湊格式。LY= b, UX=Yyb1i1y bilikyki 2,3,.nk1nXi (yi UikXk)/Uiii n,n 1,.1ki13、Crout 分解假設(shè)L為下三角矩陣，U是單位上三角矩陣，那么稱 Crout分解;算法特點(diǎn)：先計算L的列，再計算U的行，交替進(jìn)展。4、正定對稱矩陣的平方根法Cholesky分解(

8、1)正定對稱矩陣性質(zhì)與斷定：定義：是n階對稱矩陣，假設(shè)對任意非零向量 X Rn ,有X TAX 0 ,那么稱A為正定對稱矩陣;斷定：A為n階正定對稱矩陣充要條件 A的各階順序主子式大于 0(2) Cholesky 分解定理：設(shè)A為n階正定對稱矩陣，那么存在唯一主對角線元素都是正數(shù)的下三角陣L,使得 A LLT.Cholesky分解算法:a11a12.anlna21a22.a2nl 21l 22.an1an2.annl n11n2j 11l (a.12 )2Jj a jjJkk 1j 1l ij(aijlik l jk ) / l jjk 1j 1,2,.n;i j 1, j 2,.n5、追趕法

9、三對角矩陣的特殊分解biCia2b2C2a3b3C3.an 1bn 1 cn 1anbnll 11 l12. l 1nl22. l 2n.nnl nn1u1 Gl 21U2 C2l3 1.Un 1c3ln 1UnU1b1li ai/Ui 1 i 2,3,.nUi bilici 1三對角方程組的追趕法：追的過程LY=Dy1 d1V di li yi 1i 2,3,.n趕的過程UX=Yxnyn / unXi(yiCixi i)/Ui i n 1, n 2,.,1 2線性方程組的迭代解法一、 Jacobi迭代公式例：1212其解為X11, X21Xi-X221XiX22方程變形得到迭代公式1(k)2

10、X2 *1212給初值X(0)0計算，觀察解的變化。0一般地，對線性方程組a11X1a12X2a 1 n Xnb1a 21X1a 22X2.a2nXnb2a n1 X1.a n2 X2a nn Xnbn假設(shè)aii0 ,那么可從第i個方程中解出Xi，得到Jacobi迭代公式:(k 1)X1(b1八 (k) a12X2八 (k)a1 n Xn)/ a11(kXi1)(bi(k) ai1X1ain Xn ) / aii(k n1)(bn(k) an1X1(k) a nn Xn 1簡記為：n(k 1)(k)、X (biaijXj)/aHi 1,2,.,nj 1Gauss-Seidel 迭代公式(bia

11、ijXj(k 1)naijX(k)/aHi1,2,., nSOR迭代公式四、迭代公式的矩陣表示X (k 1) GX (k) D 3迭代公式的收斂性一、向量與矩陣的范數(shù)與性質(zhì)1、向量范數(shù)定義：向量X Rn ,對應(yīng)非負(fù)實(shí)數(shù)|X| ,滿足三條件：1非負(fù)性兇| 0, X 0,|X|02齊次性kX kX3三角不等式 |X Y|X| |Y|稱|X|為向量范數(shù)2、常見向量范數(shù)1 范數(shù) |XXiX2. Xn2 范數(shù) |x|2Jx； X2 . X2.ii max00范數(shù)XXi1 111 i n i3、矩陣范數(shù)定義：方陣A Rn n,對應(yīng)非負(fù)實(shí)數(shù)| A ,滿足三條件:1非負(fù)性 網(wǎng) 0, A 0,|A|02齊次性k

12、Ak|A三角不等式| a b| a |b|4絕對值不等式|ab|I a|b|稱IA為矩陣范數(shù)；向量范數(shù)與矩陣范數(shù)相容性：AX A X4、常見矩陣范數(shù)1范數(shù)，列范數(shù)：1Almax aj1 j n i 1 n8范數(shù)，行范數(shù)：IA maxaiji n j i2范數(shù)，譜范數(shù) ： n nf范數(shù)：|A|fai21 1 j 1舉例計算二、迭代公式收斂性的斷定1、向量的極限2、 矩陣的譜半徑：(A) max i i為特征值； 1 i n3、收斂性的斷定收斂的充要條件：迭代公式X (k 1) GX (k)D收斂的充要條件為譜半徑(G) 1。斷定定理1:假設(shè)問1,那么迭代公式X(k1) GX(k) D收斂。斷定定

13、理2:假設(shè)對方程AX=b的系數(shù)矩陣A為對角占優(yōu)，那么 Jacobi迭代公式，Gauss-Seidel迭代公式收斂;斷定定理3：假設(shè)對方程AX=b的系數(shù)矩陣A為對稱正定，那么 Gauss-Seidel迭代公式收斂；Jacobi迭代公式收斂與 Gauss-Seidel迭代公式收斂關(guān)系舉例:第三章非線性方程的數(shù)值解法1 .理解二分法的原理與算法；2 .掌握一般迭代法的根本思想及其收斂性斷定；3 .掌握Newton切線法、弦截法，并用它們求方程近似根的方法。本章問題：求方程 f(x)=0的根 1二分法一、根的存在性定理：函數(shù)f(x)在區(qū)間a, b連續(xù)，且f(a).f(b)0,那么方程f(x)=0在區(qū)間

14、a, b有根。方程的根存在，不一定唯一，假設(shè)在區(qū)間a, b上有唯一根，稱區(qū)間a, b為根隔離區(qū)間。二、二分法區(qū)間逐次分半法原理：通過計算根隔離區(qū)間中點(diǎn)，將區(qū)間分半，縮小區(qū)間，得到方程近似根數(shù)列xn。a,ba1,b1.an,bn.bk ak(b a)/2k一 * ， . . .取 x(an bn )/22迭代法一、迭代原理迭代法是一種逐次逼近法，由提供的遞推公式計算，逐次準(zhǔn)確，直到滿足精度要求。方程f(x)=0變形為x (x),得到遞推公式xk 1(xk)簡單迭代公式稱(x)為迭代函數(shù)給初值計算，得到數(shù)列 xn,假設(shè)例：ljm xk* 一 一x ,那么稱迭代收斂，否那么發(fā)散。求方程 10x x

15、2 0 x030.4寫出兩個簡單迭代公式:1xk 110xk 22xk 1 lg(xk 2)觀察計算得到數(shù)列 xn的收斂性。迭代法的幾何解釋:、迭代收斂性斷定收斂性定理：設(shè)方程 x (x)的迭代函數(shù)(x)在a, b滿足:1當(dāng) x a,b時，(x) a,b；2(x)在a, b可導(dǎo)，且 (x) L 1, x a, b, , 、 *那么1萬程x (x)在a, b有唯一根x ；2迭代公式xk i(xj收斂，即ljm xk *3誤差估計xxkLk1 Lxix0 說明可根據(jù)迭代函數(shù)(x)的導(dǎo)數(shù)判斷迭代收斂性。三、迭代公式的加速3 Newton迭代法一、Newton切線公式幾何作法迭代公式xk 1xkf(x

16、k)f (xk)例：利用解二次方程x2 c 0,推導(dǎo)近似計算 JC的公式。1 ,c、由Newton切線公式 xk 1 -(xk )2xk三、Newton弦截公式Newton切線公式的缺點(diǎn)及改進(jìn)幾何作法xk 1)迭代公式xk 1xkNewton弦截公式是兩步公式。第五章 插值法1 .掌握代數(shù)插值問題及其解存在唯一性，Lagrange插值多項(xiàng)式構(gòu)造及其余項(xiàng)， 插值基函數(shù)性質(zhì)；2 .掌握差商的概念及其性質(zhì)，Newton插值多項(xiàng)式構(gòu)造，兩種插值法之間的區(qū)別 與聯(lián)絡(luò)；3 .理解差分與等距節(jié)點(diǎn)插值多項(xiàng)式公式；4 .掌握Hermite 插值問題及其構(gòu)造方法。本章問題：函數(shù)f(x)復(fù)雜，或無表達(dá)式，構(gòu)造簡單函

17、數(shù)P(x)來代替f(x)。 1 Lagrange 插值一、代數(shù)插值問題及插值多項(xiàng)式存在唯一條件1、代數(shù)插值問題：f (x)在區(qū)間a,b中互異的 n+1個點(diǎn)x0,x1,xn的函數(shù)值 y0, y1,.,yn，求次數(shù) n次多項(xiàng)式R(x) % axanxn 且滿足 Pn(xi)f (xi)yi ,i=0,1，nanxn存在唯一條件是n+1個節(jié)點(diǎn)互異。2、插值多項(xiàng)式存在唯一條件：定理：Pn(x) a。 ax二、Lagrange插值構(gòu)造1、線形插值n=1幾何解釋；利用插值基函數(shù)構(gòu)造：基函數(shù)：一次多項(xiàng)式|0(x),l1(x)滿足10 (x0)1|1 (x0)0lo(x1) 0 L*) 1x xx %lO(x

18、) l(x)x x1xx0L(x)y0l0(x)y/1(x)1 次Lagrange插值多項(xiàng)式 例1 ：求 f (x) x過點(diǎn)4, 2，9, 3的1次Lagrange插值多項(xiàng)式，并計算 J5近似值2、拋物插值n=2幾何解釋；利用插值基函數(shù)構(gòu)造:基函數(shù)：二次多項(xiàng)式l0(x), l1(x), l2(x)滿足10(X0)110(X1)0l0 ( X2 )0li(Xo)0li(Xi) 1ll(X2) 0l2(X0)0l2(Xi)0l2(X2) 1l0(X)(X(X0X1)(X X2)X1)(X0 X2)l1(X)(X X)(X X2)(X1 X)(X1 X2)l2(X)(X X0)(X X1)(X2 X

19、0)(X2 X1)L1(X)y0l0(X)yJ(X)y2l2(X)2次Lagrange插值多項(xiàng)式例2:求f (x)JX過點(diǎn)1, 1，4, 2，9, 3的2次Lagrange插值多項(xiàng)式，并計算 J5近似值3、一般情形：利用插值基函數(shù)構(gòu)造:基函數(shù):n次多項(xiàng)式l0(x),l(x)，ln(x)滿足li (xj ) ijlk(x)(x %)(x X1).(X Xk1)(X Xk 1).(X Xn)(XkX0)(XkX).(XkXk 1)(XkXk 1).(Xk Xn)nLn(x)n次Lagrange插值多項(xiàng)式y(tǒng)0l0(x) W1i(X). yJn(x)ydk(x)k 0三、插值余項(xiàng) 定理：假設(shè) f (n

20、)(x)在a,b連續(xù)，f(n (x)在a,b存在，那么插值誤差f(n1)()R(x) f(x)Ln(x)；/ (X),(n 1)!其中 a,b依賴于x。 2分段插值一、分段線性插值在區(qū)間a, b,分為n個區(qū)間xXi 1 ,i=0,1,2n-1每個區(qū)間由直線代替曲線，形成分段線性插值函數(shù)(X)(x) li(x)yi li i(x)yi 1 x Xi,Xi 1X Xi 1x xili(x), li i(x)xiX 1x 1 x二、分段拋物插值 3 Newton 插值一、差商及其性質(zhì)定義：f(x)f(x。一階差商：f ,xi 1xi 1 xi二階差商:fx ,X 1,xi 2fX 1,為 2fxi,

21、x 1X 2 XK階差商：”為，為1,xi kfxi 1,xi 2,xi kfxi,xi 1,x k 1xi kxi性質(zhì)：1差商可由節(jié)點(diǎn)函數(shù)值表示;2差商值與節(jié)點(diǎn)次序無關(guān)。二、Newton插值多項(xiàng)式由差商定義f(x)f (Xo) fx0,x(x Xo)fx0,xfXo,X1 fXo,X1,X(X X1)fXo,X1,XfXo,X1,X2fXo,X1,X2,X(X X2)fXo,X1,.Xn1,XfXo,X1,.XnfXo,X1,.Xn,X(XXn)依次帶入Newton 插Nn(x)f (Xo)fXo,X1(XXo).f Xo, X,.Xn(XX0).(XXn 1)值多項(xiàng)式計算時先造差商表；三、

22、余項(xiàng)fXo,X1,.Xn,Xf(n1)()(n 1)! 4差分與等距節(jié)點(diǎn)插值多項(xiàng)式一、差分及其性質(zhì)：二、等距節(jié)點(diǎn)插值多項(xiàng)式 5 Hermite 插值一、帶導(dǎo)數(shù)的插值多項(xiàng)式1 、 問 題： 求 次 數(shù) 不 超 過 3 次 多,，、，、H3（x）,湎足MM） y（）,H3（Xi） yi,H3（X0）m（）,H3（Xi） mi ；2、利用基函數(shù)構(gòu)造H3（x）0（x）yoi（x）yi0（x）m0i（x）m10（x） （i 2）（L）2X0 Xi X0 Xii(x)(i 2j)2XiX0XiX00(x)(X、/ XXi2x0)()X0Xii(x)(X、/ X X0 2Xi)()XiX0二、一般情形i、問

23、題：求次數(shù)不超過2n+i次多項(xiàng)式H 2nl （x），滿足H 2nl （x。yi, H2n i （xi）mi ,i2、利用基函數(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不能使用微積分公式情形存在問題：1f(x)表達(dá)式復(fù)雜，原函數(shù)更復(fù)雜；2f(x)表達(dá)式不復(fù)雜，但原函數(shù)復(fù)雜；3原函數(shù)不存在；3f(x)無表達(dá)式 1 Newton-Cotes 公式數(shù)值求積根本思想1、

24、不利用原函數(shù)，直接利用函數(shù)值b積分中值定理：f(x)dx (b a)f()af ()為平均高度；機(jī)械求積方法：Iba f(x)dxnAif(xi)i 0x為求積節(jié)點(diǎn)；A為求積系數(shù) 2、幾個簡單求積公式b左矩形公式I f(x)dx (b a) f (a)ab右矩形公式I f(x)dx (b a) f (b)aba b、中矩形公式 | f (x)dx (b a) f ().bba,梯形公式 | f(x)dx (f (a) f (b) a2二、Newton-Cotes 公式1、公式推導(dǎo)由Lagrange插值多項(xiàng)式 Ln(x) 代替函數(shù)f(x)n bf(x)dx an(X)dXli(x) f (xi)

25、dx( li(x)dx) f (xi)ai 0bli (x)dx a那么Iba f(x)dxAi f (xi)0求積系數(shù)A的計算:(1)n n i!(ni)!j 0 (ij)(b a)CiCi（n）為 Cotes 系數(shù);bnn (n)I f (x)dx A f (xi) (b a) C- ) f (xi) ai 0i 02、Cotes系數(shù)性質(zhì)Newton-Cotes求積公式對稱卜CiC(n)n權(quán)性：Ci(n) 1i 03、常用公式n=1bb a.一梯形公式：I f(x)dx b-(f(a)f(b)a2n=2b .ba. a b.Simpson,拋物公式：I a f(x)dx -(f (a) 4

26、 f (-) f (b)n=4b, b aCotes公式：I f (x)dx (7f(x0) 32f (x1) 12 f(x2) 32f (x3)a90,b a xi a i44誤差估計： 見教材7 f d)舉例說明。 2 Romberg求積公式、復(fù)化梯形公式將積分區(qū)間a,b , n等份，步長hh門1Tn -f(a) 2 f(xj f(b)2i i誤差估計：、梯形公式遞推化2Tnhn2if (xi1)2三、Romberg由梯形公式修正,求積公式進(jìn)步精度SnCnRn4T2n3M2n1564cc2n63135Sn15-Cn63 3 Gauss型求積公式、代數(shù)準(zhǔn)確度定義：假設(shè)求積公式|ba f(x)

27、dxnAi f (xi)對任意0 m次代數(shù)多項(xiàng)式準(zhǔn)確成立，而對 m+1次代 i 0數(shù)多項(xiàng)式不準(zhǔn)確成立,稱求積公式具有m次代數(shù)準(zhǔn)確度。斷定：求積公式具有m次代數(shù)準(zhǔn)確度 求積公式對f(x)1,X,X2，Xm準(zhǔn)確成立；而對f(x)m 1x不準(zhǔn)確成立。例：梯形公式具有1次代數(shù)準(zhǔn)確度；定理1： n+1個節(jié)點(diǎn)的插值型求積公式代數(shù)準(zhǔn)確度至少為n；定理2； Newton-Cotes公式代數(shù)準(zhǔn)確度至少為 n；當(dāng)n為偶數(shù)時，可達(dá) n+1次代數(shù)準(zhǔn)確度。、Gauss型求積公式定義：假設(shè)n+1個節(jié)點(diǎn)求積公式|bf(x)dx anAi f (xi)具有2n+1次代數(shù)準(zhǔn)確度，那么稱為Gauss i 0型求積公式，節(jié)點(diǎn)為 G

28、auss點(diǎn)Gauss點(diǎn)的特性：見教材第八章常微分方程數(shù)值解1 .掌握Euler方法Euler公式，梯形公式，Euler預(yù)估-校正公式，局部截斷誤差，公式的階;2 .理解Runge-Kutta方法的根本思想及四階經(jīng)典 Runge-Kutta 公式;3 .掌握線性多步方法的原理與公式推導(dǎo)。本章問題：一階常微分方程初值問題dyf (x, y) dXV(Xq)Vo解的存在性定理: 解析解的概念 數(shù)值解的概念 1 Euler 方法 一、Euler 公式 導(dǎo)數(shù)離散化y (Xn)f (Xn,y(Xn)由向前差商代替導(dǎo)數(shù)y (Xn)y(Xn i) y(Xn)y(Xn i)y(Xn) hf (Xn , y(Xn)記為yniynhf(Xn,yn)Euler 顯式公式y(tǒng) (Xn l)y(Xni) y(Xn)y(Xn i