在数值分析 中,拉格朗日插值法 是以法国 18世纪数学家 约瑟夫·拉格朗日 命名的一种多项式插值 方法。许多实际问题中都用函数 来表示各结果之间某种内在联系或规律,而不少函数都只能通过繁复实验和多次观测来了解。而,如果对实践中的某个物理 量进行观测,在若干个不同的地方得到相应的观测值,拉格朗日插值法可以找到一个多项式 ,其恰好在各个观测的点取到观测到的值。上面这样的多项式就称为拉格朗日(插值)多项式 (Lagrange polynomial)。数学 上来说,拉格朗日插值法可以给出一个恰好穿过二维平面 上若干个已知点的多项式函数。拉格朗日插值法最早被英国 数学家爱德华·华林 于1779年发现[ 1] ,不久后(1783年)由莱昂哈德·欧拉 再次发现。1795年,拉格朗日在其著作《师范学校数学基础教程》中发表这个插值方法,从此他的名字就和这个方法联系在一起[ 2] 。
已知平面上4个点:(−9, 5) , (−4, 2) , (−1, −2) , (7, 9) ,拉格朗日多项式:L (x ) (黑色)穿过所有点。而每个基本多项式:y0 ℓ 0 (x ) , y1 ℓ 1 (x ) , y2 ℓ 2 (x ) 以及y3 ℓ 3 (x ) 各穿过对应的一点,并在其它的三个点的x 值上取零。
对于给定的若n+1 个点
(
x
0
,
y
0
)
,
(
x
1
,
y
1
)
,
…
,
(
x
n
,
y
n
)
{\displaystyle (x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n})}
,对应于它们的次数不超过n 的拉格朗日多项式
L
{\displaystyle \scriptstyle L}
只有一个。如果计入次数更高的多项式,则有无穷个,因为所有与
L
{\displaystyle \scriptstyle L}
相差
λ
(
x
−
x
0
)
(
x
−
x
1
)
…
(
x
−
x
n
)
{\displaystyle \lambda (x-x_{0})(x-x_{1})\ldots (x-x_{n})}
的多项式都满足条件。
对某个多项式函数 ,已知有给定的k + 1个取值点:
(
x
0
,
y
0
)
,
…
,
(
x
k
,
y
k
)
{\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k})}
其中
x
j
{\displaystyle x_{j}}
对应着自变量 的位置,而
y
j
{\displaystyle y_{j}}
对应着函数在这个位置的取值。
假设任意两个不同的x j 都互不相同,那么应用拉格朗日插值公式所得到的拉格朗日插值多项式 为:
L
(
x
)
:=
∑
j
=
0
k
y
j
ℓ
j
(
x
)
{\displaystyle L(x):=\sum _{j=0}^{k}y_{j}\ell _{j}(x)}
其中每个
ℓ
j
(
x
)
{\displaystyle \ell _{j}(x)}
为拉格朗日基本多项式 (或称插值基函数 ),其表达式为:
ℓ
j
(
x
)
:=
∏
i
=
0
,
i
≠
j
k
x
−
x
i
x
j
−
x
i
=
(
x
−
x
0
)
(
x
j
−
x
0
)
⋯
(
x
−
x
j
−
1
)
(
x
j
−
x
j
−
1
)
(
x
−
x
j
+
1
)
(
x
j
−
x
j
+
1
)
⋯
(
x
−
x
k
)
(
x
j
−
x
k
)
.
{\displaystyle \ell _{j}(x):=\prod _{i=0,\,i\neq j}^{k}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{k})}{(x_{j}-x_{k})}}.}
[ 3]
拉格朗日基本多项式
ℓ
j
(
x
)
{\displaystyle \ell _{j}(x)}
的特点是在
x
j
{\displaystyle x_{j}}
上取值为1 ,在其它的点
x
i
,
i
≠
j
{\displaystyle x_{i},\,i\neq j}
上取值为0 。
假设有某个二次多项式函数
f
{\displaystyle f}
,已知它在三个点上的取值为:
f
(
4
)
=
10
{\displaystyle f(4)=10}
f
(
5
)
=
5.25
{\displaystyle f(5)=5.25}
f
(
6
)
=
1
{\displaystyle f(6)=1}
要求
f
(
18
)
{\displaystyle f(18)}
的值。
首先写出每个拉格朗日基本多项式:
ℓ
0
(
x
)
=
(
x
−
5
)
(
4
−
5
)
⋅
(
x
−
6
)
(
4
−
6
)
{\displaystyle \ell _{0}(x)={\frac {(x-5)}{(4-5)}}\cdot {\frac {(x-6)}{(4-6)}}}
ℓ
1
(
x
)
=
(
x
−
4
)
(
5
−
4
)
⋅
(
x
−
6
)
(
5
−
6
)
{\displaystyle \ell _{1}(x)={\frac {(x-4)}{(5-4)}}\cdot {\frac {(x-6)}{(5-6)}}}
ℓ
2
(
x
)
=
(
x
−
4
)
(
6
−
4
)
⋅
(
x
−
5
)
(
6
−
5
)
{\displaystyle \ell _{2}(x)={\frac {(x-4)}{(6-4)}}\cdot {\frac {(x-5)}{(6-5)}}}
然后应用拉格朗日插值法,就可以得到
p
{\displaystyle p}
的表达式(
p
{\displaystyle p}
为函数
f
{\displaystyle f}
的插值函数):
p
(
x
)
=
f
(
4
)
ℓ
0
(
x
)
+
f
(
5
)
ℓ
1
(
x
)
+
f
(
6
)
ℓ
2
(
x
)
{\displaystyle p(x)=f(4)\ell _{0}(x)+f(5)\ell _{1}(x)+f(6)\ell _{2}(x)}
.
=
10
⋅
(
x
−
5
)
(
x
−
6
)
(
4
−
5
)
(
4
−
6
)
+
5.25
⋅
(
x
−
4
)
(
x
−
6
)
(
5
−
4
)
(
5
−
6
)
+
1
⋅
(
x
−
4
)
(
x
−
5
)
(
6
−
4
)
(
6
−
5
)
{\displaystyle .\,\,\,\,\,\,\,\,\,\,=10\cdot {\frac {(x-5)(x-6)}{(4-5)(4-6)}}+5.25\cdot {\frac {(x-4)(x-6)}{(5-4)(5-6)}}+1\cdot {\frac {(x-4)(x-5)}{(6-4)(6-5)}}}
.
=
1
4
(
x
2
−
28
x
+
136
)
{\displaystyle .\,\,\,\,\,\,\,\,\,\,={\frac {1}{4}}(x^{2}-28x+136)}
此时代入数值
18
{\displaystyle \ 18}
就可以求出所需之值:
f
(
18
)
=
p
(
18
)
=
−
11
{\displaystyle \ f(18)=p(18)=-11}
。
对于给定的k +1个点:
(
x
0
,
y
0
)
,
…
,
(
x
k
,
y
k
)
{\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k})}
,拉格朗日插值法的思路是找到一个在一点
x
j
{\displaystyle x_{j}}
取值为1 ,而在其他点取值都是0 的多项式
ℓ
j
(
x
)
{\displaystyle \ell _{j}(x)}
。这样,多项式
y
j
ℓ
j
(
x
)
{\displaystyle y_{j}\ell _{j}(x)}
在点
x
j
{\displaystyle x_{j}}
取值为
y
j
{\displaystyle y_{j}}
,而在其他点取值都是0 。而多项式
L
(
x
)
:=
∑
j
=
0
k
y
j
ℓ
j
(
x
)
{\displaystyle L(x):=\sum _{j=0}^{k}y_{j}\ell _{j}(x)}
就可以满足
L
(
x
j
)
=
∑
i
=
0
k
y
i
ℓ
i
(
x
j
)
=
0
+
0
+
⋯
+
y
j
+
⋯
+
0
=
y
j
{\displaystyle L(x_{j})=\sum _{i=0}^{k}y_{i}\ell _{i}(x_{j})=0+0+\cdots +y_{j}+\cdots +0=y_{j}}
在其它点取值为0 的多项式容易找到,例如:
(
x
−
x
0
)
⋯
(
x
−
x
j
−
1
)
(
x
−
x
j
+
1
)
⋯
(
x
−
x
k
)
{\displaystyle (x-x_{0})\cdots (x-x_{j-1})(x-x_{j+1})\cdots (x-x_{k})}
它在点
x
j
{\displaystyle x_{j}}
取值为:
(
x
j
−
x
0
)
⋯
(
x
j
−
x
j
−
1
)
(
x
j
−
x
j
+
1
)
⋯
(
x
j
−
x
k
)
{\displaystyle (x_{j}-x_{0})\cdots (x_{j}-x_{j-1})(x_{j}-x_{j+1})\cdots (x_{j}-x_{k})}
。由于已经假定
x
i
{\displaystyle x_{i}}
两两互不相同,因此上面的取值不等于0 。于是,将多项式除以这个取值,就得到一个满足“在
x
j
{\displaystyle x_{j}}
取值为1 ,而在其他点取值都是0 的多项式”:
ℓ
j
(
x
)
:=
∏
i
=
0
,
i
≠
j
k
x
−
x
i
x
j
−
x
i
=
(
x
−
x
0
)
(
x
j
−
x
0
)
⋯
(
x
−
x
j
−
1
)
(
x
j
−
x
j
−
1
)
(
x
−
x
j
+
1
)
(
x
j
−
x
j
+
1
)
⋯
(
x
−
x
k
)
(
x
j
−
x
k
)
{\displaystyle \ell _{j}(x):=\prod _{i=0,\,i\neq j}^{k}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{k})}{(x_{j}-x_{k})}}}
这就是拉格朗日基本多项式。
拉格朗日插值法中用到的拉格朗日基本多项式
ℓ
0
,
ℓ
1
,
⋯
,
ℓ
n
{\displaystyle \ell _{0},\ell _{1},\cdots ,\ell _{n}}
(由某一组
x
0
<
x
1
<
⋯
<
x
n
{\displaystyle x_{0}<x_{1}<\cdots <x_{n}}
确定)可以看做是由次数不超过n 的多项式所组成的线性空间 :
K
n
[
X
]
{\displaystyle \mathbb {K} _{n}[X]}
的一组基底 。首先,如果存在一组系数 :
λ
0
,
λ
1
,
⋯
,
λ
n
{\displaystyle \lambda _{0},\lambda _{1},\cdots ,\lambda _{n}}
使得,
P
=
λ
0
ℓ
0
+
λ
1
ℓ
1
+
⋯
+
λ
n
ℓ
n
=
0
{\displaystyle P=\lambda _{0}\ell _{0}+\lambda _{1}\ell _{1}+\cdots +\lambda _{n}\ell _{n}=0}
,
那么,一方面多项式P 是满足
P
(
x
0
)
=
λ
0
,
P
(
x
1
)
=
λ
1
,
⋯
,
P
(
x
n
)
=
λ
n
{\displaystyle P(x_{0})=\lambda _{0},P(x_{1})=\lambda _{1},\cdots ,P(x_{n})=\lambda _{n}}
的拉格朗日插值多项式,另一方面P 是零多项式,所以取值永远是0 。所以
λ
0
=
λ
1
=
⋯
=
λ
n
=
0
{\displaystyle \lambda _{0}=\lambda _{1}=\cdots =\lambda _{n}=0}
。
这证明了
ℓ
0
,
ℓ
1
,
⋯
,
ℓ
n
{\displaystyle \ell _{0},\ell _{1},\cdots ,\ell _{n}}
是线性无关 的。同时它一共包含n+1 个多项式,恰好等于
K
n
[
X
]
{\displaystyle \mathbb {K} _{n}[X]}
的维数。所以
ℓ
0
,
ℓ
1
,
⋯
,
ℓ
n
{\displaystyle \ell _{0},\ell _{1},\cdots ,\ell _{n}}
构成了
K
n
[
X
]
{\displaystyle \mathbb {K} _{n}[X]}
的一组基底。
拉格朗日基本多项式作为基底的好处是所有的多项式都是齐次的(都是n 次多项式)。
拉格朗日插值法的公式结构整齐紧凑,在理论分析中十分方便,然而在计算中,当插值点增加或减少一个时,所对应的基本多项式就需要全部重新计算,于是整个公式都会变化,非常繁琐[ 5] 。这时可以用重心拉格朗日插值法或牛顿插值法 来代替。此外,当插值点比较多的时候,拉格朗日插值多项式的次数可能会很高,因此具有数值不稳定 的特点,也就是说尽管在已知的几个点取到给定的数值,但在附近却会和“实际上”的值之间有很大的偏差(如右下图)[ 6] 。这类现象也被称为龙格现象 ,解决的办法是分段用较低次数的插值多项式。
E. Waring. Problems Concerning Interpolations. Philosophical Transactions of the Royal Society of London. 1779, 69 : 59–67.
(英文) E. Meijering. A chronology of interpolation: From ancient astronomy to modern signal and image processing, . Proceedings of the IEEE: 323.
(英文) Julius Orion Smith III. Lagrange_Interpolation . Center for Computer Research in Music and Acoustics (CCRMA), Stanford University . [2009-12-22 ] . (原始内容存档 于2009-06-28).
王兆清,李淑萍,唐炳涛. 一维重心型插值:公式、算法和应用. 山东建筑大学学报. 2007, 22 (5): 447–453.