数值分析之插值

插值

一.基本概念

1.1插值需要研究的问题

插值函数是否存在？
如何构造插值函数？
如何评估误差？

1.2插值法定义

设函数y=f(x)在区间[a,b]有定义，且已知 $a \leqslant x_{0}<x_{1}<\cdots<x_{n} \leqslant b$ 上值 $y_{0}, y_{1}, \cdots, y_{n}$ ，若存在一简单函数P(x),使得
$P\left(x_{i}\right)=y_{i} \quad(i=0,1, \cdots, n)$
成立，就称P(x)为f(x)的插值函数，点 $x_{0}, x_{1}, \cdots, x_{n}$ 称为插值节点，包含插值节点的区间[a,b]称为插值区间，求插值区间函数P(x)的方法称为插值法。若P(x)是次数不超过n的代数多项式，即 $P(x)=a+a x+\cdots+a_{n} x^{n}$ ，称P(x)为插值多项式。

二.多项式插值

定理：设区间[a,b]上给定n+1个点 $a \leqslant x_{0}<x_{1}<\cdots<x_{n} \leqslant b$ 上的函数值 $y_i=f(x_i)(i=0,1,...,n)$ ,这样次数不超过n的多项式，使 $P(x_i)=y_i(i=0,1,...,n)$ 是唯一的。

快照15.png

三.拉格朗日插值

使用解线性方程组的方法求解插值多项式，计算量大，造成的误差也不易估算，因此我们一般采取其他方法来构造插值多项式

3.1线性插值与抛物线插值

线性插值（两点插值）:

给定两个区间 $[x_k,x_{k+1}]$ 及端点函数值 $y_k=f(x_k),y_{k+1}=f(x_{k+1})$ ,求线性插值多项式 $L_1(x)$ ,满足:

$L_1(x)=y_k,L_1(x_{k+1})=y_{k+1}$

其集合意义就是过着两个点的直线。可以通过直线表达式给出：

两点式
$L_{1}(x)=\frac{x_{k+1}-x}{x_{k+1}-x_{k}} y_{k}+\frac{x-x_{k}}{x_{k+1}-x_{k}} y_{k+1}$
设
$l_{k}(x)=\frac{x-x_{k+1}}{x_{k}-x_{k+1}}, \quad l_{k+1}(x)=\frac{x-x_{k}}{x_{k+1}-x_{k}} （称他们为线性插值基函数）$
其中
$\begin{array}{ll}{l_{k}\left(x_{k}\right)=1,} & {l_{k}\left(x_{k+1}\right)=0} \\ {l_{t+1}\left(x_{k}\right)=0,} & {l_{k+1}\left(x_{k+1}\right)=1}\end{array}$
可将两点式表示为
$L_{1}(x)=y_{k} l_{k}(x)+y_{k+1} l_{k+1}(x)$
抛物线插值（三点插值）：

略

3.2拉格朗日插值多项式

将以上两个点或是三个点的情况扩展到有n+1个点，设有n+1个节点， $x_{0}<x_{1}<\cdots<x_{n}$ ，构造n次插值多项式 $L_n(x)$ 满足条件 $L_{n}\left(x_{j}\right)=y_{j} \quad(j=0,1, \cdots, n)$ 。

n次插值基函数：若n次多项式 $l_{j}(x)(j=0,1, \cdots, n)$ ，在n+1个节点 $x_{0}<x_{1}<\cdots<x_{n}$ 上满足条件 $l_{j}\left(x_{k}\right)=\begin{array}{ll}{1,} & {k=j} \\ {0,} & {k \neq j}\end{array} j,k=0,1,...,n$ 就称这为n+1个n次多项式为节点 $x_0,x_{1}, \cdots, x_{n}$ 的n次插值基函数。可以表示为

$，l_{k}(x)=\frac{\left(x-x_{0}\right) \cdots\left(x-x_{k-1}\right)\left(x-x_{k+1}\right) \cdots\left(x-x_{n}\right)}{\left(x_{k}-x_{0}\right) \cdots\left(x_{k}-x_{k-1}\right)\left(x_{k}-x_{k+1}\right) \cdots\left(x_{k}-x_{n}\right)}，j=0,1,...,n$
拉格朗日插值多项式：

可以表示为 $L_{n}(x)=\sum_{k=0}^{n} y_{k} l_{k}(x)$ ，

若将记 $\omega_{n+1}(x)=\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n}\right)$

则 $\omega_{n+1}^{\prime}\left(x_{k}\right)=\left(x_{k}-x_{0}\right) \cdots\left(x_{k}-x_{k-1}\right)\left(x_{k}-x_{k+1}\right) \cdots\left(x_{k}-x_{n}\right)$ （关于x求导）

所以可以将拉格朗日插值多项式改写为：
$L_{n}(x)=\sum_{k=0}^{n} y_{k} \frac{\omega_{n+1}(x)}{\left(x-x_{k}\right) \omega_{n+1}^{\prime}\left(x_{k}\right)}$
注：n次插值多项式的次数通常为n次，特殊情况下也可以小于n次，如三点抛物线插值三点在同一条直线上时。

3.3插值余项与误差估算

定义：若在[a,b]上用 $L_n(x)$ 近似f(x),则其截断误差
$R_{n}(x)=f(x)-L_{n}(x)$
称为插值多项式的余项。
定理：设 $f^{(n)}(x)$ 在[a,b]上连续， $f^{(n+1)}(x)$ 在[a,b]内存在，节点 $a \leqslant x_{0}<x_{1}<\cdots<x_{n} \leqslant b$ ， $L_n(x)$ 是满足上述条件的插值多项式，则对任意的 $x \in[a, b]$ ,
$R_{n}(x)=f(x)-L_{n}(x)=\frac{f^{(n+1)}(\xi)}{(n+1) !} \omega_{n+1}(x)$
这里 $\xi \in(a, b)$ 且依赖于 $x, \omega_{n+1}(x)$ 。
- 证明：（罗尔中值定理）
  
  快照13.png

快照14.png

四.均差及牛顿插值多项式

五.埃尔米特插值

六.分段低次插值

七.三次样条插值

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,490评论 6赞 508
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,581评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 165,830评论 0赞 356
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,957评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,974评论 6赞 393
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,754评论 1赞 307
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,464评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,357评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,847评论 1赞 317
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,995评论 3赞 338
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,137评论 1赞 351
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,819评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,482评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,023评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,149评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,409评论 3赞 373
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,086评论 2赞 355