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

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

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

4、(1) 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 列主元消去法例 ：說明直接消元，出

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

6、aij l ik akj（2）回代過程：1若 ann0, 則矩陣 A 奇異，程序結束；否則執行。an,n1; 對in 1,L ,2,1,計算2 xnannai, n 1naij xjj ixi1aii.舉例說明。4、消元法應用（ 1）行列式計算；（ 2）矩陣求逆。二、利用矩陣三角分解求解線性方程組1、求解原理線性方程組寫成矩陣形式為：AX=b若 A=LU，則 LUX= b，記 UX=Y則 LY= b若 L、 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 u rjjk, k1,.n;r1k1l ik( aikl ir u rk ) / ukkik, k1,.n

8、r1算法特點：先計算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） 正定對稱矩陣性質與判定：定義：是 n 階對稱矩陣，若對任意非零向量XRn ，有 X T AX0 ，則稱 A 為正定對稱矩陣；判定： A 為 n 階正

9、定對稱矩陣充要條件A 的各階順序主子式大于 0。（ 2） Cholesky 分解定理：設 A 為 n 階正定對稱矩陣，則存在唯一主對角線元素都是正數的下三角陣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 c

10、1a2b2c2l 2 1u2 C2a3b3 c3.l 3 1. . .un 1cn-1an 1 bn 1cn 1ln1unanbn.u1b1l iai / ui 1i 2,3,.nuibil i ci1三對角方程組的追趕法：追的過程LY=Dy1d1yidil i yi 1i2,3,.n趕的過程UX=Yxnyn / unxi( yici xi1 ) / uii n 1, n 2,.,1§ 2 線性方程組的迭代解法一、 Jacobi 迭代公式例：x11 x2122其解為x1 1, x211 x1x2122方程變形得到迭代公式x1( k 1)1 x2(k )2x2(k 1)1 x1( k

11、)2一般地，對線性方程組12給初值 X (0)0計算，觀察解的變化。102a11 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)(biai1x1(k ). ain xn(k ) ) / aii.xn(k1)(bnan1 x1(k ) .ann xn(k1) ) / ann.簡記為：nxi( k 1)(biaij x j ( k) ) / aiii 1

12、,2,., nj1ji二、 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迭代公式的收斂性一、 向量與矩陣的范數與性質1、 向量范數定義：向量 XRn ，對應非負實數X ，滿足三條件：（ 1）非負性（ 2）齊次性（ 3）三角不等式X0,X0, X0kXk XXYXY稱 X 為向量范數2、 常見向量范數1 范數X 1x1x2.xn2 范數X 2x12x22.xn2范數Xmaxn xi1i3、 矩

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

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

15、67;1二分法一、根的存在性定理：函數f(x) 在區間 a， b連續，且f(a).f(b)<0, 則方程 f(x)=0 在區間 a， b有根。方程的根存在，不一定唯一，若在區間a， b上有唯一根，稱區間a， b為根隔離區間。二、二分法（區間逐次分半法）原理：通過計算根隔離區間中點，將區間分半，縮小區間，得到方程近似根數列 x n 。a, ba1 , b1.an ,bn.bkak(ba) / 2 k取x*( anbn ) / 2§2迭代法一、迭代原理迭代法是一種逐次逼近法，由提供的遞推公式計算，逐次精確，直到滿足精度要求。方程 f(x)=0 變形為 x( x) ，得到遞推公式xk

16、 1(xk ) -簡單迭代公式稱 ( x) 為迭代函數給初值計算，得到數列 x n ，若lim xkx* ，則稱迭代收斂，否則發散。k例：求方程 10xx 2 0x*0.3,0.4寫出兩個簡單迭代公式：.（1） xk 110 xk2（ 2） xk 1lg( xk2)觀察計算得到數列 x n 的收斂性。迭代法的幾何解釋：二、迭代收斂性判定收斂性定理：設方程x(x) 的迭代函數( 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(

17、xk ) 收斂，即 lim xkx* ；k（ 3）誤差估計x*xkLkx1x0 。1L說明可根據迭代函數( x) 的導數判斷迭代收斂性。三、迭代公式的加速§ 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 弦截公式是兩步公式。第五

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

19、 ., x01nPn (x) a0a1 x .an xn 且滿足 Pn ( xi )f (xi )yi ，（ i=0,1, n）.2、插值多項式存在唯一條件：定理： Pn ( x)a0 a1 x.an xn 存在唯一條件是n+1 個節點互異。二、 Lagrange插值構造1、線形插值（ n=1）幾何解釋；利用插值基函數構造：基函數：一次多項式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 次 Lagra

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

21、 xx0 )( xx2 )( x)x0 )( 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、一般情形：利用插值基函數構造：基函數： n 次多項式 l 0 ( x),l1 ( x), .ln (x) 滿足l i ( x j )1ijij0ijl k ( x)( xx0 )( xx1 ).( xxk 1 )( xxk 1 ).( xxn )(xkx0 )( xkx1 ).( xkxk

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

23、 (x) yi 1x xi , xi 1 l i ( x)x xi 1， li 1 (x)x xixixi 1xi 1xi二、分段拋物插值§3Newton插值一、差商及其性質定義：一階差商： 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 ,., xik f xi , xi 1 ,.xi k 1 xixik性質：（1）差商可由節點函數值表示；（2）差商值與節點次序無關。二

24、、 Newton插值多項式由差商定義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

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

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

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

28、a梯形公式 Ibf (x)dxa(ba) f (b)ab(ba) f ()b a ( f ( a) f (b)2二、 Newton -Cotes 公式1、公式推導由 Lagrange 插值多項式 Ln ( x) 代替函數 f(x)bbbnnbl i ( x) f (xi )dxIf (x)dxLn ( x)dx( li ( x)dx) f (xi )aaa0i 0aib記 Ail i ( x)dxabn則 IAi f (xi )f ( x)dxai 0求積系數 Ai 的計算：b a( 1)n innAii!( n i )! 0 jn0ji(ti ) dt (b a)Ci( n) -(ij)C

29、i( n) 為 Cotes 系數；bnnIAi f (xi )(b a) C i(n ) f ( xi ) - Newton -Cotes 求積公式f (x)dxai 0i 02、 Cotes 系數性質對稱性： Ci( n)C n(n i)n(n )權性：Ci13、常用公式n=1Ibf ( x)dxba(f(a)f( )梯形公式：a2n=2baabbIf ( x) dx( f (a)4 f ()f(bSimpson,拋物公式：a62n=4babCotes 公式： If ( x) dx90(7 f( x0 )32f ( x1 )12 f ( x2 )32 f ( x3 ) 7 f ( x4 )a

30、.baxiai4 誤差估計：見教材舉例說明。4§2Romberg求積公式一、復化梯形公式ba將積分區間 a,b， n 等份，步長hnh f (a) 2n 1Tnf (xi ) f (b)2i 1誤差估計：二、梯形公式遞推化T2 n1 Tnh22n 1f ( xi1)i 02三、 Romberg求積公式由梯形公式修正，提高精度4 1Sn3 T2n 3 TnCn16 S2n1 Sn1515Rn64 C2n1Cn63 63§ 3 Gauss 型求積公式一、代數精確度bn定義：若求積公式If ( x)dxAi f ( xi ) 對任意 m 次代數多項式精確成立，而對m+1 次代數a

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

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