數(shù)值分析1PPT課件

1、教材教材 應用數(shù)值分析應用數(shù)值分析 鄭咸義等鄭咸義等 編著編著 （華南理工大學出（華南理工大學出版社）版社）參考書目 Numerical Analysis:Mathematics of Scientific Computing (Third Edition) David Kincaid & Ward Cheney（機械工業(yè)出版社) Numerical Analysis (Seventh Edition) Richard L. Burden & J. Douglas Faires （高等教育出版社）第1頁/共554頁 數(shù)值分析的研究對象數(shù)值分析的研究對象n 數(shù)值分析屬于計算數(shù)學的

2、范疇，是數(shù)學的一個分支，也稱為數(shù)值計算方法、計算方法、數(shù)值方法等。n 其研究對象是求解各種數(shù)學問題的數(shù)值方法的設計、分析及其有關(guān)的數(shù)學理論和具體實現(xiàn)的一門學科。n 它是科學與工程計算（科學計算）的基礎。第2頁/共554頁 許多科學與工程實際問題（如：核武器的研制、導彈的發(fā)射、氣象預報等）的解決都離不開科學計算。 目前，理論、試驗、計算已成為人類進行科學活動的三大方法。 數(shù)值分析的研究對象數(shù)值分析的研究對象第3頁/共554頁 科學計算的過程，是從數(shù)學模型的提出到上機計算得出結(jié)果的完整過程。（下圖表明了其中的圖表明了其中的主要步驟主要步驟和和相互關(guān)系相互關(guān)系 ）數(shù)學化離散化程序化數(shù)學模型數(shù)值算法編

3、制程序上機運行輸出結(jié)果實際問題 數(shù)值分析研究的對象數(shù)值分析研究的對象第4頁/共554頁 數(shù)值分析研究的對象數(shù)值分析研究的對象 n 數(shù)值分析是數(shù)學、計算機科學與其他學科數(shù)值分析是數(shù)學、計算機科學與其他學科交叉交叉的產(chǎn)物的產(chǎn)物。n 本門課程將著重介紹進行本門課程將著重介紹進行科學計算科學計算所所必須掌握的一些最基本、最常用的必須掌握的一些最基本、最常用的數(shù)值方數(shù)值方法法（數(shù)值算法），并作相關(guān)分析（數(shù)值算法），并作相關(guān)分析。第5頁/共554頁數(shù)值分析的任務數(shù)值分析的任務 對典型的數(shù)學問題給出數(shù)值求解方法對典型的數(shù)學問題給出數(shù)值求解方法( (近似方法近似方法) )，并對算法進行理論分析，使，并對算法進

4、行理論分析，使得其能夠在計算機有效地得以實現(xiàn)。得其能夠在計算機有效地得以實現(xiàn)。 數(shù)值算法的數(shù)值算法的構(gòu)造構(gòu)造 算法的理論算法的理論分析分析第6頁/共554頁數(shù)值分析的任務數(shù)值分析的任務 針對數(shù)值問題研究可在計算機上執(zhí)行且行之有效行之有效 的計算公式（數(shù)值算法）。 例：解線性方程組，已有Cramer法則，但不可行。 數(shù)值算法的分析，主要包括誤差分析誤差分析（數(shù)值問題的性態(tài)，數(shù)值方法的截斷誤差、舍入誤差和穩(wěn)定性、收斂性等）和復雜性分析復雜性分析（計算量、存儲量）。 第7頁/共554頁課程課程目的目的 學習一些常用的數(shù)值方法，掌握 數(shù)值方法的基本理論，為進一步 研究和使用更復雜的數(shù)值算法奠定 基礎。

5、 初步掌握一種科學計算軟件包 （如Matlab）的使用方法。 第8頁/共554頁課程主要內(nèi)容課程主要內(nèi)容u 插值方法；u 曲線擬合與函數(shù)逼近； 數(shù)值逼近u 數(shù)值積分與數(shù)值微分；u 線性代數(shù)方程組數(shù)值求解的直接法；u 線性代數(shù)方程組數(shù)值求解的迭代法； 數(shù)值代數(shù)u 非線性方程與方程組數(shù)值求解；u 常微分方程數(shù)值求解。 Matlab 簡介第9頁/共554頁第一章第一章 緒緒 論論主要內(nèi)容：u 一些常用概念；u 數(shù)值算法的復雜度與穩(wěn)定性。u 數(shù)值計算中的誤差；u 數(shù)值算法設計的若干原則；第10頁/共554頁 1. 1.數(shù)值分析中常用的一些概念數(shù)值分析中常用的一些概念 F 數(shù)值問題F 數(shù)值解F 算法F

6、計算量F 病態(tài)問題F 算法數(shù)值穩(wěn)定性第11頁/共554頁 數(shù)值問題、數(shù)值解數(shù)值問題、數(shù)值解 、算法、算法 由一組已知數(shù)據(jù)（輸入數(shù)據(jù)），求出一組結(jié)果數(shù)據(jù)（輸出數(shù)據(jù)），使得這兩組數(shù)據(jù)之間滿足預先制定的某種關(guān)系的問題，稱為數(shù)值問題。 由數(shù)值計算公式算出的數(shù)值形式的解(通常由計算機計算得到)稱為數(shù)值解。一般數(shù)值解是近似解。由給定的已知量，經(jīng)過有限次的四則運算及規(guī)定的運算順序，求出所關(guān)心的未知量的數(shù)值解，這樣所構(gòu)成的整個計算步驟，稱為數(shù)值算法（簡稱算法）。 第12頁/共554頁 計算量計算量一個算法所需要的乘法和除法總次數(shù)稱為計算量。計算量的單位為flop，表示完成一次浮點數(shù)乘或除法所需要的時間。算法的

