數(shù)值計算方法復習提綱

1、.數(shù)值計算方法復習提綱第一章數(shù)值計算中的誤差分析1了解誤差及其主要來源，誤差估計；2了解誤差 ( 絕對誤差、相對誤差 ) 和有效數(shù)字的概念及其關系；3掌握算法及其穩(wěn)定性，設計算法遵循的原則。1、 誤差的來源模型誤差觀測誤差截斷誤差舍入誤差2 誤差與有效數(shù)字絕對誤差E（x）=x-x*絕對誤差限x*x x*相對誤差Er (x) ( x x* ) / x ( xx* ) / x*有效數(shù)字x*0.a1 a2 .an10 m若 xx*110mn ，稱 x* 有 n 位有效數(shù)字。2有效數(shù)字與誤差關系（ 1）m 一定時，有效數(shù)字n 越多，絕對誤差限越??；（ 2）x* 有 n 位有效數(shù)字，則相對誤差限為Er

2、(x)110 (n 1) 。2a1選擇算法應遵循的原則1、 選用數(shù)值穩(wěn)定的算法，控制誤差傳播；例 I n11nexdxex0I011I n1nI n1e xnn! x02、 簡化計算步驟，減少運算次數(shù)；3、 避免兩個相近數(shù)相減，和接近零的數(shù)作分母；避免;.第二章線性方程組的數(shù)值解法1了解 Gauss 消元法、主元消元法基本思想及算法；2掌握矩陣的三角分解，并利用三角分解求解方程組；（ Doolittle 分解； Crout 分解； Cholesky 分解；追趕法）3掌握迭代法的基本思想，Jacobi 迭代法與 Gauss-Seidel迭代法；4掌握向量與矩陣的范數(shù)及其性質(zhì), 迭代法的收斂性及其

3、判定。本章主要解決線性方程組求解問題，假設n 行 n 列線性方程組有唯一解，如何得到其解？a11x1a12 x2.a1n xnb1a21x1a22 x2.a2n xnb2.an1x1an 2 x2.ann xnbn兩類方法，第一是直接解法，得到其精確解；第二是迭代解法，得到其近似解。一、Gauss消去法1、 順序 auss 消去法記方程組為：a11(1) x1a12(1) x2. a1(1n) xnb1(1)a21(1) x1a22(1) x2. a2(1n) xnb2(1).an(11) x1an(12) x2. ann(1) xnbn(1)消元過程：經(jīng)步消元，化為上三角方程組a11(1)

4、x1b1(1)a 21(2) x1a22(2 ) x2b2( 2).an(1n) x1a n(n2) x2.ann(n ) xnbn( n)第步若 akk(k)0( k 1)( k)aik(k )(k )( k 1)( k )aik(k )( k)aijaijakk(k ) akjbibiakk(k )bkk 1,.n 1 i, j k 1,.,n回代過程：;.xn bn(n)/ ann(n)nxi (bi(i )aij(i ) x j ) / aii(i)(i n 1, n 2,.1)ji 1、 auss消去法避免回代，消元時上下同時消元、 auss 列主元消去法例 ：說明直接消元，出現(xiàn)錯誤

5、0.00001x12x22x1x23由順序 auss 消去法，得 x21, x1 0 ； auss 列主元消去法原理：每步消元前，選列主元，交換方程。算法：將方程組用增廣矩陣AMbaijn( n 1) 表示。（ 1）消元過程：對 k=1,2,n-1,選主元，找 i k k, k 1, n 使得aik, kmax aikk i n如果 aik ,k0 ，則矩陣 A 奇異，程序結束；否則執(zhí)行3。如果 ikk，則交換第 k 行與第 ik 行對應的元素位置，akjai k j , jk,ggg,n1.消元，對 i=k+1,L ,n,計算likaik, 對 j=L+1,L ,n+1,計算akkaijai

