拉格朗日插值多项式

摘要

在数值分析中，多项式插值是最常提到的内容

多项式插值

定义

给定有序点集 ${x_0,x_1,\cdots,x_n}$ 且 $x_0 \lt x_1\lt \cdots\lt x_n$ 以及定义在 $x_0,x_n$ 上的连续函数$f(x)$或对应于 $x$ 值的 $y$ 值集合 $y_0,y_1,\cdots,y_n$ (即 $(x_i,y_i)$) 对.
多项式插值就是要求出对数据 $(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)$ 进行插值的次数最多为 $n$ 的多项式 $p(x)$ ,即

$$y_0 = p(x_0)$$ $$y_1 = p(x_1)$$ $$\vdots$$ $$y_n = p(x_n)$$

称 $p$ 在 ${x_0,x_1,\cdots,x_n}$ 上插值 $f$ ，且 $p$ 是插值. 插值必须在相应点 ${x_0,x_1,\cdots,x_n}$ 上与函数 $f$ 或 $y_0,y_1,\cdots,y_n$ 取值相同，这些点通常称为节点(或分割点).
则插值多项式为

$$p(x) = a_n x^n + a_n-1 x^n-1 + \cdots + a_1 x + a_0$$

插值条件为

$$a_n x_0^n + a_n-1 x_0^n-1 + \cdots +a_1 x_0 + a_0 = y_0$$ $$a_n x_1^n + a_n-1 x_1^n-1 + \cdots +a_1 x_1 + a_0 = y_1$$ $$\vdots$$ $$a_n x_n^n + a_n-1 x_n^n-1 + \cdots +a_1 x_n + a_0 = y_n$$

其中矩阵

$$V = \begin{bmatrix}1&x_0 &x_0^2 & \cdots & x_0^n \\1&x_1 &x_1^2 & \cdots & x_1^n \\ 1&x_2 &x_2^2 & \cdots & x_2^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1&x_n &x_n^2 & \cdots & x_n^n \end{bmatrix}$$

由 $x$ 构成，形如 $V$ 的矩阵称为 $Vandermonde$ 矩阵，如果 $x_i$ 互异，则 $Vandermonde$ 矩阵非奇异，因此多项式插值存在且唯一. 插值多项式的系数由方程

$$V \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_n\end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n\end{bmatrix}$$

的解给出，可以采用Vandermonde方程组的专门解法解出.

例题

对正弦曲线上的数据点 $(0,0),( \pi / 2,1),( \pi ,0),(3 \pi / 2, -1)$进行多项式插值，这里 ${x_0,x_1,x_2,x_3 } = { 0,\pi / 2,\pi ,3 \pi /2 } , {y_0,y_1,y_2,y_3 } = { 0,1,0,-1 } $,求解

$$\begin{bmatrix} 1&0&0&0 \\ 1&\frac{\pi}{2} & \frac{\pi^2}{4} & \frac{\pi^3}{8} \\ 1 & \pi & \pi^2 & \pi^3 \\ 1 & \frac{3\pi}{2} & \frac{9\pi^2}{4} & \frac{27\pi^3}{8}\end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3\end{bmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ -1 \end{pmatrix}$$

得 $ a_0,a_1,a_2,a_3 $
V\y

$$\begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix} = \begin{pmatrix} 0 \\ 1.6977 \\ -0.8106 \\ 0.0860 \end{pmatrix}$$

得

$$p(x) = 0.0860 x^3 - 0.8106 x^2 +1.6997 x$$

验证

x = linspace(0,3/2*pi);
y = sin(x);
a = [0.0860 -0.8106 1.6977 0];
p = polyval(a,x);
plot(x,y,'k-',x,p,'r--');
legend('sin(x)','polyval(a,x)')

Runge函数

多项式插值近似函数的效果似乎不错，但有时很差，因为Vandermonde矩阵一般是病态的，即使求解过程是精确的.
比如高阶多项式插值的振荡问题，即在节点间出现大的迂回.
Runge函数

$$f(x) = \frac{1}{1 + 25 x^2}$$

图中画出了Runge函数以及它的10次插值多项式，函数的振幅会随着n的增大而增大，近似程度将越来越差， $x \in (-1,1)$ 时

x = -1:0.2:1;
x_ = linspace(-1,1);
x = x';
y = 1./(1+25.*(x.^2));
y_ = 1./(1+25.*(x_.^2));
A = ones(11,1);
for i = 1:10
A = [A x.^i];
end
a = A\y;
a = a';
a = a(:,end:-1:1);
x = -1:0.001:1;
p=zeros(11,1);
for i = 10:-1:0
p = p+a(1,11-i)*(x.^i);
end
plot(x_,y_,'k-',x,p,'r--'),legend('1/(1+25*(x^2))','p(x)'),xlim([-1,1]),ylim([-0.5,2])

​

因此需要推导和理解其他方法.

拉格朗日插值多项式

定义

假定要对两个互异点 $x_a,x_b$ 进行直线插值，先定义函数 $ L_a(x) $ 和 $ L_b(x) $

$$L_a(x) = \frac{x - x_b }{x_a - x_b}$$ $$L_b(x) = \frac{x - x_a }{x_b - x_a}$$

则

$$L_a(x_a ) = 1,\quad L_a(x_b = 0)$$ $$L_b(x_a ) = 1,\quad L_b(x_b = 0)$$

