数值分析：多项式插值

作者: 胜负55开 | 来源:发表于2019-04-05 20:02 被阅读0次

前言

插值不仅仅用在数值积分，更是有限元和谱元法的基础！在多种多样的插值方法中，首先推荐的是分段线性(拉格朗日)插值，在后文我们就会看到它的通用性和近似的精确性。在开始之间，要首先明确"插值与拟合"的区别：

插值：寻找一个能反映函数 $f(x)$ 特性，且形式简单、性质良好的函数 $\varphi(x)$ 来"近似"！必须满足的条件：必过一系列插值点。
拟合：同样是为了"近似"原函数 $f(x)$ ，并反映其总体趋势。但是拟合没有强制必须过哪些点。

多项式插值原理

一句话总结：拉格朗日插值，就是用"一系列多项式相加"来近似原函数。即：

$f(x) ≈ P_n(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$

上式中的 $P_n(x)$ 就叫做"原函数的插值多项式"，对应的方法就是"多项式插值法"！已经证明：插值多项式具有"存在性"和"唯一性"，因此可以放心使用。各种不同的插值方法，只是实现的方式不同，但是原理都是求解那唯一的插值多项式。

拉格朗日插值

一阶拉格朗日插值：共2个插值节点，这2点间(都经过)用直线段代替；
二阶拉格朗日插值：共3个插值节点，这2点间(都经过)用二次函数代替；
n阶拉格朗日插值：共n+1个插值节点，这n+1点间(都经过)用n次函数代替。

规律：拉格朗日插值阶数 = 基函数个数 = 区间分段总数 = 总插值节点数 - 1

下面先给出一阶和二阶的公式：

拉格朗日插值	2点一阶(一次多项式)	3点二阶(二次多项式)
插值节点	$(x_0,y_0)、(x_1,y_1)$	$(x_0,y_0)、(x_1,y_1)、(x_2,y_2)$
基函数	$l_0(x)=\frac{x-x_1}{x_0-x_1} \quad l_1(x)=\frac{x-x_0}{x_1-x_0}$	$l_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$ $l_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} \quad l_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}$
插值函数	$L_1(x) = y_0l_0(x) + y_1l_1(x)$	$L_2(x) = y_0l_0(x) + y_1l_1(x) + y_2l_2(x)$
说明	每2点间有2个基函数	每3点间有3个基函数

下面给出n阶的插值基函数公式：

$l_0(x) = \frac{(x-x_1)(x-x_2)\cdots (x-x_n)}{(x_1-x_0)(x_1-x_2)\cdots (x_0-x_n)}$
$l_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)} \quad (i=1,2,\cdots ,n-1)$
$l_0(x) = \frac{(x-x_1)(x-x_2)\cdots (x-x_{n-1})}{(x_n-x_0)(x_n-x_2)\cdots (x_n-x_{n-1})}$
$L_n(x) = \sum_{i=0}^{n}y_il_i(x)$

但是，以上的这3种方法都不能用！一阶和二阶精度太低，n阶("满配"——有几个插值点就用几阶多项式去近似)会出现"过度拟合"，也就是Runge现象(稍微复杂一点、有一些弯曲变换的函数在高阶近似都会出现)：

图1：10阶拉格朗日插值普遍出现龙格现象

注意一点：龙格现象都大的误差/影响，在函数的两端！即图中函数两端的蓝圈。

拉格朗日插值节点的选取

一般情况下，插值节点都是区间的等分点；但事实上，插值节点的选取完全可以任意！可以不遵循任何分布的规律！一般情况下对区间的等分或等比划分，只是为了编程方便而已！本文采取的就是均分的情况。但是在有限元和谱元法中，一定不会再用均分了！！！

在强调一遍：拉格朗日的插值节点是可以任意分布的！

分段线性拉格朗日插值

当插值点很多的时候，上面的方法都不能用！此时我们最好的工具就是"分段线性拉格朗日插值"！即：即使插值节点再多，每2个相邻插值点间用一阶拉格朗日插值，然后每一段加起来(分段函数表示也行)即可。这才是实际中会用到的。