6、jlik akj（2）回代過程：1若 ann0, 則矩陣 A 奇異，程序結束；否則執(zhí)行。xnan,n 1n1,L,2,1,計算2ann ; 對inai , n1aij x jj i 1xiaii;.舉例說明。4、消元法應用（ 1）行列式計算；（ 2）矩陣求逆。二、利用矩陣三角分解求解線性方程組1、求解原理線性方程組寫成矩陣形式為：AX=b若 A=LU，則 LUX= b，記 UX=Y則 LY= b若 L、 U 為特殊矩陣，則求解線性方程組變?yōu)榻鈨蓚€特殊線性方程組問題。2、 Doolittle 分解L 為下三角矩陣 , U 為上三角矩陣 ,不一定能分解 ,分解也不一定唯一 ; 設 L 或 U 是單

7、位三角矩陣 , 若能分解 ,則可分解唯一 .L 是單位下三角矩陣,稱為 Doolittle 分解 ;U 是單位上三角矩陣,稱為 Crout 分解；定理 : n 階矩陣 A 有唯一分解的充要條件為A 的前 n-1 階主子式都不為0.Doolittle 分解算法：a11a12.a1n1u11u12.u1na21a22.a2nl 211u22.u2 n. . . . . . .an1an2.annln1l n2.1unn由矩陣乘法：aijnl ik ukjk1得到：k1ukjakjl kr urjjk, k1,.n;r1k1l ik( aikl ir u rk ) / ukkik, k1,.nr1算

8、法特點：先計算U 的行，再計算L 的列，交替進行；存儲時可用緊湊格式。矩陣分解后，解兩個三角方程組：LY= b，UX=Y;.i 1y1b1yibilik yki2,3,.nk 1nxi( yiuik xk ) / uiiin, n1,.1k i13、 Crout 分解若 L 為下三角矩陣， U 是單位上三角矩陣，則稱Crout 分解；算法特點：先計算L 的列，再計算U 的行，交替進行。4、正定對稱矩陣的平方根法（Cholesky 分解）（1） 正定對稱矩陣性質(zhì)與判定：定義：是 n 階對稱矩陣，若對任意非零向量XRn ，有 X T AX0 ，則稱 A 為正定對稱矩陣；判定： A 為 n 階正定對

9、稱矩陣充要條件A 的各階順序主子式大于 0。（ 2） Cholesky 分解定理：設 A 為 n 階正定對稱矩陣，則存在唯一主對角線元素都是正數(shù)的下三角陣L，使得 A LLT .Cholesky 分解算法：a11a12.a1nl11ll 11l12.l1na21a22.a2nl 21l 22l 22.l 2n. . . . . . .an1an2.annl n1l n 2 .l nnl nnj 11l jj(a jjl 2jk ) 2k 1j 1l ij( aijl ik l jk ) / l jjk 1j1,2,.n;ij1, j2,.n5、 追趕法三對角矩陣的特殊分解b1c11u1 c1a

10、2b2c2l 2 1u2C2a3b3 c3.l3 1. . .un 1cn-1an 1 bn 1cn 1ln1unanbn;.u1b1l iai / ui 1i 2,3,.nuibil i ci1三對角方程組的追趕法：追的過程LY=Dy1d1yidili yi 1i2,3,.n趕的過程UX=Yxnyn / unxi( yici xi1 ) / uii n 1, n 2,.,1§ 2線性方程組的迭代解法一、 Jacobi 迭代公式例：x11x2122其解為 x1 1, x211x1x2122方程變形得到迭代公式(k 1)1(k )1x12x22給初值 X (0)0計算，觀察解的變化。(

11、 k 1)1(k )10x22x12一般地，對線性方程組a11 x1a12 x2.a1n xnb1a21 x1a22 x2.a2n xnb2.an1 x1an2 x2.ann xnbn若 aii0 ，則可從第 i 個方程中解出 xi ,得到 Jacobi 迭代公式：x1( k1)(b1a12 x2(k).a1n xn(k) ) / a11.xi( k 1)(biai1 x1(k ). ain xn(k ) ) / aii.xn(k1)(bnan1x1(k ) .ann xn(k1) ) / ann;.簡記為：nxi( k 1)(biaij x j ( k) ) / aiii 1,2,., nj

