計算方法課件第五章插值法

計算方法課件第五章插值法第一頁，共七十二頁，編輯于2023年，星期五1函數(shù)表達式過于復雜不便于計算,而又需要計算許多點處的函數(shù)值2僅有幾個采樣點處的函數(shù)值,而又需要知道非采樣點處的函數(shù)值……上述問題的一種解決思路：建立復雜函數(shù)或者未知函數(shù)的一個便于計算的近似表達式.解決方法－插值法

§5.0插值問題一、問題提出第二頁，共七十二頁，編輯于2023年，星期五二、插值問題定義求插值函數(shù)(x)的問題稱為插值問題。第三頁，共七十二頁，編輯于2023年，星期五三、幾何意義、內(nèi)插法、外插法內(nèi)插外插第四頁，共七十二頁，編輯于2023年，星期五四、多項式插值問題對于不同的函數(shù)族Φ的選擇，得到不同的插值問題當Φ為一些三角函數(shù)的多項式集合時:三角插值;當Φ為一些有理分式集合時：有理插值；當Φ為一些多項式集合時：多項式插值（代數(shù)插值）第五頁，共七十二頁，編輯于2023年，星期五五、插值多項式的存在唯一性分析對于多項式插值問題，插值條件（1）等價于確定多項式的系數(shù)，使得滿足如下的線性方程組

定理1(存在唯一性)

滿足插值條件(1)的不超過n次的插值多項式是存在唯一的。第六頁，共七十二頁，編輯于2023年，星期五定理證明：多項式插值問題滿足的線性方程組是關(guān)于多項式的系數(shù)a0，a1，a2，…，an的n＋1階線性方程組，其系數(shù)矩陣的行列式Vn(x0,x1,…,xn)稱為范德蒙(Vandermonde)行列式。利用行列式的性質(zhì)可以求得由于假設(shè)ij時，xixj，故所有因子xi-xj0，于是Vn(x0,x1,…,xn)0。由克萊姆(Grammer)法則，方程組的解存在且唯一，從而插值多項式是存在唯一的。證畢第七頁，共七十二頁，編輯于2023年，星期五六、插值余項引理已知函數(shù)f(x)在[a,b]上具有m-1階連續(xù)導函數(shù)，且在（a,b）上存在m階導數(shù)。若它在該區(qū)間上有m+1個零點，則它的m階導函數(shù)在(a,b)內(nèi)至少存在一個零點。第八頁，共七十二頁，編輯于2023年，星期五分析：第九頁，共七十二頁，編輯于2023年，星期五第十頁，共七十二頁，編輯于2023年，星期五第十一頁，共七十二頁，編輯于2023年，星期五七、插值方法由于插值多項式的存在唯一性，無論是用何種方法構(gòu)造出的插值多項式，它們均恒等，進而截斷誤差也都相同。本章我們要討論的插值方法有：Lagrange插值法Newton插值法等距節(jié)點插值公式帶導數(shù)的插值問題第十二頁，共七十二頁，編輯于2023年，星期五§5.1拉格朗日插值一、插值基函數(shù)1.定義：若n次多項式lk(x)(k=0,1,…,n)在n+1個插值節(jié)點x0<x1<…<xn上滿足插值條件：則稱這n＋1個n次多項式l0(x),l1(x),…,ln(x)為插值節(jié)點x0,x1,…,xn上的n次插值基函數(shù)。Remark：容易驗證，n次插值基函數(shù)的線性組合在插值節(jié)點x0,x1,…,xn上滿足插值條件，從而可以利用插值基函數(shù)來構(gòu)造插值多項式。第十三頁，共七十二頁，編輯于2023年，星期五2.插值基函數(shù)的構(gòu)造由于ik時，lk(xi)=0，故x0,x1,…,xk-1,xk+1,…,xn為lk(x)的零點，從而可以設(shè)由lk(xk)＝1可得故若記，則有，從而第十四頁，共七十二頁，編輯于2023年，星期五3.插值基函數(shù)的性質(zhì)性質(zhì)1：性質(zhì)2：插值基函數(shù)lk(x)(k=0,1,…,n)為由插值節(jié)點x0,x1,…,xn唯一確定的n次函數(shù)。性質(zhì)3：基函數(shù)組所含的基函數(shù)個數(shù)與插值節(jié)點個數(shù)相同。第十五頁，共七十二頁，編輯于2023年，星期五二、Lagrange型插值公式上式是不超過n次的多項式，且滿足所有的插值條件，因而就是我們所需構(gòu)造的插值多項式，稱之為Lagrange插值多項式。當n＝1時，有當n＝2時，有第十六頁，共七十二頁，編輯于2023年，星期五L1(x)和L2(x)分別稱為線性插值多項式和二次插值多項式，其幾何意義分別表示通過點(x0,y0),(x1,y1)的一條直線和通過點(x0,y0),(x1,y1)，(x2,y2)的一條拋物線。類似地可以寫出當n為其它值時地插值多項式，如n＝3時，有第十七頁，共七十二頁，編輯于2023年，星期五三、Lagrange插值多項式的余項設(shè)f(x)為定義在[a,b]上的被插值函數(shù)，Ln(x)為f(x)的n次Lagrange插值多項式，其插值余項為：

