插值方法是數(shù)值分析中的一種古老而重要的方法早在6世紀(jì)

1、第二章 插值法§1 Lagrange插值插值方法是數(shù)值分析中的一種古老而重要的方法。早在6世紀(jì)，我國的六(554610)就首先提出等距節(jié)點插值方法，并成功地應(yīng)用于天文計算。17世紀(jì)I. Newton和J. Gregory建立了等距節(jié)點上的插值公式。18實際J. L. Lagrange給出了更一般的非等距節(jié)點上的插值公式。在近代，插值方法是數(shù)據(jù)處理、函數(shù)近似表示和計算機(jī)幾何造型等常用的工具，又是導(dǎo)出其他許多數(shù)值方法（如數(shù)值積分、非線性方程求根、微分方程數(shù)值解等）的依據(jù)。在生產(chǎn)和科學(xué)實驗中，函數(shù)有時僅能獲得它的若干點的函數(shù)值或微商值，即只給出的一張數(shù)據(jù)表。如果根據(jù)這張數(shù)據(jù)表，構(gòu)造一個簡單

2、函數(shù)，使之滿足數(shù)據(jù)表中的數(shù)據(jù)。這樣的函數(shù)就是的逼近函數(shù)。這種逼近問題就稱為插值問題。一、插值問題1. 設(shè)表示所有次數(shù)不超過的多項式的集合。設(shè)是一組互異的點，所謂次多項式插值，就是求多項式，使之滿足 (1.1)其中稱為插值節(jié)點，是插值多項式，是被插（值）函數(shù)，(1.1)是插值條件， (1.2)是插值余項，是插值區(qū)間，稱為型值點。二、插值多項式的存在性和唯一性1. 定理1（存在性和唯一性）滿足插值條件(1.1)的多項式存在，并且唯一。證 設(shè)，由插值條件(1.1)得非齊次線性方程組 (1.3)其系數(shù)行列式是Vandermonde行列式。 因為是一組互異的點，所以.由Cramer法則知：方程組(1.3

3、)有唯一的一組解，即滿足插值條件(1.1)的多項式存在，并且唯一。 證畢！2. 幾何解釋：通過曲線上給定的個點，可唯一地作一條次代數(shù)曲線作為曲線的近似曲線。三、Lagrange插值公式1. 定理2（Lagrange插值公式） 次多項式 (1.4)滿足插值條件(1.1)，其中 (1.5)稱(1.4)式為Lagrange插值多項式或Lagrange插值公式；(1.5)式為Lagrange插值基函數(shù)。證 作次多項式，使之滿足對，有又因為，即，所以構(gòu)造次多項式，顯然即滿足條件(1.1)的插值多項式。 證畢！注 若設(shè)，則，于是 (1.6)例1 已知，求的Lagrange插值多項式。解 設(shè)，則故所求插值多

4、項式為.例2 求經(jīng)過點三點的Lagrange插值多項式。解 設(shè)，則故所求插值多項式為.2. 定理3（Lagrange插值公式的余項）設(shè)在包含插值節(jié)點的區(qū)間上次可微，則對，存在（與有關(guān)），使得 (1.7)證 當(dāng)時，(1.7)自然成立。當(dāng)時，作輔助函數(shù) (1.8)顯然在上次可微，且.因為互不相同，由Rolle定理知：在內(nèi)至少有個不同的零點。同理，由Rolle定理知：在內(nèi)至少有個不同的零點。依此類推，在內(nèi)至少有1個不同的零點，即即. 證畢！推論 若是次數(shù)不超過次的多項式，的次Lagrange插值多項式為，則.證 由(1.7)式立得！或：由插值多項式的唯一性立得！或：由代數(shù)基本定理立得！ 證畢！命題

5、(1) ；(2) ;(3) .證 (1) 令，則；則由上述推論知：的次Lagrange插值多項式為，即.(2) 對，令，則；則由上述推論知：的次Lagrange插值多項式為，即.(3) 對，有.3. Lagrange插值公式的優(yōu)、缺點：優(yōu)點：結(jié)構(gòu)緊湊、思想清晰、顯式表示、公式對稱，與插值節(jié)點的編號無關(guān)，適合理論分析。缺點：沒有承襲性。§2 逐步線性插值為了清楚起見，用一個例子說明Aitken算法。例 已知列表函數(shù) 1 2 3 4 0 5 6 3用Aitken算法求的近似值。解 ，用列表方法求解。故Aitken算法的優(yōu)、缺點：優(yōu)點：(1) 將一個高次插值過程轉(zhuǎn)化為線性插值的多次重復(fù)。計

