欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

数学建模竞赛知识点汇总（3）--插值算法

最编程 2024-06-30 13:00:56
...

本文已参与「新人创作礼」活动，一起开启掘金创作之路。

简介

​ 数模中，有时需要根据已知的函数点进行数据处理，但有时现有数据太少，就需要用插值方法，模拟产生一些新的、比较靠谱的数据来满足需求。构造函数，使过这些点，插值点处的函数值即为插值

在这里插入图片描述

分类

  1. 多项式插值，P(x)P(x)是多项式

  2. 分段插值，P(x)P(x)是分段多项式

  3. 三角插值， P(x)P(x)​ 是三角多项式（此处不做讨论）

插值法定理： P(x)P(x)个互不相同的节点，满足插值条件的多项式存在且唯一

证：用了范德蒙行列式，具体步骤略

常见的插值算法

拉格朗日插值

​ 对某个多项式函数，已知有给定的 k+1k+1 个取值点： (x0,y0),…,(xk,yk)\left(x_{0}, y_{0}\right), \ldots,\left(x_{k}, y_{k}\right) ，其中 xjx_{j} 对应着自变量 的位置，而 yjy_{j} 对应着函数在这个位置的取值。假设任意两个不同的 xjx_{j} 都互不相同，那么应用拉格朗日 揷值公式所得到的拉格朗日揷值多项式为:

L(x):=∑j=0kyjℓj(x)L(x):=\sum_{j=0}^{k} y_{j} \ell_{j}(x)

​ 其中每个 ℓj(x)\ell_{j}(x) 为拉格朗日基本多项式 (或称揷值基函数)，其表达式为:

ℓj(x):=∏i=0,i≠jkx−xixj−xi=(x−x0)(xj−x0)⋯(x−xj−1)(xj−xj−1)(x−xj+1)(xj−xj+1)⋯(x−xk)(xj−xk)\ell_{j}(x):=\prod_{i=0, i \neq j}^{k} \frac{x-x_{i}}{x_{j}-x_{i}}=\frac{\left(x-x_{0}\right)}{\left(x_{j}-x_{0}\right)} \cdots \frac{\left(x-x_{j-1}\right)}{\left(x_{j}-x_{j-1}\right)} \frac{\left(x-x_{j+1}\right)}{\left(x_{j}-x_{j+1}\right)} \cdots \frac{\left(x-x_{k}\right)}{\left(x_{j}-x_{k}\right)}

​ 拉格朗日基本多项式 ℓj(x)\ell_{j}(x) 的特点是在 xjx_{j} 上取值为 1 ，在其它的点 xi,i≠jx_{i}, i \neq j 上取值为 0 。 即：对于给定的 n+1n+1 个点 (x0,y0),(x1,y1),…,(xn,yn)\left(x_{0}, y_{0}\right),\left(x_{1}, y_{1}\right), \ldots,\left(x_{n}, y_{n}\right) ，对应于它们的次数不超过 nn 的拉格朗日 多项式 LL 只有一个。

​ 拉格朗日插值是一种多项式插值方法。但因为高次插值会产生龙格现象，两端波动非常大，所以不要轻易使用高次插值。

牛顿插值法

差商： 函数 f(x)f(x) 在两个互异点 xi,xjx_{i}, x_{j}​​ 处的一阶差商定义为:

f[xi,xj]=f(xi)−f(xj)xi−xj(i≠j,xi≠xj)f\left[x_{i}, x_{j}\right]=\frac{f\left(x_{i}\right)-f\left(x_{j}\right)}{x_{i}-x_{j}}\left(i \neq j, x_{i} \neq x_{j}\right)

2阶差商:

f[xi,xj,xk]=f[xi,xj]−f[xj,xk]xi−xk(i≠k)f\left[x_{i}, x_{j}, x_{k}\right]=\frac{f\left[x_{i}, x_{j}\right]-f\left[x_{j}, x_{k}\right]}{x_{i}-x_{k}}(i \neq k)