多項式插值

插值法又稱“內插法”，是利用函式f (x)在某區間中已知的若干點的函式值，作出適當的特定函式，在區間的其他點上用這特定函式的值作為函式f (x)的近似值，這種方法稱為插值法。如果這特定函式是多項式，就稱它為多項式插值。常用的幾種多項式差值法有：直接法、拉格朗日插值法和牛頓插值法。

基本介紹

• 中文名：多項式插值
• 外文名：polynomial interopolation
• 類型：插值技術
• 方法：直接法;拉格朗日法；牛頓法
• 用來：曲線擬合、回歸
• 套用領域：人工智慧

定義

給定n+1個點 （稱為插值點），所謂多項式插值就是找到一個多項式（稱為插值多項式）

使得它滿足條件

其中，i=0,1,...,n。也就是說，多項式y=P(x)的圖像要經過給定的n+1個點。

在實際套用中，這些插值點可能來自某次實驗測量所得的數據，也可能來自某個複雜函式 的值。通過計算插值多項式，我們可以找到這些實驗數據間的規律，或者使用簡單的多項式函式 來近似複雜的函式 。

唯一性和誤差

定理一：

給定n+1個點 ,若 兩兩不同，則存在唯一一個次數不超過n的多項式 ，使得 成立。

證明：利用范德蒙德矩陣和代數學基本定理即得。

當 的值來自某個函式 ，且f(x)具有n+1階連續導數時，下面的定理可以用來計算多項式插值的（截斷）誤差。

定理二：

給定n+1個點 ,其中 ，進一步假設函式f(x)具有n+1階連續導數，則插值多項式P(x)的誤差R(x)為

其中，

計算方法

給定n+1個點, 計算插值多項式的主要方法有：直接法、拉格朗日多項式插值和牛頓多項式插值。下面我們分別介紹這三種方法。

（注意，根據定理一，這三種方法得到的插值多項式在理論上說應該是一致的，而且誤差也相同。）

直接法

根據定理一，假設插值多項式為

由插值條件 ，我們得到關於係數 , ,…, , 的線性方程組

通過求解這個線性方程組，即得到插值多項式。

優點：直接，性質一目了然。

缺點：待求解的線性方程組的係數矩陣為范德蒙德(Vandermonde)矩陣，它是一個病態矩陣，這使得在實際求解方程組時將產生很大的誤差。

拉格朗日多項式插值

拉格朗日(Lagrange)多項式插值的原理是：先構造一組拉格朗日基函式 ，這些基函式為次數不超過n的多項式，且具有性質

然後將這些基函式做線性組合，得到拉格朗日插值多項式

容易驗證，多項式L(x)滿足插值條件

拉格朗日基函式 的構造如下：

由基函式的性質，當 時， ，即 為 的零點，可以假設

其中，K為待定係數。再由 ，得到

從而得到

因此，基函式

令 ，則 還可以表示為

下面的定理說明 稱為基函式的原因：

定理三：令 為全體次數不超過n的多項式構成的集合，則 是線性空間 的一組基。

Matlab 實現

function [y,Lb] = LagrangeInterpolation(X,Y,x)% 拉格朗日多項式插值函式% 注意：插值點的個數為n，差值多項式的次數為n-1%% 輸入參數% X,Y: 插值點坐標% x: 求值點%% 輸出參數% y: 拉格朗日插值多項式在x點的值% Lb: 拉格朗日基函式在x點的值if length(X) ~= length(Y)    error('X和Y的長度不相等');    endn = length(X);    %獲取插值點的個數    %初始化    y = 0;    Lb = ones(1,n);    for i = 1:n           for j = 1:n %計算拉格朗日基函式在x點的值            if j ~= i               Lb(i) = Lb(i) * (x-X(j))/(X(i)-X(j));                    end       end       y = y + Lb(i)*Y(i);        %計算拉格朗日插值多項式的值     endend

均差與牛頓多項式插值

牛頓多項式插值是基於均差的計算。首先定義均差如下：

函式f(x)關於點的一階均差（或差商）為

一階均差反映了函式在區間的平均變化率

用遞歸的方式，我們定義二階均差為

同理，k階均差為

特別地，0階均差定義為 。

根據均差的定義，構造均差表如下：

如果將x也看作一個點，由均差的定義可以得到

其中，

稱為牛頓插值多項式。

為插值餘項。

由定理一和定理二得到均差和導數的關係如下：

其中，

Matlab實現

function [y,Nt]=NewtonInterpolation(X,Y,x)% 牛頓多項式插值函式% 注意：插值點的個數為n，差值多項式的次數為n-1%% 輸入參數% X,Y: 插值點坐標% x: 求值點%% 輸出參數% y：牛頓差值多項式在x點的值% Nt：均差表if length(X) ~= length(Y)    error('X和Y的長度不相等');    endn = length(X);     Nt = zeros(n);     %初始化均差表，按列存放各階均差    Nt(1,1) = Y(1);     %0階均差    for i = 2:n     %按行計算均差表       Nt(i,1) = Y(i); %0階均差       for j = 2:i           Nt(i,j) = (Nt(i,j-1)-Nt(i-1,j-1))/(X(i)-X(i-j+1));           end    end    %計算牛頓插值多項式在x點上的值w = 1;    y = Nt(1,1) * w;    for i = 2 : n        w = w * (x - X(i-1));        y = y + Nt(i,i) * w;    end end

比較

拉格朗日多項式插值的計算量大於牛頓多項式插值的計算量。

特別地，當新增一個插值點時，拉格朗日插值需要重新計算全部的基函式，而牛頓插值只需計算均差表中新的一行的值即可。