插值算法之：拉格朗日插值

記一下拉格朗日插值公式的推導和一些要點【這裡說的都是二維插值，多元上的以此類推】

1、插值問題：在做實驗的過程中，往往得到一堆離散的資料，現在想用數學公式模拟這堆離散資料。怎麼辦，數學家們提出了插值問題。插值問題的提法是這樣的給定一堆資料點(x0, y0), (x1, y1), (x2, y2)...(xn, yn)，要求一個函數 y = f(x) ，要求該函數經過上面所有的資料點。

2、多項式插值及其唯一性：在所有的函數中，多項式函數是最簡單的函數，是以隻要是人就會想到用多項式函數來作為插值函數，好，以上給定了n+1個點，現在要求一個n次多項式y = an * x^n + ... a1 * x + a0, 使它們經過這n+1個點；通過範德蒙行列式 和 克萊姆法則，可以判定如果這n+1個點的x值各不相同，那麼這個多項式是唯一的。結果唯一，但是用直接法很不好求。現在用别的辦法來求之。這就是：拉格朗日多項式

3、拉格朗日多項式的構造，以四個點為例子進行說明

由于函數經過4個點(x0, y0)，(x1, y1)，(x2, y2)，(x3, y3)，是以可以設函數為：

f(x) = b0(x) * y0 + b1(x) * y1 + b2(x) * y2 + b3(x) * y3

注意：b0(x)，...，b3(x)都是x的3次多項式，稱之為拉格朗日插值基函數。

由于要求當x為x0時候，f(x) = y0, 是以最簡單的做法就是讓b0(x0) = 1, b1(x0) = b2(x0) =  b3(x0) = 0;

同理可知，在x1，x2，x3點上，插值基函數的值構造如下：

                b0(x)        b1(x)        b2(x)        b3(x)

x=x0         1                0              0              0

x=x1         0                1              0              0

x=x2         0                0              1              0

x=x3         0                0              0               1

問題1、根據這些值來确定b0(x)的表達式，

由于b0(x1) = b0(x2) = b0(x3) = 0，是以x1, x2, x3是b0(x)的零點，由于b0(x)是三次多項式，是以設

b0(x) = c0 * (x-x1) * (x-x2) * (x-x3)

由于b0(x0) = 1,是以 1 = c0 * (x0-x1) * (x0-x2) * (x0-x3)  得到 c0 = 1/[(x0-x1)(x0-x2)(x0-x3)]

是以：b0(x) = (x-x1)*(x-x2)*(x-x3)/[(x0-x1)*(x0-x2)*(x0-x3)]

同理可求b1(x)、b2(x)，略

問題2、根據上面的表格說明插值基函數的一個性質：無論x取和值，它們的和都為1.【這個叫做調和函數】

以3次為例子說明：将上述表格的每一行分别相加，得到的事函數：g(x) = b0(x) + b1(x) + b2(x) + b3(x)在x0, x1, x2, x3的值，都為1.

                     b0(x) + b1(x) + b2(x) + b3(x)

x=x0                    1+0+0+0 = 1

x=x1                    0+1+0+0 = 1

x=x2                    0+0+1+0 = 1

x=x3                    0+0+0+1 = 1

是以：方程g(x) - 1 = 0，應該有4個根x0, x1, x2, x3；但是，由于b0(x)、b1(x)、b2(x)、b3(x)都是3次多項式，是以，g(x)最多也是3次多項式，至多隻有3個根，是以等式：g(x) = 1 應該是恒等式。得證。

問題3、基函數：b0(x)、b1(x)、b2(x)、b3(x) 是線性無關的。

設：數t0, t1, t2, t3使得：t0 * b0(x) + t1 * b1(x) + t2 * b2(x) + t3 * b3(x) = 0

x=x0時候：0 = t0 * b0(x0) + t1 * b1(x0) + t2 * b2(x0) + t3 * b3(x0) = t0 * 1 + t1 * 0 + t2 * 0 + t3 * 0 得到：t0 = 0;

同理有：t1 = t2 = t3 = 0，根據定義（所有系數為0）。是以插值基函數是線性無關的。