Interpolation

记笔记
本文基本上不包含个人理解

---

1

Given (finR([a,b])) 以及它在 ({x_i}_{i=0}^nsubset[a,b]) 集合内各点处的值
如果函数集合 (Phi) 中的函数 (phi(x)) satisfies (phi(x_i)=f(x_i),quad i=0,1,cdots,n)
那么 (phi) 是函数集合 (Phi) 中 (f) 的一个 interpolation

这种简单的插值问题等价于确定系数 ({a_i}_{i=0}^n) 使得

[left[ egin{array}{l} 1 & x_0 & x_0^2 & cdots & x_0^n \ 1 & x_1 & x_1^2 & cdots & x_1^n \ vdots &vdots &vdots &&vdots \ 1 & x_n & x_n^2 & cdots & x_n^n end{array} ight] left[ egin{array}{l} a_0\ a_1\ vdots\ a_n end{array} ight] = left[ egin{array}{l} f(x_0)\ f(x_1)\ vdots\ f(x_n) end{array} ight] ]

可以知道，满足插值条件的不超过 (n) 次的插值多项式是唯一的
同时有插值余项

[R_n(x)=f(x)-phi(x)=dfrac{f^{(n+1)}(xi)}{(n+1)!}omega_{n+1}(x) ]

式中

[omega_{n+1}(x)=prodlimits_{i=0}^{n}(x-x_i) ]

---

2

拉格朗日插值。

[l_i(x)=dfrac{omega_{n+1}(x)}{(x-x_i){omega'}_{n+1}(x_i)} ]

[L_n(x)=sumlimits_{i=0}^n f(x_i)l_i(x) ]

其中 (omega'_{n+1}(x_i)=prodlimits_{j=0\j e i}^{n}(x_i-x_j))
有一道经典例题叫做证明拉格朗日基函数的和为一。
有两种方法，第一种方式：因为拉格朗日基函数只与 (x) 有关，所以任意选一个简单的 (f) 就可以证明
第二种方式：因为拉格朗日基函数的和是个不超过 (n) 次的多项式，并且在 (n+1) 个点处值为 (1) 所以是常函数

反插值法：……。
用的时候注意必须要满足单调性条件。

---

3

牛顿插值法：
不难得知 (L_n(x)-L_{n-1}(x)=Aomega_n(x)) 其中 (A) 为常数，显然就是 (L_n(x)) 的首项系数
所以 (A=sumlimits_{i=0}^ndfrac{f(x_i)}{{omega'}_{n+1}(x_i)}) 即差商 (f[x_0,x_1,cdots,x_n])

[f[x_a,cdots,x_b]=dfrac{f[x_a,cdots,x_{b-1}]-f[x_{a+1},cdots,x_{b}]}{x_a-x_b} ]

以及差分和牛顿向前插值公式，在此略过

---

4

带导数的插值问题，Hermite插值

如果带完全导数，那么分别设 (alpha_i(x),quad beta_i(x)) 两个 (2n+1) 次多项式
满足

[left{ egin{array}{lcl} alpha_i(x_j)=delta_{ij}, \ alpha'_i(x_j)=0. end{array} ight.qquad j=0,1,2,cdots,n ]

[left{ egin{array}{lcl} eta_i(x_j)=0, \ eta'_i(x_j)=delta_{ij}. end{array} ight.qquad j=0,1,2,cdots,n ]

(H_{2n+1}(x)=sumlimits_{i=0}^nf(x_i)alpha_i(x)+sumlimits_{i=0}^nf'(x_i)eta_i(x))
嗯，(alpha_i(x)=(A_ix+B_i){l_i}^2(x)=left[1+2(x_i-x)sumlimits_{k=0\k e i}^ndfrac{1}{x_i-x_k} ight]{l_i}^2(x))
(eta_i(x)=(x-x_i){l_i}^2(x)) 。。
可以证得满足带导数一共　(2n) 个插值条件的不超过 (2n+1) 次的多项式唯一。

带不完全导数的
例如

[left{ egin{array}{l} H_3(x_i)=f(x_i),quad i=0,1,2\ {H'}_3(x_0)=f'(x_0). end{array} ight.]

比较简单，如果只带一个的话可以直接设系数，求导解出
或者直接用带重节点的差商表。表中 (f[x_r,x_r]) （比如说例题就是 (f[x_0,x_0])）替换成 (f'(x_r))

---

5

分段插值

三次样条
（MATLAB）conds — End conditions：
'clamped' | 'complete' | 'not-a-knot' | 'periodic' | 'second' | 'variational'

clamped=complete：已知转角（边界一阶导）
second：已知弯矩（边界二阶导）
variational：即natural，自然边界条件
periodic：周期性边界条件（左右边界一阶导相等，二阶导相等）
not-a-knot：it requires that the third derivative of the spline is continuous at (x_0) and (x_{n-1})

求解过程：矩阵又大还多，不码了
进行一个书的搬

---

6

B-Spline

定义略

[B_{j,m}(x)=frac{x_j-x_{j-m-1}}{x_{j-1}-x_{j-m-1}}B_{j-1,m-1}(x)-frac{x-x_{j}}{x_j-x_{j-m}}B_{j,m-1}(x) ]

[B'_{j,m}(x)=mleft[dfrac{B_{j-1,m-1}(x)}{x_{j-1}-x_{j-m-1}}-dfrac{B_{j,m-1}(x)}{x_{j}-x_{j-m}} ight] ]

[BC=F ]

对于 (m=3) 即 cubic b-spline
(C=[c_1,cdots,c_{n+3}]^{ m T})
(F=[f'(x_0),f(x_0),f(x_1),cdots,f(x_n),f'(x_n)]^{ m T})
(B=left[ egin{array}{l} b'_1(x_0)&b'_2(x_0)&b'_3(x_0)&0&cdots&0&0&0\ b_1(x_0)&b_2(x_0)&b_3(x_0)&0&cdots&0&0&0\ 0&b_2(x_1)&b_3(x_1)&b_4(x_1)&cdots&0&0&0\ 0&0&b_3(x_2)&b_4(x_2)&cdots&0&0&0\ vdots&vdots&vdots&vdots&&vdots&vdots&vdots\ 0&0&0&0&cdots&b_{n+1}(x_n)&b_{n+2}(x_n)&b_{n+3}(x_n)\ 0&0&0&0&cdots&b'_{n+1}(x_n)&b'_{n+2}(x_n)&b'_{n+3}(x_n)\ end{array} ight])
里面 (b_k(x)=B_{k,3}(x))。(b')同理
求出系数 (c_1,cdots,c_{n+3})
得到 (3) 次样条插值函数：(s(x)=sumlimits_{k=1}^{n+3}c_kB_{k,3(x)})

补贴一张图