6、算簡便、便于編程、占用存儲空間小。(2) 具有承襲性。Aitken插值表中的每個數(shù)據(jù)都是插值結(jié)果。每做一步，檢查計算結(jié)果的精度，若不滿足精度要求，則增加一個節(jié)點再算，直到滿足精度要求為止。檢查的方法：對給定的精度，看是否滿足。缺點：主要用于計算具體點處的近似值，而不是得到一個具體的插值公式，不便于理論分析。§3 Newton插值公式一、差分及其性質(zhì) 差分的理論是微分學(xué)的原始形式，也是微分的離散化。在歷史上，微分學(xué)正是由有限差分的理論產(chǎn)生的，因此差分與微分有著極其相似的性質(zhì)。下面僅以向強(qiáng)差分為例進(jìn)行說明。1. 定義1 設(shè)；是步長，稱 (3.1)為在處的一階向前差分； (3.2)為在處的

7、二階向前差分；一般地，在處的階向前差分定義為階向前差分的一階向前差分： (3.3)定義2 設(shè)；是步長，稱 (3.4)為在處的一階向后差分； (3.5)為在處的二階向后差分；一般地，在處的階向后差分定義為階向后差分的一階向前差分： (3.6)此外還可以定義在處的一階中心差分 (3.7)2. 差分的性質(zhì)（以向前差分為例，向后差分和中心差分也有類似的性質(zhì)）(1) 常數(shù)的差分等于零。即：若（常數(shù)），則(2) 若是常數(shù)，則(3) 若，其中是常數(shù)，則.(4) 設(shè)是次多項式（最高次系數(shù)為），則當(dāng)時，的階差分為次多項式；且；當(dāng)時，.(5) 設(shè)；，則 (3.8)其中.(6) 設(shè)；則， 實際計算向前差分時，一般采

8、用向前差分表一階差分二階差分三階差分四階差分實際計算向后差分時，一般采用向后差分表一階差分二階差分三階差分二、差商及其性質(zhì)1. 定義3 設(shè)是一組互異的點，稱 (3.9)為在處的一階差商。 (3.10)為在處的二階差商。（一階差商的差商）其中.一般地，在處的階差商（差商的差商）是 (3.11)2. 性質(zhì)(1) 若， 是常數(shù)，則.(2) 若，則.(3) ，其中.（為清楚起見，用二階差商具體推導(dǎo)出： (4) 差商具有對稱性。（In fact, 由性質(zhì)(3)立得。） (5) 若是關(guān)于的次多項式，則是關(guān)于的次多項式。In fact, 記，則是關(guān)于的次多項式。因為，所以；其中是關(guān)于的次多項式。于是是關(guān)于的

9、次多項式。證畢！(6) 若，則.3. 重節(jié)點的差商 ；一般地，.實際計算差商時，一般利用差商表一階差商二階差商三階差商三、Newton插值公式定理1 設(shè)是一組互異的點，則次多項式 (3.12)滿足插值條件，并稱(2.1)為Newton插值多項式。且余項為 (3.13)證 因為，所以 (3.14)其中；因為，所以代入(3.14)，得 (3.15)其中；依次類推，得其中； . 證畢！注 1) 由§1的插值問題解的唯一性知：Newton插值公式僅是Lagrange插值公式的一種變形。2) Newton插值公式既具有Lagrange插值公式便于理論上分析的優(yōu)點，又具有Aitken算法的承襲性

10、。例1 已知列表函數(shù) 1 2 3 4 0 5 6 3試求滿足上述插值條件的3次Newton插值多項式解 造差商表則所求3次Newton插值多項式為定理2 設(shè)在包含插值節(jié)點的區(qū)間上次可微，則存在介于之間的，使得 (3.16)證 由Lagrange插值余項及Newton插值余項，介于與之間，得：特別地，當(dāng)時，有 ，介于之間。 證畢！四、等距節(jié)點上的Newton插值公式設(shè)是一組等距插值節(jié)點，. 用數(shù)學(xué)歸納法，可以證明函數(shù)的差分與差商之間的關(guān)系：定理3 ； (3.17). (3.18)1. ，即在左端點附近進(jìn)行插值，一般地，宜用Newton向前插值公式。設(shè)的滿足插值條件的次Newton插值公式為 (3

11、.19)利用(3.17)式及，(3.19)化為 (3.20)并稱(3.20)式為Newton向前插值公式。2. ，即在右端點附近進(jìn)行插值，一般地，宜用Newton向后插值公式。設(shè)的滿足插值條件的次Newton插值公式為 (3.21)利用(3.18)式及，(3.21)化為 (3.22)并稱(3.22)式為Newton向后插值公式。例2 已知函數(shù)的數(shù)值表 0 1 2 3 1 2 17 64試分別求出的三次Newton向前和向后插值公式；并分別計算和時，的近似值。解 造向前和向后差分表則所求三次Newton向前插值公式為，.所求三次Newton向后插值公式為，.§4 Hernite插值公式

