北航計算方法復(fù)習(xí)題課件

1、計算方法復(fù)習(xí)課 2019-12-29教學(xué)內(nèi)容引論第一章 插值方法第二章 數(shù)值積分第三章 常微分方程的差分方法第四章 方程求根的迭代法第五章 線性方程組的迭代法第六章 線性方程組的直接法（但精度、誤差等概念要貫穿于考題中）考題形式填空題主要考察基本概念，對方法的理解共8題，共40分五章的內(nèi)容基本平均分配大題計算、證明等5-6道題，共60分五章的內(nèi)容基本平均分配其中有1-2道題為作業(yè)題或書上的例題（可能改數(shù)）第一章 插值方法拉格朗日插值（插值余項）埃特金算法牛頓插值埃爾米特插值分段插值樣條插值曲線擬合的最小二乘法第一章 插值方法計算函數(shù)值 需要計算函數(shù)值，但函數(shù)關(guān)系復(fù)雜，沒有解析表達式。 常見的有

2、：由觀測數(shù)據(jù)計算未觀測到的點的函數(shù)值。 由觀測數(shù)據(jù)構(gòu)造一個適當(dāng)?shù)暮唵魏瘮?shù)近似的代替要尋求的函數(shù)插值法。 第一章 插值方法幾個典型問題： 問題1：設(shè)函數(shù)y=f(x)定義域為a，b，x0，x1，xn是a，b上的n+1個互異點，且yi=f(xi)已知，要構(gòu)造一個函數(shù)g(x)，使得g(xi)=yi(i=0,1, ,n)。 問題2：求做n次多項式pn(x)，使?jié)M足條件： 為一組已給數(shù)據(jù)。 問題3：=問題1+問題2：即過給定點，也要求導(dǎo)數(shù)相同。第一章 插值方法 問題1：設(shè)函數(shù)y=f(x)定義域為a，b，x0，x1，xn是a，b上的n+1個互異點，且yi=f(xi)已知，要構(gòu)造一個函數(shù)g(x)，使得g(xi

3、)=yi(i=0,1, ,n)。幾何意義：x0 x1x2x3x4xg(x) f(x)代數(shù)插值： 為多項式函數(shù)集第一章 插值方法 問題1：設(shè)函數(shù)y=f(x)定義域為a，b，x0，x1，xn是a，b上的n+1個互異點，且yi=f(xi)已知，要構(gòu)造一個函數(shù)g(x)，使得g(xi)=yi(i=0,1, ,n)。代數(shù)插值： 為多項式函數(shù)集Lagrange插值公式Aitken插值公式Newton插值公式 第一章 插值方法Lagrange插值公式Lagrange多項式Lagrange基函數(shù)滿足與 節(jié)點 有關(guān)，而與 f 無關(guān)給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪個是

4、l2(x)的圖像？ y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x ABC第一章 插值方法Lagrange插值公式Lagrange多項式Lagrange基函數(shù)思考1：令Rxn+1表示所有的不高于n次的實系數(shù)多項式和零多項式構(gòu)成的集合，假設(shè)函數(shù)y=f(x)的已知值(xi，yi) (yi=f(xi)，i=0，1，n)，尋找一個多項式Pn(x) Rxn+1，滿足：Pn(xi)=f(xi) (i=0，1，n) (*)唯一性？思考2：f(x)=

5、xk(k=0,1,n)關(guān)于互異節(jié)點xi(i=0,1,n)的拉格朗日插值公式第一章 插值方法Lagrange插值公式Lagrange多項式Lagrange基函數(shù) 1.2 0.4 -0.8 -2.0yi=f(xi) 2.0 1.8 1.4 1.0 xi求 的值 求方程 在1，2內(nèi)根的近似值 。 反插值問題例：已知單調(diào)連續(xù)函數(shù) 在如下采樣點的函數(shù)值：第一章 插值方法Lagrange插值公式Lagrange多項式Lagrange基函數(shù)（2）Lagrange插值多項式結(jié)構(gòu)對稱，形式簡單.注： （1）若不將多項式次數(shù)限制為 n ，則插值多項式不唯一。（4）當(dāng)插值節(jié)點增加時，拉氏基函數(shù)需要重新計算， n較大

