当插值结点互异时，满足插值条件式 P n ( x i ) = y i P_n(x_i)=y_i Pn(xi)=yi 的n次插值多项式 p n ( x ) p_n(x) pn(x) 存在且唯一
说明：拉格朗日插值 和 Newton插值 的多项式是相同的多项式，只是形式上有所差异。
将相邻插值点连成线段。
对于两点
(
x
0
,
y
0
)
(x_0,y_0)
(x0,y0),
(
x
1
,
y
1
)
(x_1,y_1)
(x1,y1)线性插值：
L
(
x
)
=
x
−
x
1
x
0
−
x
1
y
0
+
x
−
x
0
x
1
−
x
0
y
1
L(x) = \frac{x-x_1}{x_0-x_1}y_0+\frac{x-x_0}{x_1-x_0}y_1
L(x)=x0−x1x−x1y0+x1−x0x−x0y1
∣ R ( x ) ∣ = ∣ f ( x ) − S 1 ( x ) ∣ ≤ h 2 8 M h = m a x a ≤ x ≤ b ∣ x i + 1 − x i ∣ , M = m a x a ≤ x ≤ b ∣ f ′ ′ ( x ) ∣ |R(x)|=|f(x)-S_1(x)|\le \frac{h^2}{8}M \\ \quad \\ h=\underset{a\le x\le b}{max}|x_{i+1}-x_i|\quad ,M=\underset{a\le x\le b}{max}|f''(x)| ∣R(x)∣=∣f(x)−S1(x)∣≤8h2Mh=a≤x≤bmax∣xi+1−xi∣,M=a≤x≤bmax∣f′′(x)∣
过相邻三点 ( 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)的抛物线
L 2 ( 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 0 ) ( x 2 − x 1 ) y 2 L_2(x) = \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_0)(x_2-x_1)}y_2 L2(x)=(x0−x1)(x0−x2)(x−x1)(x−x2)y0+(x1−x0)(x1−x2)(x−x0)(x−x2)y1+(x2−x0)(x2−x1)(x−x0)(x−x1)y2
考虑过
n
+
1
n+1
n+1 个点的插值多项式
L
n
(
x
)
=
∑
i
=
0
n
[
(
∏
j
=
0
,
j
≠
i
n
x
−
x
j
x
i
−
x
j
)
y
i
]
L_n(x) = \sum_{i=0}^{n} \left [ \left ( \prod_{j=0,j \ne i}^{n} \frac{x-x_j}{x_i-x_j}\right ) y_i \right ]
Ln(x)=i=0∑n⎣⎡⎝⎛j=0,j=i∏nxi−xjx−xj⎠⎞yi⎦⎤
或等价的简化写为
P
n
(
x
)
=
∑
j
=
0
n
y
j
ω
n
+
1
(
x
)
(
x
−
x
j
)
ω
n
+
1
′
(
x
j
)
,
n
>
0
ω
n
+
1
(
x
)
=
∏
i
=
0
n
(
x
−
x
i
)
P_{n}(x)=\sum_{j=0}^{n} y_{j} \frac{\omega_{n+1}(x)}{\left(x-x_{j}\right) \omega_{n+1}^{\prime}\left(x_{j}\right)}, n>0\\\omega_{n+1}(x)=\prod_{i=0}^{n}\left(x-x_{i}\right)
Pn(x)=j=0∑nyj(x−xj)ωn+1′(xj)ωn+1(x),n>0ωn+1(x)=i=0∏n(x−xi)
f ( x ) f(x) f(x)在 [ a , b ] [a,b] [a,b]内的n+1阶导数连续，记为 f ( x ) ∈ C n + 1 [ a , b ] f(x) \in C^{n+1}[a,b] f(x)∈Cn+1[a,b]
R n ( x ) = f ( x ) − L n ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ω n + 1 ( x ) 其 中 ： a < ξ < b R_{n}(x) = f(x)-L_{n}(x)=\frac{f^{(n+1)}(\xi)}{(n+1) !}\prod_{i=0}^{n}\left(x-x_{i}\right) =\frac{f^{(n+1)}(\xi)}{(n+1) !} \omega_{n+1}(x)\\ \quad \\其中： a<\xi<b Rn(x)=f(x)−Ln(x)=(n+1)!f(n+1)(ξ)i=0∏n(x−xi)=(n+1)!f(n+1)(ξ)ωn+1(x)其中：a<ξ<b
由余项定理可推出误差估计，如下。
∣ R n ( x ) ∣ ⩽ M ( n + 1 ) ! ∣ ∏ i = 0 n ( x − x i ) ∣ M = max a ⩽ x ⩽ b ∣ f ( n + 1 ) ( x ) ∣ \left|R_{n}(x)\right| \leqslant \frac{M}{(n+1) !}\left|\prod_{i=0}^{n}\left(x-x_{i}\right)\right| \\ \quad \\ M=\max _{a \leqslant x \leqslant b}\left|f^{(n+1)}(x)\right| ∣Rn(x)∣⩽(n+1)!M∣∣∣∣∣i=0∏n(x−xi)∣∣∣∣∣M=a⩽x⩽bmax∣∣∣f(n+1)(x)∣∣∣
f [ x 0 , x 1 , ⋯ , x n ] = f [ x 0 , x 1 , ⋯ , x n − 1 ] − f [ x 1 , x 2 , ⋯ , x n ] x 0 − x n f\left[x_{0}, x_{1}, \cdots, x_{n}\right] = \frac{f\left[x_{0}, x_{1}, \cdots, x_{n-1}\right]-f\left[x_{1}, x_{2}, \cdots, x_{n}\right]}{x_{0}-x_{n}} f[x0,x1,⋯,xn]=x0−xnf[x0,x1,⋯,xn−1]−f[x1,x2,⋯,xn]
N n ( x ) = f ( x 0 ) + f ( x 0 , x 1 ) ( x − x 0 ) + ⋯ + f ( x 0 , x 1 , ⋯ , x n ) ω n ( x ) ‾ N n ( x ) = N n − 1 ( x ) + f ( x 0 , x 1 , ⋯ , x n ) ∏ i = 0 n − 1 ( x − x i ) ‾ , x ∈ [ a , b ] N_{n}(x)=f\left(x_{0}\right)+f(x_{0}, x_{1})\left(x-x_{0}\right)+\cdots + \underline{ f(x_{0}, x_{1}, \cdots, x_{n}) \omega_{n}(x)} \\ \quad \\ N_{n}(x)=N_{n-1}(x)+\underline{f(x_{0}, x_{1}, \cdots, x_{n}) \prod_{i=0}^{n-1}\left(x-x_{i}\right)}, \quad x \in[a, b] Nn(x)=f(x0)+f(x0,x1)(x−x0)+⋯+f(x0,x1,⋯,xn)ωn(x)Nn(x)=Nn−1(x)+f(x0,x1,⋯,xn)i=0∏n−1(x−xi),x∈[a,b]
由递推关系
f
[
x
0
,
x
1
,
⋯
,
x
n
]
=
f
[
x
0
,
x
1
,
⋯
,
x
n
−
1
]
−
f
[
x
1
,
x
2
,
⋯
,
x
n
]
x
0
−
x
n
f\left[x_{0}, x_{1}, \cdots, x_{n}\right] = \frac{f\left[x_{0}, x_{1}, \cdots, x_{n-1}\right]-f\left[x_{1}, x_{2}, \cdots, x_{n}\right]}{x_{0}-x_{n}}
f[x0,x1,⋯,xn]=x0−xnf[x0,x1,⋯,xn−1]−f[x1,x2,⋯,xn]
可依次得到
f
(
x
0
)
f
(
x
1
)
f
[
x
0
,
x
1
]
f
(
x
2
)
f
[
x
1
,
x
2
]
f
[
x
0
,
x
1
,
x
2
]
⋮
⋮
⋮
f
(
x
n
)
f
[
x
n
−
1
,
x
n
]
f
[
x
n
−
2
,
x
n
−
1
,
x
n
]
⋯
f
[
x
0
,
,
x
1
,
⋯
,
x
n
]
\begin{array}{l} {\color{Red}f\left(x_{0}\right)} \\ f\left(x_{1}\right) \quad \quad {\color{Red}f\left[x_{0}, x_{1}\right]} \\ f\left(x_{2}\right) \quad \quad f\left[x_{1}, x_{2}\right] \quad \quad {\color{Red}f\left[x_{0}, x_{1}, x_{2}\right] } \\ \quad \vdots \quad \quad \quad \quad \quad \vdots \quad \quad \quad \quad \quad \quad\quad \vdots \\ f\left(x_{n}\right) \quad \quad f\left[x_{n-1}, x_{n}\right] \quad \quad f\left[x_{n-2}, x_{n-1}, x_{n}\right] \cdots {\color{Red}f\left[x_{0}, ,x_1,\cdots, x_{n}\right]} \end{array}
f(x0)f(x1)f[x0,x1]f(x2)f[x1,x2]f[x0,x1,x2]⋮⋮⋮f(xn)f[xn−1,xn]f[xn−2,xn−1,xn]⋯f[x0,,x1,⋯,xn]
红色部分即为Newton插值多项式需要的参数
由 插值多项式的存在唯一性定理 可知：Newton插值误差与Lagrange插值误差完全一样。为：
R
n
(
x
)
=
f
(
x
)
−
L
n
(
x
)
=
f
(
n
+
1
)
(
ξ
)
(
n
+
1
)
!
∏
i
=
0
n
(
x
−
x
i
)
=
f
(
n
+
1
)
(
ξ
)
(
n
+
1
)
!
ω
n
+
1
(
x
)
其
中
：
a
<
ξ
<
b
R_{n}(x) = f(x)-L_{n}(x)=\frac{f^{(n+1)}(\xi)}{(n+1) !}\prod_{i=0}^{n}\left(x-x_{i}\right) =\frac{f^{(n+1)}(\xi)}{(n+1) !} \omega_{n+1}(x)\\ \quad \\其中： a<\xi<b
Rn(x)=f(x)−Ln(x)=(n+1)!f(n+1)(ξ)i=0∏n(x−xi)=(n+1)!f(n+1)(ξ)ωn+1(x)其中：a<ξ<b
许多问题不仅需要函数插值节点的函数值相同，还需要各节点上的导数值也相同，满足这些条件的插值，称为Hermite插值。
每两点间做一次插值。
H ( x ) = h 0 ( x ) y 0 + h 1 ( x ) y 1 + H 0 ( x ) y 0 ′ + H 1 ( x ) y 1 ′ H(x)=h_0(x)y_0+h_1(x)y_1+H_0(x)y'_0+H_1(x)y'_1 H(x)=h0(x)y0+h1(x)y1+H0(x)y0′+H1(x)y1′
h 0 ( x ) = ( 1 + 2 x − x 0 x 1 − x 0 ) ( x − x 1 x 0 − x 1 ) 2 h 1 ( x ) = ( 1 + 2 x − x 1 x 0 − x 1 ) ( x − x 0 x 1 − x 0 ) 2 H 0 ( x ) = ( x − x 0 ) ( x − x 1 x 0 − x 1 ) 2 η 0 ( x ) = ( x − x 1 ) ( x − x 0 x 1 − x 0 ) 2 \begin{array}{l} h_{0}(x)=\left(1+2 \frac{x-x_{0}}{x_{1}-x_{0}}\right)\left(\frac{x-x_{1}}{x_{0}-x_{1}}\right)^{2} \\ h_{1}(x)=\left(1+2 \frac{x-x_{1}}{x_{0}-x_{1}}\right)\left(\frac{x-x_{0}}{x_{1}-x_{0}}\right)^{2} \\ H_{0}(x)=\left(x-x_{0}\right)\left(\frac{x-x_{1}}{x_{0}-x_{1}}\right)^{2} \\ \eta_{0}(x)=\left(x-x_{1}\right)\left(\frac{x-x_{0}}{x_{1}-x_{0}}\right)^{2} \end{array} h0(x)=(1+2x1−x0x−x0)(x0−x1x−x1)2h1(x)=(1+2x0−x1x−x1)(x1−x0x−x0)2H0(x)=(x−x0)(x0−x1x−x1)2η0(x)=(x−x1)(x1−x0x−x0)2
在手算中（考试中）使用待定系数法是较为简单的计算方式
H ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 H(x)=a_0+a_1x+a_2x^2+a_3x^3 H(x)=a0+a1x+a2x2+a3x3
H
(
0
)
,
H
′
(
0
)
,
H
(
1
)
,
H
′
(
1
)
H(0),H'(0),H(1),H'(1)
H(0),H′(0),H(1),H′(1)
得到系数
R ( x ) = f ( 4 ) ( ξ ) 4 ! ( x − x 0 ) 2 ( x − x 1 ) 2 R(x)=\frac{f^{(4)}(\xi)}{4!}(x-x_0)^2(x-x_1)^2 R(x)=4!f(4)(ξ)(x−x0)2(x−x1)2
∣ R ( x ) ∣ = ∣ f ( x ) − S 3 ( x ) ∣ ≤ h 4 384 M 4 h = m a x 0 ≤ i ≤ n − 1 ∣ x i + 1 − x i ∣ , M 4 = m a x a ≤ x ≤ b ∣ f ( 4 ) ( x ) ∣ |R(x)| = |f(x)-S_3(x)|\le \frac{h^4}{384}M_4 \\ \quad \\ h=\underset{0\le i\le n-1}{max}|x_{i+1}-x_i|,M_4=\underset{a\le x\le b}{max}|f^{(4)}(x)| ∣R(x)∣=∣f(x)−S3(x)∣≤384h4M4h=0≤i≤n−1max∣xi+1−xi∣,M4=a≤x≤bmax∣f(4)(x)∣
在相邻两点 （ x i ， y i ） , （ x i + 1 ， y i + 1 ） （x_i，y_i）,（x_{i+1}，y_{i+1}） （xi，yi）,（xi+1，yi+1）构造三次多项式插值。
函数的值，以及一阶导数值，二阶导数值在该点连续。相比于Hermite插值多了二阶导数相同的条件。这在许多工程技术中解决了对函数插值光滑性有较高的计算。
计算
S
k
S_k
Sk（第k，k+1个点间的三次函数）需要
S
k
−
1
′
(
x
k
)
,
S
k
+
1
′
(
x
k
+
1
)
以
及
S
k
−
1
′
′
(
x
k
)
,
S
k
+
1
′
′
(
x
k
+
1
)
S'_{k-1}(x_k), S'_{k+1}(x_{k+1}) \\ 以及\\ S''_{k-1}(x_k), S''_{k+1}(x_{k+1})
Sk−1′(xk),Sk+1′(xk+1)以及Sk−1′′(xk),Sk+1′′(xk+1)
即需要这两点的一阶、二阶导数值确定。
若给定边界条件
S
′
(
x
0
)
=
f
0
′
,
S
′
(
x
n
)
=
f
n
′
S'(x_0)=f'_0,S'(x_n)=f'_n
S′(x0)=f0′,S′(xn)=fn′，
S
′
′
(
x
0
)
=
f
0
′
′
,
S
′
′
(
x
n
)
=
f
n
′
′
S''(x_0)=f''_0,S''(x_n)=f''_n
S′′(x0)=f0′′,S′′(xn)=fn′′
则三次样条插值是一个递归计算。
已知：
设：
求得
条件：
m
0
=
f
0
′
m_0=f'_0
m0=f0′,
m
n
=
f
n
′
m_n=f'_n
mn=fn′
则有
(
2
μ
1
λ
2
2
μ
2
λ
3
2
μ
3
⋱
⋱
⋱
λ
n
−
2
2
μ
n
−
2
λ
n
−
1
2
)
(
m
1
m
2
⋮
m
n
−
2
m
n
−
1
)
=
(
d
1
−
λ
1
f
0
′
d
2
⋮
d
n
−
2
d
n
−
1
−
μ
n
−
1
y
n
′
)
\left(\begin{array}{ccccc} 2 & \mu_{1} & & & \\ \lambda_{2} & 2 & \mu_{2} & & \\ & \lambda_{3} & 2 & \mu_{3} & & \\ \\ & &\ddots & \ddots & \ddots & \\ \\ & & & \lambda_{n-2} & 2 & \mu_{n-2} \\ & & & &\lambda_{n-1} & 2 \end{array}\right)\left(\begin{array}{c} m_{1} \\ m_{2} \\ \\ \vdots \\ \\ m_{n-2} \\ m_{n-1} \end{array}\right)=\left(\begin{array}{c} d_{1}-\lambda_{1} f_{0}^{\prime} \\ d_{2} \\ \\ \vdots \\ \\ d_{n-2} \\ d_{n-1}-\mu_{n-1} y_{n}^{\prime} \end{array}\right)
⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛2λ2μ12λ3μ22⋱μ3⋱λn−2⋱2λn−1μn−22⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛m1m2⋮mn−2mn−1⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛d1−λ1f0′d2⋮dn−2dn−1−μn−1yn′⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞
用追赶法求得
m
i
,
i
=
1
,
2
,
3
,
⋯
,
n
−
1
m_i,i=1,2,3,\cdots, n-1
mi,i=1,2,3,⋯,n−1
可得
S
i
(
x
)
=
(
x
−
x
i
)
(
x
−
x
i
+
1
)
2
h
i
2
m
i
+
(
x
−
x
i
)
2
(
x
−
x
i
+
1
)
h
i
2
m
i
+
1
S_i(x) = \frac{(x-x_i)(x-x_{i+1})^2}{h_i^2}m_i+ \frac{(x-x_i)^2(x-x_{i+1})}{h_i^2}m_{i+1}
Si(x)=hi2(x−xi)(x−xi+1)2mi+hi2(x−xi)2(x−xi+1)mi+1
条件：
S
′
′
(
x
0
)
=
f
0
′
′
，
S
′
′
(
x
n
)
=
f
n
′
′
S''(x_0)=f''_0，S''(x_n)=f''_n
S′′(x0)=f0′′，S′′(xn)=fn′′
则有：
(
2
1
λ
1
2
μ
1
λ
2
2
μ
2
⋱
⋱
⋱
λ
n
−
1
2
μ
n
−
1
1
2
)
(
m
0
m
1
⋮
m
n
−
1
m
n
)
=
(
d
0
d
1
⋮
d
n
−
1
d
n
)
\left(\begin{array}{ccccc} 2 & 1 & & & \\ \lambda_{1} & 2 & \mu_{1} & & \\ & \lambda_{2} & 2 & \mu_{2} & & \\ \\ & &\ddots & \ddots & \ddots & \\ \\ & & & \lambda_{n-1} & 2 & \mu_{n-1} \\ & & & &1 & 2 \end{array}\right)\left(\begin{array}{c} m_{0} \\ m_{1} \\ \\ \vdots \\ \\ m_{n-1} \\ m_{n} \end{array}\right)=\left(\begin{array}{c} d_{0}\\ d_{1} \\ \\ \vdots \\ \\ d_{n-1} \\ d_{n} \end{array}\right)
⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛2λ112λ2μ12⋱μ2⋱λn−1⋱21μn−12⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛m0m1⋮mn−1mn⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛d0d1⋮dn−1dn⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞
求得
m
i
m_i
mi
(
(
φ
0
,
φ
0
)
(
φ
0
,
φ
1
)
⋯
(
φ
0
,
φ
m
)
(
φ
1
,
φ
0
)
(
φ
1
,
φ
1
)
⋯
(
φ
1
,
φ
m
)
⋮
⋮
⋮
(
φ
m
,
φ
0
)
(
φ
m
,
φ
1
)
⋯
(
φ
m
,
φ
m
)
)
(
a
0
a
1
⋮
a
m
)
=
(
d
0
d
1
⋮
d
m
)
\left(\begin{array}{cccc} \left(\varphi_{0}, \varphi_{0}\right) & \left(\varphi_{0}, \varphi_{1}\right) & \cdots & \left(\varphi_{0}, \varphi_{m}\right) \\ \left(\varphi_{1}, \varphi_{0}\right) & \left(\varphi_{1}, \varphi_{1}\right) & \cdots & \left(\varphi_{1}, \varphi_{m}\right) \\ \vdots & \vdots & & \vdots \\ \left(\varphi_{m}, \varphi_{0}\right) & \left(\varphi_{m}, \varphi_{1}\right) & \cdots & \left(\varphi_{m}, \varphi_{m}\right) \end{array}\right)\left(\begin{array}{c} a_{0} \\ a_{1} \\ \vdots \\ a_{m} \end{array}\right)=\left(\begin{array}{c} d_{0} \\ d_{1} \\ \vdots \\ d_{m} \end{array}\right)
⎝⎜⎜⎜⎛(φ0,φ0)(φ1,φ0)⋮(φm,φ0)(φ0,φ1)(φ1,φ1)⋮(φm,φ1)⋯⋯⋯(φ0,φm)(φ1,φm)⋮(φm,φm)⎠⎟⎟⎟⎞⎝⎜⎜⎜⎛a0a1⋮am⎠⎟⎟⎟⎞=⎝⎜⎜⎜⎛d0d1⋮dm⎠⎟⎟⎟⎞
(
φ
j
,
φ
k
)
=
∑
i
=
0
n
φ
j
(
x
i
)
φ
k
(
x
i
)
,
d
k
=
∑
i
=
0
n
y
i
φ
k
(
x
i
)
\left(\varphi_{j}, \varphi_{k}\right)=\sum_{i=0}^{n} \varphi_{j}\left(x_{i}\right) \varphi_{k}\left(x_{i}\right), \quad d_{k}=\sum_{i=0}^{n} y_{i} \varphi_{k}\left(x_{i}\right)
(φj,φk)=i=0∑nφj(xi)φk(xi),dk=i=0∑nyiφk(xi)
当 φ i = x i \varphi_i = x^i φi=xi时称为多项式拟合。
若设拟合函数为线性方程 p ( x ) = a 0 + a 1 x p(x)=a_0+a_1x p(x)=a0+a1x,则只有 φ 0 , φ 1 \varphi_0,\varphi_1 φ0,φ1,求解 a 0 , a 1 a_0,a_1 a0,a1。
当n较大时，拟合所求法方程一般为病态方程组，故需要进行正交多项式拟合。
这里就不叙述相关内容，可自行查阅。