下面给出分段线性插值的基函数公式：

$l_0(x)=\begin{cases} \frac{x-x_1}{x_0-x_1} & x_0≤x≤x_1 \\ 0 & 其他 \end{cases}$

$l_i(x)=\begin{cases} \frac{x-x_{i-1}}{x_i - x_{i-1}} & x_{i-1}≤x≤x_{i} \\ \frac{x-x_{i+1}}{x_i - x_{i+1}} & x_{i}≤x≤x_{i+1} \quad\quad (i=1,2,\cdots, n-1)\\ 0 & 其他 \end{cases}$

$l_0(x)=\begin{cases} \frac{x-x_{n-1}}{x_n-x_{n-1}} & x_{n-1}≤x≤x_{n} \\ 0 & 其他 \end{cases}$

$L(x) = y_0l_0(x) + y_1l_1(x) + y_2l_2(x) + y_3l_3(x) + \cdots + y_nl_n(x)$

基函数的图像为：

图2：各个基函数图像(画到一起了)

我们发现：各个基函数(一阶/直线)，它们的值域都是 $[0,1]$ (这是一定的)，并且斜率一样(这不一定，这里因为区间是等分的，所以各基函数的分母都是一样的)。这一堆看似平凡，并且值域和原函数的值域相差甚远的一群线性基函数，怎么会拼凑在一起就能近似原函数呢？
因为：每一个基函数前面都会乘以一个 $y_i$ ，这个必过的插值点的y值与对应的基函数合作，就可以把基函数的值给拉起来！拉到和原函数一样的高度。

注意： $l_i(x)$ 中比如 $l_2(x)$ ，同样的标志 $l_2(x)$ 是有2个不同的表达式的！！！即：
$l_2(x) = \frac{x-x_1}{x_2 - x_1} \quad\quad x_1≤x≤x_2$

$l_2(x) = \frac{x-x_3}{x_2 - x_3} \quad\quad x_2≤x≤x_3$

根据公式可能不太好理解，只需记住其内涵——每2个相邻插值点间用一阶拉格朗日插值即可。
实际操作，我们一般用分段函数表示。

下面给出matlab实现分段线性拉格朗日插值：

clear; clc;

xnum = [1 2 2.3 5.1 6.2 6.8 8 8.4 9.1];  
ynum = sqrt(xnum);  % 针对的sqrt(x)的函数,其他函数都同理

n = length(xnum);
syms x L;
L_tmp = sym(zeros(1,n-1));

% 每一段(两个相邻点)拉格朗日插值直线:
for m = 1:n-1
    l0 = (x-xnum(m+1))/(xnum(m)-xnum(m+1));
    l1 = (x-xnum(m))/(xnum(m+1)-xnum(m));
    L_tmp(m) = ynum(m)*l0 + ynum(m+1)*l1;
end

% 分段函数做图没有问题:就是一段一段画而已
figure(1);
for m = 1:n-1
    x = [xnum(m),xnum(m+1)];
    y = double(subs(L_tmp(m)));
    plot(x,y);
    hold on;
end
grid on;

% 原始函数图像(画到一起)
x1 = xnum(1):0.1:xnum(n);
y1 = sqrt(x1);
plot(x1,y1,'--k');
title('分段线性近似y=sqrt(x)函数');
xlabel('x');  ylabel('y');

效果如下：

图3：分段线性拉格朗日插值近似效果图

其他插值方法

牛顿插值、埃尔米特插值(需要求一阶导数)、三次样条插值等。我们最常用的，以及后面数值积分的各种方法，都是基于分段线性拉格朗日插值的！

所有插值方法的核心思路：用一个简单的多项式去替代原函数！要想提高插值函数近似的精度，只要增加插值节点。

所有插值方法的重要细节：插值点完全可以是随意分布的！从未要求一定是区间的等分或等比点。

数值分析：多项式插值

前言

多项式插值原理

拉格朗日插值

拉格朗日插值节点的选取

分段线性拉格朗日插值

其他插值方法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

GIS相关

GIS