Rn(x)=f(x)-Ln(x)定理：如果f(n)(x)在區(qū)間[a,b]上連續(xù)，f(n＋1)(x)在(a,b)內(nèi)存在，Ln(x)為在節(jié)點ax0<x1<…<xnb上滿足插值條件的n次Lagrange插值多項式，則對任一x(a,b),其插值余項為：其中(a,b)且依賴于x。上式給出的余項通常稱為Lagrange型余項。第十八頁，共七十二頁，編輯于2023年，星期五定理證明證畢第十九頁，共七十二頁，編輯于2023年，星期五Remark一般情況下，余項表達式中的(a,b)的具體數(shù)值無法知道。但是，如果能夠求出，則可以得出插值多項式的截斷誤差限為：由此可以看出，誤差大小除了與Mn+1有關(guān)外，還與插值節(jié)點有密切關(guān)系。當給定m個點處的函數(shù)值，但僅選用其中n＋1（n＋1<m）個作為插值條件而求某個點處函數(shù)值時，n＋1個節(jié)點的選取應盡可能接近，以使使得所計算的函數(shù)值的誤差限盡可能小。第二十頁，共七十二頁，編輯于2023年，星期五例題#第二十一頁，共七十二頁，編輯于2023年，星期五四、反插值法分析第二十二頁，共七十二頁，編輯于2023年，星期五問題求解#第二十三頁，共七十二頁，編輯于2023年，星期五Lagrange

插值公式的特點：形式對稱通常用于理論分析當增加插值節(jié)點時，在計算實踐中不方便§5.2牛頓插值問題：想要構(gòu)造一個更加方便靈活的插值格式，當增加插值節(jié)點時，只需在原有格式的基礎(chǔ)上再增加一些即可。解決方法：Newton插值第二十四頁，共七十二頁，編輯于2023年，星期五一、差商的定義及性質(zhì)一般地，K階差商為：定義：給定函數(shù)f(x)在互異節(jié)點x0<x1<…<xn處的函數(shù)值f(x0),f(x1),…,f(xn)，稱為函數(shù)f(x)在節(jié)點xi，xj處的一階差商。稱為函數(shù)f(x)在節(jié)點xi，xj，xk處的二階差商。即f(x)的k-1階差商的差商稱為k階差商（均差）。第二十五頁，共七十二頁，編輯于2023年，星期五差商的性質(zhì)由于性質(zhì)1：故差商是微商的離散形式。性質(zhì)2：k階差商f[x0,x1,…,xk]可以表示為函數(shù)值f(x0),f(x1),…,f(xk)的線性組合，即k=1,2,…,n性質(zhì)3：差商與插值節(jié)點的排列次序無關(guān)。第二十六頁，共七十二頁，編輯于2023年，星期五1.Lagrange插值多項式間的關(guān)系二、Newton插值多項式注：A是Lk(x)的首項系數(shù)。第二十七頁，共七十二頁，編輯于2023年，星期五2.Newton型插值公式……………第二十八頁，共七十二頁，編輯于2023年，星期五k=1,2,…,nRemark:遞推關(guān)系第二十九頁，共七十二頁，編輯于2023年，星期五3.差商的計算第三十頁，共七十二頁，編輯于2023年，星期五根據(jù)插值多項式的存在唯一性知，如果f(x)充分光滑，則有估計不足：對函數(shù)的光滑性要求高；需估計導函數(shù)的最值；偏保守。導數(shù)型誤差估計三、Newton插值余項第三十一頁，共七十二頁，編輯于2023年，星期五差商型誤差估計導數(shù)和差商的關(guān)系差商型誤差估計特點：對被插值函數(shù)光滑性要求不高；但不適用于實際計算。第三十二頁，共七十二頁，編輯于2023年，星期五四、例題解

