数学建模笔记1.3——插值

发布时间：2024-09-09 12:55:54浏览次数：

本文使用 Zhihu On VSCode 创作并发布

啊,我实在是理解不了夏令营那个神奇的进度了,所以决定抛弃它,先把插值加进来,再写分类和聚类.

其实很多人都不太清楚插值和拟合的区别.

从图像上来看,插值要求过每一个点,而拟合不必须过每一个点.

插值可以看成是过每一个样本点的拟合.

众所周知,拟合是用来预测的,那插值呢?插值是用来干什么的呢?

貌似也可以用来预测,但这不是最主要的

其实在我做数学的应用的过程中,插值用的频率甚至要多于拟合.

拿数据为例,很多时候我们拿到的数据是残缺不全的.

就比如是这样

这个时候如果用第一节的拟合去修补缺失的值,显然是不妥的,因为这样就会影响到原来的确定的样本值,造成没有必要的损失,这时候就会用到插值,也就是所谓的过每一个样本点的拟合.

另外就是在数字图像处理中,以灰度图片为例,灰度图片的信息是由一维矩阵来储存的.在图片放大的过程中,显然矩阵是变大的,那么空出来的位置的像素就需要用二维插值去补上.

啊,到了擅长的领域就会不知不觉的说多(装x)

设函数 $y=f(x)$ 在区间[a,b]上有定义，且在点

$a\\leq x_{0}<x_{1}<\\cdots<x_{n}\\leq b$

上的值分别为： $y_{0},y_{1},\\cdots,y_{n},$

若存在一简单的函数 $P(x)$ 使 $P(x_{i})=y_{i}\\quad(i=0,1,2,\\cdots,n)$

则称 $P(x)$ 为 $f(x)$ 的插值函数，点 $x_{0},x_{1},\\cdots,x_{n}$ 称为插值节点，包含插值节点的区间[a,b]称为插值区间，求插值函数 $P(x)$ 的方法称为插值法

问题如下：已经有 $n+1$ 个节点 $(x_{i},y_{i})(i=(0,1,\\cdots,n))$ ,其中 $x_{i}$ 互不相同
不妨假设 $a\\leq x_{0}<x_{1}<\\cdots<x_{n}\\leq b$ ,求任一插值点 $x^{*}(\ eq x_{i})$ 处的插值 $y_{*}$

思路也是很简单的，构造函数 $y=f(x)$ ，使得 $f(x)$ 过所有节点，求 $f(x^{*})$ 即可得到 $y^{*}$

定理：设有 $n+1$ 个互不相同的节点 $(x_{i},y_{i})(i=0,1,2,\\cdots,n)$ ,则存在唯一的多项式： $L_{n}=a_{0}+a_{1}x+a_{2}x^{2}+\\cdots+a_{n}x^{n}$

使得 $L_{n}(x_{j})=y_{i}\\quad (j=0,1,2,\\cdots n)$

【注1】只要 $n+1$ 个节点互异，满足上述插值条件的多项式是唯一存在的

【注2】如果不限制多项式的次数，插值多项式并不唯一

每两个样本点确定一条直线,将相邻的样本点用直线连在一起就是分段线性插值

两个点： $(x_{0},y_{0}),(x_{1},y_{1})$

$f(x)=\\frac{x-x_{1}}{x_{0}-x_{1}}y_{0}+\\frac{x-x_{0}}{x_{1}-x_{0}}y_{1}$

三个点： $(x_{0},y_{0}),(x_{1},y_{1}),(x_{2},y_{2})$

$f(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}$

四个点： $(x_{0},y_{0}),(x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3})$

