共分五次
第一次　線性插值的唯一性和拉格朗日插值
第二次　牛頓插值
第三次　赫米特插值
第四次　分段插值
第五次　習(xí)題課和小結(jié)

$\Large\mathbf{第一節(jié) 多項(xiàng)式插值的唯一性和拉格朗日插值}$

$\large\mathbf{多項(xiàng)式插值的唯一性}$

一.多項(xiàng)式插值引言

??實(shí)際問題中，對離散點(diǎn)的函數(shù)擬合，以及對函數(shù)表達(dá)式復(fù)雜的函數(shù) $y=f(x)$ 可以使用一個(gè)簡單的連續(xù)函數(shù) $g(x)$ 來近似替代，以簡化問題。其中 $f(x)$ 為被逼近函數(shù)， $g(x)$ 為逼近函數(shù)。
??如果要求構(gòu)造的函數(shù) $g(x)$ 取給定的離散數(shù)據(jù)，即 $g(x_i)=f(x_i) (i=1, 2,3,...,n)$ ,當(dāng) $g(x)$ 為代數(shù)多項(xiàng)式時(shí)，與之對應(yīng)的插值逼近稱為代數(shù)多項(xiàng)式插值。

$\large{多項(xiàng)式插值問題:}$
??確定一個(gè)次數(shù)不高于n的多項(xiàng)式，
$p_n(x)=a_0+a_1x+a_2x^2+...a_nx^n\tag{2.1}$
使其滿足
$p_n(x_i)=y_i \qquad i=0,1,2,...,n \tag{2.2}$
點(diǎn) $x_i(i=0,1,2,...)$ 互異,稱為插值節(jié)點(diǎn)，包含插值節(jié)點(diǎn)的區(qū)間 $[a,b]$ 稱為插值區(qū)間。
??從幾何上看，多項(xiàng)式插值問題即是求作一條曲線 $y=f(x)$ 上給定的n+1個(gè)點(diǎn)的n次代數(shù)曲線 $y=p_n(x)$ 作為 $y=f(x)$ 的近似。

這樣的多項(xiàng)式的是唯一的，下面給出證明:

證明:

該多項(xiàng)式滿足

$\begin{equation} \left\{ \begin{array}{lr} a_0+a_1x_0+a_2x_0^2+...+a_nx_0^n=y_0\\ a_0+a_1x_1+a_2x_1^2+...+a_nx_1^n=y_1\\ ...\\ a_0+a_1x_n+a_2x_n^2+...+a_nx_n^n=y_n\\ \end{array} \right. \end{equation}$

可以寫成形如 $AX=b$ 的形式,其中 $X=[a_0,a_1,a_2,...,a_n]^T\quad b=[y_0,y_1,y_2,...y_n]$
其系數(shù)矩陣
$A=\left[ \begin{array}{1} 1 & x_0 & x_0^2 & ... & x_0^n \\ 1 & x_1 & x_1^2 & ... & x_1^n \\ .\\ .\\ .\\ 1 & x_n & x_n^2 & ... & x_n^n \end{array} \right]$

根據(jù)線性代數(shù)中的非齊次線性方程組的有解性，以及 $x_i \neq x_j (i \neq j)$ 可知系數(shù)矩陣A是一個(gè)滿秩的范德蒙行列式，故解唯一，即插值多項(xiàng)式存在且唯一。

結(jié)論:
??對于給定了互異的n+1個(gè)插值節(jié)點(diǎn)n次代數(shù)多項(xiàng)式插值，其n次代數(shù)多項(xiàng)式是存在且唯一的，其形式為 $p_n(x)=a_0+a_1x+a_2x^2+...a_nx^n$

$\Large \mathbf{拉格朗日插值}$

2.2.1 線性插值

[引入] $\begin{equation} 函數(shù)y=f(x)給定兩點(diǎn)(x_0,y_0),(x_1,y_1)求一個(gè)次數(shù)小于1的多項(xiàng)式 \end{equation}$
$p_1(x)=a_0+a_1x$
使它滿足
$p_1(x_i)=y_i\qquad i=0,1$
形如此類構(gòu)造即為線性插值。

特別的，這種構(gòu)造可以寫成基函數(shù)的形式，對插值點(diǎn)有基函數(shù) $l_i(x_i)=1, l_i(x_j)=0 (i\neq j),$
這樣就可以構(gòu)造 $l_i(x)=\frac{ {\prod\limits_{ j=0, i\neq j}^n}(x-x_j)}{{\prod\limits_{ j=0, i\neq j}^n}(x_i-x_j)}$ 這樣的話，只有基函數(shù)對應(yīng)的插值點(diǎn)時(shí)值為1,否則為0。

2.2.2 拋物插值

雖然直線插值簡單方便，但是由于它是用直線代替曲線，基于導(dǎo)數(shù)推導(dǎo)的知識(shí)我們知道，這種方法只適合插值區(qū)間 $[x_0,x_1]$ 較小的情況，且 $f(x)$ 在插值區(qū)間上變化平穩(wěn)，否則誤差可能很大。
為了克服這一問題，考慮用更高次的多項(xiàng)式來近似地替代。
(更高次替代更準(zhǔn)確的原因類比泰勒展開，函數(shù)的特征在于增減性和函數(shù)值，在這兩個(gè)要素上越接近，逼近函數(shù)越契合被逼近函數(shù)，但是這是已知函數(shù)解析式的情況下，對于插值，高次擬合會(huì)產(chǎn)生runge現(xiàn)象，后面會(huì)提到)

類似的，利用基函數(shù)來構(gòu)造
$\begin{equation} l_0(x_0)=1\qquad l_1(x_1)=1\qquad l_2(x_2)=1\\ \end{equation}$
其余不對應(yīng)的基函數(shù)值為0。
這樣，我們構(gòu)造出
$\begin{equation} l_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}\\ l_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}\\ l_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}\\ \end{equation}$
得到的拋物構(gòu)造函數(shù)為 $p_2(x)=\sum\limits_{i=0}^2 l_i(x)*y_i$