7、計算量可以衡量算法的優(yōu)劣，因為它體現(xiàn)著算法的計算效率，通常算法的計算量越小，則算法的計算效率越高，因而該算法也越好。由于計算機做加減法要比乘除法快得多，故算法的計算量可以不考慮加減法的時間。例: 設A，分別為1020，2050，5010的矩陣，計算 D=ABC 就有如下不同的算法和計算量 算法1：D=(AB)C 計算量 N1=15000 flop; 算法2：D=A(BC) 計算量 N2=12000 flop.第13頁/共554頁 病態(tài)問題病態(tài)問題因初始數(shù)據(jù)的微小變化，導致解產(chǎn)生劇烈變化問題稱為病態(tài)問題。病態(tài)問題也稱為壞問題，這類問題通常是問題本身固有的。 求解病態(tài)問題應該特別注意，因為實際問題

8、的數(shù)據(jù)都是近似的或經(jīng)計算機計算要對輸入數(shù)據(jù)做舍入處理，這都引起原始數(shù)據(jù)的擾動，若所求解的正好是個病態(tài)問題，則采用通常算法計算就會出現(xiàn)很隱蔽的錯誤，導致不良的后果。病態(tài)問題在函數(shù)計算、方程求根及方程組求解中都是存在的，它的計算或求解應用專門的方法或?qū)⑵滢D(zhuǎn)化為非病態(tài)問題來求解。第14頁/共554頁 例例：病態(tài)的方程組病態(tài)的方程組考察方程組和 上述方程組盡管只是右端項有微小擾動，但解大不相同： 一個是 ，一個是 。 這類方程組稱為病態(tài)的。 121221.00012.0001xxxx121221.00012xxxx121xx122,0 xx第15頁/共554頁算法的數(shù)值穩(wěn)定性算法的數(shù)值穩(wěn)定性 在計算過

9、程中產(chǎn)生的舍入誤差能被控制在一定的范圍內(nèi)，且對最后的結(jié)果影響不大的算法稱為數(shù)值穩(wěn)定算法。不是數(shù)值穩(wěn)定的算法稱為數(shù)值不穩(wěn)定算法。 數(shù)值不穩(wěn)定算法會導致計算結(jié)果失真，對數(shù)值不穩(wěn)定的算法常采用轉(zhuǎn)化成相應的數(shù)值穩(wěn)定的算法來處理 。第16頁/共554頁 2. 2.對算法所要考慮的問題對算法所要考慮的問題2 20 09 9. .7 7 1 10 01. 計算速度。計算速度。 例如，求解一個20階線性代數(shù)方程組，若用克萊姆法則要進行約 次乘法運算，如用每秒1億次乘法運算的計算機要30萬年。而用Gauss消去法只需約3000次乘法運算，用普通微機1秒之內(nèi)便可算出結(jié)果。20209.7109.71021102.

10、存儲量。 大型問題有必要考慮。 3. 收斂性。 不收斂的算法無使用價值。 4. 數(shù)值穩(wěn)定性。 在大量計算中，舍入誤差的積累能否控制住，這與算法有關(guān)。第17頁/共554頁3. 3. 數(shù)值計算中的誤差數(shù)值計算中的誤差來源及種類 - 模型誤差、參數(shù)誤差、 截斷誤差、舍入誤差。1. 模型誤差（也稱描述誤差）模型誤差（也稱描述誤差） 模型誤差是在建立數(shù)學模型時，由于忽略了一些次要因素而產(chǎn)生的誤差，它是數(shù)學建模階段要考慮的誤差，不是計算方法可以解決的。2. 參數(shù)誤差（也稱觀測誤差）參數(shù)誤差（也稱觀測誤差） 測量已知參數(shù)時，數(shù)據(jù)帶來的誤差 ，它也不是計算方法能解決的問題。第18頁/共554頁 數(shù)值計算中的誤

11、差數(shù)值計算中的誤差3. 截斷誤差（也稱方法誤差）截斷誤差（也稱方法誤差） 截斷誤差是對參與計算的數(shù)學公式做簡化可行處理后所產(chǎn)生的誤差（用有限過程代替無限過程或用容易計算的方法代替不容易計算的方法），即數(shù)學模型的數(shù)值解與精確解之間數(shù)值解與精確解之間的誤差的誤差，是計算方法關(guān)注的內(nèi)容。（舉例：P6 sinx = ）4. 舍入誤差（也稱計算誤差）舍入誤差（也稱計算誤差） 舍入誤差是由于計算機只能表示有限位數(shù)字，因而只能取取有限位數(shù)進行計算所得的誤差有限位數(shù)進行計算所得的誤差，它也是計算方法關(guān)注的內(nèi)容。 （舉例： ）3.141592653第19頁/共554頁 數(shù)值計算中的誤差數(shù)值計算中的誤差誤差的基本

12、概念 絕對誤差 - 近似數(shù) x * 關(guān)于準確數(shù) x 的絕對誤差： E(x) = x x *（或E(x *) = x x * ） - 近似數(shù) x * 關(guān)于準確數(shù) x 的絕對誤差限：E(x)= x x * - 工程上表示準確數(shù) x 的范圍： x * x x * + 或 x = x * - 函數(shù)值的絕對誤差：Ef (x) f (x) E(x) （利用微分中值公式導出） 舉例：f (x) = x3第20頁/共554頁數(shù)值計算中的誤差數(shù)值計算中的誤差相對誤差 - 近似數(shù) x * 關(guān)于準確數(shù) x 的相對誤差：( )( )( )( )或rr xE xE xE xE xxxxxxxx( )rE xxxx( )