1）建立差商表1.01.52.00.84150.99750.90930.312-0.1764-0.48842）插值第三十三頁，共七十二頁，編輯于2023年，星期五Newton插值多項式適用于節(jié)點任意分布的情形。但當節(jié)點等距分布時，可以簡化Newton插值公式?！?.3等距節(jié)點插值設(shè)a=x0<x1<…<xn=b，yi=f(xi)為等距節(jié)點xi=x0+h(i=0,1,…,n)上的函數(shù)值，其中h=(b-a)/n稱為步長。在此基礎(chǔ)上我們先定義差分，用差分表示Newton插值多項式，從而得到等距節(jié)點的插值公式。第三十四頁，共七十二頁，編輯于2023年，星期五一、差分的定義與性質(zhì)定義：稱yi=yi+1-yi (i=0,1,…,n-1)為f(x)在xi處以h為步長的一階向前差分。

2yi＝y(tǒng)i＋1-yi=yi+2-2yi+1+yi(i=0,1,…,n-2)稱為f(x)在xi處以h為步長的二階向前差分。一般地，myi＝m-1yi＋1-m-1yi(i=0,1,…,n-m)稱為f(x)在xi處以h為步長的m階向前差分。第三十五頁，共七十二頁，編輯于2023年，星期五差分的性質(zhì)性質(zhì)1：各階差分可用函數(shù)值線性表示，其計算公式為：其中性質(zhì)2：差分與差商滿足下述關(guān)系：證明：利用數(shù)學歸納法當k＝1時，有即結(jié)論成立。第三十六頁，共七十二頁，編輯于2023年，星期五設(shè)k＝m-1時結(jié)論成立，即則當k＝m時，有由數(shù)學歸納法知，結(jié)論成立。證畢第三十七頁，共七十二頁，編輯于2023年，星期五Remark：類似地可以定義向后差分與中心差分：性質(zhì)3：差分與導數(shù)滿足關(guān)系：證明：利用差商與導數(shù)、差分的關(guān)系，有：證畢第三十八頁，共七十二頁，編輯于2023年，星期五二、Newton向前插值公式令x=x0+th，由xi=x0+ih(i=0,1,…,n)得：x-xi=(t-i)h，則有:將差商與差分的關(guān)系式帶入Newton插值多項式，得:第三十九頁，共七十二頁，編輯于2023年，星期五從而可得Newton向前插值多項式及其余項為：第四十頁，共七十二頁，編輯于2023年，星期五三、差分表Newton向前插值公式，又稱表初公式，它利用差分表的最上面一個斜行的數(shù)值進行計算。第四十一頁，共七十二頁，編輯于2023年，星期五四、例題解第四十二頁，共七十二頁，編輯于2023年，星期五#第四十三頁，共七十二頁，編輯于2023年，星期五五、Newton向后插值公式類似于向前差分，也可以得到差商與向后差分的關(guān)系：將插值節(jié)點從大到小排列，即類似于向前插值公式，可得到Newton向后插值公式，又稱表末公式，它利用差分表的最下面一個斜行的數(shù)值進行計算。同樣，還可以利用中心差分，構(gòu)造插值公式，稱為貝塞爾（Bessel）插值公式。第四十四頁，共七十二頁，編輯于2023年，星期五這一類插值問題為埃爾米特(Hermite)插值問題。其幾何意義是在插值點上插值曲線與被插值曲線有公共切線。由這2n+2個條件可以唯一確定一個2n+1次的插值多項式。具體我們采用基函數(shù)的方法來確定?！?.4埃爾米特插值一、問題第四十五頁，共七十二頁，編輯于2023年，星期五1.輔助問題及Hermit插值二、一般情形第四十六頁，共七十二頁，編輯于2023年，星期五2.輔助問題的求解第四十七頁，共七十二頁，編輯于2023年，星期五第四十八頁，共七十二頁，編輯于2023年，星期五3.Hermite插值問題解的存在唯一性存在性：

