函数插值
华中科技大学数值分析课程地址
插值方法
函数逼近问题：
有$y_i=f(x_i)(i=0,1,...,n)$，希望使用一个简单函数$p(x)$近似$f(x)$，使$p(x_i)=f(x_i)(i=1,2,...,n)$
通过已知的数据估计$f(x)$
插值法定义：
设函数$y=f(x)$在区间[a,b]上有定义，且$a<=x_0<x_1<...<x_n<=b$（无重合节点），已知点$x_0,x_1,...,x_n$上的值$y_0,y_1,...,y_n$
若存在简单函数$p(x)$，使 $$ p(x_i)=y_i,i=0,1,2...,n $$ 成立，就称$p(x)$$为$$f(x)$$的插值函数，点$$x_i$$称为插值节点，[a,b]称为插值区间
常用插值法：
多项式插值：P(x)为多项式函数
分段插值：P(x)为分段多项式函数
三角插值：P(x)为三角函数
......
插值多项式的存在唯一性：
满足$P(x_i)=y_i,i=0,1,...,n$，次数不超过n的插值多项式是唯一存在的
证明方法略，hint：范德蒙行列式
如何构造插值多项式：
待定系数法：
1.构造插值多项式$P(x)=a_0+a_1x+a_2x^2+...+a_nx^n$，构造时候注意唯一性条件，次数不能超过n
2.带入已知条件求解插值多项式的未知数
拉格朗日插值
待定系数法在线性方程组维数高时很难求解，其优点是基函数简单，缺点是方程组系数难以计算
拉格朗日插值法与待定系数法基函数不同
拉格朗日多项式：
为了解决方程组系数难以计算的问题，使方程组系数就等于$y_i$
求n次多项式$L_n(x)=y_0l_0(x)+y_1l_1(x)+...+y_nl_n(x)$
使得$L_n(x_i)=y_i，i=0,1,2,...,n$
条件：无重合节点
$l_i(x)$称为拉氏基函数，使得$l_i(x)$满足条件$l_i(x_j)=\delta_{ij}$时，满足$L_n(x_i)=y_i，i=0,1,2,...,n$
注：$\delta_{ij}=\begin{cases}0&\text{i$\neq$j}\\1&\text{i$=$j}\end{cases}$
$l_{i}(x)=\prod_{\substack{j \neq i \ j=0}}^{n} \frac{\left(x-x_{j}\right)}{\left(x_{i}-x_{j}\right)}$
$L_{n}(x)=\sum_{i=0}^{n} L_{i}(x) y_{i}$
注：拉格朗日基函数仅与插值节点有关而与函数无关
插值余项：
没听懂
$R_{n}(x)=\frac{f^{(n+1)}\left(\xi_{x}\right)}{(n+1) !} \prod_{i=0}^{n}\left(x-x_{i}\right)$
误差估计上界为：
$\frac{M_{n+1}}{(n+1) !} \prod_{i=0}^{n}\left|x-x_{i}\right|$
其中$\left|f^{(n+1)}(x)\right|<=M_{n+1}$
一般用估计上界来估计误差
拉格朗日插值法每新增或者减少一个节点，需要重新计算所有基函数$ l_k(x)$
为了解决这个问题，设计一种可以逐次生成插值多项式的算法，即为牛顿插值法
插商：
零阶差商
$$f(x)$$
一阶差商
$$f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j}(i\neq j,x_i\neq x_j)$$
二阶差商
$$f[x_i,x_j,x_k]=\frac{f[x_i,x_j]-f[x_j,x_k]}{x_i-x_k}(i\neq k)$$
...
k+1阶差商
$$\begin{aligned} f\left[x_{0}, \ldots, x_{k+1}\right] &=\frac{f\left[x_{0}, x_{1}, \ldots, x_{k}\right]-f\left[x_{1}, \ldots, x_{k}, x_{k+1}\right]}{x_{0}-x_{k+1}} \ &=\frac{f\left[x_{0}, \ldots, x_{k-1}, x_{k}\right]-f\left[x_{0}, \ldots, x_{k-1}, x_{k+1}\right]}{x_{k}-x_{k+1}} \end{aligned}$$
牛顿插值：
$N_n(x)=c_0+c_1(x-x_0)+c_2(x-x_0(x-x_1)+...+c_n(x-x_0)(x-x_1)...(x-x_n-1)$
$c_k=f[x_0,x_1,...,x_k]$
等距节点公式：
节点等距分布：$x_i=x_0+ih(i=0,...,n)$
函数逼近
一致逼近：$||f(x)-y(x)||\infty = \mathop{max}\limits{a\leq x\leq b}|f(x)-y(x)|$
平方逼近：$||f(x)-y(x)||_2^2=\int_a^b\rho(x)[f(x)-y(x)]^2dx$
Weierstrass逼近定理：闭区间上的连续函数可以用多项式一致逼近
内积空间
内积：$(f,g)=\int_a^b\rho(x)f(x)g(x)dx$$称为函数$$f(x)$$和$$g(x)$$在$$[a,b]$$上的内积，$$\rho(x)$$是$$[a,b]$上的权函数
内积空间的四条公理
满足内积定义的函数空间称为内积空间
范数：
$||f||_2=\sqrt{\int_a^b\rho(x)f^2(x)dx}+\sqrt{(f,f)}$
称为$f(x)$的欧式范数
定理：
Cauchy-Schwarz不等式$|(f,g)|\leq||f||_2||g||_2$
三角不等式$||f+g||_2\leq||f||_2+||g||_2$
平行四边形定律$||f+g||_2^2+||f-g||_2^2=2(||f||_2^2+||g||_2^2)$
正交函数族
线性无关函数族（与线性代数的线性无关类似）
判断函数族线性无关的充要条件：克莱姆行列式$G_{n-1}\neq 0$
函数的最佳平方逼近
求$a_k^*(k+0,1,...,n)$使
$$||f(x)-s^*(x)||2^2||f(x)-\sum\limits{k=1}^na_k^\phi_k(x)||2^2=\min\limits{s(x)\in\Phi}||f(x)-s(x)||_2^2$$
$f(x)$是要逼近的函数
法方程组：
$$\begin{bmatrix}(\phi_0，\phi_0)&(\phi_0,\phi_1)&\cdots&(\phi_0,\phi_n)\(\phi_1，\phi_0)&(\phi_1,\phi_1)&\cdots&(\phi_1,\phi_n)\\vdots&\vdots&\cdots&\vdots\(\phi_n，\phi_0)&(\phi_n,\phi_1)&\cdots&(\phi_n,\phi_n)\end{bmatrix}\begin{bmatrix}a_0\a_1\\vdots\a_n\end{bmatrix}=\begin{bmatrix}(\phi_0,y)\(\phi_1,y)\\vdots\(\phi_n,y)\end{bmatrix}$$
法方程组的系数矩阵希尔伯特阵(系数矩阵与基函数有关，并不是所有情况都能用希尔伯特阵，只适用于基函数为单项式函数的情况)：
$$H=\left[\begin{array}{cccc} 1 & \frac{1}{2} & \cdots & \frac{1}{n+1} \ \frac{1}{2} & \frac{1}{3} & \cdots & \frac{1}{n+2} \ \vdots & \vdots & & \vdots \ \frac{1}{n+1} & \frac{1}{n+2} & \cdots & \frac{1}{2 n+1} \end{array}\right]$$
求解过程：
先求法方程等号右边（求内积）
再带入法方程系数矩阵求解法方程
一个求最佳平方逼近的matlab demo:
function [A] = BSapproximation(f,ft)
%BSAPPROXIMATION 求最佳逼近，区间[0,1]，基函数为一次多项式
b1 = integral(f, 0, 1);
b2 = integral(ft, 0, 1);
H = [1,1/2;1/2,1/3];
B = [b1; b2];
A=mldivide(H,B);
end
只能求解区间[0,1]上的一次多项式最佳平方逼近，作为一个求解过程的示例
基函数为单项式函数${1,t,\cdots,t^{n-1}}$，此时系数矩阵为希尔伯特矩阵
f是要逼近的方程，ft是要逼近的方程*t，用于求解法方程等号右端项
最小二乘拟合
最佳平方逼近的离散版本
引入离散型内积
$\sum\limits_{i=1}^N\omega(x_i)f(x_i)g(x_i)$