6、時，計算量非常大,故常用于理論分析。（3）誤差估計第一章 插值方法Aitken插值公式(效率，或臨時增加一個節(jié)點)利用兩個k-1次插值fk-1(xk-1)， fk-1(xi)再做線性插值，結(jié)果得到k次插值fk(xi)的結(jié)果特點： 高次插值過程歸結(jié)為線性插值的多次重復(fù)； 數(shù)據(jù)的一致程度可判斷插值結(jié)果的精度。給定3個節(jié)點及節(jié)點上的函數(shù)值(xi，f(xi)(i=0，2)，按Aitken插值方法構(gòu)造插值函數(shù)，試在下圖中畫出任意給定x對應(yīng)的f2(x2) 第一章 插值方法Newton插值公式具有承襲性的顯示插值公式差商具有對稱性余項？第一章 插值方法問題2：求做n次多項式pn(x)，使?jié)M足條件： 為一組已

7、給數(shù)據(jù)。Taylor插值第一章 插值方法問題3：=問題1+問題2：即過給定點，也要求導(dǎo)數(shù)相同。Hermite插值求函數(shù)f(x)的二次近似式P2(x)，滿足： P2(x0)= f(x0) =y0, P2(x0)= f(x0) =y0, P2(x1)= f(x1) =y1。求函數(shù)f(x)的三次近似式p3(x)，滿足： P3(x0)= f(x0) =y0, P3(x0)= f(x0) =y0, P3(x1)= f(x1) =y1， P3(x1)= f(x1) =y1基函數(shù)法余項？第一章 插值方法分段插值高次插值可能會產(chǎn)生龍格現(xiàn)象 -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0

8、.5 1 1.5 2 2.5 第一章 插值方法高次插值可能會產(chǎn)生龍格現(xiàn)象分段插值光滑性問題樣條插值第二章 數(shù)值積分機械求積牛頓-柯特斯公式龍貝格算法高斯公式數(shù)值微分第二章 數(shù)值積分為什么研究數(shù)值積分： (1) 有些函數(shù)的原函數(shù)不能用初等函數(shù)表現(xiàn)為有限的形式； (2) 原函數(shù)的形式復(fù)雜； (3) 原函數(shù)沒有具體的表達式，只有離散點。定積分的數(shù)值解法(效率+精度)。第二章 數(shù)值積分機械求積 用被積函數(shù)f(x)的若干節(jié)點xi (ax0 x1 xnb)處的函數(shù)值f(xi)的線性組合 (數(shù)值積分公式，求積公式) 作為I(f)的近似值。 求積節(jié)點：xi(i=0，1，n) 求積系數(shù)：Ai(i=0，1，n)與

9、f(x)無關(guān)；一般形式 第二章 數(shù)值積分機械求積一般形式 一般性問題： 求積公式的收斂性:求積系數(shù)的特征:求積公式的穩(wěn)定性:求積系數(shù)全為正時，公式是穩(wěn)定的第二章 數(shù)值積分機械求積一般形式 一般性問題： 求積公式的精度： 如果求積公式對一切不高于m次的多項式都恒成立，而對于某個m+1次多項式不能精確成立，則稱該求積公式具有m次代數(shù)精度。 求積公式 具有次m代數(shù)精度的充要條件是 為 時求積公式精確成立，而 為 時求積公式不能成為等式。第二章 數(shù)值積分機械求積一般形式 Q1、節(jié)點已知，系數(shù)Ai如何選取Q2、節(jié)點自由選取，怎么選第二章 數(shù)值積分求積節(jié)點固定的情況一般思想：取簡單的、便于積分且又逼近于被

10、積函數(shù)f(x)的函數(shù)(x)代替f(x)來構(gòu)造求積公式；典型插值多項式pn(x)dx插值型求積公式插值型求積公式余項：插值型求積公式的代數(shù)精度： 插值型求積公式至少具有n次代數(shù)精度 具有n次代數(shù)精度的求積公式必是插值型的第二章 數(shù)值積分求積節(jié)點固定的情況第二章 數(shù)值積分求積節(jié)點固定的情況設(shè)a，b為有限區(qū)間，取h=(b-a)/n，等距節(jié)點 xi=a+ih(i=0，1，n)。記x=a+th(0t n)，則：牛頓-柯特斯公式第二章 數(shù)值積分求積節(jié)點固定的情況梯形公式Simpson公式Cotes公式階數(shù)越高越好？精度？穩(wěn)定性？ n為偶數(shù)時， NewtonCotes求積公式至少具有n+1次代數(shù)精度。 n為

