多项式插值与点值方法

问题与唯一性

给定 $n+1$ 个互异节点 $x_0,\ldots,x_n$ 及指定值 $y_0,\ldots,y_n$ ，希望找次数不超过 $n$ 的多项式 $P$ ，满足 $P(x_i)=y_i$ 。节点和值可以为实数，也可以为复数。

若 $P,Q$ 都符合要求，则 $P-Q$ 的次数至多为 $n$ ，却在这 $n+1$ 个节点为零，故恒为零。这证明至多有一个解；下面还要构造解，才能证明存在。不要把“至多一个”和“存在唯一一个”混为一谈。

拉格朗日插值公式及证明

对 $i=0,\ldots,n$ ，定义基多项式

L_i(x)=\prod_{\substack{0\le j\le n\\j\ne i}}\frac{x-x_j}{x_i-x_j}.

所有分母非零，因为节点互异。 $L_i$ 在自己的节点 $x_i$ 取值 $1$ ，在其他节点取值 $0$ 。因此

P(x)=\sum_{i=0}^n y_iL_i(x)

次数不超过 $n$ ，且代入 $x_k$ 时只有第 $k$ 项保留下来，得到 $P(x_k)=y_k$ 。结合唯一性，这就是所求多项式。 $n=0$ 时空乘积取 $1$ ，公式给出常数 $y_0$ 。

插值结果的实际次数可能小于 $n$ ，例如全部 $y_i$ 相同。节点重复时公式没有意义：重复的相同条件不增加信息，重复节点给出不同数值则根本无解。

不展开全部系数也能求值

已知次数不超过二的 $P$ 满足 $P(0)=1,P(1)=2,P(2)=5$ 。直接插值得

P(x)=\frac{(x-1)(x-2)}2-2x(x-2)+\frac52x(x-1)=x^2+1.

若只求 $P(3)$ ，可先把 $3$ 代入三个基多项式：系数依次为 $1,-3,3$ ，故 $P(3)=1-6+15=10$ 。计算量来自点值的线性组合，不必先设一般式再解完整方程组。

比较最高次项与构造含已知根的多项式

若 $P(x)=a_nx^n+\cdots+a_0$ ，允许 $a_n=0$ ，比较插值式中的 $x^n$ 系数得到

a_n=\sum_{i=0}^n\frac{P(x_i)}{\prod_{j\ne i}(x_i-x_j)}.

特别地，取 $P(x)=x^k$ ，当 $0\le k<n$ 时该和为零， $k=n$ 时为一。 $k=0$ 表示常数多项式 $1$ ，并不要求对零节点解释 $0^0$ 。这些关系可用于点值估计和求系数。

若点值具有其他共同结构，先构造一个含已知根的多项式往往更短。例如已知 $P(t_i)=1/t_i$ 且 $t_i\ne0$ ，则 $xP(x)-1$ 在各 $t_i$ 为零。先核对其次数，再提出这些一次因式，最后用其他点求常数。完整例子见点值构造。若次数仍有余量，商可能是非常数多项式，不能直接写成常数倍。

插值与余式、差分的联系

设 $D(x)=\prod_{i=0}^n(x-x_i)$ ，节点互异。任意多项式 $F$ 除以 $D$ 的余式 $R$ 次数至多为 $n$ ，且 $R(x_i)=F(x_i)$ 。所以对 $F$ 的节点值做插值，得到的正是余式，而不必等于 $F$ 本身。

节点等距时，可用有限差分与牛顿有限展开组织同一插值问题；重复节点则需要导数值等额外条件，见重根除式的余式。有限个样本总能插值，不代表原函数在未给出的点也服从这个多项式，更不能凭此断言数列的无限规律。

关联阅读

问题与唯一性

给定

n+1

个互异节点

x_0,\ldots,x_n

及指定值

y_0,\ldots,y_n

，希望找次数不超过

n

的多项式

P

，满足

P(x_i)=y_i

。节点和值可以为实数，也可以为复数。

若

P,Q

都符合要求，则

P-Q

的次数至多为

n

，却在这

n+1

个节点为零，故恒为零。这证明至多有一个解；下面还要构造解，才能证明存在。不要把“至多一个”和“存在唯一一个”混为一谈。

拉格朗日插值公式及证明

对

i=0,\ldots,n

，定义基多项式

L_i(x)=\prod_{\substack{0\le j\le n\\j\ne i}}\frac{x-x_j}{x_i-x_j}.

所有分母非零，因为节点互异。

L_i

在自己的节点

x_i

取值

1

，在其他节点取值

0

。因此

P(x)=\sum_{i=0}^n y_iL_i(x)

次数不超过

n

，且代入

x_k

时只有第

k

项保留下来，得到

P(x_k)=y_k

。结合唯一性，这就是所求多项式。

n=0

时空乘积取

1

，公式给出常数

y_0

。

插值结果的实际次数可能小于

n

，例如全部

y_i

相同。节点重复时公式没有意义：重复的相同条件不增加信息，重复节点给出不同数值则根本无解。

比较最高次项与构造含已知根的多项式

若

P(x)=a_nx^n+\cdots+a_0

，允许

a_n=0

，比较插值式中的

x^n

系数得到

a_n=\sum_{i=0}^n\frac{P(x_i)}{\prod_{j\ne i}(x_i-x_j)}.

特别地，取

P(x)=x^k

，当

0\le k<n

时该和为零，

k=n

时为一。

k=0

表示常数多项式

1

，并不要求对零节点解释

0^0

。这些关系可用于点值估计和求系数。

若点值具有其他共同结构，先构造一个含已知根的多项式往往更短。例如已知

P(t_i)=1/t_i

且

t_i\ne0

，则

xP(x)-1

在各

t_i

为零。先核对其次数，再提出这些一次因式，最后用其他点求常数。完整例子见点值构造。若次数仍有余量，商可能是非常数多项式，不能直接写成常数倍。

插值与余式、差分的联系

设

D(x)=\prod_{i=0}^n(x-x_i)

，节点互异。任意多项式

F

除以

D

的余式

R

次数至多为

n

，且

R(x_i)=F(x_i)

。所以对

F

的节点值做插值，得到的正是余式，而不必等于

F

本身。