12、在某些問題中，為了保證插值函數(shù)能更好地密合原來的函數(shù)，不但要求“過點”，即：兩者在節(jié)點處具有相同的函數(shù)值，而且要求“相切”，即：兩者在節(jié)點處還具有相同的導(dǎo)數(shù)值，這類插值稱作“切觸插值”或“Hermite插值”。一、兩個節(jié)點的三次Hermite插值1. 問題 已知，求作三次多項式，使之滿足 (4.1)2. 幾何解釋 代數(shù)曲線與曲線不但有兩個交點，而且在點處兩者相切。3. 求解為簡化計算，先設(shè)，則插值條件(4.1)化為 (4.2)定理1 三次多項式 (4.3)滿足插值條件(4.2)，其中 (4.4)并稱(4.3)為三次Hermite插值公式，(4.4)為三次Hermite插值基函數(shù)。證 作三次多項

13、式，使之分別滿足 (4.5)由條件(4.5)可設(shè)，其中.因為，所以；又因為，且，即所以. 同理可得其他。且證畢！推論 設(shè)為任意兩個節(jié)點，令，則 (4.6) (4.7)4. 插值余項定理2 設(shè)在包含插值節(jié)點的區(qū)間上4次可微，則對，存在介于與之間的，使得 (4.8)證 若或，則(4.8)顯然成立。設(shè)（不妨設(shè)），作輔助函數(shù) (4.9)其中. 則令，則.分別在上對運用Rolle定理，得：，使得再分別在上對運用Rolle定理，得：，使得.再分別在上對運用Rolle定理，得：，使得.再在上對運用Rolle定理，得：，使得，即即，于是. 證畢！二、個節(jié)點的Hermite插值1. 問題 已知，求作次多項式，使

14、之滿足 (4.10)類似于三次Hermite插值公式的構(gòu)造過程，得定理3 次多項式 (4.11)滿足插值條件(4.10)，其中 (4.12)并稱(4.11)為次Hermite插值公式，(4.12)為次Hermite插值基函數(shù)。定理4 設(shè)在包含插值節(jié)點的區(qū)間上次可微，則對，存在介于與之間的，使得 (4.13)§5 分段多項式插值一、分段多項式插值的概念1. 高次多項式插值的Rung現(xiàn)象 多項式歷來被認(rèn)為是最好的逼近工具之一，用多項式作插值函數(shù)，就是前面已經(jīng)討論過的代數(shù)插值。對于這種插值，插值多項式的次數(shù)隨著節(jié)點的個數(shù)的增加而升高，然而高次多項式插值的逼近效果往往并不理想。上世紀(jì)初，Ru

15、ng就發(fā)現(xiàn)：隨著節(jié)點的加密，采用高次多項式插值，當(dāng)增大時，插值函數(shù)在兩端回發(fā)生激烈的振蕩。這就是所謂的Rung現(xiàn)象。對于這一情形，F(xiàn)aber證明過以下結(jié)果：Faber定理 對區(qū)間上任意給定的三角陣總存在，使得由三角陣中的任一行元素為插值節(jié)點所生成的次插值多項式，當(dāng)時，不能一致收斂到.2. 分段多項式插值定義 將所考察的區(qū)間作一分劃：在每個小區(qū)間上構(gòu)造插值多項式；將每個小區(qū)間上的插值多項式拼接在一起，作為整個區(qū)間上的插值函數(shù)。并稱這樣構(gòu)造出的插值函數(shù)為分段插值多項式。若分段插值多項式在每個小區(qū)間上都是次多項式，則稱為具有分劃的分段次多項式，點稱為的結(jié)點。二、分段三次Hermite插值1. 求作具

16、有分劃的分段3次多項式，使之滿足 (5.1)由“§4 Hermite插值”得：對，有 (5.2)滿足插值條件(5.1). 其中 ， (5.3)2. 誤差估計及收斂性定理 設(shè)在區(qū)間上4次可微，則對，有 (5.4)其中.若，則當(dāng)時，在區(qū)間上一致收斂到.證 記，對，由三次Hermite插值余項定理得 (5.5)由高等數(shù)學(xué)中求最大值的方法，易知：當(dāng)時，在區(qū)間上達(dá)到最大值，由(5.5)得若，則. 故當(dāng)時，由(5.4)知：在區(qū)間上一致收斂到. 證畢！3. 分段多項式插值的優(yōu)、缺點優(yōu)點：1) 顯式算法，算法簡單，收斂性、穩(wěn)定性好。只要結(jié)點間距充分小，分段插值總能獲得所要求的精度，而不會出現(xiàn)Rung

