數(shù)值分析—插值法與最小二乘擬合法

1、數(shù)值分析數(shù)值分析1第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分第第5 5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法&4.1 代數(shù)插值法及其唯一性代數(shù)插值法及其唯一性&4.2 Lagrange插值法插值法&4.3 Newton插值法插值法 &4.5 Hermite插值法插值法&4.7 三次樣條插值法三次樣條插值法&4.8 最小二乘擬合法最小二乘擬合法Interpolation and Linear Least Square Method數(shù)值分析數(shù)值分析2第第5章章 插值法與最小二乘擬合法插

2、值法與最小二乘擬合法2022年年7月月5日日12時時52分分 更一般地，給定一個函數(shù)表更一般地，給定一個函數(shù)表:要求出任意點上的函數(shù)值。要求出任意點上的函數(shù)值。 在工程技術(shù)中，經(jīng)常會遇到只給定一個函數(shù)表，要在工程技術(shù)中，經(jīng)常會遇到只給定一個函數(shù)表，要求根據(jù)該函數(shù)表求出某些點上函數(shù)值的問題。求根據(jù)該函數(shù)表求出某些點上函數(shù)值的問題。 求高度求高度=2.7時的大氣壓為多少時的大氣壓為多少? x x0 x1 xn y=f(x) y0 y1 yn方法一：方法一：插值法插值法, 插值曲線經(jīng)過給定的插值點插值曲線經(jīng)過給定的插值點 高度高度 0 1.5 2.5 3 4.8大氣壓大氣壓 1 0.9 0.85 0

3、.7 0.67方法二：方法二：擬合法擬合法,200 ()( ),max()niiiiii nxyyxQQxy 求求一一連連續(xù)續(xù)曲曲線線使使得得誤誤差差達(dá)達(dá)到到最最小小或或 達(dá)達(dá)到到最最小小。 高度與大氣壓的探測數(shù)據(jù)高度與大氣壓的探測數(shù)據(jù)數(shù)值分析數(shù)值分析3第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分插值法插值法 /* Interpolation */ 當(dāng)精確函數(shù)當(dāng)精確函數(shù) y = f(x) 非常復(fù)雜或未知時，在非常復(fù)雜或未知時，在一系列一系列節(jié)點節(jié)點 x0 xn 處測得函數(shù)值處測得函數(shù)值 y0 = f(x0), yn = f(xn)，由此構(gòu)造一

4、個簡單易算的近似函數(shù)由此構(gòu)造一個簡單易算的近似函數(shù) P(x) f(x)，滿足條件滿足條件P(xi) = f(xi) (i = 0, n)。這里的這里的 P(x) 稱為稱為f(x) 的的插值函數(shù)插值函數(shù)。最常用的插。最常用的插值函數(shù)是值函數(shù)是 ?多項式多項式x0 x1x2x3x4xP(x) f(x)數(shù)值分析數(shù)值分析4第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分&插值法是數(shù)值分析中的一個古老的分支；插值法是數(shù)值分析中的一個古老的分支；&等距節(jié)點內(nèi)插法等距節(jié)點內(nèi)插法隋朝數(shù)學(xué)家劉焯隋朝數(shù)學(xué)家劉焯zhou(公元公元544-610年年)首