11、奇數(shù)時，NewtonCotes求積公式至少具有n次代數(shù)精度。復(fù)化求積公式第二章 數(shù)值積分求積節(jié)點可選擇的情況高斯求積公式提高精度當(dāng)求積節(jié)點個數(shù)確定后，不管這些求積節(jié)點如何選 取，求積公式的代數(shù)精度最高能達到多少？具有最高代數(shù)精度的求積公式中求積節(jié)點如何選??？第二章 數(shù)值積分求積節(jié)點可選擇的情況高斯求積公式提高精度不失一般性，由代數(shù)精度構(gòu)造插值型數(shù)值求積公式 求積節(jié)點xi(i=1，2，n)( ax1 x2 xn b)。適當(dāng)?shù)倪x取求積節(jié)點xi和求積系數(shù)Ai，可以使得該插值公式具有2n-1次代數(shù)精度。高斯求積公式和高斯求積點。第二章 數(shù)值積分求積節(jié)點可選擇的情況高斯求積公式提高精度n=1： 中點公式

12、n=2： 具有3次代數(shù)精度。對于任意區(qū)間a,b，第二章 數(shù)值積分求積節(jié)點可選擇的情況高斯求積公式提高精度高斯點的特點 節(jié)點xi(i=1，2，n)是高斯點的充要條件是：多項式 與一切次數(shù)n-1的多項式p(x)正交，即成立：高次的高斯公式不便于應(yīng)用，一般可借鑒復(fù)合求積方法第二章 數(shù)值積分求積節(jié)點可選擇的情況高斯求積公式提高精度高斯求積公式的余項 Gauss型求積公式總是穩(wěn)定的。設(shè)f在a,b上連續(xù)，則Gauss型求積公式是收斂的高斯求積公式的穩(wěn)定性 高斯求積公式的收斂性 第三章 常微分方程的差分方法歐拉方法改進的歐拉方法龍格-庫塔方法亞當(dāng)姆斯方法收斂性與穩(wěn)定性方程組與高階方程的情形邊值問題重點： 構(gòu)

13、造某種格式 格式的收斂性和穩(wěn)定性 格式的精度第三章 常微分方程的差分方法典型的微分方程(一階方程的初值問題)求解的核心消除導(dǎo)數(shù) 離散化方法差分方法是一類重要的數(shù)值解法初值問題 的解表示過點 的一條曲線初值問題 的數(shù)值解表示一組離散點列第三章 常微分方程的差分方法局部截斷誤差整體截斷誤差設(shè) 是準(zhǔn)確的，用某種方法計算 時產(chǎn)生的截斷誤差，稱為該方法的局部截斷誤差稱 為某方法在點 的整體截斷誤差去掉 準(zhǔn)確的前提如果其局部截斷誤差為O(hp+1)，稱該數(shù)值方法的精度是p階的定義精度判斷收斂性第三章 常微分方程的差分方法Euler方法差商代替導(dǎo)數(shù)隱式Euler方法向后差商兩步Euler格式中心差商公式第三

14、章 常微分方程的差分方法微分方程轉(zhuǎn)化為積分方程選取不同的數(shù)值積分公式不同的離散方法(差分格式)矩形格式 梯形格式第三章 常微分方程的差分方法改進的歐拉方法：預(yù)報-校正系統(tǒng)第三章 常微分方程的差分方法龍格-庫塔方法高精度(構(gòu)造！)思想核心是如何確定 區(qū)間xn, xn+1上的平均斜率第三章 常微分方程的差分方法龍格-庫塔方法高精度(構(gòu)造！)思想核心是如何確定 區(qū)間xn, xn+1上的平均斜率第三章 常微分方程的差分方法龍格-庫塔方法二階龍格-庫塔：取xn和xn+p= xn+ph，0p1。合理的確定、p，以提高精度。有： p=1/2。二階Runge-Kutta格式（二階精度）=1/2，p=1，改進的