且
$ L_a(x) $和 $ L_b(x) $ 都是 $x$ 的线性函数.给定 $y_a = f(x_a )$ 和 $y_b = f(x_b )$，则

$$l(x) = y_a L_a (x) + y_b L_b (x)$$

满足

$$\begin{aligned} l(x_a ) ={}& y_a L_a (x_a) + y_b L_b (x_a) {} \\ ={}& y_a \cdot 1 + y_b \cdot 0 \\ ={}& y_a \end{aligned}$$ $$\begin{aligned} l(x_b ) ={}& y_a L_a (x_b) + y_b L_b (x_b) {} \\ ={}& y_a \cdot 1 + y_b \cdot 0 \\ ={}& y_b \end{aligned}$$

即 $l(x)$ 是 $f$ 在 $(x_a , y_a )$ 和 $(x_b,y_b)$ 上的插值.由于 $l(x)$ 是两个线性函数的和，所以是线性的，又因为过互异两点的直线只有一条，所以 $l(x)$ 是唯一的.
将这种做法推广到 $n+1$ 个互异点 $x_0,x_1,\cdots,x_n $(有序且 $ x_0 \lt x_1 \lt \cdots \lt x_n $ )，定义函数

$$\begin{aligned} L_{n,i} (x) ={}& \frac{(x-x_0)(x-x_1) \cdots (x-x_{i-1})(x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_0)(x_i-x_1) \cdots (x_i-x_{i-1})(x_i-x_{i+1}) \cdots (x_i-x_n)} \\ ={}& \prod_{k=0 \\ k\neq i}^{n} \frac{(x-x_k)}{(x_i - x_k)} \end{aligned}$$

当 $n \neq i$ 时，有

$$L_{n,i} (x_n) = 0$$ $$L_{n,i} (x_i) = 1$$

上式为Lagrange多项式.
由于 $n$ 次多项式的和是次数最多为 $n$ 的多项式，所以用Lagrange多项式可以得到过点 $(x_0,y_0),(x_1,y_1), \cdots , (x_n,y_n) $ 的次数不超过 $n$ 的插值多项式 $p(x)$

$$\begin{aligned} p(x) ={}& y_0 L_{n,0} (x) + y_1 L_{n,1} (x) + \cdots + y_n L_{n,n} (x) \\ ={}& \sum_{i=1}^{n} y_i L_n (x) \end{aligned}$$

有 $L_i(x_j) = 0 $

$$\begin{aligned} p(x) ={}& \sum_{i=0}^{n} y_i L_i (x_j) \\ ={}& y_0 L_0 (x_j) + y_1 L_1 (x_j) + \cdots + y_n L_n (x_j) \\ ={}& y_j \cdot 1 \\ ={}& y_j \end{aligned}$$

$p$ 就是所求的多项式插值，与Vandermonde矩阵的结果相同.

例题

对正弦曲线上的数据点 $(0,0),( \pi / 2,1),( \pi ,0),(3 \pi / 2, -1)$进行多项式插值，这里 ${x_0,x_1,x_2,x_3 } = { 0,\pi / 2,\pi ,3 \pi /2 } , {y_0,y_1,y_2,y_3 } = { 0,1,0,-1 } $,Lagrange多项式

$$\begin{aligned}L_0(x) ={}& \frac{(x-x_1)(x-x_2)(x-x_3)}{(x_0-x_1)(x_0-x_2)(x_0-x_3)} \\ ={}& - \frac{4}{3\pi^3} (x-\frac{\pi}{2})(x-\pi)(x-\frac{3\pi}{2}) \end{aligned}$$ $$L_1(x) = \frac{4}{\pi^3}x(x-\pi)(x-\frac{3\pi}{2})$$ $$L_2(x) = - \frac{4}{3\pi^3} (x-\frac{\pi}{2})(x-\frac{3\pi}{2})$$ $$L_3(x) = \frac{4}{3\pi^3} (x-\frac{\pi}{2})(x-\pi)$$

插值多项式为

$$\begin{aligned} p(x) ={}& 0 \cdot L_0(x) + 1 \cdot L_1(x) + 0 \cdot L_2(x) + (-1) \cdot L_3(x) \\ ={}& 0.0860 x^3 - 0.8106 x^2 +1.6997 x \end{aligned}$$

同前

补充

Cauchy余项定理

给定 $a \leq x_0 \lt x_1 \lt \cdots \lt x_n \leq b$ 及 $f \in C^{n+1}[a,b]$，则对任意 $x \in [a,b]$，都存在 $\xi = \xi(x) \in [a,b]$，使$f$在$x_0,x_1,\cdots,x_n$ 上的插值多项式 $p(x)$ 满足

$$f(x) - p(x) = \frac{f^{n+1}(\xi)}{(n+1)!}(x-x_0)(x-x_1)\cdots(x-x_n)$$

证明略

Weierstrass定理

若$f \in C[a,b]$，则对任意给定的 $\varepsilon \gt 0$ 都存在多项式 $p(x)$ ,使对任意 $x \in [a,b]$，有

$$\left | f(x) - p(x) \right | \leq \varepsilon$$

说明任何连续函数都可以被高次多项式任意逼近.

结束

Lagrange只讨论了求出插值多项式系数的方法，区间外，Lagrange插值是不准确的，如果问题中要求多项式的值，可以使用更为有效和精确的方法.