第二章1_插值法2.1~2.3

1、1第第2 2章章 插插 值值 法法22.1 2.1 引言引言 2.2 Lagrange2.2 Lagrange插值插值2.3 2.3 均差與均差與NewtonNewton插值多項式插值多項式2.4 Hermite2.4 Hermite插值插值2.5 2.5 分段低次插值分段低次插值2.6 2.6 三次樣條插值三次樣條插值32.1 2.1 引引 言言 設函數(shù) 在區(qū)間 上有定義，且已知在點)(xfy ,ba 上的值 ，bxxxan10nyyy,10函數(shù) ，)(xP), 1 , 0()(niyxPii（1.1）成立，就稱 為 的插值函數(shù)插值函數(shù)，點 稱為插插)(xP)(xfnxxx,10值節(jié)點值節(jié)點

2、，包含節(jié)點的區(qū)間 稱為插值區(qū)間插值區(qū)間，求插值函數(shù),ba若存在一簡單使)(xP的方法稱為插值法插值法. .2.1.1 2.1.1 插值問題的提出插值問題的提出4 插值函數(shù)插值函數(shù) p (x) 作為作為 f (x) 的近似，可以選自不同的近似，可以選自不同類型的函數(shù)類型的函數(shù), 如如 p (x) 為代數(shù)多項式、三角多項式、有為代數(shù)多項式、三角多項式、有理分式理分式；其函數(shù)性態(tài)可以是光滑的、亦可以是分段光其函數(shù)性態(tài)可以是光滑的、亦可以是分段光滑的。其中，滑的。其中，代數(shù)多項式代數(shù)多項式類的插值函數(shù)占有重要地位：類的插值函數(shù)占有重要地位： (a) 結(jié)構(gòu)簡單、計算機容易處理、任何多項式的導數(shù)結(jié)構(gòu)簡單、

3、計算機容易處理、任何多項式的導數(shù)和積分也易確定。和積分也易確定。(b) 著名的著名的Weierstrass逼近定理逼近定理(定義在閉區(qū)間上的定義在閉區(qū)間上的任何連續(xù)函數(shù)任何連續(xù)函數(shù) f(x) , 存在代數(shù)多項式存在代數(shù)多項式p(x)一致逼近一致逼近f(x),并達到所要求的精度并達到所要求的精度)。因此，我們主要考慮代數(shù)多項式的插值問題。因此，我們主要考慮代數(shù)多項式的插值問題。2022-6-2945nnxaxaaxP10)(（1.2） 若 是次數(shù)不超過 n 的代數(shù)多項式，即)(xP其中 為實數(shù)，就稱 為插值多項式插值多項式，ia)( xP本章只討論多項式插值與分段插值. 若 為分段的多項式，就稱

4、為分段插值分段插值. .)( xP 若 為三角多項式 ，就稱為三角插值三角插值. .)( xP相應的插值法稱為多項式插值多項式插值. .6 從幾何上看，插值法就是就曲線 ，使其通過給定的 個點 ，并用它近似已知曲線 . )(xPy 1nniyxii, 1 ,0),()(xfy 圖2-1見圖2-1.71. 插值問題是否可解. 若有解,是否唯一.2. 如何求插值函數(shù)P(x).3. P(x)與 f(x)的誤差如何估計.4. 當插值節(jié)點無限加密時, P(x)是否收斂 于f(x).插值法的研究內(nèi)容插值法的研究內(nèi)容8【問題問題】 設函數(shù) 在區(qū)間 上有定義，且已知在點)(xfy ,ba 上的值 ，bxxxa

5、n10nyyy,10的多項式 ，使得)(xP., 1 , 0,)(niyxPii（1.3）求次數(shù)不超過n2.1.2 2.1.2 插值多項式的存在唯一性插值多項式的存在唯一性9 在次數(shù)不超過 的多項式集合 中，滿足條件(1.3)的插值多項式 是存在唯一的. nHnnnHxP)( 由（1.3）式得到關于系數(shù) 的線性方程組因此，線性方程組（1.3）的解存在唯一，證畢.定理定理1 1證明證明其系數(shù)矩陣的行列式(是Vandermande行列式)naaa,10.,101111000010nnnnnnnnnyxaxaayxaxaayxaxaa（1.4）. 0)(111det)det(101100njijin

6、nnnnxxxxxxxxA（1.5）10插值余項與誤差估計插值余項與誤差估計 若在 上用 近似 ， ,ba)(xPn)(xf),()()(xPxfxRnn 設 在 上連續(xù)， 在 內(nèi))()(xfn,ba)()1(xfn ),(ba存在，節(jié)點 是滿足條件(2.6)的插值多項式，)(,10 xPbxxxann則對任何 ，插值余項,bax )()!1()()()()(11(xnfxPxfxRnnnn這里 且依賴于 ，),(bax則其截斷誤差為也稱為插值多項式的余項余項. .定理定理2 2).()()(101nnxxxxxxx11 余項表達式只有在 的高階導數(shù)存在時才能應用. )(xf 但 在 內(nèi)的具體

7、位置通常不可能給出，),(ba如果可以求出 那么插值多項式 逼近 的截斷誤差限是 ,)(max1)1(nnbxaMxf)(xPn)(xf. )()!1()(11xnMxRnnn12 2.2.1 2.2.1 線性插值與拋物插值線性插值與拋物插值 對給定的插值點，可以用多種不同的方法求得形如(1.2)的插值多項式. 先討論 的簡單情形.1n【問題問題】給定區(qū)間 及端點函數(shù)值 ，,10 xx)(),(1100 xfyxfy要求線性插值多項式 ，)(1xL.)(,)(111001yxLyxL2.2 Lagrange 2.2 Lagrange 插值插值使它滿足13)(1xL)()(0010101xxxx

8、yyyxL（點斜式），101001011)(yxxxxyxxxxxL（兩點式），（2.1） 由兩點式看出， 是由兩個線性函數(shù))(1xL,)(1010 xxxxxl,)(0101xxxxxl（2.2）的線性組合得到，其系數(shù)分別為 及 ，即ky1ky)()()(11001xlyxlyxL（2.3）14顯然， 及 也是線性插值多項式，在節(jié)點 及)(0 xl)(1xl0 x1x稱 及 為線性插值基函數(shù)線性插值基函數(shù)，)(0 xl)(1xl, 1)(00 xl;0)(10 xl,0)(01xl, 1)(11xl上滿足條件圖形見圖2-3.15圖2-316下面討論 的情形.2n 假定插值節(jié)點為 ， ， ，要

9、求二次插值多項式1kxkx1kx),(2xL) 1, 1()(2kkkjyxLjj 幾何上 是通過三點 的拋物線.)(2xL),(),(),(1111kkkkkkyxyxyx 可以用基函數(shù)的方法求 的表達式，此時基函數(shù))(2xL);1,(,0)(, 1)(111kkjxlxljkkk);1, 1(,0)(, 1)(kkjxlxljkkk（2.4）)., 1(,0)(, 1)(111kkjxlxljkkk使它滿足),(1xlk ),(xlk)(1xlk 是二次函數(shù)，且在節(jié)點上滿足條件17 接下來討論滿足（2.4）的插值基函數(shù)的求法，以求 為例，)(1xlk 由插值條件，它應有兩個零點 及 ，kx

10、1kx),)()(11kkkxxxxAxl可由插值條件 定出1)(11kkxl其中 為待定系數(shù)，A)(1111kkkkxxxxA于是.)()()(11111kkkkkkkxxxxxxxxxl可表示為18同理.)()()(1111kkkkkkkxxxxxxxxxl.)()()(11111kkkkkkkxxxxxxxxxl 二次插值基函數(shù) ， ， 在區(qū)間 上的圖形見圖2-4.)(1xlk )(xlk)(1xlk ,11kkxx19圖2-420 利用 ， ， ，)(1xlk )(xlk)(1xlk )()()()(11112xlyxlyxlyxLkkkkkk（2.5）顯然，將 , ， 代入 (2.5

11、) ,)(1xlk )(xlk)(1xlk )()()(111112kkkkkkkxxxxxxxxyxL)()(1111kkkkkkkxxxxxxxxy.)()(11111kkkkkkkxxxxxxxxy立即得到二次插值多項式).1, 1( ,)(2kkkjyxLjj它滿足條件得21 2.2.2 2.2.2 拉格朗日插值多項式拉格朗日插值多項式 將前面的方法推廣到一般情形，討論如何構(gòu)造通過 個節(jié)點 的 次插值多項式 .1nnxxx10n)( xLn)., 1 ,0()(njyxLjjn（2.6） 根據(jù)插值的定義 應滿足)(xLn先定義 次插值基函數(shù).n 為構(gòu)造 ，)(xLn22 定義定義1 1

12、 若 次多項式 在 個節(jié)點 n), 1 ,0()(njxLj1n), 1 , 0,(., 0;, 1)(nkjjkjkxlkj（2.7）就稱這 個 次多項式 為節(jié)點 1nn)(,),(),(10 xlxlxln上的 次插值基函數(shù)次插值基函數(shù).nxxx,10nnxxx10上滿足條件23顯然它滿足條件（2.7）. 于是，滿足條件（2.6）的插值多項式 可表示為 )( xLn. )()(0nkkknxlyxL（2.9）)()()()()()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl)., 1 , 0(nk（2.8） 與前面的推導類似， 次插值基函數(shù)為 n24由 的定

13、義，知)(xlk)., 1 ,0()()(0njyxlyxLjnkjkkjn形如（2.9）的插值多項式 稱為拉格朗拉格朗日插值多項式插值多項式，)( xLn而(2.3)與(2.5)是 和 的特殊情形.1n2n容易求得 ),()()()(1101nkkkkkkknxxxxxxxxx),()()(101nnxxxxxxx（2.10） 若引入記號 25于是公式（2.9）可改寫成 .)()()()(011nkknknknxxxxyxL（2.11） 注意注意: : 次插值多項式 通常是次數(shù)為 的多項式，n)(xLnn特殊情況下次數(shù)可能小于 .n26若取 ，則 0m.1)(0nkkxl（2.18）.,1

14、,0.)(0nmxxlxnkmkmk（2.17）可得, 1 , 0,)(nmxxfm若令它可用來檢驗函數(shù)組 的正確性., 1 ,0),(nkxlk27當 時，線性插值余項為 1n),)()(21)()(21)(1021xxxxfxfxR ,10 xx（2.17）當 時，拋物插值余項為 2n),)()()(61)(2102xxxxxxfxR ,20 xx（2.18）28由題意, 取 ,314567. 0,32. 000yx.352274. 0,36. 022yx（1）用線性插值計算，的值并估計截斷誤差. ,333487. 034. 0sin,314567. 032. 0sin,352274.03

15、6.0sin,333487. 0,34. 011yx例例1 1已知3367.0sin用線性插值及拋物插值計算解解,34. 0,32. 010 xx取由公式（2.1）29)3367. 0(3367. 0sin1L0167. 002. 001892. 0314567. 0)3367. 0(00101xxxyyy.330365. 030 由（2.17）,其截斷誤差,)(2)(1021xxxxMxR其中 )(max102xfMxxx 于是 )3367.0(3367.0sin)3367.0(11LR0033. 00167. 03335. 021xxxxsinmax10,3335.0sin1x.1092.

16、 0531（2） 用拋物插值計算，由公式（2.5）得 )()()()(3367.0sin21012012010210 xxxxxxxxyxxxxxxxxy)()(1202102xxxxxxxxy)3367.0(2L333487.00008.0107689.0314567.040008.0105511.0352274.00004.01089.344330374. 032 由（2.18）,截斷誤差限,)()(6)(21032xxxxxxMxR其中 )(max203xfMxxx 于是 這個結(jié)果與6位有效數(shù)字的正弦函數(shù)表完全一樣，0cos x,828.0這說明查表時用二次插值精度已相當高了. 33)3

