多項式插值

在數值分析這個數學分支中，多項式插值用多項式對一組給定資料進行插值的過程。換句話說就是，對於一組給定的資料，其目的就是尋找一個恰好透過這些資料點的多項式。應用.多項式可以根據少數給定的資料點來逼近複雜的曲線，如字型排印學中的文字。一個相關的應用是估計自然對數和三角函式的值：選擇幾個已知的資料點、構建一個查詢表、然後在這些資料點之間進行插值。這樣可以得到非常快速的計算。另外多項式插值也是數值積分和數值常微分方程中演算法的基礎。多項式插值在 sub-quadratic 乘法以及平方運算中也很關鍵。例如，有 "a" = "f"("x") = "a"0"x"0 + "a"1"x"1 + ... 以及 "b" = "g"("x") = "b"0"x"0 + "b"1"x"1 + ... 那麼乘積 "ab" 等於 "W"("x") = "f"("x")"g"("x")。基於這些點的插值將得到 "W"("x") 以及乘積 "ab"。對於 Karatsuba 乘法來說，這項技術的速度要比普通數目輸入的二次乘法速度要快，尤其是在用並行的硬體實現的時候更是這樣。定義.給定一組 "n"+1 個數據點，其中任意兩個 "x""i" 都不相同， 需要找到一個滿足formula_1的不大於 "n" 階的 "p" 階多項式。唯一性定理表明存在一個並且僅有一個這樣的 "p" 階多項式。用更加複雜的說法，這個多項式可以表述為：對於 "n"+1 個插值點 ("x""i")，多項式插值定義了一個線性雙射formula_2其中 formula_3 是小於或者等於 "n" 的多項式的向量空間。構建插值多項式.假設插值多項式的形式為formula_4"p" 對資料點進行插值其含義為formula_5如果代入等式，就得到係數為 formula_6 的線性方程系統，用矩陣向量形式表示為formula_7為了構建插值多項式 formula_8，我們要解這個系統計算係數 formula_6。左側的矩陣通常叫作範德蒙矩陣，它的行列式不為零，這也就證明了唯一性定理：存在唯一的一個插值多項式。非範德蒙解.我們要在 "n" 階多項式向量空間 formula_3 中構建唯一的一個插值多項式。當用單項式基表示 formula_3 時，為了建立插值多項式的係數 formula_6 我們要解範德蒙矩陣，這個過程可能會耗費大量的計算量。透過為 formula_3 選擇另外一種基我們可以簡化係數的計算，但是如果需要用單項式基表示的話當然需要一些額外的計算工作。其中一個方法是將插值多項式表示成牛頓型多項式，並且使用均差方法建立係數。其代價是formula_14運算，而高斯消去需要 formula_15運算。另外，如果在資料集中添加了額外的點，也只需要很少的額外運算；而其它方法通常都需要全部重新計算。另外一個方法是使用拉格朗日型的插值多項式，得到的結果公式馬上就表明在滿足上面定理所定義條件下存在插值多項式。Bernstein form 最初是 Sergei Natanovich Bernstein 在魏爾施特拉斯逼近定理的建設性證明中所用的形式，如今它在計算機圖形學的貝塞爾曲線中得到了非常重要的應用。插值誤差.用 "n" 階多項式在節點 "x""0"、...、"x""n" 對函式 "f" 插值的誤差為：formula_16其中formula_17是均差符號。如果 "f" 在包含節點 "x""i" 的最小區間 "I" 上 "n"+1 次連續可導，那麼我們可以將在 "I" 中 formula_18 的誤差寫成拉格朗日型formula_19這樣，拉格朗日型泰勒定理的餘數就是所有插值節點 "x""i" 都相同的情況下的插值誤差特例。如果插值節點等距分佈 formula_20，那麼插值誤差為 formula_21。但是，這並不意味著隨著 "n" → ∞ 插值誤差將趨近於 0；實際上，在接近區間 formula_22 端點的時候，誤差甚至可能會變得無限大，這種現象叫作龍格現象。上面的誤差範圍說明我們要選擇使乘積 | ∏ ("x" − "x""i") | 儘可能小的插值點 "x""i"。切比雪夫節點就可以實現這個結果。勒貝格常數.在插值節點 "x"0、...、"x""n" 以及包含所有插值節點的區間 ["a", "b"] 確定下來，插值的過程就是將函式 "f" 對映到多項式 "p"。這定義了一個 ["a", "b"] 區間上所有連續函式從空間 "C"(["a", "b"]) 到其自身的對映。對映 "X" 是線性的，並且它是函式 "f" 在子空間 Π"n" 上的投影。勒貝格常數 "L" 定義為 "X" 的運算元範數，它滿足勒貝格引理：formula_23換句話說，插值多項式的誤差最多是最優逼近的倍，這表明我們要找使 "L" 最小的插值節點。尤其是選擇切比雪夫節點時：formula_24我們再次證明切比雪夫節點是多項式插值中比較好的選擇，但是這些節點並不是最優的。收斂性.很自然我們有一個疑問，即對於什麼型別的函式以及什麼樣的插值節點情況下，插值多項式才能夠收斂到被插值的函式。收斂性有不同的型別，如點態收斂、一致收斂或者積分收斂。下面將討論一致收斂。下面的定理是一個相當令人振奮的答案：對於在區間 ["a","b"] 內連續的任意函式 "f"("x")，存在一個節點表使得插值多項式 formula_25 在 ["a","b"] 內一致收斂於 "f"("x")。證明：根據魏爾施特拉斯逼近定理，我們知道最優逼近多項式序列 formula_26 一致收斂到 "f"("x")。 現在我們只需證明每個 formula_26 都可以透過在特定節點的插值得到，但是根據切比雪夫交錯定理這是最優逼近多項式的一個特性。我們明確地得知這樣的多項式至少與函式 "f"("x") 相交 "n"+1 次。將這些交點作為插值的節點，那麼插值多項式就是最優逼近多項式。但是這個方法的缺點是對每個新函式 "f"("x") 都要重新計算插值節點，而這個演算法很難用數值方法實現。是不是存在一個節點表能夠滿足插值多項式序列收斂到任意一個連續函式 "f"("x") 呢？這個問題的答案是否定的，其理由在於下面的定理的結論：對於任何的節點表都存在一個連續函式 "f"("x") 在區間 ["a","b"] 上使得插值多項式發散。這個證明主要是依據勒貝格常數下限的估計，它定義了 'X""n" 的運算元範數，其中 'X""n" 是在 Π"n" 上的投影運算元。現在我們要找一個對於任意的 formula_28 符合formula_29條件的節點表。根據 Banach-Steinhaus定理，只有當 "X""n" 的範數一致有界時才存在這樣的節點表，但是根據 formula_30 我們知道這是不可能的。例如，如果選擇等距點作為插值節點，那麼龍格現象中的函式表明這樣的插值就會出現發散現象。需要注意的是這個函式不僅連續而且在 [−1, 1] 內無限可導。但是對於效果較好的切比雪夫節點，根據下面的定理很難出現這個問題。對於每個在 [−1, 1] 區間絕對連續的函式，在切比雪夫節點上構建的插值多項式序列一致收斂於 "f"("x")。相關概念.龍格現象表明高階插值多項式可能在資料點之間出現震盪，通常可以透過樣條插值來解決這個問題，在這種情況下，它不僅僅是一個多項式，而且是樣條：一串低階多項式組合。使用調和分析函式對週期函式的插值通常是使用傅立葉級數實現的，如在離散傅立葉變換中所作的那樣。這可以看作是一種帶有調和基函式的多項式插值，角插值與三角多項式。埃爾米特插值問題是不僅給出了多項式 "p" 的值，而且給出了一些導數。伯克霍夫插值是給定一些導數而沒有給定 "p" 自身的值的插值方法的一般形式。微分與積分方程的配置法解法都是基於多項式插值。