文章目录

• 目的
• 概念
• 分类
• • 一般插值多项式
  • 拉格朗日插值法
  • 分段线性插值
  • • 分段二次插值
  • 牛顿插值法
  • 埃尔米特插值原理
  • 分段三次埃米尔特插值
  • 三次样条插值

目的

比赛中常常需要根据已知的函数点进行数据、模型的处理和分析，而有时候现有的数据是极少的，不足以支撑分析的进行，这时就可以使用一些方法“模拟产生”一些新的但又比较靠谱的值，这就是插值的作用。

概念

设函数 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​+a1​x+…+an​xn
• 分段插值
  • 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​+a1​x+a2​x2+…+an​xn​，使得 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​−x1​x−x1​​y0​+x1​−x0​x−x0​​y1​​

• 三个点 ( 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​−x0​f(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​−x0​f[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​),​

具体见代码

注意：实际比赛中多用分段三次和三次样条