12、1ji二、 Gauss-Seidel迭代公式i1nxi( k 1)(biaij x j ( k 1)aij x(j k) ) / aiii 1,2,.,nj1j i 1三、 SOR迭代公式四、 迭代公式的矩陣表示X (k1)GX ( k ) D§ 3迭代公式的收斂性一、 向量與矩陣的范數(shù)與性質(zhì)1、 向量范數(shù)定義：向量 XRn ，對應非負實數(shù)X ，滿足三條件：（ 1）非負性（ 2）齊次性（ 3）三角不等式X0,X0,X0kXk XXYXY稱 X 為向量范數(shù)2、 常見向量范數(shù)1 范數(shù)X 1x1x2.xn2 范數(shù)X 2x12x22.xn2范數(shù)Xmaxn xi1i3、 矩陣范數(shù)定義：方陣 A

13、Rn n ，對應非負實數(shù)A ，滿足三條件：（1）非負性A 0,A 0,A0;.（ 2）齊次性（ 3）三角不等式kAk AABAB（4）絕對值不等式ABA B稱 A 為矩陣范數(shù)；向量范數(shù)與矩陣范數(shù)相容性：AXAX4、常見矩陣范數(shù)n1 范數(shù)，列范數(shù)：A1maxaij1 j ni 1n范數(shù)，行范數(shù)：Amaxaij1 i n1j2 范數(shù)，譜范數(shù)：nnaij2F范數(shù)： A Fi 1j1舉例計算二、 迭代公式收斂性的判定1、 向量的極限2、 矩陣的譜半徑：( A)max ii為特征值；1 in3、收斂性的判定收斂的充要條件：迭代公式X (k 1)GX ( k )D 收斂的充要條件為譜半徑(G ) 1。判定

14、定理1：若 G1, 則迭代公式 X (k 1)GX ( k )D 收斂。判定定理2：若對方程AX=b 的系數(shù)矩陣 A 為對角占優(yōu)，則Jacobi 迭代公式， Gauss-Seidel迭代公式收斂；判定定理3：若對方程AX=b 的系數(shù)矩陣 A 為對稱正定，則Gauss-Seidel迭代公式收斂；Jacobi 迭代公式收斂與Gauss-Seidel迭代公式收斂關系舉例：;.第三章非線性方程的數(shù)值解法1了解二分法的原理與算法；2掌握一般迭代法的基本思想及其收斂性判定；3掌握 Newton 切線法、弦截法，并用它們求方程近似根的方法。本章問題：求方程f(x)=0 的根§1二分法一、根的存在性

15、定理：函數(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ū)間逐次分半法）原理：通過計算根隔離區(qū)間中點，將區(qū)間分半，縮小區(qū)間，得到方程近似根數(shù)列 x n 。a, ba1 ,b1.an ,bn.bkak(ba) / 2k取x*(anbn ) / 2§2迭代法一、迭代原理迭代法是一種逐次逼近法，由提供的遞推公式計算，逐次精確，直到滿足精度要求。方程 f(x)=0 變形為 x( x) ，得到遞推公式 xk 1(xk ) -簡單迭代公式稱

16、 ( x) 為迭代函數(shù)給初值計算，得到數(shù)列 x n ，若lim xkx* ，則稱迭代收斂，否則發(fā)散。k例：求方程 10xx 2 0x*0.3,0.4寫出兩個簡單迭代公式：;.（1） xk 110xk2（ 2） xk 1lg( xk2)觀察計算得到數(shù)列 x n 的收斂性。迭代法的幾何解釋：二、迭代收斂性判定收斂性定理：設方程x(x) 的迭代函數(shù)( x) 在 a， b滿足：（1）當 x a,b 時，(x)a,b ；（2） ( x) 在 a， b可導，且( x)L1 ， x a, b ，則（ 1）方程 x(x) 在 a， b有唯一根 x*；（ 2）迭代公式 xk 1( xk ) 收斂，即 lim x

