函数插值

华中科技大学数值分析课程地址

插值方法

函数逼近问题：

有$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:

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)$