5、先提出首先提出的；的；&不等距節(jié)點內(nèi)插法不等距節(jié)點內(nèi)插法唐朝數(shù)學(xué)家張遂唐朝數(shù)學(xué)家張遂(公元公元683-727年年)首先提出的；首先提出的；& 插值法在數(shù)值積分、數(shù)值微分、微分方程數(shù)值解、曲線曲面擬插值法在數(shù)值積分、數(shù)值微分、微分方程數(shù)值解、曲線曲面擬 合、函數(shù)值近似計算中有著廣泛的應(yīng)用。合、函數(shù)值近似計算中有著廣泛的應(yīng)用。 插值法的歷史背景插值法的歷史背景常用常用 插值函數(shù)的類型插值函數(shù)的類型代數(shù)插值：代數(shù)插值：多項式插值多項式插值, 0,)(0111 nnnnnaaxaxaxaxP有理插值：有理插值：有理分式函數(shù)有理分式函數(shù)三角插值：三角插值：三角函數(shù)三角函數(shù))()()(xQ

6、xPxPnm 數(shù)值分析數(shù)值分析5第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分4.1 代數(shù)插值法及其唯一性代數(shù)插值法及其唯一性4.1.1 插值多項式及其唯一性插值多項式及其唯一性定義定義4-1 已知函數(shù)已知函數(shù)f(x)在互不相同的點在互不相同的點x0 x1 0, 使得對一切使得對一切x(a,b)都有都有f (4)(x) M, 則有則有定理定理4-3 若若 (x)在在a,b上有直到上有直到3階的連續(xù)導(dǎo)數(shù)階的連續(xù)導(dǎo)數(shù),且在且在(a,b)內(nèi)存內(nèi)存在在4階導(dǎo)數(shù)，則對任意一點階導(dǎo)數(shù)，則對任意一點x a,b時時, 都存在都存在(a,b)，使得，使得(4)2

7、2330101( )( )( )( )() () , ,4!fRxf xPxxxxxxx 22301( )() ()4!MRxxxxx 余項余項數(shù)值分析數(shù)值分析47第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分例例4-4 以以 4和和9為插值節(jié)點，利用為插值節(jié)點，利用3次次Hermite插值多項式求插值多項式求 在在x=5處的近似值，并估計插值引起的誤差。處的近似值，并估計插值引起的誤差。( )f xx 解：解： 由由 f(4)=2, f(9)=3，且，且12( ),fxx 故故114946( ),( ),ff 223224994( )1221

8、23944949949141 (4)(9)494946xxxxpxxxxx 4771515151516 12820481616 4( )xx 223115( )(54) (59)0.007634!2048Rx 38395( 5)2.23733375P 52.236067977499790 實際誤差實際誤差 0.0012數(shù)值分析數(shù)值分析48第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分4.5 三次樣條插值法三次樣條插值法 我們已經(jīng)知道插值有多種方法：我們已經(jīng)知道插值有多種方法：Lagrange 插值、插值、Newton插值、插值、Hermite

9、插值等多種方式。插值的目的就是數(shù)值逼近的插值等多種方式。插值的目的就是數(shù)值逼近的一種手段，而數(shù)值逼近是為得到一個數(shù)學(xué)問題的精確解或足夠一種手段，而數(shù)值逼近是為得到一個數(shù)學(xué)問題的精確解或足夠精確的解。那么，精確的解。那么，是否插值多項式的次數(shù)越高，是否插值多項式的次數(shù)越高，越能夠達(dá)到這越能夠達(dá)到這個目的呢？現(xiàn)在我們來討論一下這個問題。個目的呢？現(xiàn)在我們來討論一下這個問題。 f(x)在在n+1個節(jié)點個節(jié)點xi(i=0，1，2，n) 上的上的n次插值多次插值多項式項式Pn (x) 的余項的余項 niinnxxnfxPxfxR011)()!()()()()()( 設(shè)想當(dāng)節(jié)點數(shù)增多時會出現(xiàn)什么情況。由插

10、值余項可知，設(shè)想當(dāng)節(jié)點數(shù)增多時會出現(xiàn)什么情況。由插值余項可知，當(dāng)當(dāng)f(x)充分光滑時，若充分光滑時，若余項隨余項隨n增大而趨于增大而趨于0時，這說明可用時，這說明可用增增加節(jié)點加節(jié)點的方法達(dá)到這個目的，那么的方法達(dá)到這個目的，那么實際實際是這樣嗎？是這樣嗎？4.4.1 背景背景數(shù)值分析數(shù)值分析49第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分構(gòu)造拉格朗日插值多項式為構(gòu)造拉格朗日插值多項式為函數(shù)函數(shù) 在在 上的各階導(dǎo)數(shù)均存在上的各階導(dǎo)數(shù)均存在. .5 , 5)1/(1)(2xxf.)()()(11)(1102jnjnnjjnxxxxxxL 在在

11、5, 5上考察上考察 的的Ln(x)。取。取211)(xxf),., 0(105niinxi 令令),(2112/1nnnxxx994889.39952449.39042440.020080751.20123671.20042920.018217397.10173867.10043530.016288409.5332743.5044334.014800440.2755000.2045440.012531662.1578721.1047059.010880668.0831017.0049651.08553416.0607879.0054463.06423216.0356826.0066390.0

12、4621684.0759615.0137931.02)()()(2/12/12/1nnnnxRxLxfn5表2數(shù)值分析數(shù)值分析50第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分 -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 實踐上作插值時一般只用一次、二次最多用三次插值多項式。實踐上作插值時一般只用一次、二次最多用三次插值多項式。那么如何提高插值精度呢？那么如何提高插值精度呢？分段分段低次低次插值插值n=2n=4n=10n=8n 越大，越大，端點附近抖動端點附近抖動越大，稱為越大，稱為Run

13、ge （龍格）（龍格）現(xiàn)象現(xiàn)象數(shù)值分析數(shù)值分析51第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分(1)分段線性插值分段線性插值(2)分段二次插值分段二次插值(3)分段分段Hermite插值插值(4)分段三次樣條插值分段三次樣條插值數(shù)值分析數(shù)值分析52第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分 分段線性插值分段線性插值 /* piecewise linear interpolation */在每個區(qū)間在每個區(qū)間 上，用上，用1次多項式次多項式 (直線直線) 逼近逼近 f (x):,1 iixx

14、11111)()( iiiiiiiiyxxxxyxxxxxPxf,for 1 iixxx記記 ，易證：當(dāng)，易證：當(dāng) 時，時，|max1iixxh 0h)()(1xfxPh一致一致失去了原函數(shù)的光滑性。失去了原函數(shù)的光滑性。 分段分段Hermite插值插值 /* Hermite piecewise polynomials */給定給定nnnyyyyxx ,.,;,.,;,.,000在在 上利用兩點的上利用兩點的 y 及及 y 構(gòu)造構(gòu)造3次次Hermite函數(shù)函數(shù),1 iixx導(dǎo)數(shù)一般不易得到。導(dǎo)數(shù)一般不易得到。數(shù)值分析數(shù)值分析53第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年

15、年7月月5日日12時時52分分 上面介紹的上面介紹的分段低次插值分段低次插值，雖然具有計算簡便，收，雖然具有計算簡便，收斂性有保證，數(shù)值穩(wěn)定性又好且易在計算機上實現(xiàn)等優(yōu)斂性有保證，數(shù)值穩(wěn)定性又好且易在計算機上實現(xiàn)等優(yōu)點，但它卻點，但它卻不能保證整條曲線的光滑性不能保證整條曲線的光滑性，從而不能滿足，從而不能滿足某些工程技術(shù)上的要求，從六十年代開始，首先由于航某些工程技術(shù)上的要求，從六十年代開始，首先由于航空、造船等工程設(shè)計的需要而發(fā)展起來的空、造船等工程設(shè)計的需要而發(fā)展起來的樣條插值樣條插值（spline)方法方法，既保留了分段低次插值的各種優(yōu)點，又，既保留了分段低次插值的各種優(yōu)點，又提高了插