13、( )( )( )( )( )rE f xE xEfffxxf xx- 函數(shù)值的相對誤差限： - 近似數(shù) x * 關(guān)于準確數(shù) x 的相對誤差限：第21頁/共554頁 數(shù)值計算中的誤差數(shù)值計算中的誤差有效數(shù)字 - 用 x * 表示 x 時準確到小數(shù)點后第 k 位：1102kxx11211221 20.1010 (101010 ),01102mnnnnmnmxx xxxxxx x xxx nm xx 即 其中 = 0 9，且 （最左一位非零字）； 是正整數(shù)，是整數(shù)。- 近似數(shù) x * 具有 n 位有效數(shù)字：舉例1113.1415926530.314592653103.14160.31416 103

14、.140.314 10第22頁/共554頁 數(shù)值計算中的誤差數(shù)值計算中的誤差有效數(shù)字與相對誤差的關(guān)系 - n 位有效數(shù)字的近似數(shù) x * 其相對誤差：11(1)11002( )nrxxEx（最左一位），且 (1)11( )11002(1)nrExxx（最左一位），且 - 相對誤差為 的近似數(shù) x * 至少具有 n 位有效數(shù)字。注：在未標明近似數(shù)的絕對誤差時默認該近似數(shù)準確到末位數(shù)字， 從其最左邊的非零數(shù)字起直到最右邊的一位數(shù)字止均為有效數(shù)字。第23頁/共554頁 4. 4. 數(shù)值計算中應注意的幾個問數(shù)值計算中應注意的幾個問題題若干原則 - 注意簡化計算步驟，減少運算次數(shù)； （例：秦九韶算法)避

15、免兩個相近的數(shù)相減，減少有效 數(shù)字的損失；（例）使用數(shù)值穩(wěn)定的算法;（例:習題1.16）小心處理病態(tài)的數(shù)學問題；第24頁/共554頁復習題習題 1.1(3)(4)、1.2、1.3、1.4、 1.6、1.9 (1) 、1.15、1.16第25頁/共554頁2.1 插值問題的提出第二章 函數(shù)近似計算的插值法第26頁/共554頁( )iiyf xxf1. 在工程實際問題中,某些變量之間的函數(shù)關(guān)系是存在的, 但通常不能用式子表示,只能由實驗或觀測得到 在一系列離散點上的函數(shù)值. 2( )f x. 有的函數(shù)雖然有表達式,但比較復雜, 計算函數(shù)很 不經(jīng)濟且不利于在計算機上進行計算.( ,)( ).iixf

16、yf x希望通過這些數(shù)據(jù)計算函數(shù)在其他指定點處的近似值或獲取其他信息,( )( ).P xf x這兩種情況下 都希望用簡單的函數(shù)來逼近原函數(shù)插值問題的提出第27頁/共554頁插值：已知a, b上的函數(shù)y= f (x)在n+1個互異點處的函數(shù)值:fnf2f1f0f(x)xnx2x1x0 x求簡單函數(shù) P (x)，使得( )0,1,( ),*iiP xfin計算 f (x)可通過計算 P (x)來近似代替。如下圖所示。yxx0 x1f0f1x2f2xifixi+1fi+1xn-1fn-1xnfnP (x)f(x)一、插值問題的數(shù)學提法第28頁/共554頁這就是插值問題, (*)式為插值條件,( )