2.2.3 Lagrange插值公式

[引入] 設(shè) $y=f(x)$ 在給定的互異節(jié)點(diǎn) $x_0,x_1,x_2,...,x_n$ 上的函數(shù)值為 $y_0,y_1,y_2,...y_n$ ,求作一個(gè)次數(shù)小于n的多項(xiàng)式。
$\\p_n(x)=a_0+a_1x+a_2x^2+...a_nx^n$
使它滿足
$\\p_n(x_i)=y_i \qquad i= 0,1,2,...,n$
類似的，我們以基函數(shù)構(gòu)造 $p_n(x)=\sum\limits_{i=0} ^n l_i(x)*y_i \tag{2.3 拉格朗日插值公式}$
其中 $l_i(x)是一個(gè)n次多項(xiàng)式，滿足多項(xiàng)式次數(shù)條件，且由于l_i(x)的對性，也滿足p_n(xi)=y_i$
構(gòu)造完畢，這就是拉格朗日插值公式，基于基函數(shù)的構(gòu)造方法。
注: $l_i(x)=\frac{ {\prod\limits_{ j=0, i\neq j}^n}(x-x_j)}{{\prod\limits_{ j=0, i\neq j}^n}(x_i-x_j)}$
$對插值區(qū)間[a,b]\forall x \in [a,b],\quad\sum l_i(x)=1。$

2.2.4插值余項(xiàng)

了解了插值擬合方法，也需要確定插值的精度，此時(shí)結(jié)合 $R_n(x)=f(x)-p_n(x)$ 計(jì)算n次代數(shù)多項(xiàng)式插值的截?cái)嗾`差，也是插值余項(xiàng)。

證明有兩種，一種是本教材的證明，另外一種是《數(shù)值分析　第五版》李慶楊著中的證法，考慮到證明的自然性，這里先使用李書中的證法。

證法一:
由構(gòu)造方法知道，當(dāng)x取值在插值點(diǎn)時(shí)是沒有誤差的，故可以構(gòu)造下列式子，其根包含所有插值點(diǎn)
$R_n(x)=K(x)*(x-x_0)(x-x_1)(x-x_2)...(x-x_n)$
其中, $K(x)$ 是與 $x$ 有關(guān)的待定系數(shù)，現(xiàn)在把 $x$ 看作是 $[a,b]$ 上的一個(gè)固定點(diǎn)，K(x)是一個(gè)常量,作函數(shù)

$\varphi(t)=f(t)-p_n(t)-K(x)*(t-x_0)(t-x_1)(t-x_2)...(t-x_n)$
$取t=x 則\qquad \varphi(x)=f(x)-p_n(x)-R_n(x)=0$
$另外的，對于t=x_i \quad (i=0,1,...,n) \quad \varphi(t)=0$
故 $\varphi(t)有n+2個(gè)零點(diǎn)，分別為x,x_0,x_1,...,x_n,由Rolle(羅爾)定理，使用n+1次可得$
$\varphi^{(n+1)}(\xi)= f^{(n+1)}(\xi)-K(x)*(n+1)!=0$
$\therefore K(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}$
$\therefore R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}*\prod\limits_{i=0} ^{n} (x-x_i) \qquad \xi \in[a,b]$
這樣就可以給出拉格朗日插值余項(xiàng)的解析解，但是 $\xi$ 是區(qū)間上的某點(diǎn)，不能準(zhǔn)確獲得，所以類似的，采用誤差限的方式，我們求取插值余項(xiàng)的誤差限。