16、值函數(shù)的光滑性，在許多領(lǐng)域有越來越廣泛的提高了插值函數(shù)的光滑性，在許多領(lǐng)域有越來越廣泛的應(yīng)用。應(yīng)用。 樣條樣條是繪圖員用于描繪光滑曲線的一種機械器件是繪圖員用于描繪光滑曲線的一種機械器件,它它是一些易彎曲材料制成的窄條或棒條是一些易彎曲材料制成的窄條或棒條.在繪制需要通過某在繪制需要通過某點的光滑曲線時點的光滑曲線時, 對它在這些點的位置上對它在這些點的位置上“壓鐵壓鐵”,它就被它就被強制通過或接近圖表上確定的描繪點強制通過或接近圖表上確定的描繪點.“樣條函數(shù)樣條函數(shù)”這個術(shù)這個術(shù)語意在點出這種函數(shù)的圖象與機械樣條畫出的曲線很象語意在點出這種函數(shù)的圖象與機械樣條畫出的曲線很象.數(shù)值分析數(shù)值分析

17、54第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分4.4.2 三次樣條插值的概念三次樣條插值的概念/* cubic spline interpolant */.定義定義4-5 給定函數(shù)給定函數(shù) f(x)在區(qū)間在區(qū)間a,b上的上的n+1個點個點a=x0 x1xn=b處的處的函數(shù)值函數(shù)值 yi=f(xi) (i=0,1,2, ,n), 若函數(shù)若函數(shù)S(x)滿足滿足 (1) S(x)在每個小區(qū)間在每個小區(qū)間xi , xi+1 )(i=1,2, ,n)上是一個次數(shù)上是一個次數(shù) 不超過不超過3次的多項式；次的多項式； (2) Si=yi(i=1,2, ,

18、n)； (3) S(x)在區(qū)間在區(qū)間a , b 上具有上具有2階的連續(xù)導(dǎo)數(shù)，則稱階的連續(xù)導(dǎo)數(shù)，則稱S(x)是是f(x) 基于節(jié)點基于節(jié)點x0 , x1 , , xn 的的三次樣條插值函數(shù)三次樣條插值函數(shù)，簡稱，簡稱三次三次 樣條樣條/* Cubic Spline */. f(x)H(x)S(x)注：注：三次樣條與分段三次樣條與分段Hermite插值的根本區(qū)別在于插值的根本區(qū)別在于S(x)自身光滑自身光滑，不需要知道，不需要知道 f 的導(dǎo)數(shù)值（除了在的導(dǎo)數(shù)值（除了在2個端點可能個端點可能需要）；而需要）；而Hermite插值依賴于插值依賴于f 在所有插值點的導(dǎo)數(shù)值。在所有插值點的導(dǎo)數(shù)值。數(shù)值分析