17、( )P xf x稱函數(shù)為函數(shù)的 插值函數(shù)則稱之為插值多項式為多項式函數(shù)如果,)(xP稱為插值節(jié)點點, 2 , 1 , 0,nixi稱為插值區(qū)間區(qū)間,ba個等分點上若給定如函數(shù)5,0,sinxy 其插值函數(shù)的圖象如圖第29頁/共554頁00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533

18、.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy( )( )f xP x對于被插函數(shù)和插值函數(shù)ix在節(jié)點處的函數(shù)值必然相等( )( )P xf x但在節(jié)點外的值可能就會偏離( )( )P xf x因此近似代替必然存在著誤差（截斷誤差）第30頁/共554頁整體誤差的大小反映了插值函數(shù)的好壞.為了使插值函數(shù)更方便在計算機上運算,一般插值函數(shù)都使用代數(shù)多項式或有理函數(shù).本章討論的就是(代數(shù))多項式插值.第31頁/共554頁1. 滿足插值條件的多項式 P(x)是否存在且唯一？2. 若滿足插值條件的P(x)存在,又如何構(gòu)造出P(x);即插值多項式的常用構(gòu)造方法有哪些？

19、3. 用P(x)代替f(x)的誤差估計，即截斷誤差的估計；對于多項式插值，我們主要討論以下幾個問題：4. 當插值節(jié)點無限加密時，插值函數(shù)是否收斂于 f(x)。第32頁/共554頁二、插值多項式的存在唯一性( ) , yf xa b設函數(shù)在區(qū)間上的代數(shù)插值多項式為nnnxaxaxaaxP2210)(且滿足()0,1,2, ,niiP xfin.ia其中是n+1個待定的系數(shù)第33頁/共554頁012( ),nnP xa a aa即多項式的系數(shù)滿足線性方程組20102000nnaa xa xa xf201 12111nnaa xa xa xf2012nnnnnnaa xa xa xf-(1)上述方程

20、組的系數(shù)行列式為n+1階Vandermond行列式nnnnnnxxxxxxxxxV212110200111101)(ninijijxxjixx 0第34頁/共554頁定理1. 由Cramer法則,線性方程組(1)有唯一解nnnxaxaxaaxP2210)()0,1,2,niiP xfin-(3)-(2),(jixxji若插值節(jié)點則滿足插值條件的次數(shù) n 的插值多項式存在且唯一.雖然線性方程組(1)推出的插值多項式存在且唯一,但通過解線性方程組(1)求插值多項式卻不是好方法.第35頁/共554頁 2.2 Lagrange插值多項式第二章 函數(shù)近似計算的插值法第36頁/共554頁若通過求解線性方程

21、組(1)來求解插值多項式 系數(shù) , 不但計算工作量較大, 且難于得到ia( )nP x的簡單表達式.一、 代數(shù)多項式的構(gòu)造:( )nP x可通過找插值基函數(shù)的方法,得到插值多項式!十八世紀法國數(shù)學家Lagrange對以往的插值算法進行研究與整理，提出了易于掌握和計算的統(tǒng)一公式，稱為Lagrange插值公式。 它的特例是線性插值公式和拋物線插值公式。Lagrange插值多項式第37頁/共554頁1. 線性插值 已知兩個插值點及其函數(shù)值：xx0 x1f(x)f0f1插值節(jié)點對應的函數(shù)值求一次多項式1( ),P xabx使得 11110001)()(fbxaxPfbxaxP 由于方程組的系數(shù)行列式0

22、110110 xxxx第38頁/共554頁所以，按Gramer法則，有唯一解01100110110011xxfxfxxxxfxfa 010110101111xxffxxffb 于是,)(01010110011xxxffxxfxfxxP 101001011)(fxxxxfxxxxxP 或(B-1）第39頁/共554頁 容易驗證，過點（x0，f0）與（x1，f1）直線方程就是式（B-1），如圖2-3所示。yxx0 x1P1(x)f(x)P1(x)f(x)誤差圖2-3第40頁/共554頁2. 拋物線插值 已知三個插值節(jié)點及其函數(shù)值：f2f1f0f(x)x2x1x0 x求一個二次多項式22( )P x

23、abxcx使得 222222121112020002)()()(fcxbxaxPfcxbxaxPfcxbxaxP由于該方程組的系數(shù)行列式 。行列式行列式階階eVandermondxxxxxx30111222211200 第41頁/共554頁所以，有唯一解。即滿足這樣條件的二次多項式是唯一確定的。滿足上述條件，所以它就是所求的二次多項式。 容易看出2120210121012002010212)()()()()()()(fxxxxxxxxfxxxxxxxxfxxxxxxxxxP（B-2）容易驗證，P2(x)是過點(x0, f0)、(x1, f1)與(x2, f2)三點的拋物線，如圖2-4所示。yx

24、x1x0 x2P2(x)f(x)圖2-4f0f1f2第42頁/共554頁3. n 次Lagrange插值已知 n+1 個插值節(jié)點及其函數(shù)值：fnf2f1f0f(x)xnx2x1x0 x插值節(jié)點相應的函數(shù)值求次數(shù)不超過 n 的多項式Pn(x) 。2012( )nnnP xaa xa xa x使得 nnnnnnnnnnnnnnnnnfxaxaxaaxPfxaxaxaaxPfxaxaxaaxPfxaxaxaaxP2210222222102112121101002020100)()()()(第43頁/共554頁維的間是的多項式構(gòu)成的線性空所有次數(shù)不超過n1n根據(jù)線性空間的理論,11nn這個維線性空間的

25、基也由個多項式組成并且形式不是唯一的n而任意一個 次多項式可由基線性表示且在不同的基下有不同的形式01( ),( ),( )1nxxxn設為上述維線性空間的一個基第44頁/共554頁線性表示可由次多項式且任意)(,),(),()(10 xxxxPnnn線性無關(guān)顯然)(,),(),(10 xxxn)()()()(1100 xaxaxaxPnnn的插值函數(shù)為某個函數(shù)如果)()(xfxPn為插值基函數(shù)則稱)(,),(),(10 xxxnnifxPiin, 2 , 1 , 0)(且滿足插值條件:為插值節(jié)點其中nixi,2 , 1 , 0,()0,1,2,iif xfin第45頁/共554頁上的一組節(jié)點

26、為區(qū)間如果,210babxxxxannjxlnj,2 , 1 ,0),(次多項式我們作一組)()()()()()()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnjiiijixxxx0)()(nj,2 , 1 ,0010()()()()nniixxxxxxxx1( )nx令)(1jnx則)()()(1110njjjjjjjxxxxxxxxxxn+1次多項式第46頁/共554頁)()()()()()()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnj,2 , 1 ,0且()jilx10ijijnji,2 , 1

27、,0,-(4)線性無關(guān)顯然)(,),(),(),(210 xlxlxlxln)()(11jjnnxxxx從而第47頁/共554頁的插值基函數(shù)作如果用)()(,),(),(),(210 xfyxlxlxlxln則的插值多項式為而,)()(xfxPn)()()()(1100 xlaxlaxlaxPnnn為待定參數(shù)、其中naaa10)(inxPnifxfii, 2 , 1 , 0)(令即njijjxla0)(nifi, 2 , 1 , 0由(4)式,可得nifaii, 2 , 1 , 0第48頁/共554頁為記為項式為插值基函數(shù)的插值多以上在節(jié)點于是)(), 1 , 0()(,), 1 , 0()(

28、,xLnixlnixxfynji0011( )( )( )( )nnnL xlx fl x flx f)(xljnjiiijixxxx0)()(其中-(6)-(5)(5)( )( )nL xyf xLagrange稱式為的插值多項式( ) (0,1, )jlxinnLagrange稱(6)式為 次插值基函數(shù)第49頁/共554頁0( )( )( )nnnkkkP xL xlxf其中11( )( )()()nknkkxlxxxx 這個改寫了的Lagrange插值公式，在許多理論分析中是比較有用的。Lagrange插值公式的標準型公式:第50頁/共554頁例1:15)225(,13)169(,12)