15、Euler公式；=1，p=1/2，變形的Euler公式中點公式；類似可得三階Runge-Kutta格式（三階精度）第三章 常微分方程的差分方法龍格庫塔方法的基本思想亞當(dāng)姆斯方法的基本思想第三章 常微分方程的差分方法亞當(dāng)姆斯方法基本思想：利用xn，xn-1， xn-2 上的斜率值減少計算yn+1的計算量或提高精度。取合理的，使上述格式具有二階精度 二階Adams格式（=-1/2）第三章 常微分方程的差分方法亞當(dāng)姆斯方法斜率外推變成內(nèi)插（改善精度）隱式亞當(dāng)姆斯格式三階四階二階隱式Adams格式第三章 常微分方程的差分方法收斂性與穩(wěn)定性 收斂性問題 若 ，則稱該方法收斂。 歐拉格式：如果初值準(zhǔn)確，則

16、有h0,en 0，Euler格式收斂。第三章 常微分方程的差分方法收斂性與穩(wěn)定性 穩(wěn)定性問題每一步的計算并不嚴(yán)格準(zhǔn)確，存在計算誤差的傳播問題擾動。 若則稱為穩(wěn)定的。第四章 方程根的迭代法迭代過程的收斂性迭代過程的加速牛頓法弦截法重點： 不動點理論 寫出有收斂性的格式，用于解題第四章 方程根的迭代法迭代法基本思想 從給定的一個或幾個初始近似值(初始值)x0、x1、x2、xr出發(fā)，按某種方法產(chǎn)生的一個序列x0，x1，x2，xr， xr+1，xk ，稱為迭代序列，使得此序列收斂于方程f(x)=0的一個根x*。 當(dāng)k足夠大時，取xk作為x*的近似值。需要討論的問題 迭代法的構(gòu)造(迭代格式)； 迭代序列

17、的收斂性和收斂速度； 誤差估計。第四章 方程根的迭代法迭代格式 如何構(gòu)造序列x0，x1，x2，xk 如何判斷迭代格式的好壞收斂性及收斂速度誤差估計第四章 方程根的迭代法收斂性 解的收斂與初值選取范圍有關(guān)。 大范圍收斂：從任何可取的初始值出發(fā)都能保證收斂； 局部收斂：初始值充分接近于所要求的根，如果存在鄰域： ，使迭代過程對于任何初值x0 均收斂。 收斂速度收斂階數(shù) 令 若存在實數(shù)和非零常數(shù)C，使得 則稱該迭代法為階收斂，或者說收斂階數(shù)為。第四章 方程根的迭代法將非線性方程f(x)=0化為等價方程 x=g(x)f (x) = 0 x = g (x)（迭代函數(shù)）等價變換f (x) 的根g (x)

18、的不動點第四章 方程根的迭代法 假設(shè)g(x)為定義在有限區(qū)間a，b上的一個實函數(shù)，滿足下列條件： (1) (2) 存在 0 L1，對于任意x a，b ，成立則對任意的初始值x0 a，b ，由Picard迭代產(chǎn)生的序列都收斂于g(x)的唯一不動點x*，并有誤差估計式不動點迭代不動點理論（壓縮映像原理）定理1第四章 方程根的迭代法封閉性條件壓縮性條件判斷結(jié)果的精度速度迭代步數(shù)估計 1）兩個條件： (1) (2) 存在 0 L2)階連續(xù)導(dǎo)數(shù)，x*是方程f(x)=0的單根，則當(dāng)x0充分接近x*時，Newton法收斂，且至少為二階收斂。Newton法的收斂性與x0的選取有關(guān)牛頓迭代法的優(yōu)缺點 優(yōu)點： 在單根附近, 牛頓迭代法具有平方收斂(至少)的 速度，所以在迭代過程中只要迭代幾次就會得 到很精確解。 缺點:1. 重根情形下為局部線性收斂; 2. 牛頓迭代法計算量比較大:因每次迭代除計算 函數(shù)值外還要計算導(dǎo)數(shù)值; 3. 選定的初值要接近方程的解，否則有可能得不 到收斂的結(jié)果;第四章 方程根的迭代法第四章 方程根的迭代法弦截法導(dǎo)數(shù)計算比較復(fù)雜，采用差商公式替換Newton公式中的導(dǎo)數(shù)，有：當(dāng)x0充分接近x*，0|g(x)|1，從而線性收斂提高收斂速度？第五章 線性方程組的迭代法迭代公式的建立迭代過程的收斂性迭代法的基