17、現(xiàn)象。2) 局部性。如果要修改某個數(shù)據(jù)，插值曲線僅僅在某個局部范圍內(nèi)受到影響；而代數(shù)插值卻會影響到整個插值區(qū)間。缺點：光滑度不高。若要提高光滑度，必須提供較多的信息才能達(dá)到。§6 有理函數(shù)插值 一、 有理函數(shù)插值的基本概念有理分式函數(shù)是典型的非線性插值，當(dāng)函數(shù)在某點附近無界，或者當(dāng)而趨于某一定值時，采用多項式插值是不合適，因為多項式不能反映在某點附近無界的函數(shù)性態(tài)。而當(dāng)時，多項式的值總是趨于無窮。但有理分式函數(shù)，如卻能刻畫在附近無界，有能保證當(dāng)而趨于定值. 因此討論有理插值問題具有實際應(yīng)用價值。設(shè),和都是非負(fù)整數(shù)，記所有次數(shù)不超過的一元多項式，：，0. 給定型值點，其中互異。所謂有理

18、函數(shù)插值問題，就是尋求有理分式函數(shù) (6.1)使之滿足條件 (6.2)考慮齊次線性方程組即 (6.3)一般來說齊次線性方程組(6.3)的解未必是(6.2)的解，即有理插值問題的解不一定總是存在的，見下面的例1。也就是說：有理插值問題的解存在是有條件的，這也是有理插值與多項式插值的不同點。例1 已知型值點，設(shè)，由(6.3)得解得，取，則得.于是，顯然不滿足已知插值條件。 定義1 若與是互質(zhì)的兩個多項式，即與沒有非常數(shù)的公因式，則稱有理函數(shù)為最簡有理分式函數(shù)。定義2 設(shè)有兩個有理分式函數(shù)和，若存在一個非零常數(shù)，使得，則稱與恒等，記為. 若，則稱與等價，記為.命題 與等價與的最簡有理分式恒等。注 以

19、后視等價的有理分式為同一個函數(shù)。定理1 有理插值問題(6.1)、(6.2)若有解，則其解必唯一。二、有理插值的存在性下面給出有理插值問題(6.1)、(6.2)的存在性定理。設(shè)，其中互異。令 (6.4) (6.5)及的逆矩陣 . (6.6)經(jīng)過計算，我們得到下列遞推公式： (6.7)利用代數(shù)知識可以證明定理2 滿足插值條件(6.2)的有理函數(shù)存在的充分必要條件是方程組 (6.8)存在一組解滿足, ，且 (6.9)其中注 定理2不但給出了有理插值問題的解存在的充要條件，還給出了有理插值函數(shù)的顯式表達(dá)式。例2 給定型值點及有理插值函數(shù)類型求，使之滿足插值條件.解 由(6.4)得于是它的逆矩陣可由(6

20、.7)算出再由(6.8)得解此方程組，得解向量，其中為非零常數(shù)。取，得解向量，代入(6.8)，得滿足插值條件的有理函數(shù)三、連分式插值眾所周知在多項式插值中，Newton插值是一種重要的插值形式。仿照它，我們可以構(gòu)造有理插值函數(shù)的反差商公式。為此首先定義反差商。對于給定的型值點，其中互異。稱 (6.10)為函數(shù)在處的一階反差商； (6.11)為函數(shù)在處的二階反差商；一般地 (6.12)為函數(shù)在處的階反差商。計算反插商可利用反插商表一階反差商二階反差商三階反差商類似于Newton多項式插值的構(gòu)造方法，記，其中. 由(6.11)得，其中.反復(fù)利用高階反差商(6.12)表示，得上式是一個連分式，用下面

21、記號表示. (6.13)記 ， (6.14)可以驗證它滿足插值條件，.并稱為反差商有理插值函數(shù)。將式(6.14)由后向前逐步有理化，得這是一個有理分式，且當(dāng)為偶數(shù)時，即時，；當(dāng)為奇數(shù)時，即時，其中是非負(fù)整數(shù)。例3 已知型值點如例2，利用反差商表一階反差商二階反差商三階反差商四階反差商得 . 這個結(jié)果與例2的結(jié)果完全一致。我們知道差商是其自變量的對稱函數(shù)，即在階差商中任意調(diào)換的位置，差商值不變。而反差商不是其自變量的對稱函數(shù)，為此我們引入倒差商的概念。記，稱 (6.15)為函數(shù)在處的一階倒差商， (6.16)為函數(shù)在處的二階倒差商. 一般地，稱 (6.17)為函數(shù)在處的階倒差商.可以證明（這里不證） 倒差商是其自變量的對稱函數(shù)，即在階倒差商中任意調(diào)換的位置，倒差商的值不變。 (6.18)計算倒差商可以利用下面的倒差商表一階倒差商二階倒差商三階倒差商利用倒差商代替(6.14)中的反差商就產(chǎn)生所謂Thiele型連分式 (6.19)四、逐步有理插值定義序列, (6.20)其中由上面的討論知，是過點的有理插值函數(shù)。引入序列 (6.21