$f(x)=\\frac{(x-x_{1})(x-x_{2})(x-x_{3})}{(x_{0}-x_{1})(x_{0}-x_{2})(x_{0}-x_{3})y_{0}} +\\frac{(x-x_{0})(x-x_{2})(x-x_{3})}{(x_{1}-x_{0})(x_{1}-x_{2})(x_{1}-x_{3})}y_{1} +\\frac{(x-x_{0})(x-x_{1})(x-x_{3})}{(x_{2}-x_{0})(x_{2}-x_{1})(x_{2}-x_{3})}y_{2} +\\frac{(x-x_{0})(x-x_{1})(x-x_{2})}{(x_{3}-x_{0})(x_{3}-x_{1})(x_{3}-x_{2})}y_{3}$

总结起来，拉格朗日插值多项式可以表示成以下形式

$\\omega_{n+1}(x)=(x-x_{0})(x-x_{1})\\cdots(x-x_{n})$

$\\omega_{n+1}^{'}(x_{k})=(x_{k}-x_{0})\\cdots(x_{k}-x_{k-1})(x_{k}-x_{k+1})\\cdots (x_{k}-x_{n})$

$l_{i}(x)=\\frac{\\omega_{n+1}(x)}{(x-x_{i})\\omega_{n+1}^{'}(x_{i})}$

$L_{n}=\\sum\\limits_{i=0}^{n}y_{i}l_{i}(x)$

$L_{n}=\\sum\\limits_{k=0}^{n}y_{k}\\frac{\\omega_{n+1}(x)}{(x-x_{k})\\omega_{n+1}^{'}(x_{k})}$

当然，插值函数的次数不是越高越好，高次插值会产生龙格现象，即在两端处波动极大，产生明显的震荡。在不熟悉曲线运动趋势的前提下，不要轻易使用高次插值

为了避免这种情况，我们可以不使用整体插值函数，而进行分段低次插值

$f(x)=f(x_{0})+f[x_{0},x_{1}](x-x_{0}) +f[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})+\\cdots +f[x_{0},x_{1},\\cdots,x_{n-2},x_{n-1}](x-x_{0})(x-x_{1})\\cdots(x-x_{n-2})(x-x_{n-1}) +f[x_{0},x_{1},\\cdots,x_{n-1},x_{n}](x-x_{0})(x-x_{1})\\cdots(x-x_{n-1})(x-x_{n})$

差商定义：称 $f[x_{0},x_{k}]=\\frac{x_{k}-x_{0}}{x_{k}-x_{0}}$ 为函数 $f(x)$ 关于点
$x_{0},x_{k}$ 的一阶差商（亦称均差）

二阶差商： $f[x_{0},x_{1},x_{2}]=\\frac{f[x_{0},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{1}}$

由此可以得出k阶差商： $f[x_{0},x_{1},\\cdots,x_{k}]=\\frac{f[x_{0},x_{1},\\cdots,x_{k-1},x_{k}]-f[x_{0},x_{1},\\cdots,x_{k-1}]}{x_{k}-x_{0}}$

与拉格朗日插值法一样，牛顿插值法也有着同样的龙格现象

两种插值仅仅在被插节点与被插函数有相等的函数值，不能全面反映被插值函数的性态

差商定义：称 $f[x_{0},x_{k}]=\\frac{x_{k}-x_{0}}{x_{k}-x_{0}}$ 为函数 $f(x)$ 关于点
$x_{0},x_{k}$ 的一阶差商（亦称均差）

二阶差商： $f[x_{0},x_{1},x_{2}]=\\frac{f[x_{0},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{1}}$

由此可以得出k阶差商： $f[x_{0},x_{1},\\cdots,x_{k}]=\\frac{f[x_{0},x_{1},\\cdots,x_{k-1},x_{k}]-f[x_{0},x_{1},\\cdots,x_{k-1}]}{x_{k}-x_{0}}$

与拉格朗日插值法一样，牛顿插值法也有着同样的龙格现象

两种插值仅仅在被插节点与被插函数有相等的函数值,不能全面反映被插值函数的性态

埃尔米特插值是针对插值问题的较高要求

一般地插值问题只要求： $\\varphi(x_{i})=y_{i}\\qquad(i=0,1,2,\\cdots n)$

但是有些插值问题有着较高的要求：

1. $\\varphi(x_{i})=y_{i}\\qquad(i=0,1,2,\\cdots n)$

2. $\\varphi^{'}(x_{i})=y_{i}^{'}\\qquad(i=0,1,2,\\cdots n)$

这就需要用埃尔米特插值

其中我们最常用的是分段三次埃尔米特插值

同样是十分常用的插值方法,但原理解释起来比较麻烦

-------------------------------------------更新!-------------------------------------------

这大概是我时隔一年多补上的(也许是两年)

我们知道,所谓的插值,可以粗略的看成是经过某些点的拟合,当初我学习插值的时候,就觉得很疑惑,这些难道不是拟合就可以解决的问题吗,何必要去插值呢?后来发现其实很多问题要求我们需要"拟合"一条曲线(或者是高维曲面),并且要求这些曲线要经过某些点.

那一个非常直观的插值想法就出现了,我把这些点依次连上不就好了吗?就像连折线图那样.这其实就引出了分段线性插值的概念.

但如此简单的插值方式显然是不适用于大多数实际情况的.很致命的一点就是,它不够光滑.之后引出的插值都是为了改善插值函数的光滑性引出的.

那么函数的光滑性是如何控制的呢?保证其导数就可以让曲线看起来光滑一些.那如何让曲线更加光滑呢?保证高阶导数即可.

接下来引出三次样条插值.

先说所谓的样条插值

样条插值是一种常用的插值方法，它通过拟合一组分段函数来逼近原始数据，从而实现对于给定的一组数据点的插值计算。

具体而言，样条插值将插值区间 $[a,b]$ 分为若干个小区间，每个小区间上均用一个多项式进行插值。在每个小区间中，多项式的系数由两个约束条件确定：第一个是要保证多项式能够经过数据点；第二个是要保证相邻两个小区间上的多项式在共同节点处一阶导数和二阶导数连续。这样，就可以得到一个二次导数连续的插值函数，使得插值函数在插值区间内具有较好的平滑性和拟合度。

三次样条就是将每个小区间上用的多项式具体的写成三次的多项式.

简而言之,三次样条插值是满足如下条件的插值:

分段的插值多项式为三次多项式
共同节点的一阶导数和二阶导数连续,即第 $[x_{i-1},x_{i}]$ 段的插值多项式 $s_{i-1}$ 在 $x_i$ 点的一阶导数和二阶导数与第 $[x_{i},x_{i+1}]$ 段的插值多项式 $s_{i}$ 在 $x_i$ 点的一阶导数和二阶导数是对应相等的.

一般来说三次样条插值是可以有一个很好的连续性的,因此日常中最常用的也是三次样条插值.

作为1维插值的推广,试想一下,如果现在的坐标已经不是 $(x_1,y_1)$ 这种的,而是 $(x_1,x_2,\\cdots,x_n,y_1)$ 这样的呢?n个 $x$ 对应一个 $y$ ,是否还是可以同样的进行插值操作呢?当然可以,函数变成向量值函数就好了.

n维插值有什么用处呢?

最为常见的,各位应当都用手机放大过图片,图像的储存方式是3层矩阵,我们就以最简单的灰度图像为例吧,灰度图是用一个矩阵来存储的,每个像素都可以看成是矩阵的元素,在放大图片的时候,像素实际上是变多了的,那这些多的像素是从何而来呢?插值插出来的.当你放大到一定程度的时候图像会变模糊,这是当然的,放大过程涉及到从现有像素中推断新像素的值,那随着插值出的像素越来越多,就会导致插值出来的像素并不准确.

不同的插值方法会影响到这种模糊程度,比如PS,据说PS用的是某种样条插值,放大的时候最大程度的保留连续性,因此显得不是那么模糊.

上一篇 : 优化器可以做什么？

下一篇 : 新时代经济法优化营商环境的路径选择

400-123-4567

数学建模笔记1.3——插值

联系我们

在线留言