29、144()(fffxf滿足已知.)175(,)(的近似值并求插值多項式的二次作fLagrangexf解:225,169,144210 xxx設)(0 xl插值基函數(shù)為的二次則Lagrangexf)()()(201021xxxxxxxx2025)225)(169(xx)(1xl)()(210120 xxxxxxxx1400)225)(144(xx)(2xl)()(120210 xxxxxxxx4536)169)(144(xx01212,13,15fff第51頁/共554頁插值多項式為的二次因此Lagrangexf)(20 01 12 2( )( )( )( )L xf lxf l xf lx且)

30、175(f)175(2L)175(15)175(13)175(12210lll73158230.13在例1中,如果只給出兩個節(jié)點169和225,也可以作插值多項式,即1次Lagrange插值多項式,有兩個插值基函數(shù),也就是Lagrange線性插值.第52頁/共554頁Lagrange線性插值基函數(shù)(一次插值)為Lagrange線性插值多項式為0101,x xff節(jié)點函數(shù)值101xxxx0( )lx1( )l x010 xxxx10011( )( )( )L xlx fl x f1001xxfxx0110 xxfxx第53頁/共554頁例2.).175(1fLagrange中的線性插值多項式求例

31、用之間與在由于插值點22516917521xxx解:為插值節(jié)點與因此取22516921xx)(1xl212xxxx56225x)(2xl121xxxx56169xLagrange插值基函數(shù)為Lagrange線性插值多項式為11 12 2( )( )( )L xf l xf lx5622513x5616915x第54頁/共554頁)175(f5622517513561691751571285214.13所以第55頁/共554頁二、插值余項插值的從上節(jié)可知Lagrangexfy)(,0( )( )nnjjjL xlx f滿足nixfxLiin, 1 , 0)()(,bax但)()(xfxLn不會完

32、全成立因此, 插值多項式存在著截斷誤差, 那么我們怎樣估計這個截斷誤差呢？1( )( )( ),( )( )( )( )( )nninnnRxf xL xxRxf xL xK xx設則 為其零點，可設第56頁/共554頁1( )( )( )( )nnf xL xK xx01( )( )( )( )( )nntf tL tK xt若引入輔助函數(shù))(x則有0的區(qū)分與注意xt)(ix且)()()(1ininxxKxR0即個零點上至少有在區(qū)間若令因此,2,)(,nbatxxi,0)(xni, 1 , 0nixi, 2 , 1 , 0,0)(1( )( ),( ),( )nnL xxf xt由于和為多項

33、式 因此若可微 則也可微1( )( )( )( )nnf xL xK xx1()()( )()ininif xL xK xx則成立第57頁/共554頁根據(jù)Rolle定理,個零點上有至少在區(qū)間1),()(nbat再由Rolle定理,個零點上有至少在區(qū)間nbat),()( 依此類推階導數(shù)為零的使得內(nèi)至少有一個點在區(qū)間1)(,),(ntba0)()1(n)()1(tn1()()()( )()nntf tL tK xt(1)(1)(1)1( )( )( )( )nnnnnftLtK xt由于第58頁/共554頁)!1()()()1(nfxKn)()()(1xxKxRnn)()!1()(1)1(xnfn

34、n所以)()()(截斷誤差的余項為插值多項式稱xPxRnn(1)(1)(1)(1)1( )( )( )( )( )nnnnnnfLK x因此)!1()()()1(nxKfn0即第59頁/共554頁定理1.0( ) , 1,( )( ) , , , , , ,nniif xa bnLxf xa bnxa bxa b 設在區(qū)間上階可微為在上的 次插值多項式 插值節(jié)點為則有( )nRx(1)1( )( )(1)!nnfxn,)()(01niinxxx其中.,),(xba且依賴于Lagrange型余項n=1:n=2:第60頁/共554頁|)(|max)1(1xfMnbxan|)(|)(|011niin

35、nxxxN設|)(|xRn則)()!1()(1)1(xnfnn11)!1(1nnNMn第61頁/共554頁插值基函數(shù)的性質(zhì)(1)10(1)00:( )( )( )1( )( )( )(1)!( )1,1(1,2, )( )0,( )1( )1nnnniininiiinniif xLxRxl x ffxnf xfinl xfl x 插值基函數(shù)的一個重要性質(zhì):證明取則及故第62頁/共554頁Lagrange插值算法特點&局限性 優(yōu)點：公式簡潔, 理論分析方便 直觀； 對稱；容易編程上機等。 缺點：基函數(shù)計算復雜，計算量大 每增加一個節(jié)點，插值多項式的所有 系數(shù)都得重算；計算量為 。 222

36、nn下一節(jié)提出的Newton插值法就克服了上述缺點。第63頁/共554頁羅爾(Rolle)定理補充資料補充資料-01 如果函數(shù) f(x) 在閉區(qū)間 a, b 上連續(xù)，在開區(qū)間(a, b)內(nèi)具有導數(shù)，且在區(qū)間端點的函數(shù)值相等，即 f(a) = f(b) ，那么在(a, b) 內(nèi)至少有一點 （a b），使得函數(shù)f(x)在該點的導數(shù)等于零：( )0 f。Rolle定理的幾何意義是：如果連續(xù)曲線 y = f(x)的弧 上除端點外處處具有不垂直于 x 軸的切線且兩端點的縱坐標相等（ f(a) = f(b) ） ，那么這弧 上至少有一點C處的切線平行于 x 軸（見圖-A）。BA BA 圖-AABCabyx

37、 （1）第64頁/共554頁Lagrange中值定理 如果函數(shù) f(x) 在封閉區(qū)間 a,b 上連續(xù)，在開區(qū)間(a,b)內(nèi)具有導數(shù)，那么在(a,b) 內(nèi)至少有一點 （a 7時,舍入誤差亦會增大.可知, Runge現(xiàn)象是由f(x)的高階導數(shù)無界所致.)()!()()()()()(xwnfxLxfxRnnnn1 考考慮慮第103頁/共554頁01i1 (x) a,b , (1) ( ) , ;() (2) (x) , 0,1) ( ) ( ) niffffxxC a bx xinf xkxf x定義:設是定義在區(qū)間 上的函數(shù)，在結(jié)點上的函數(shù)值為若函數(shù) （ ）滿足連續(xù)在子區(qū)間（上是的 次插值多項式。

38、則稱 （ ）是在 , a bk上的分段次插值多項式。分段低次插值第104頁/共554頁二、分段線性Lagrange插值,ix設插值節(jié)點為,0,1,ifin函數(shù)值為,11kkkkxxxx形成一個插值區(qū)間任取兩個相鄰的節(jié)點構(gòu)造Lagrange線性插值1,2 , 1 ,0,1nixxhiiiiihhmax1. 分段線性插值的構(gòu)造第105頁/共554頁11kkkkxxfxx11kkkkxxfxx1, 1 , 0nk-(1)-(2)( )kx顯然,當 時1,kkkxxx 或者通過分段插值基函數(shù) 的線性組合來表示 :0 ( )niil x( )x( )x0( )( ) ,niiixl x f , xa b

39、第106頁/共554頁其中0( )lx 101,xxxx01,xx x01,xx x( )il x 11,iiixxxx1,iixxx1 ,iixx x( )nlx 11,nnnxxxx1,nnxxx1,nnxxx0,11,iiixxxx0,11,iixxx0,且0( )1niil x第107頁/共554頁-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-1012

40、34-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81( )yx分段線性插值的圖象( ,) ,0,1,iix yin實際上是連接點的一條折線也稱折線插值,如右圖曲線的光滑性較差在節(jié)點處有尖點 但如果增加節(jié)點的數(shù)量減小步長,會改善插值效果0lim ( )hx)(xf上連續(xù)在若,)(baxf因此則第108頁/共554頁)()!1()(1)1(xnfnn由第二節(jié)定理1可知,n次Lagrange插值多項式的余項為)()()(xPxfxRnn( )x那么分段線性插值的余項為1( )( )( )R xf

41、 xx)(2)(1 kkxxxxf有關(guān)與且xxxxkk,1|)(|1xR| )( |max| )(|max2111 kkxxxbxaxxxxxfkk224121hM 2281hM2. 分段線性插值的誤差估計第109頁/共554頁2121 f(x)C , ,(),(0,1, ), ( ) (ab), , h |f(x)- (x)|max |( ) | (6.5.1)8 iini iii na bf xyinxy l xxxa bfx 定理 設且（ ）則對任意有其中11 hmax()iii nxx 第110頁/共554頁三、分段三次Hermite插值( ) , ,0,1,iif xa bxf in

42、設函數(shù)在上的節(jié)點 上的函數(shù)值為,0,1,iixf in 在節(jié)點 上的導數(shù)值為1, 1 ,0,1nkxxkk對任意兩個相鄰的節(jié)點可構(gòu)造兩點三次Hermite插值多項式( )( )( )( )( )3011011( )( )( )( )( )kkkkkkkkkHxfxfxfxfx,1kkxxx1, 1 ,0nk插值基函數(shù)為Hermitexxxxkkkk)(),(),(),()(1)(0)(1)(0第111頁/共554頁)()(0 xk)()(1xk)()(0 xk)()(1xk1121kkkxxxx21kkkxxxxkxx 211kkkxxxx21kkkxxxx1kxxkkkxxxx121211k

43、kkxxxx其中我們稱( )331( )( ) ,0,1,1kkkHxHxxxxkn 為分段三次Hermite插值多項式，其余項為)()(! 4)(max)(max)(212)4(10)(3103kknkknkxxxxfxRxR212104)()(max! 41kknkxxxxxxxMkk第112頁/共554頁例2.21( )1f xx設函數(shù)在節(jié)點處的函數(shù)值及導數(shù)值,比較幾種插值.我們分別用分段二次、三次Lagrange插值和分段兩點三次Hermite插值作比較解:44221104384)4)(max! 4hMxxMkknk)(3xR即第113頁/共554頁 f(x)0.80000 0.307

44、690.137930.075470.04160 H3(x) 0.81250 0.30750 0.13750 0.07537 0.04159 x0.51.52.53.54.8 R3(x)=f(x)-H3(x)-0.01250000000000 0.00019230769231 0.00043103448276 0.00009972579487 0.00001047427455 L2(x)0.875000.32500 0.12500 0.072060.04087 L3(x)0.800000.325000.133820.074430.04269第114頁/共554頁分段低次插值的特點:計算較容易可以

45、解決Runge現(xiàn)象,可保證收斂性但插值多項式分段插值曲線在節(jié)點處會出現(xiàn)尖點,不可導第115頁/共554頁 習題 2.12.4、2.62.11、 2.13 、2.15、 2.20(1) 復習題第116頁/共554頁第二章第二章 函數(shù)近似計算的插值法函數(shù)近似計算的插值法 2.6 樣條函數(shù)及三次樣條插值第117頁/共554頁 2.6 三次樣條插值樣條:是 指飛機或輪船等的制造過程中為描繪出光滑的外形曲線(放樣)所用的工具.樣條本質(zhì)上是一段一段的三次多項式拼合而成的曲線在拼接處,不僅函數(shù)是連續(xù)的,且一階和二階導數(shù)也是連續(xù)的1946年,Schoenberg將樣條引入數(shù)學,即所謂的樣條函數(shù)一、三次樣條插值

46、函數(shù)定義1. 的一個分割為區(qū)間,10babxxxan:,)(上滿足條件在區(qū)間如果函數(shù)baxS第118頁/共554頁,)(,)(),(),()1(2baCxSbaxSxSxS 即上連續(xù)都在區(qū)間上都是三次多項式在每個小區(qū)間,)()2(1kkxxxS上的三次樣條函數(shù)為區(qū)間則稱,)(baxS處的函數(shù)值為在節(jié)點如果函數(shù)nxxxxf,)()3(10njyxfjj, 1 , 0,)(滿足而三次樣條函數(shù))(xSnjyxSjj, 1 , 0,)(上的三次樣條插值函數(shù)在為則稱,)()(baxfxS-(1)第119頁/共554頁二、三次樣條插值構(gòu)造法 三轉(zhuǎn)角方法處的函數(shù)值為在節(jié)點如果函數(shù)nxxxxf,)(10njy

47、xfjj, 1 , 0,)(的一個分割為區(qū)間,10babxxxan則其必滿足的三次樣條插值函數(shù)是如果,)()(xfxSnjyxSjj, 1 , 0,)(1, 1,)()(limnjmxSxSjjxxj1, 1),()(lim njxSxSjxxj1, 1,)()(limnjyxSxSjjxxj-(2)第120頁/共554頁條件個共要滿足上述四組)24()(nxS即然是分段函數(shù)上必在,)(baxS,)(,)(,)(11211100nnnxxxxSxxxxSxxxxS)(xS滿足三次樣條插值多項式兩點上的是,)(,)(1kkkxxxSjjkyxS)()(lim)(lim1xSxSkxxkxxkk)

