多项式插值

多项式逼近

给定点对$(x_i,y_i),i=1,\cdots,n$,找到次数尽可能低的多项式P满足

$P(x_i)=y_i，i=1,\cdots,n$

这样的问题称为插值多项式

Prob:

• existence
• uniqueness
• How to caculate

唯一性的证明是比较明显的，若不然，存在满足条件的次数不超过n的多项式$P,Q$
则

$\delta = P-Q$

有n+1个零点，则$\delta$为零多项式

存在性的证明
由归纳法，设结论在k-1时已成立，对k的情况
已有多项式$P_k(x_j)=y_j,j=1,\cdots ,n$
令

$P_k=P_{k-1}+c\Pi_{i=1}^{k-1}(x-x_i)$

调整c使得 $P_k(x_k)=y_k$即可！

ps: 以上被称为一个校准的过程
ps：我们可以得到

$P_n=\sum_{i=0}^nc_i\Pi_{j=0}^{i-1}(x-x_j)$

ps：直接进行计算，算法复杂度为$\frac{1}{2}n^2$量级

秦九邵算法(针对于某一个固定的x求值，一个漂亮的递推)

拉格朗日插值

我们可以改写多项式为

$P_n=\sum_{i=0}^{n}y_il_i$

其中

$l_i(x_j)=\delta_{ij}$

容易得到

$l_i(x)=\Pi_{j=0,j\ne i}^{n}\frac{x-x_j}{x_i-x_j}$

其他的插值的方式

误差的估计

Theorem 2.3 :设$x_0,\cdots,x_n\in [a,b]$,有$\xi_x\in(a,b)$满足

$f-P=\frac{1}{(n+1)!}f^{n+1}(\xi_x)\Pi_{i=0}^{n}(x-x_i)$

对不同于$x_i$的$x$，设$\omega(t)=\Pi_{i=0}^{n}(t-x_i),\phi(t)=f-P-\lambda\omega$
取$\lambda$满足

$\phi(x)=0$

则$\phi(t)\in C^{n+1}(a,b)有n+2个零点$，由Rolle定理,$\phi^{n+1}$至少有1个零点$\xi_x\in(a,b)$

Chebyshev多项式

Theorem 2.5
对$x\in [-1,1]$,有Chebyshev多项式

$T_n(x)=\cos(n\cos^{-1}x),n\ge 0$

$T_n(x)$有如下递推

$T_0(x)=1,T_1(x)=x\\ T_{n+1}=2xT_n(x)-T_{n-1}(x),n\ge 1$

Properties

Theorem 2.6
设$p$是首一的n次多项式，则有

$|p|_{\infty}= max_{-1\le x \le x}|p(x)|\ge 2^{1-n}$

(进行一个证明的贴)

---

3.10

---

样条插值

将区间分成$t_0\le t_1 \le,\cdots\le t_n$,

满足

• 在$[t_{i-1},t_i]$上，$S$为一个次数不超过k的多项式
• $S\in C^{k-1}(t_0,t_n)$

三次样条插值

然后利用

$S^{'}_i(t_{i-1})=S^{'}_{i-1}(t_{i-1})$

得到

$h_{i-1}z_{i-1}+2(h_{i-1}+h_{i})z_i+h_iz_{i+1}=\frac{6}{h_i}(y_{i+1}-y_i)-\frac{6}{h_{i-1}}(y_{i}-y_{i-1})$

Algotithm

theorem
设$f\in C^2[a,b],a=t_0\le \cdots \le t_n =b$,$S$为插值$f$的自然样条函数，则

$\int_a^b(S^{''}(x))^2dx\le \int_a^b(f^{''}(x))^2dx$

证明：设$g=f-S，g(t_i)=0,0\le i\le n$,我们有

$\int_a^b(f^{''}(x))^2dx=\int_a^b(S^{''}(x))^2dx+\int_a^b(g^{''}(x))^2dx+\int_a^b((S^{''}g^{''}))^2dx$

下面说明

$\int_a^b((S^{''}g^{''}))^2dx\ge 0$

(以后再补叭 偷个懒)

追赶法

解微分方程

$-\frac{d^2u}{dx^2}=f\\ u(0)=u(1)=0$

差分法
取节点$0=x_0\le x_1\le\cdots\le x_{n+1}=1,h_i=x_i-x_{i-1}$
近似

$-\frac{u_{i-1}-2u_i+u_{i+1}}{h^2}=f(x_i)\\ u_0=u_{n+1}=0$

definition:三对角矩阵

矩阵分解

由条件(1)(2)(3)
知满足

$\beta_i=b_i,i=2,\cdots,n\\ \alpha_1=a_1, \alpha_i\gamma=c_i,i=1,\cdots,n\\ \beta_i\gamma_{i-1}+\alpha_{i}=a_i,i=2,\cdots,n$

的解是存在的！