17、367.0(3367.0sin)3367.0(22LR0233. 0033. 00167. 0828. 061.10178.06342.3 2.3 均差與牛頓插值公式均差與牛頓插值公式 2.3.1 2.3.1 插值多項式的逐次生成插值多項式的逐次生成 利用插值基函數(shù)很容易得到Lagrange插值多項式，公式結(jié)構(gòu)緊湊，在理論分析中甚為方便，但當插值節(jié)點增減時全部插值基函數(shù) 均要重新計算.), 1 ,0)(nkxlk【Lagrange插值多項式的缺陷】35),()(),()(111001xfxPxfxP利用點斜式直線方程得 為了克服這一缺點，我們設計一種逐次生成插值多項式的方法：對n=1,插值多項

18、式 滿足)(1xP).()()()()(0010101xxxxxfxfxfxP它可看成零次插值 的修正：)()(00 xfxP),()()(01001xxaxPxP其中 是函數(shù) 的差商.01011)()(xxxfxfa)(xf36,)()(01011xxxfxfa.)()()()()()()(1201010202120221222xxxxxfxfxxxfxfxxxxxPxPa其中),)()()(1020102xxxxaxxaaxP 對n=2，插值多項式 可表示為 )(2xP這里 是函數(shù) 的“差分的差分”，稱為“二階差分”，也稱“均差”. 2a)(xf37)()()(102010 xxxxaxx

19、aaxPn)()(10nnxxxxa（3.1）其中 為待定系數(shù)，naaa,10), 1 ,0()(njfxPjjn確定 . 一般地，插值多項式 表示為如下便于計算的形式 可由 個插值條件1n)(xPn（3.2）38 稱 為函數(shù) 關于點 的一階均差一階均差. 000)()(,xxxfxfxxfkkk)(xfkxx ,0110010,xxxxfxxfxxxfkkk稱為 的二階均差二階均差.)(xf定義定義2 2 2.3.2 2.3.2 均差及其性質(zhì)均差及其性質(zhì)3911102010,kkkkkkxxxxxfxxxfxxxf（3.3） 一般地，稱為 的 階均差階均差k)(xf（均差也稱為差商）.40

20、均差有如下的基本性質(zhì)基本性質(zhì)： .)()()()(,011010kjkjjjjjjjkxxxxxxxxxfxxxf（3.4）這個性質(zhì)可用歸納法證明. 1 階均差可表為函數(shù)值 的線性組合，)(,),(),(10kxfxfxfk 這性質(zhì)也表明均差與節(jié)點的排列次序無關，稱為均差的對稱性. 即41 3 若 在 上存在 階導數(shù)，且節(jié)點)(xf,ban,10baxxxn.,!)(,)(10banfxxxfnk（3.5）這公式可直接用羅爾定理證明.,010110 xxxxfxxfxxxfkkkk(3.3) 2 由性質(zhì)1及（3.3）可得 ,0120110 xxxfxxxxfxxxfkkk即則 階均差與導數(shù)關系

21、如下：n42,)(,)(,)(,)()()(4321043214324344321032132332102122101100 xxxxxfxxxxfxxxfxxfxfxxxxxfxxxfxxfxfxxxxfxxfxfxxxfxfxxfxxfxkk四階均差三階均差二階均差一階均差1表2 均差計算可列均差表如下（表2-1）. 43 2.3.3 Newton 2.3.3 Newton 插值多項式插值多項式 根據(jù)均差定義，把 看成 上一點，x,ba),(,)()(000 xxxxfxfxf),(,110100 xxxxxfxxfxxf).(,101010nnnnxxxxxxfxxxfxxxf可得44只

22、要把后一式代入前一式，就得到 )(,)()(0100 xxxxfxfxf)(,10210 xxxxxxxf),()(xRxNnn)(,)()(0100 xxxxfxfxNn)(,10210 xxxxxxxf其中 )()(,1010nnxxxxxxxf)(,10 xxxxfnn（3.6）),()(,1010nnxxxxxxxf45),(,)()()(10 xxxxfxNxfxRnnnn（3.7） 是由（2.10）定義的. )(1xn 顯然，由（3.6）確定的多項式 滿足插值條件，)(xNn且次數(shù)不超過 ，n)., 1 , 0(,0nkxxfakk稱 為牛頓（牛頓（NewtonNewton）均差插

23、值多項式）均差插值多項式. )(xNn 系數(shù) 就是均差表2-1中加橫線的各階均差，它比拉格朗日插值計算量省，且便于程序設計.ka其系數(shù)為 它就是形如（3.1）的多項式，46 但（3.7）更有一般性，它在 是由離散點給出的情形或 導數(shù)不存在時也是適用的.ff （3.7）為插值余項，由插值多項式唯一性知，它與拉格朗日插值多項式的余項應該是等價的. 事實上，利用均差與導數(shù)關系式就可以證明這一點. 牛頓插值多項式的優(yōu)點還在于它的遞進性，當增加插值節(jié)點時，只要在原來插值多項式的基礎上增加一項即可.47 首先根據(jù)給定函數(shù)表造出均差表. 給出 的函數(shù)表（見表2-2），求4次牛頓插值多項式，并由此計算 的近似

24、值.)596.0(f)(xf0.000120.031260.228630.524931.515331.253821.050.031340.213000.433481.384101.026520.900.197330.358931.275730.888110.800.280001.186000.696750.651.116000.578150.550.410750.40五階均差四階均差三階均差二階均差一階均差2表2)f(xxkk例例4 448 從均差表看到4階均差近似常數(shù)，5階均差近似為0. 故取4次插值多項式 做近似即可. )(4xN)55. 0)(4 . 0(28. 0)4 . 0(116.

25、 141075. 0)(4xxxxN)65. 0)(55. 0)(4 . 0(19733. 0 xxx于是 ,63192.0)596.0()596.0(4 Nf),8 . 0)(65. 0)(55. 0)(4 . 0(03134. 0 xxxx 按牛頓插值公式，將數(shù)據(jù)代入49截斷誤差 .1063.3)596.0(,)(95504xxfxR這說明截斷誤差很小，可忽略不計. 502.3.4 2.3.4 差分與等距節(jié)點的差分與等距節(jié)點的NewtonNewton插值插值 實際應用時經(jīng)常遇到等距節(jié)點的情形，這時插值公式可以進一步簡化，計算也簡單得多. 2.3.4.1 2.3.4.1 差分及其性質(zhì)差分及其

26、性質(zhì) 設函數(shù) 在等距節(jié)點 上的值 為已知，這里 為常數(shù)，稱為步長步長.)(xfy ), 1 , 0(0nkkhxxk)(kkxff h 為了得到等距節(jié)點的插值公式，先介紹差分的概念.51記號 ,1kkkfff（4.1）,1kkkfff（4.2）,)2/()2/(2121kkkkkffhxfhxff（4.3）分別稱為 在 處以 為步長的向前差分向前差分，向后差分向后差分)(xfkxh 符號 ， ， 分別稱為向前差分算子向前差分算子，向后差分算子向后差分算子定義定義3 3及中心差分中心差分. 及中心差分算子中心差分算子.52 利用一階差分可定義二階差分為 .21212kkkkkkffffff一般地

27、可定義 階差分階差分為 m.111kmkmkmfff.111kmkmkmfff 中心差分 用到了 及 這兩個值，但它們并不是函數(shù)表上的值.kf21kf21kf 如果用函數(shù)表上的值，一階中心差分應寫成53這樣，二階中心差分為 21212kkkfff 除了已引入的差分算子外，常用算子符號還有不變算不變算子子 及移位算子移位算子 ，IE,kkffI,1kkffE于是，由,)(1kkkkkkfIEfIfEfff),(IE ,121kkkfff,121kkkfff.2)(1111kkkkkkkfffffff定義如下：可得54,1EI,2121EE同理可得 55 差分基本性質(zhì). 性質(zhì)性質(zhì)1 1knknfI

28、Ef)(knknfEIf)(1其中 為二項式展開系數(shù). !) 1() 1(jjnnnjn例如各階差分均可用函數(shù)值表示.kjnnjjfEjn0) 1(（3.9a）,) 1(0jknnjjfjnknjnjjnfEjn0) 1(（3.9b）,) 1(0njknjjnfjn56 性質(zhì)性質(zhì)2 2 例如，可用向前差分表示 ，knf所以 .0kjnjknfjnf（3.10）knknfEf可用各階差分表示函數(shù)值.因為knfI)(,0kjnjfjn57 性質(zhì)性質(zhì)3 3kkkkkkxxffxxf111,kkkkkkkkkxxxxfxxfxxxf212121,2122kfh 例如，對向前差分，均差與差分有密切關系.

29、由定義,hfkhhxfxfhxfxfkkkk2)()()()(11258同理，對向后差分有 ,1!1,1kmmmkkkfhmxxxf 利用（4.7）及均差與導數(shù)的關系又可得到),()(nnknfhf （3.12）其中 ，),(nkkxx,1!1,kmmmkkfhmxxf).,2,1(nm 一般地有 這就是差分與導數(shù)的關系.（3.11a）（3.11b）594434222343133244043212233032122021100443322)()()()()()()()()()()()()()(ffffffffffffffffffffffffffk 3表2 計算差分可列差分表（見表2-3），表中

30、 為向前差分， 為向后差分. 60 2.3.4.2 2.3.4.2 等距節(jié)點的等距節(jié)點的NewtonNewton插值公式插值公式 將牛頓均差插值多項式（3.6）中各階均差用相應差分代替，就可得到各種形式的等距節(jié)點插值公式. .)() 1()(101kjkjkhktttxx 如果節(jié)點 ，要計算 附近點 ), 1 , 0(0nkkhxxk0 x的函數(shù) 的值，x)(xf 這里只推導常用的前插與后插公式.于是, 10,0tthxx可令6102000! 2) 1()(fttftfthxNn,!) 1() 1(0fnntttn（3.13）將此式及均差與差分的關系代入牛頓插值公式，則得 ),()!1()()

31、 1()()1(1nnnfhnntttxR).,(0nxx（3.14）稱為NewtonNewton前插公式前插公式， 由（3.7）得余項62 如果要表示 附近的函數(shù)值 ，也可使用牛頓插值公式（3.6），但為了降低誤差，插值點應按 的次序排列，nx)(xf01,xxxnn)(,)()(1nnnnnxxxxfxfxN)(,121nnnnnxxxxxxxf 作變換 ，并利用公式均差與向后差分關系公式（4.8），01,tthxxn這時).()(,101xxxxxxxfnnn得63稱其為牛頓后插公式牛頓后插公式，)()()(thxNxfxRnnn),()!1()() 1()1(1nnfhnnttt（4.13）其中 ).,(0nxx02! 2) 1()(fttftfthxNnnnn,!) 1() 1(nnfnnttt（4.12）其余項64 通常求開頭部分插值點附近函數(shù)值時使用牛頓前插公式，求插值節(jié)點末尾附近函數(shù)值時使用牛頓后插公式. 如果用相同節(jié)點進行插值，則向前向后兩種公式只是形式上差別，其計算結(jié)果是相同的.65為使用牛頓插值公式，先構(gòu)造差分表（表2-4）. 給出 在 xxfcos)(1 .0,6 , 1 ,0,hkkhxk