唯一性：0第四十九頁，共七十二頁，編輯于2023年，星期五4.插值余項分析：第五十頁，共七十二頁，編輯于2023年，星期五定理證明函數(shù)零點（從小到大）…………至少2n+1個零點……至少1個零點ξ證畢第五十一頁，共七十二頁，編輯于2023年，星期五三、特殊情形－帶不完全導數(shù)的插值問題舉例分析（方法1）：誤差：#第五十二頁，共七十二頁，編輯于2023年，星期五方法2：（用帶有重節(jié)點的差商表）#第五十三頁，共七十二頁，編輯于2023年，星期五#第五十四頁，共七十二頁，編輯于2023年，星期五1.高次插值的評述

在實際應用中,很少采用高次插值。①.在兩相鄰插值節(jié)點間,插值函數(shù)未必能夠很好地近似被插值函數(shù)。一、分段插值法②.對于等距節(jié)點的牛頓插值公式,函數(shù)值的微小擾動可能引起高階差分有很大的變化.§5.5三次樣條插值第五十五頁，共七十二頁，編輯于2023年，星期五函數(shù)在區(qū)間[-5,5]上用等距節(jié)點的插值問題是上世紀初Runge研究過的一個有名實例.在區(qū)間上分別采用10次、15次、20次的等距節(jié)點插值多項式。隨著插值次數(shù)的提高,在范圍內(nèi)的近似程度并沒有變好,反而變壞.高次插值并不一定帶來更好的近似效果。第五十六頁，共七十二頁，編輯于2023年，星期五(a)

第五十七頁，共七十二頁，編輯于2023年，星期五(b)(c)函數(shù)的等距節(jié)點插值公式在區(qū)間[0,5]上的近似程度示意圖

第五十八頁，共七十二頁，編輯于2023年，星期五2.分段插值

設(shè)已知節(jié)點上的函數(shù)值若滿足

則稱為分段插值函數(shù)。是整體插值區(qū)間上的連續(xù)函數(shù),隨著子區(qū)間長度變小,不提高子區(qū)間上的插值冪次便可以滿足給定的任意精度要求.但一般說來,在子區(qū)間的端點處導數(shù)是不存在的.

為了避免高次插值的缺點，常采用分段插值，即將插值區(qū)間分成若干小區(qū)間，在每個小區(qū)間上利用前面介紹的插值方法構(gòu)建低次插值多項式。第五十九頁，共七十二頁，編輯于2023年，星期五二、三次樣條插值

分段插值法具有一致的收斂性,但它只保證插值函數(shù)整體的連續(xù)性,但在連接處不一定光滑，不能夠滿足精密機械設(shè)計（如船體、飛機、汽車等的外形曲線設(shè)計）對函數(shù)光滑性的要求。早期的工程技術(shù)人員在繪制給定點的曲線時，使用一種具有彈性的細長木條（或金屬條），稱之為樣條（Spline），強迫它彎曲通過已知點。彈性力學理論指出樣條的撓度曲線具有二階連續(xù)的導函數(shù)，并且在相鄰給定點之間為三次多項式，即為數(shù)學上的三次樣條插值曲線。第六十頁，共七十二頁，編輯于2023年，星期五1.三次樣條插值函數(shù)的定義

定義

給定區(qū)間的一個分劃①.在小區(qū)間上是3次多項式.

②.在節(jié)點處具有2階連續(xù)的導數(shù);則稱S(x)是關(guān)于分劃的3次樣條函數(shù).若實值函數(shù)S(x)滿足若還滿足③.

,則稱S(x)是f(x)關(guān)于分劃的3次樣條插值函數(shù)。第六十一頁，共七十二頁，編輯于2023年，星期五三次樣條插值函數(shù)在每一個小區(qū)間上是3次的多項式,在整個插值區(qū)間上有4n個系數(shù).且有4n-2個約束:內(nèi)節(jié)點

邊界節(jié)點第六十二頁，共七十二頁，編輯于2023年，星期五要確定4n個系數(shù)，還需附加2個約束條件.常用的約束條件有以下三類：此時一般有成立.③.周期性邊界條件,②.彎矩邊界條件特別的稱為自然邊界條件.①.轉(zhuǎn)角邊界條件

第六十三頁，共七十二頁，編輯于2023年，星期五2.三彎矩構(gòu)造法記,基本步驟如下：①.取為待定參數(shù)，并用S(x)的插值條件寫出的表達式。④.代入S(x)的表達式，得各個區(qū)間上的表達式。②.用在內(nèi)節(jié)點