48、(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk 1,2 , 1nk個條件共24 n1,; 1, 2 , 1 , 0kkjnk-(3)-(4)第121頁/共554頁個待定的系數(shù)應有式上的三次樣條插值多項是4,)(1kkkxxxS個待定的系數(shù)必須確定即要確定nxS4)(少兩個條件并且我們不能只對插值函數(shù)在中間節(jié)點的狀態(tài)進行限制也要對插值多項式在兩端點的狀態(tài)加以要求也就是所謂的邊界條件:第一類(一階)邊界條件:00)(fxSnnfxS)(第二類(二階)邊界條件:00)(fxS nnfxS )(第三類(周期)邊界條件:()()001()()ppnnSxSx2

49、 , 1 ,0p-(5)-(6)-(7)第122頁/共554頁加上任何一類邊界條件(至少兩個)后個好也是個待定的系數(shù)的條件正必須確定確定nnxS44)(一般使用第一、二類邊界條件,即jjkyxS)()(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk 1,2 , 1nk1,; 1, 1 , 0kkjnk1,2 , 1nk1,2 , 1nkkm00)(fxSnnfxS)(-(8)00)(fxS nnfxS )(或常用第二類邊界條件.第123頁/共554頁njmxSjj, 1 ,0,)(設)(,)(1xSxxxf

50、kkk上的三次插值多項式在小區(qū)間逐個求插值多項式上的兩點三次表示為將HermitexxxSkkk,)(1)(xSk)()()()()()(11)(0)(11)(0)(3xmxmxyxyxHkkkkkkkkk11121kkkkxxxxy21kkkxxxxkkxxm211kkkxxxx21kkkxxxx11kkxxmkkkkxxxxy121211kkkxxxx-(9)第124頁/共554頁kkkkkkyxxhxxhxS213)()(2)(1231)()(2kkkkkyxxhxxhkkkkmxxhxx212)()(1221)()(kkkkmxxhxx加以整理后可得并整理后得求二階導數(shù)對,)(xSk)

