文章目录
目的
比赛中常常需要根据已知的函数点进行数据、模型的处理和分析，而有时候现有的数据是极少的，不足以支撑分析的进行，这时就可以使用一些方法“模拟产生”一些新的但又比较靠谱的值，这就是插值的作用。
概念
设函数 y = f ( x ) y=f(x) y=f(x)在区间 [ a , b ] [a,b] [a,b]上有定义，且已知在点 a ≤ x 0 < x 1 < … < x n ≤ b a≤x_0<x_1<…<x_n≤b a≤x0<x1<…<xn≤b上的值分别为 y 0 , y 1 , … , y n y_0,y_1,…,y_n y0,y1,…,yn，若存在一简单函数 P ( x ) P(x) P(x)使 P ( x i ) = y i ( i = 0 , 1 , 2 , … , n ) P(x_i)=y_i(i=0,1,2,…,n) P(xi)=yi(i=0,1,2,…,n)则称 P ( x ) P(x) P(x)为 f ( x ) f(x) f(x)的插值函数，点 x 0 , x 1 , … , x n x_0,x_1,…,x_n x0,x1,…,xn称为插值节点，包含插值节点的区间 [ a , b ] [a,b] [a,b]称为插值区间，求插值函数 P ( x ) P(x) P(x)的方法称为插值法
分类
- 插值多项式
- P ( x ) P(x) P(x)是次数不超过 n n n的代数多项式，即 P ( x ) = a 0 + a 1 x + … + a n x n P(x)=a_0+a_1x+…+a_nx^n P(x)=a0+a1x+…+anxn
- 分段插值
- P ( x ) P(x) P(x)为分段多项式
- 三角插值
一般插值多项式
定理：设有 n + 1 n+1 n+1个互不相同的节点 ( x i , y i ) , ( i = 0 , 1 , 2 … , n ) (x_i,y_i),(i=0,1,2…,n) (xi,yi),(i=0,1,2…,n)，则存在唯一的多项式 L n ( x ) = a 0 + a 1 x + a 2 x 2 + … + a n x n L_n(x)=a_0+a_1x+a_2x^2+…+a_nx^n Ln(x)=a0+a1x+a2x2+…+anxn，使得 L n ( x j ) = y j , ( j = 0 , 1 , 2 … , n ) L_n(x_j)=y_j,(j=0,1,2…,n) Ln(xj)=yj,(j=0,1,2…,n)
注意：①只要 n + 1 n+1 n+1个节点互异，满足上述插值条件的多项式是唯一存在的；②如果不限制多项式次数，插值多项式并不唯一
拉格朗日插值法
-
两个点 ( x 0 , y 0 ) , ( x 1 , y 1 ) (x_0,y_0),(x_1,y_1) (x0,y0),(x1,y1)
- f ( x ) = x − x 1 x 0 − x 1 y 0 + x − x 0 x 1 − x 0 y 1 f(x)=\large \frac {x-x_1}{x_0-x_1}y_0+\frac {x-x_0}{x_1-x_0}y_1 f(x)=x0−x1x−x1y0+x1−x0x−x0y1
-
三个点 ( x 0 , y 0 ) , ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_0,y_0),(x_1,y_1),(x_2,y_2) (x0,y0),(x1,y1),(x2,y2)
- f ( x ) = ( x − x 1 ) ( x − x 2 ) ( x 0 − x 1 ) ( x 0 − x 2 ) y 0 + ( x − x 0 ) ( x − x 2 ) ( x 1 − x 0 ) ( x 1 − x 2 ) y 1 + ( x − x 0 ) ( x − x 1 ) ( x 2 − x 1 ) ( x 2 − x 1 ) y 2 f(x)=\large \frac {(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}y_0+\frac {(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}y_1+\frac {(x-x_0)(x-x_1)}{(x_2-x_1)(x_2-x_1)}y_2 f(x)=(x0−x1)(x0−x2)(x−x1)(x−x2)y0+(x1−x0)(x1−x2)(x−x0)(x−x2)y1+(x2−x1)(x2−x1)(x−x0)(x−x1)y2
-
四个点 ( x 0 , y 0 ) , ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x 3 , y 3 ) (x_0,y_0),(x_1,y_1),(x_2,y_2),(x_3,y_3) (x0,y0),(x1,y1),(x2,y2),(x3,y3)
- f ( x ) = ( x − x 1 ) ( x − x 2 ) ( x − x 3 ) ( x 0 − x 1 ) ( x 0 − x 2 ) ( x 0 − x 3 ) y 0 + ( x − x 0 ) ( x − x 2 ) ( x − x 3 ) ( x 1 − x 0 ) ( x 1 − x 2 ) ( x 0 − x 3 ) y 1 + ( x − x 0 ) ( x − x 1 ) ( x − x 3 ) ( x 2 − x 1 ) ( x 2 − x 1 ) ( x 0 − x 3 ) y 2 f(x)=\large \frac {(x-x_1)(x-x_2)(x-x_3)}{(x_0-x_1)(x_0-x_2)(x_0-x_3)}y_0+\frac {(x-x_0)(x-x_2)(x-x_3)}{(x_1-x_0)(x_1-x_2)(x_0-x_3)}y_1+\frac {(x-x_0)(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_1)(x_0-x_3)}y_2 f(x)=(x0−x1)(x0−x2)(x0−x3)(x−x1)(x−x2)(x−x3)y0+(x1−x0)(x1−x2)(x0−x3)(x−x0)(x−x2)(x−x3)y1+(x2−x1)(x2−x1)(x0−x3)(x−x0)(x−x1)(x−x3)y2
分段线性插值
分段二次插值
牛顿插值法
定义 f [ x 0 , x k ] = f ( x k ) − f ( x 0 ) x k − x 0 f[x_0,x_k]=\Large \frac {f(x_k)-f(x_0)}{x_k-x_0} f[x0,xk]=xk−x0f(xk)−f(x0)为函数 f ( x ) f(x) f(x)关于点 x 0 , x k x_0,x_k x0,xk的一阶差商， f [ x 0 , x 1 , x 2 ] = f [ x 1 , x 2 ] − f [ x 0 , x 1 ] x 2 − x 0 f[x_0,x_1,x_2]=\Large \frac {f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0} f[x0,x1,x2]=x2−x0f[x1,x2]−f[x0,x1]为二阶差商
牛顿插值： f ( x ) = f ( x 0 ) + f [ x 0 , x 1 ] ∗ ( x − x 0 ) + f [ x 0 , x 1 , x 2 ] ∗ ( x − x 0 ) ∗ ( x − x 1 ) + … + f [ x 0 , x 1 , … x n − 2 , x n − 1 ] ∗ ( x − x 0 ) ∗ ( x − x 1 ) ∗ … ( x − x n − 3 ) ( x − x n − 2 ) + f [ x 0 , x 1 , … x n − 1 , x n ] ∗ ( x − x 0 ) ∗ ( x − x 1 ) ∗ … ( x − x n − 2 ) ( x − x n − 1 ) f(x)=f(x_0)+f[x_0,x_1]*(x-x_0)+f[x_0,x_1,x_2]*(x-x_0)*(x-x_1)+…+f[x_0,x_1,…x_{n-2},x_{n-1}]*(x-x_0)*(x-x_1)*…(x-x_{n-3})(x-x_{n-2})+f[x_0,x_1,…x_{n-1},x_n]*(x-x_0)*(x-x_1)*…(x-x_{n-2})(x-x_{n-1}) f(x)=f(x0)+f[x0,x1]∗(x−x0)+f[x0,x1,x2]∗(x−x0)∗(x−x1)+…+f[x0,x1,…xn−2,xn−1]∗(x−x0)∗(x−x1)∗…(x−xn−3)(x−xn−2)+f[x0,x1,…xn−1,xn]∗(x−x0)∗(x−x1)∗…(x−xn−2)(x−xn−1)
埃尔米特插值原理
设函数 f ( x ) f(x) f(x)在区间 [ a , b ] [a,b] [a,b]上有 n + 1 n+1 n+1个互异节点 a = x 0 < x 1 < x 2 < … < x n = b a=x_0<x_1<x_2<…<x_n=b a=x0<x1<x2<…<xn=b，定义在 [ a , b ] [a,b] [a,b]上函数 f ( x ) f(x) f(x)在节点上满足 f ( x i ) = y i , f ′ ( x i ) = y i ′ f(x_i)=y_i,f'(x_i)=y_i' f(xi)=yi,f′(xi)=yi′可唯一确定一个次数不超过 2 n + 1 2n+1 2n+1的多项式 H 2 n + 1 ( x ) = H ( x ) H_{2n+1}(x)=H(x) H2n+1(x)=H(x)满足 H ( x j ) = y j , H ′ ( x j ) = m j , ( j = 0 , 1 , … , n ) H(x_j)=y_j,H'(x_j)=m_j,(j=0,1,…,n) H(xj)=yj,H′(xj)=mj,(j=0,1,…,n)，其余项为 R ( x ) = f ( x ) − H ( x ) = f ( 2 n + 2 ) ( ξ ) ( 2 n + 2 ) ! ω 2 n + 2 ( x ) R(x)=f(x)-H(x)=\frac {f^{(2n+2)}(\xi)}{(2n+2)!}\omega_{2n+2}(x) R(x)=f(x)−H(x)=(2n+2)!f(2n+2)(ξ)ω2n+2(x)
- 不但要求在节点上的函数值相等，而且还要求对应的导数值也相等
分段三次埃米尔特插值
见代码
三次样条插值
除了满足基本插值条件 S ( x i ) = f i S(x_i)=f_i S(xi)=fi还应该满足
S ( x ) = { S 0 ( x ) , x ∈ [ x 0 , x 1 ] S 1 ( x ) , x ∈ [ x 1 , x 2 ] ⋮ S n − 1 ( x ) , x ∈ [ x n − 1 , x n ] S(x)=\begin{cases}{S_0(x),x∈[x_0,x_1]}\\S_1(x),x∈[x_1,x_2]\\{\vdots }\\{S_{n-1}(x),x∈[x_{n-1},x_n]}\end{cases} S(x)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧S0(x),x∈[x0,x1]S1(x),x∈[x1,x2]⋮Sn−1(x),x∈[xn−1,xn]
并且满足
{ S i − 1 ( x i ) = S i ( x i ) , S i − 1 ′ ( x i ) = S i ′ ( x i ) , S i − 1 ′ ′ ( x i ) = S i ′ ′ ( x i ) , \begin{cases}{S_{i-1}(x_i)=S_i(x_i),}\\{S'_{i-1}(x_i)=S'_i(x_i),}\\{S''_{i-1}(x_i)=S''_i(x_i),} \end{cases} ⎩⎪⎨⎪⎧Si−1(xi)=Si(xi),Si−1′(xi)=Si′(xi),Si−1′′(xi)=Si′′(xi),
具体见代码
注意：实际比赛中多用分段三次和三次样条