函数插值
华中科技大学数值分析课程地址
插值方法
函数逼近问题：
有$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 若存在简单函数$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: 只能求解区间[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)$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
最小二乘拟合