17、kx* ；k（ 3）誤差估計x*xkLkx1x0 。1L說明可根據(jù)迭代函數(shù)( x) 的導數(shù)判斷迭代收斂性。三、迭代公式的加速§ 3Newton迭代法一、 Newton 切線公式幾何作法迭代公式f ( xk )xk 1xkf ' (xk )例：利用解二次方程x 2c0, 推導近似計算c 的公式。由 Newton 切線公式xk 11 (xkc )2xk三、 Newton 弦截公式Newton 切線公式的缺點及改進幾何作法迭代公式;.xk 1f ( xk )xk( xk xk 1 )f ( xk )f (xk 1 )Newton 弦截公式是兩步公式。第五章插值法1. 掌握代數(shù)插值問

18、題及其解存在唯一性， Lagrange插值多項式構造及其余項，插值基函數(shù)性質(zhì)；2. 掌握差商的概念及其性質(zhì)， Newton 插值多項式構造， 兩種插值法之間的區(qū)別與聯(lián)系；3了解差分與等距節(jié)點插值多項式公式；4. 掌握 Hermite 插值問題及其構造方法。本章問題：函數(shù)f ( x) 復雜，或無表達式，構造簡單函數(shù)P(x) 來代替 f (x) 。§ 1 Lagrange插值一、代數(shù)插值問題及插值多項式存在唯一條件1、代數(shù)插值問題：已知 f( x) 在區(qū)間 a,b 中互異的n+1 個點 x0 , x1, ., xn 的函數(shù)值 y0 , y1 ,., yn ，求次數(shù)n 次多項式Pn (x)