19、數(shù)值分析55第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分如何求如何求 的的三次樣條插值函數(shù)三次樣條插值函數(shù): :( )S x( )f x1012121( ),( ),( )( ),nnns xxxxs xxx xS xsxxxx 23( )iiiiis xxabc xd x 4n個未知數(shù)個未知數(shù)),0()0(jjxSxS 因為因為 在在 上二階導(dǎo)數(shù)連續(xù)，所以在節(jié)點上二階導(dǎo)數(shù)連續(xù)，所以在節(jié)點 )( xS,ba)1,2, 1(njxj處應(yīng)滿足連續(xù)性條件處應(yīng)滿足連續(xù)性條件),0()0(jjxSxS).0()0( jjxSxS 滿足滿足 個插值條件；

20、個插值條件； )(xS1n三次樣條插值條件的分析三次樣條插值條件的分析 個條件個條件33n共有共有 個條件，還需要個條件，還需要2個才能確定個才能確定. 24n數(shù)值分析數(shù)值分析56第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分 邊界條件邊界條件通?？稍趨^(qū)間通?？稍趨^(qū)間a,b 端點端點a=x0, b=xn 上各加一個條件（稱為上各加一個條件（稱為邊界條件邊界條件），），常見的邊界條件有以下常見的邊界條件有以下3種：種：1.1.第第I I型邊界條件：已知兩端的型邊界條件：已知兩端的一階導(dǎo)數(shù)值一階導(dǎo)數(shù)值，即，即.)(,)(00nnfxSfxS 2.2

21、.第第II型邊界條件：型邊界條件：已知兩端的已知兩端的二階導(dǎo)數(shù)值二階導(dǎo)數(shù)值，即，即當(dāng)當(dāng) 時，稱為時，稱為自然邊界條件自然邊界條件,)(,)(00nnfxSfxS 0()()0nSxSx 3.3.第第III型邊界條件：型邊界條件：S(x)是以是以xn- - x0 為周期的為周期的周期函數(shù)周期函數(shù)，即，即),0()0(0 nxSxS此時此時S(x0)=S(xn) , S(x)稱為稱為周期樣條函數(shù)。周期樣條函數(shù)。),0()0(0 nxSxS).0()0(0 nxSxS數(shù)值分析數(shù)值分析57第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分設(shè)設(shè)S(x)的二階

22、導(dǎo)數(shù)值的二階導(dǎo)數(shù)值S(xj)=Mj (j=0,1,n)，求，求S(x). 由于由于S(x)在區(qū)間在區(qū)間xj , xj+1上是三次多項式，故上是三次多項式，故S(x)在在xj , xj+1上是線上是線性函數(shù)，且性函數(shù)，且jjjjjjhxxMhxxMxS 11)(對對S(x)積分兩次并利用積分兩次并利用S(xj)=yj 及及S(xj+1)=yj+1 ，得三次樣條表達(dá)式，得三次樣條表達(dá)式j(luò)jjjjjjjjjjjjjjjhxxhMyhxxhMyhxxMhxxMxS 666)(6)()(211123131).1,1 ,0( nj三次樣條函數(shù)的表達(dá)式三次樣條函數(shù)的表達(dá)式未知數(shù)未知數(shù)n+1個個數(shù)值分析數(shù)值分

23、析58第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分對對 求導(dǎo)得求導(dǎo)得 )(xSjjjjjjhxxMhxxMxS2)(2)()(2112 ;611jjjjjjhMMhyy 求得求得 11603(.)jjjjjjjjhhyyMhxMS 類似地可求出類似地可求出 在區(qū)間在區(qū)間 上的表達(dá)式，從而得上的表達(dá)式，從而得 )( xS,1jjxx 11111630(),jjjjjjjjhhyyMMSxh 利用利用 可得可得 (0)(0)jjSxSx ),1, 2 , 1(211 njdMMMjjjjjj ,1 jjxxx,62)(2)()(111111211

24、21jjjjjjjjjjjjjjxxxhMMhyyhxxMhxxMxS 構(gòu)造三彎矩方程組構(gòu)造三彎矩方程組數(shù)值分析數(shù)值分析59第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分.,6,611111 jjjjjjjjjjxxxfhhxxfxxfd 第一種邊界條件第一種邊界條件 ).,(62),(62111010010nnnnnnxxffhMMfxxfhMM其中其中 , 1, 1,111 njhhhhhhjjjjjjjj令令 ),(6,1010000fxxfhd ),(6,111nnnnnnxxffhd 未知數(shù)未知數(shù)n+1個個方程方程n-1個個112(1

25、,2,1),jjjjjjMMMdjn.222211011011110 nnnnnnnddddMMMM 矩陣形式矩陣形式 嚴(yán)格對角占優(yōu)陣，有唯一解嚴(yán)格對角占優(yōu)陣，有唯一解,三彎矩方程三彎矩方程數(shù)值分析數(shù)值分析60第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分 第二種邊界條件第二種邊界條件,00fM .nnfM 令令 , , nnnfdfd 2,2,0000 矩陣形式矩陣形式.1022011101101111 nnnnnnfddfMMMM 第三種邊界條件第三種邊界條件其中其中 ,010hhhnn ,601110hhxxfxxfdnnnn ,0nMM

26、 ,211nnnnndMMM ,1011hhhnnnn 嚴(yán)格對角占優(yōu)陣，有唯一解嚴(yán)格對角占優(yōu)陣，有唯一解,數(shù)值分析數(shù)值分析61第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分矩陣形式矩陣形式.2222121121112211 nnnnnnnnddddMMMM jjjjjjjjjjjjjjjjhxxhMyhxxhMyhxxMhxxMxS 666)(6)()(211123131,1 jjxxx數(shù)值分析數(shù)值分析62第第5章章 插值法與最小二乘擬合法插值法與最小二乘擬合法2022年年7月月5日日12時時52分分注：注：另有另有三轉(zhuǎn)角法三轉(zhuǎn)角法得到樣條函數(shù)，即設(shè)得到樣條函數(shù)，即設(shè) Sj(xj) = mj，則，則易知易知xj 1, xj 上的上的Sj(x) 就是就是Hermite函數(shù)函數(shù)。再利用。再利用S”的連續(xù)性，可導(dǎo)出關(guān)于的連續(xù)性，可導(dǎo)出關(guān)于mj 的的方程組，加上邊界條件方程組，加上邊界條件即可解。即可解。Cubic Spline 由由boundary conditions 唯一唯一確定。確定。收斂性：收斂性：若若 ，且，且 ，則，則,baCf Chhiiminmax一致一致S(x