多項式插值方法教學目的及要求：要求掌握基本的定理及各種插值方法。插值方法是數(shù)學分析中很古老的一個分支.它有悠久的歷史.等距結點內(nèi)插公式是由我國隋朝數(shù)學家劉焯(公元544—610年)首先提出的;而不等距結點內(nèi)插公式是由唐朝數(shù)學家張遂(公元683—727年)提出的.這比西歐學者相應結果早一千年.插值方法在數(shù)值分析的許多分支(例如,數(shù)值積分,數(shù)值微分,微分方程數(shù)值解,曲線曲面擬合,函數(shù)值近似計算,等等)均有應用.下面僅以近似計算函數(shù)值為例來說明設已知某個函數(shù)關系的列表函數(shù)值而問應該如何估值對于函數(shù)關系,我們所知道僅僅上述的表列值,它們常常是間接求得的.例如是由實驗(觀測)得來的,或者是從級數(shù)或微分方程求得的.我們可以使用插值方法估計y.插值方法的目的是尋求簡單的連續(xù)函數(shù),使它在n+1個點處取給定值,而在別處希望它也能近似地代表函數(shù).因為已是有解析表達式的簡單函數(shù),所以它在處的值可以按表達式精確地計算出來.這樣我們就可以將看成的近似值了給定點為插值結點.稱函數(shù)為函數(shù)的關于的插值函數(shù).稱為被插函數(shù).嚴格的說,插值方法一詞只用于落在給定點之間的情形,所以也稱它為內(nèi)插法.如果落在給定點之外,并且仍以插值函數(shù)在處近似地代替,則一般稱這種近似計算函數(shù)的方法為外插法.本章我只研究多項式插值，亦即是x的多項式的情形.這不僅僅因為多項式是最簡單的函數(shù)，而且因為在許多場合，函數(shù)容易用多項式近似地表示出來.此外,用多項式作插值函數(shù)可滿意地解決一系列有應用價值的重要問題.特別是數(shù)值積分與數(shù)值微分的問題.本章講不涉及三角插值法.其實,只要理解了代數(shù)多項式插值方法的實質(zhì)讀者就不難自行導出關于三角多項式插值方法的一系列相應與代數(shù)多項式插值方法的理論結果§1.Lagrange插值公式設是實變量x得單值函數(shù)，且已知在給定的n+1個互異點處的值,即插值的基本問題是,尋求多項式,使得設是一個m次多項式則插值問題是，如何確定中的系數(shù),使得(1.1)式得以滿足.所以該問題等價于求解下述的線性方程組:上述的線性方程組的系數(shù)矩陣為它是一個(n+1)×（m+1）矩陣.當m>n時，A的列數(shù)大于行數(shù).不難證明矩陣A的秩數(shù)為n+1.因為A的前n+1列所組成的行列式為(稱為Vandermonde行列式)我們有為證(1.3),考慮n次多項式顯然均為它的零點,且它的系數(shù)恰為即從而有下述遞推關系式運用它即可證明(1.3)式根據(jù)(1.3),并注意到諸互異，從而線性方程組(1.2)的系數(shù)矩陣的秩數(shù)為n+1.它表明(1.2)的解是不唯一的，即插值問題(1.1)的解不唯一。當m<n時,矩陣A的行數(shù)大于列數(shù).按照(1.3)式,線性方程組(1.2)的每m+1個方程組成的方程組均有唯一一組解.但一般說來，如此求出的各組未必相同.即此時(1.2)可能是矛盾方程組.鑒于以上情形，看來取m=n是最為適宜的.現(xiàn)在我們重提多項式插值問題:給定n+1個互異點,對任意一組數(shù)，是否存在唯一的，使得如下插值條件被滿足該問題的答案是肯定的.今采用構造性方法把所要求的多項式求出來。試設想,如果可求出具有如下性質(zhì)的特殊的插值多項式則多項式必為滿足(1.4)的多項式.但(1.5)中上面的等式,指出中除外,均為的零點,因此其中c為常數(shù)，但(1.5)中下面的等式指出所以記，則又可表示為更簡潔的形式總之n次多項式滿足插值條件（1.4）若也滿足插值條件（1.4）,則必以為零點,即.這樣一來,n次多項式竟然有n+1個不同的零點.是故所以由(1.7)表示的n次多項式（嚴格地說，是次數(shù)不超過n的多項式）是中滿足插值條件的唯一多項式.它常常稱作為Lagrange插值多項式,并記為按前述推理可知Lagrange插值多項式也可視為是從下面的行列式方程中解出來的:(請讀者自行補證).由(1.9)式表示的公式便于推廣到一般形式的插值問題由于篇幅所限,此處不能祥述.由(1.1)所示的條件稱為插值條件,點組稱為插值結點.上面所得到的結果可以從幾何上解釋為,有且僅有一條n次代數(shù)曲線，通過平面上事先給定的n+1個點.其中Lagrange插值公式（1.8）具有結構清晰、緊湊的特點，因而適合于作理論分析和應用.例1已知。求的Lagrange插值多項式解依公式有從而例2設則依Lagrange插值公式，有§2.Newton插值公式Lagrange插值公式的缺點是，當插值結點的個數(shù)有所變動時（例如，為了提高精度,有時需增加插值節(jié)點的個數(shù)）Lagrange因子就要雖之發(fā)生變化,從而整個公式的結構也要發(fā)生變化,這在計算實踐中是不方便的.為了克服它的上述缺點,在這一節(jié)中我們引進了Newton形的插值公式顯然,n+1個結點上的n次Lagrange插值多項式也可以寫成下列形式：下面，來確定上式中的令表示n個結點上的（n-1）次Lagrange插值多項式，由于,所以此處c為常數(shù)，由條件可以定出又因故又有引進記號得與之間的關系同理繼續(xù)下去，最終得到公式（2.2）就是Newton型插值公式.系數(shù)由（2.1）式確.Newton插值公式的導數(shù)很不好記,因此有必要另尋方法確定它們.為此我們引進差商的概念,并指出Newton插值公式中各導數(shù)即是的i階差商.設已知不同的自變量上的函數(shù)值稱為的一階差商(或均差).一階差商的一階差商叫做的二階差商.一般說來我們稱(n-1)階差商的一階差商為函數(shù)的n階差商差商有以下諸性質(zhì)若，c為常數(shù)，則若，則若，m為自然數(shù),則差商是的對稱函數(shù),亦即當任意調(diào)換的位置時,差商的值不變,例如5.差商可以表示成兩行列式之商:注規(guī)定，當n=0時，=1:.性質(zhì)1和性質(zhì)2由定義可以直接推出。現(xiàn)在我們證明性質(zhì)3。的一階差商可根據(jù)定義直接計算出來： 如所見，它是的次齊次函數(shù)。相繼作出各階差商并依完全歸納法，可證實下列公式：此處求和運算遍及所有可能的形如的的次齊次項。這樣便證明了性質(zhì)3。再來證明性質(zhì)4。作出相繼的各階各差商之后，讀者不難看出它們是由形如的個項的和表示出來的。由完全歸納法，易求得可由（2.1）式的右端表出。使用前面的記號也可將它寫成如此便證明了性質(zhì)4。最后，用完全歸納法同樣可以證明性質(zhì)5。為了作數(shù)值計算，常利用形式如下的差商表：一階差商二階差商三階差商由性質(zhì)4得知Newton插值公式(2.2)中的系數(shù)恰標出）。因此，當已知時利用差商表可以很容易地算出的各階差商的值，而不必去記憶公式。因為在個不同的點上取給定值的次數(shù)不超過ｎ的多項式是唯一的，所以次數(shù)相同的插值多項式與插值多項式是恒等的，它們的差異僅是書寫形式不同而已。但是，這種差異卻為計算實踐帶來了很大的方便。實際上，對于插值公式來說，當需要增加一個插值結點時，只需在原插值多項式的后面再添加一個新項就可以了。例１已知列表函數(shù)：２３５６５２３４求這個函數(shù)的插值多項式。解先造好下列的差商表：一階差商二階差商三階差商然后從上表頂部對角線上取得的值代入公式，便可得到要求的多項式：§３．插值余項設是在點處關于的插值多項式。我們希望知道時，與的偏差，意指此方法所固有的誤差，而忽略在計算時造成的舍入誤差。通常，舍入誤差與在逼近中的固有誤差相比是小的。按習慣，稱為插值誤差（插值余項）。下面定理給出了的表達式。定理1若于包含著插值結點的區(qū)間上次可微，則對任意，有與有關的ξ存在（a<ξ<b）,使得（3.1）其中。證明今取一點，顯然當時，(3.1)式是自然滿足的。以下設不是插值結點，作輔助函數(shù)。（3.2）顯然于上次可微，并且。因為各不相同，由Rolle引理知于內(nèi)至少有個不同的根。依此類推，最后知于內(nèi)至少有一個根ξ，亦即由(3.2)式應有。由此，便得到了公式(3.1)。證畢。通常我們并不知道(3.1)式中的ξ（一旦知道了ξ，就知道了精確的誤差），盡管如此，我們還是能從(3.1)式得到有用的信息。例如，若上有上界，亦即，則由(3.1)式立刻得到。(3.3)設已知，并且。如所知，為了構造一個次插值多項式，只需要個插值結點。因此自然提出這樣的問題：在所有的已知點的橫坐標中，如何選取插值結點使得(3.4)為此，只須從中選擇使差取最小值的作為第一個插值結點。然后，在剩下的個點中再選擇使得為最小的點作為第二個插值結點。如此等等，直到選出為止。顯然，這樣選取的滿足(3.4)的要求。關于在整個插值區(qū)間上的余項極小化問題，與第二章中Tchebyshev最小零偏差多項式直接相關。事實上，由(3.3)式，為使插至余項在整個區(qū)間上盡可能地小的“最佳”插值結點組，應該取為該區(qū)間上最小零偏差多項式的零點。以下給出插值余項的Peano估計。它是意大利數(shù)學家G.Peano在1913年給出的。令是有限區(qū)間，是整數(shù)。若在上連續(xù)，而上分段連續(xù)且，則說函數(shù)屬于函數(shù)類.令。容易驗證。令及則因此，，同時令是實數(shù)，是整數(shù)。二個變量的函數(shù)定義如下若為固定常數(shù)，則的截斷多項式。對于截斷多項式的圖形如下(圖3.1)：當固定時，是t的函數(shù)，請讀者繪出它的圖形().我們用來記包含著點的最小區(qū)間。仍表插值誤差，亦即其中在結點上的次插值多項式。定理2設是正整數(shù)(),則當屬于時，存在一個僅依賴于的函數(shù)：(3.6)使得(3.7)證明依假設條件，可以將展成Taylor級數(shù)：其中顯然，由于當是次數(shù)的多項式時插值是精確的，所以，因此（3.8）現(xiàn)在，我們寫出：把上式中的積分合并，并依公式（3.6）和（3.8），即得（3.7）。證畢。定理2也稱為關于插值公式的核定理。函數(shù)稱為Peano核。顯然，只依賴于，而不依賴于。利用方程（3.7），可以估計插值誤差的界。例如，有下面的定理。定理3設是一正整數(shù)（），則,(3.9)其中（3.10）證明由于所以證畢。自然會問，估計式（3.9）中的常數(shù)能不能用較小的常數(shù)代替？結論由下面的定理給出。定理4設是一正整數(shù)由公式（3.10）給出，則有函數(shù)使得證明令（3.11）于是，通過對次不定積分運算，即可求出（自然它含有個任意的積分常數(shù)）。依（3.11）式，從而證畢。由（3.3）所給出的估計式與估計式（3.9）是一致的（?。?。定理5由（3.3）式與（3.9）式給出的插值誤差的界是恒等的，換言之（3.12）這個定理的證明基于以下三個引理。引理1當時，核函數(shù)上至少改變一次符號。證明考慮多項式。若，則。但是，從而并因此至少在上改變一次符號。證畢。引理2如果上改變次符號，則上至少改變次符號。證明依（3.6）式，另一方面，不難看出的不定積分（取負號）。由此推出，若處改變符號，則上最多改變一次符號。引理3當上恰好改變次符號（從而，上不變號）。證明我們知道，是階分段多項式，特別，分別是常數(shù)。處有跳躍。因為這些點中有兩個是的兩端點，所以的符號在上最多改變次。如果的變號次數(shù)小于，或者如果對于任何的變號次數(shù)小于，則依引理2，不變號。但是，依引理1這是不可能的，于是恰好改變符號次。定理5的證明考慮函數(shù)由于所以但是，依（3.7）式又有由于不變號，故綜合之，即得（3.12）式。證畢?！?.有限差分計算這一節(jié)介紹有限差分的概念。設已知函數(shù)在一串等距結點上的值定義表達式為在點處的一階有限差分，或簡稱一階差分。一階差分的一階差分叫二階差分，記為一般說來，階差分定義為階差分的一階差分：例如按定義可知符號滿足指數(shù)律：其中是正整數(shù)。有限差分的理論是微分學的原始形式。在歷史上，微分學正是由有限積分的理論產(chǎn)生的，所以差分與微分有著極其相似的性質(zhì)。茲列舉如下：常數(shù)的差分等于零，亦即若，則常數(shù)因子可以提到差分號外，亦即若為常數(shù)，則有如果當時，其中是一些常數(shù)，用歸納法可以證明如果當則用歸納法可以證明上述結論。設次多項式（最高次項的系數(shù)為），則階差分為次多項式；當時，是常數(shù)，即時為零。不失一般性，讀者可以僅就的情形，用歸納法證明這一結論。設已知的值，用逐次代入法容易證明，計算差分有以下公式：（4.1）按相似的方法，對(4.1)型方程用逐次消元法，得到（4.2）實際計算差分時，常用如下表格（差分表）： …下面的定理揭示了函數(shù)的差商，差分和到數(shù)之間的關系。定理6設函數(shù)在包含結點的區(qū)間上為次可微函數(shù)，則此處證明首先，用歸納法容易證明（4.3）式?，F(xiàn)在證明（4.4）式。令表示在結點上的次插值多項式。因為插值余項于處為零，類似于定理1的證明知有某使得另一方面，由Newton插值公式知道聯(lián)合以上兩式可得（4.4）式。最后，由(4.3)與(4.4)式即可導出(4.5)式。證畢。熟知，次多項式的階導數(shù)等于零，因此它的階差分也等于零。這個性質(zhì)使得我們可以借助于差分表的性質(zhì)來確定所需的插值多項式的次數(shù)。例如，當發(fā)現(xiàn)函數(shù)的第階差分為常數(shù)或近似為常數(shù)時，則用次多項式去作插值多項式就會有較好的結果。上面介紹的差分叫向前差分。鑒于計算實踐的需要，我們再介紹向后差分和中心差分的概念。設為已知，則分別定義為在處的向后1階，2階，階差分。由向后差分定義，容易驗證在實際計算向后差分時，我們常采用向后差分表：由方程定義的差分叫作一階中心差分。類似地，稱為階中心差分。容易驗證可以利用下表計算中心差分三種差分間有下列關系：今定義位移算子E為其中為步長。單位算子（恒等算子）I定義為即。諸多算子間有以下關系式成立：鑒于對足夠光滑的，有所以由此不難看出，的任一近似計算公式都可派生出一個相應的數(shù)值微分公式（至于誤差則要作具體分析）。這表明對數(shù)函數(shù)和指數(shù)函數(shù)的近似計算問題具有十分重要的意義。因為由此我們可以“發(fā)現(xiàn)”新的數(shù)值微分和數(shù)值積分公式。應該指出的是，這里介紹的觀點可以用來“發(fā)現(xiàn)”一些新的數(shù)值微分與數(shù)值積分公式，但不能作為嚴格的手段來運用。事實上，人們在“發(fā)現(xiàn)”了新的公式之后，還應該用嚴密的推理來論證它們。只有這樣，才是周全的。§5.等距結點上的插值公式對于給定的等距結點的數(shù)據(jù)，我們可以靈活運用插值余項極小化原則，給出適應具體要求的插值公式。一般說來，在左端點附近進行插值，宜用Newton向前插值公式；在右端點附近插值，宜用Newton向后插值公式。如果在插值區(qū)間中間進行插值，宜用帶中心差分的插值公式。下面分別予以簡要介紹。5.1Newton向前插值公式設已知，需求于處的近似值。按余項極小化原則，插直結點應取注意差商與差分的關系，由Newton插值公式，得到其中通常稱該公式為Newton向前插值公式。5.2Newton向后插值公式設，由插值公式（2.2），可得Newton向后插值公式：此處其中在諸之間。該公式適用于計算函數(shù)在最后一個結點附近的近似值（內(nèi)插或外推）。5.3Gauss插值公式現(xiàn)在我們引進帶中心差分的插值公式。在插值公式（2.2）中，用結點列替代結點列得到若設，則有（5.1）在（5.1）式中，當時，取至偶數(shù)階差分時，取至基數(shù)階差分插值余項為：當時，(5.2)當時，通常，稱上述公式為Gauss向前公式。在公式(2.2)中，若用結點列替代結點列時，得到的是Gauss向后公式：(5.3)在公式(5.3)(5.1)中，“或”的意義相同。是余項，并且當時，它由(5.2)給出，而當時，§6.Hermite插值公式為了理論和應用上的需要，本節(jié)討論一類具有重結點的多項式插值方法，即Hermite插值方法。因為此類插值問題要求在結點處滿足相應的導數(shù)條條件，所以它也被稱為切觸插值問題。設(6.1)為事先指定的實數(shù)，其中為正整數(shù)：(6.2)今構造一個次多項式使之滿足插值條件：(6.3)為解決插值問題(6.3)，最直接的方法是采用代定系數(shù)法，或者求解由(6.3)所確定的線性方程組。此處我們采用構造基本多項式的辦法來解決Hermite插值問題(6.3)。構造一批次多項式使之滿足(6.4)和(6.5)顯然，只要上述問題一解決，則次多項式(6.6)就必滿足插值條件(6.3)。以下集中來構造由(6.4)和(6.5)，可知其中是某次多項式。若令則上式可縮寫為(6.7)為確定還需利用條件(6.5)和Taylor展開可得(6.8)比較(6.7)與(6.8)，有其中為確定的常數(shù)，所以它必定是函數(shù)于處Taylor展開的前項和。若把這項和記為則由(6.7)式，應有從而(6.9)若于(6.3)中取則相應的Hermite插值多項式為(6.10)例1設則插值問題(6.3)就是通常多項式插值問題。此時，按定義有其中相應的Hermite插值多項式恰為一般Lagrange插值公式例2設僅有一個重的結點則而相應的Hemite插值多項式恰為于點附近Taylor展開式的部分和例3設則相應的Hermite插值問題為求次多項式使之滿足(6.11)這個特定的Hermite插值問題的幾何意義在于使曲線不僅通過給定的型值點而且在處與曲線有相同的切線。為推導相應Hermite插值公式，記則又因故由(6.10)式，有更特殊地，當時，相應插值公式為下述3次多項式(6.13)這是一個非常重要的Hermite插值多項式。它所刻畫的曲線是這樣一條曲線；其在區(qū)間兩個端點處，不僅通過曲線上的點與，而且與有相同的切線。Hermite插值公式(6.12)的誤差估計由下述定理給出。定理7設于上連續(xù)，于內(nèi)存在，又設則由(6.12)式所確定的Hermite插值多項式有如下的估計式(6.14)其中證明若為中的某一個，則顯然(6.14)成立。以下假設中的任一個。由于以為二重零點，因此可設(6.15)對上述給定的作輔助函數(shù)按插值條件，可知這表明有個2重零點和單零點。由Rolle定理，于以及這個不同點所形成的個小區(qū)間內(nèi)部各有一個零點。注意到原來已有個零點，從而有個互異的零點。再次運用Rolle定理，有個零點。依此類推，最后可知有一個零點，記為。根據(jù)的定義和(6.15)式，即知(6.14)式成立。證畢?！?.多元多項式插值在一元插值問題中，我們曾利用差商算法導出Newton插值公式。本節(jié)將討論多元多項式插值問題。先從比較簡單的二元插商插值算法開始。設D是上的有界閉區(qū)域，是定義在D上的連續(xù)函數(shù)。取定D中的結點組（可整序格點網(wǎng)）(7.1)其中對于函數(shù)，可視自變量為固定值，則可按一元差商的定義而得到再視上述差商中的諸為固定，則又可得到它關于自變量的差商這樣一來，我們已經(jīng)給出了二元差商的一種定義方式，并可以計算出它們來。為了書寫方便，記按一元Newton插值公式，可知從而上的插值公式為(7.2)其中=(7.3)是滿足插值條件(,)=(7.4)的多項式，而相應插值余項為（7.5）應該注意到，上述插值多項式空間為.容易直接驗證以上插值多項式是唯一的.例1在插值公式(7.2)中取,則得到矩形網(wǎng)點上的插值公式,(7.6)其中 =這里和落在包含的最小區(qū)間內(nèi)，而和落在包含的最小區(qū)內(nèi)．注意此時插值空間為．例２在插值公式（7.2）中取,則得到插值空間中的插值公式+(7.7)其中利用插值公式（7.2）,人們還可以引導出許多插值公式。讀者可以根據(jù)需要來確定和使用它們。設函數(shù)定義在區(qū)間上，對于給定的個不同的點個數(shù)值顯然插值問題有解，必須且只須行列式（7.8）一個由個定義在點集上的函數(shù)組成的系統(tǒng)稱為在上是唯一可解的，如果對于中任意給定的個互異點，來說，（7.8）恒成立。顯然，在上唯一可解，必須且只須在的個互異點上取值為零的線性組合必恒為零.由1，組成的函數(shù)組在上是唯一可解的，但在[-1，1]上卻不是唯一可解的.在任何區(qū)間[]上,函數(shù)組是唯一可解的.三角函數(shù)系在-π＜π上是唯一可解的.以下Haar定理指出，在高維空間中，唯一可解性通常是保證不了的。定理8（Haar）設是歐氏空間中包含一個內(nèi)點的點集。設定義于上，且其中每個函數(shù)均在的一個鄰域內(nèi)連續(xù)。則這個函數(shù)組在上不是唯一可解的。證明設是一個包含在中以為中心的小球，它使得諸在其內(nèi)是連續(xù)的。選取中個不同的點?？梢约俣ǎ?.9）若不然，則該函數(shù)組已經(jīng)不是唯一可解，從而定理已證完了。現(xiàn)固定，并在內(nèi)連續(xù)的移動和，使得和互換位置。由于是中的小球，因而在和互換位置的過程中，人們既可保證和不相重合，又可保證它們也不與中的任一點相重合。注意到當我們按上述要求交換了與的位置后，（7.9）式右端行列式的第1列和第2列恰好交換了位置。按行列式性質(zhì)，交換前后兩行列式異號。因為是內(nèi)的連續(xù)函數(shù)，所以在和互換位置的過程中必然存在某個中間位置，使與之相對應的行列式為零。從而函數(shù)組在上不是唯一可解的。證畢。順便指出，為使上述Haar定理成立，可以不必要求點集中包含有內(nèi)點。事實上，只須要求中包含有一個“三岔“點，亦即在點處有3段互相遇就可以了（見圖7.1）。因為人們可以仿照火車慣用的方法使得與互換位置。根據(jù)Haar定理,在構造多元插值多項式時,插值結點組的選取是一個關鍵的問題。因為并不是對于任意給定的插值結點組，多元插值多項式都是存在并且唯一的。為搞清插值結點組的選取問題，先須引入相應的概念。設是一組線性無關的實系數(shù)二元多項式，P=span.D是上的有界閉區(qū)域，是D中無異的點。二元多項式插值問題，是要尋求，使得下述插值條件被滿足：.(7.10)這樣的多項式稱為在P中的插值多項式，稱為插值結點。由Harr定理，為求得插值多項式，首要的問題是選擇插直結點組，使得插值問題（7.10）的解存在并且唯一。若對給定的被插函數(shù)，插值問題（7.10）的解存在并且唯一，則稱是空間P的適定節(jié)點組。設是P中的一個非零多項式,P中的代數(shù)曲線由下述點集所定義：。由插值適定結點組的定義和線性代數(shù)理論，可以建立下述引理。引理點組是空間P的適定結點組，必須且只須該點組不在P中的任何一條曲線上。該引理的必要性是顯然的。事實上，如果是P中的適定結點組，則表明插值問題（7.10）對任意給定的均有唯一的解存在。于是行列式。若有某非零多項式存在，使得點組落在代數(shù)曲線上。即。有適定性定義，必有。這與多項式的非零性相矛盾。必要性得證。以下證明充分性。假定不是P的適定結點組。于是=0。這表明 的k個行向量組是線性相關的，即存在一組不全為零的實數(shù)，使得。它說明落在P中的代數(shù)曲線上。充分性得證。Bezout定理設與分別是m與n次的代數(shù)多項式.如果它們的公共零點數(shù)多于mn,則與必有公共因子存在。這是一條十分重要的定理，由于篇幅所限