19、a0a1 x .an xn 且滿足 Pn ( xi )f (xi ) yi ，（i=0,1,n）.2、插值多項式存在唯一條件：定理： P ( x)a0a x.anxn 存在唯一條件是 n+1 個節(jié)點互異。n1二、 Lagrange插值構造1、線形插值（ n=1）幾何解釋；利用插值基函數(shù)構造：基函數(shù)：一次多項式l 0 ( x),l1 (x) 滿足l 0 ( x0 ) 1l1 ( x0 )0l0 ( x1 ) 0l1 (x1 ) 1;.xx1xx0l 0 ( x)x1l1 ( x)x0x0x1L1 (x) y0 l0 ( x)y1l1 (x) -1 次 Lagrange插值多項式例 1：求 f (

20、 x)x 過點（ 4， 2），（9， 3）的 1 次 Lagrange 插值多項式，并計算5 近似值。2、拋物插值（ n=2）幾何解釋；利用插值基函數(shù)構造：基函數(shù)：二次多項式l 0 ( x),l1 ( x),l 2 (x) 滿足l 0 ( x0 )1l1 ( x0 )0l 0 ( x1 )0l1 ( x1 )1l0 ( x2 )0l1 (x2 )0l 0( xx1 )( xx2 )( x)x1 )( x0x2 )(x0l 2( xx0 )( xx1 )( x)x0 )( x2x1 )(x2l 2 (x0 )0l 2 (x1 )0l 2 (x2 )1l 1( xx0 )( xx2 )( x)x0

21、 )( x1x2 )( x1L1 (x)y0 l0 ( x)y1l1 (x)y2 l 2 (x) -2 次 Lagrange插值多項式例 2：求 f ( x)x 過點（ 1， 1），（4， 2），（9， 3）的 2 次 Lagrange 插值多項式，并計算5 近似值。3、一般情形：利用插值基函數(shù)構造：基函數(shù)： n 次多項式 l 0 ( x),l1 (x),.l n (x) 滿足l i ( x j )1ijij0ijl k ( x)( xx0 )( xx1 ).( xxk 1 )( xxk 1 ).( xxn )(xkx0 )( xkx1 ).( xkxk 1 )( xkxk 1 ).( xkx

22、n )nLn (x)y0 l0 ( x)y1l1 (x) .ynl n ( x)k 0yk l k (x)-n 次 Lagrange 插值多項式三、插值余項定理：若f( n)(n1)(x)在 a,b存在 ， 則插值誤差( x)在 a, b連續(xù) ，f;.Rn (x)f (n 1)( )f (x) Ln ( x)( x) ，(n1)!其中 a,b依賴于 x 。§ 2分段插值一、分段線性插值在區(qū)間 a，b，分為 n 個區(qū)間 xi , xi 1 ,i=0,1,2n-1每個區(qū)間由直線代替曲線，形成分段線性插值函數(shù)(x)( x)l i ( x) yil i 1 (x) yi 1x xi , xi

23、 1 l i ( x)x xi 1， li 1 ( x)x xixixi 1xi 1xi二、分段拋物插值§3Newton插值一、差商及其性質(zhì)定義：一階差商： f xi , xi 1f ( xi 1 )f ( xi )xixi 1f xi 1 , xi 2 f xi , xi 1 二階差商： f xi , xi 1, xi 2 xi 2xiK 階差商： f xi , xi 1 ,., xi k f xi 1 , xi2 ,., xi k f xi , xi 1 ,.xi k 1 xi kxi性質(zhì)：（ 1）差商可由節(jié)點函數(shù)值表示；（ 2）差商值與節(jié)點次序無關。二、 Newton 插值多項

24、式由差商定義f ( x)f ( x0 )f x0 , x( xx0 )f x0 , xf x0 , x1 f x0 , x1 , x( xx1 )f x0 , x1 , xf x0 , x1 , x2 f x0 , x1, x2 , x( xx2 )。f x0 , x1 ,.xn 1 , xf x0 , x1 ,.xn f x0 , x1 ,.xn , x( xxn );.依次帶入N n ( x)f ( x0 )f x0 , x1 ( xx0 ).f x0 , x1 ,.xn ( xx0 ).( xxn 1 ) - Newton 插值多項式計算時先造差商表；三、余項f (n 1) ()f x0

25、 , x1 ,.xn , x(n1)!§4差分與等距節(jié)點插值多項式一、差分及其性質(zhì)：二、等距節(jié)點插值多項式§ 5 Hermite 插值一、帶導數(shù)的插值多項式1、問題：求次數(shù)不超過3次多項式H 3 ( x), 滿足 H 3 (x0 )y0 , H 3 ( x1 )y1 , H 3' ( x0 ) m0 , H 3' (x1 )m1 ；2、利用基函數(shù)構造H 3 ( x)0 (x) y01 ( x) y10 (x)m01 ( x) m10 (x)(1 2x x0 )(x x1 ) 2x0x1x0x11 (x) (1 2xx1 )( x x0 ) 2x1x0x1x0

26、0 (x)(x x0 )(xx1 ) 2x0x11 (x)(x x1 )(xx0 ) 2x1x0二、一般情形1、問題：求次數(shù)不超過2n+1 次多項式 H 2n1 ( x), 滿足 H 2 n1 (xi )yi , H 2'n1 (xi )mi ,i0,1,.n;2、利用基函數(shù)構造見教材;.第七章數(shù)值微積分1. 了解數(shù)值求積基本思想；2. 掌握 Newton-Cotes 公式（梯形公式， Simpson 公式，Cotes 公式）推導及誤差；3. 了解 Romberg 求積公式原理；4了解數(shù)值微分的方法。本章問題：數(shù)值積分問題b求定積分f ( x)dxF (b)F (a)a不能使用微積分公

27、式情形存在問題：（ 1）f(x)表達式復雜，原函數(shù)更復雜；（ 2）f(x)表達式不復雜，但原函數(shù)復雜；（ 3）原函數(shù)不存在；（ 3）f(x)無表達式§ 1 Newton-Cotes 公式一、 數(shù)值求積基本思想1、 不利用原函數(shù)，直接利用函數(shù)值b積分中值定理：f ( x)dx(ba) f ( )af ( ) 為平均高度；bn機械求積方法： If ( x)dxAi f ( xi )ai 0xi 為求積節(jié)點；Ai 為求積系數(shù)。2、 幾個簡單求積公式左矩形公式右矩形公式Ib(b a) f ( a)f (x)dxaIb(b a) f (b)f ( x)dxa;.中矩形公式 Ib(ba) f (

28、 ab )f ( x)dx2abab( )()梯形公式f (x)dxfafbI2a二、 Newton-Cotes 公式1、公式推導由 Lagrange 插值多項式 Ln (x) 代替函數(shù) f(x)bbbnIf (x)dxLn ( x)dxl i ( x) f ( xi )dxaaai 0b.nb(l i ( x)dx) f ( xi )ai0記 Ail i ( x)dxabnAi f ( xi )則 If ( x)dxa0i求積系數(shù) Ai 的計算：b a( 1)n innAini!( n i )!0 j0ji(ti ) dt (b a)Ci( n) -(ij )Ci( n) 為 Cotes 系

29、數(shù)；bnnAi f ( xi )(b a) C i( n ) f ( xi ) - Newton-Cotes 求積公式If (x)dxai 0i 02、 Cotes 系數(shù)性質(zhì)對稱性： Ci( n)C n(n i)n權性：Ci(n )1i 03、常用公式n=1bba()()If ( x)dxff梯形公式：a2n=2Simpson,拋物公式： Ibbaabf ( x) dx( f (a) 4 f () f (b)a62n=4Cotes 公式： Ibba (7 f ( x0 )32 f ( x1 )12 f ( x2 ) 32 f ( x3 ) 7 f ( x4 )f ( x)dxa90baxiai

30、4;.4 誤差估計：見教材舉例說明。§2Romberg求積公式一、復化梯形公式將積分區(qū)間 a,b， n 等份，步長hbanh f (a) 2n 1Tnf (xi ) f (b)2i 1誤差估計：二、梯形公式遞推化T2 n1 Tn h22n 1f (x 1 )i 0i2三、 Romberg求積公式由梯形公式修正，提高精度Sn4 T2n1 Tn3316 1Cn15 S2n 15 SnRn64 C2n1 Cn6363§ 3Gauss型求積公式一、代數(shù)精確度bn定義：若求積公式If ( x)dxAi f ( xi ) 對任意 m 次代數(shù)多項式精確成立，而對m+1 次代數(shù)ai 0多項

31、式不精確成立，稱求積公式具有m 次代數(shù)精確度。判定 ：求 積公 式 具有 m 次 代數(shù) 精確 度求 積公 式對 f ( x)1, x, x 2 ,., x m 精確 成 立； 而對f (x) x m 1不精確成立。例：梯形公式具有1 次代數(shù)精確度；定理 1：n+1 個節(jié)點的插值型求積公式代數(shù)精確度至少為n；定理 2；Newton-Cotes 公式代數(shù)精確度至少為 n；當 n 為偶數(shù)時，可達n+1 次代數(shù)精確度。二、 Gauss 型求積公式bn定義：若 n+1 個節(jié)點求積公式 If ( x) dxAi f ( xi ) 具有 2n+1 次代數(shù)精確度，則稱為 Gauss 型ai 0;.求積公式，節(jié)

32、點為Gauss 點。Gauss 點的特性：見教材第八章常微分方程數(shù)值解1. 掌握 Euler 方法（ Euler 公式，梯形公式， Euler 預估 -校正公式），局部截斷誤差，公式的階；2. 了解 Runge-Kutta 方法的基本思想及四階經(jīng)典 Runge-Kutta 公式；3. 掌握線性多步方法的原理與公式推導。本章問題：一階常微分方程初值問題dyf (x, y)dxy( x0 )y0解的存在性定理：解析解的概念數(shù)值解的概念§ 1 Euler 方法一、 Euler 公式導數(shù)離散化y' (xn )f ( xn , y( xn )由向前差商代替導數(shù)y' (xn )y( xn 1 ) y( xn )h得y( xn 1 )y( xn ) hf ( xn , y( xn )記為 yn1yn hf (xn , yn ) - Euler 顯式公式由向后差商代替導數(shù)y' (xn 1 )y( xn 1 ) y(xn )h得y( xn 1 )y( xn ) hf ( xn 1 , y(xn 1 )記為 yn1yn