51、()2(6)(131kkkkkkyyhxxxxS kkkkmhxxx21426121246kkkkmhxxx-(10)-(11)1, 1 ,01nkxxhkkk，令第125頁/共554頁)(lim)(lim1xSxSkxxkxxkk 1,2 , 1nk由條件)(limxSkxxk )(612kkkyyhkkmh412kkmh)(lim1xSkxxk )(6121kkkyyh112kkmhkkmh14由于以上兩式相等,得11111)11(21kkkkkkkmhmhhmh)(321121kkkkkkhyyhyy1, 1nk個未知量個方程共個1,1nn第126頁/共554頁得并加以整理除上式的兩邊用

52、,111kkhh112kkkkkmmmkg1kkkkhhh11kkkkhhh)(3111kkkkkkkkkhyyhyyg1, 1nk-(12)1, 1nk個未知量個方程共個1,1nn(12)式稱為基本方程組其中：第127頁/共554頁如果問題要求滿足第一類(一階)邊界條件:00)(fxSnnfxS)(-(5)00fmnnfm-(5)基本方程組(12)化為n-1階方程組0112112fgmmkkkkkkgmmm1122, 3 ,2nknnnnnnfgmm111212-(13)即將(13)式化為矩陣形式第128頁/共554頁222222122433221nnn12321nnmmmmmnnnnfgg

53、ggfg11232011-(14)這是一個三對角方程組如果問題要求滿足第二類(二階自然)邊界條件:00)(fxS nnfxS )(時，稱為自然邊界條件00 nff第129頁/共554頁由(11)式,可知)()2(6)(013001000yyhxxxxS 020100426mhxxx120100246mhxxx)(60120yyh004mh102mh0f )(6)(1211 nnnnnyyhxS112nnmhnnmh14nf -(15)-(16)整理后得的方程式是關(guān)于,)16)(15(110nnmmmm第130頁/共554頁0000110232fhhyymm nnnnnnnfhhyymm 232

54、11110gng-(17)-(18)與基本方程組(12)聯(lián)合,并化為矩陣形式,得212222121132211nnnnmmmmm1210nnggggg1210-(19)第131頁/共554頁(19)式與(14)一樣,都是三對角方程組,并且都嚴格對角占優(yōu)可以使用追趕法求解,并且解是唯一的對于問題要求滿足第三類(周期)邊界條件請同學們自己思考現(xiàn)在回到(10)式后解出式或通過nmmm,)19()14(10式代入將)10(,10nmmm)()(,),(),(110 xSxSxSxSn三次樣條插值函數(shù)從而得到便可得到第132頁/共554頁思考：5 , 5112xxy函數(shù)使用不同的插值方法于定理 . 次樣

55、條插值函數(shù)，滿足任意邊界條件的三為節(jié)點是以設,), 1 ,0()(,)(2nkxxSbaCxfk,min,max,10101iniiniiiihhhxxh設時則當 ch)()(,)()(xfxfbaxSxS和上一致收斂到在和最后，給出一個有用的結(jié)論第133頁/共554頁則有且若,)(4baCxf)(|)()(|max4)()(kkkbxahoxSxf2 , 1k 復習題 習題 2.26、2.27第134頁/共554頁第三章第三章 曲線擬合的最小二乘法曲線擬合的最小二乘法 / /函數(shù)平方逼近初步函數(shù)平方逼近初步第135頁/共554頁曲線擬合問題: (建立試驗數(shù)據(jù)的模型) 在實際應用中，往往并不需

56、要曲線通過給定的數(shù)據(jù)點，而只要求用曲線(函數(shù))近似代替給定的列表函數(shù)時，其 誤差在某種度量意義下最小。函數(shù)逼近問題: (連續(xù)函數(shù)的逼近) 在實際應用中常需為解析式子比較復雜的函數(shù)尋找一個簡單函數(shù)來近似代替它，并要求其誤差在某種度量意義下最小?？山y(tǒng)稱為最佳逼近問題 3.1 擬合與逼近問題第136頁/共554頁插值法是使用插值多項式來逼近未知或復雜函數(shù)的，它要求插值函數(shù)與被插函數(shù)在插值節(jié)點上函數(shù)值相同 ，而在其他點上沒有要求。在非插值節(jié)點上有時函數(shù)值會相差很大。若要求在被插函數(shù)的定義區(qū)間上都有較好的近似，就是最佳逼近問題。必須找到一種度量標準來衡量什么是最佳逼近.第137頁/共554頁 最佳一致逼

57、近是在函數(shù)空間 M中選 P(x) 滿足 但由于絕對值函數(shù)不宜進行分析運算，常替之以來討論，于是最佳逼近問題變?yōu)樽罴哑椒奖平鼏栴} 這即為連續(xù)函數(shù)的最佳平方逼近.對于離散的問題，最佳平方逼近問題為:就是常說的曲線擬合的最小二乘法. (*)min)()(maxxpxfbxamin)()()(2dxxxpxfbamin)()(20 xpxfiimii第138頁/共554頁二. 預備知識K,(u,v),:(1) (u, u)0, (u, u)=0u=0;(2) (u, v)=(u, v);(3) ( u, v)= (u, v), K;(4) (u+v, w)=(u, w)+(v, w), wX,(u,

58、v) u v X設X是數(shù)域K上的線性空間,若對 u,vX,有 中一個數(shù)與之對應 記為其滿足且則 稱為 與的內(nèi)積; 而定義了內(nèi)積的線性空間 稱為內(nèi)積空間.內(nèi)積:第139頁/共554頁常采用的內(nèi)積與范數(shù)n12121. Rxyx(,)y(,)iiiTnTnx yx xxy yyni=1向量空間上的內(nèi)積:( , )=212: x(x,x)niiix由內(nèi)積定義范數(shù)（滿足三個條件）范數(shù)第140頁/共554頁2. , :, , ,( , )( ) ( );( , )( ) ( ) ( ),( ).babaC a bf gC a bf gf x g x dxf gx f x g x dxx 連續(xù)函數(shù)空間 上的

59、內(nèi)積設 定義內(nèi)積:及加權(quán)內(nèi)積為權(quán)函數(shù)1122222:( , )( )( )baff fx fx dx范數(shù)第141頁/共554頁0123.1.1, , ,(Gram)nC a b 定理設由他們的內(nèi)積構(gòu)成的矩陣 稱矩陣G ),(),(),(01000n),(),(),(11101n),(),(),(10nnnn012G,.n 則 非奇異的充分必要條件是:線性無關(guān)第142頁/共554頁 1.正交函數(shù)族與正交多項式 定義1 若f(x),g(x)Ca,b, (x)為a,b上的權(quán)函數(shù) 且滿足: 則稱f(x)與g(x)在a,b上帶權(quán)(x)正交。 正交多項式 第143頁/共554頁 若函數(shù)族 0(x), 1(

60、x), , n(x), 滿足關(guān)系 則稱k(x)是a,b上帶權(quán)(x)的正交函數(shù)族。 例如，三角函數(shù)族 1 ,cosx , sinx , cos2x , sin2x , 就是在區(qū)間 -, 上的正交函數(shù)族。 第144頁/共554頁 定義2 設 n(x) 是a,b上首項系數(shù) an0 的 n次多項式,(x)為a,b上權(quán)函數(shù)，如果多項式序列 滿足關(guān)系式: 則稱為多項式序列 為在a,b上帶權(quán)(x)正交，稱n(x)為a,b上帶權(quán)(x)的n次正交多項式。 第145頁/共554頁 只要給定區(qū)間a,b及權(quán)函數(shù)(x), 均可由一族線性無關(guān)的冪函數(shù) 1 , x , , xn , 利用逐個正交化手續(xù)(Gram-Schmidt正交化方法)： 構(gòu)