插值法和线性拟合　第二节

[引入]求作n次多项式
$N_n(x)=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)+...+c_n(x-x_0)(x-x_1)...(x-x_n-1)$
使满足
$\\N_n(x_i)=y_i=f(x_i)\qquad i=0,1,2,...,n$
为了简化，引入下列记号
$\begin{equation} \left\{ \begin{array}{lr} \varphi_0(x)=1\\ \varphi_1(x)=x-x_0\\ \varphi_i(x)=(x-x_{i-1})\varphi_{i-1}(x)\\ =(x-x_0)(x-x_1)...(x-x_{i－1}) \qquad i=0,1,2,...,n \end{array} \right. \end{equation}$
$\varphi_i(x)$ 就是多项式的第 i 项的非系数部分。
当 $c_i$ 是常数，且只与当前的插值节点相关时，再增加新的节点，只需计算 $c_{n+1}$ 和 $\varphi_{n＋1}(x)$

$c_0=f(x_0)$
$c_1=\frac{f(x_0)-f(x_1)}{x_0-x_1}$
$c_2=\frac{1}{x_0-x_2} (\frac{f(x_0)-f(x_1)}{x_0-x_1} - \frac{f(x_1)-f(x_2)}{x_1-x_2})$
此时，需要计算 $c_i$ ,引入差商的概念。

2.3.2 差商的概念

给定 $[a,b]$ 中互不相同的点 $x_0,x_1,x_2,..x_n$ ,以及函数 $f(x)$ 在这些点处对应的函数值 $f(x_0),f(x_1),f(x_2),...f(x_n)$ 。
$f(x)在x_0处的零阶差商$ $f[x_0]=f(x_0)$
$f(x)在x_0,x_1两点的一阶差商$ $f[x_0,x_1]=\frac{f(x_0)-f(x_1)}{x_0-x_1}$
$f(x)在x_0,x_1,x_2三点的二阶差商$ $f[x_0,x_1,x_2]=\frac{f[x_0-x_1]-f[x_1-x_2]}{x_0-x_2}$
...
$f(x)在x_0,x_1,...,x_n的n阶差商$ $f[x_0,x_1,...,x_n]=\frac{f[x_0,x_1,...,x_n]-f[x_1,x_2,...,x_n]}{x_0-x_n}$

综上，对于顺序排列的 $x_0,x_1,...x_n,\quad c_i=f[x_0,x_1,...x_i]$ ,由 $\varphi_i(x)和c_i,可计算出插值多项式。$

2.3.3 差商的性质

线性性
对称性
降次性

(1) $k阶差商f[x_0,x_1,...,x_k]是函数值f(x_0),f(x_1),...,f(x_k)的线性组合。$
$f[x_0,x_1,...,x_k]=\sum\limits_{j=0}^{k} \frac{f(x_j)}{(x_j-x_0)(x_j-x_1)...(x_j-x_{j－1})(x_j-x_{j＋1})...(x_j- x_k)}$

证明使用数学归纳法
$当k=1时,f[x_0,x_1]=\frac{f(x_0)}{x_0- x_1}+\frac{f(x_1)}{x_1- x_0}成立$
$设当k=m-1时成立$
$当k=m时，f[x_0,x_1,x_k]=\frac{1}{x_0-x_k} (f[x_0,x_1,...,x_{k－1}]- f[x_1,x_2,...,x_k])$
$=\frac{1}{x_0－x_k} (\frac{f(x_0)}{(x0-x_1)(x_0-x_2)...(x_0-x_{k－1})} -\frac{f(x_k)}{(x_k-x_1)(x_k-x_2)...(x_k－x_{k－1})} + \sum\limits_{i=1}^{k-1}(f(x_i)* \frac{x_0 - x_k}{(x_j-x_0)(x_j-x_1)...(x_j－x_k)} )$
$=\sum\limits_{j=0}^{k} \frac{f(x_j)}{(x_j-x_0)(x_j-x_1)...(x_j-x_{j－1})(x_j-x_{j＋1})...(x_j- x_k)}$

(2) $差商f[x_0,x_1,...,x_k]的值与插值点的内部排序无关，也称对称性$
由性质一线性组合即可证明。

(3) $若差商f[x,x_0,x_1,...,x_k]是x的m次多项式，则f[x,x_0,x_1,...,x_k,x_{k＋1}]是x的m-1次多项式$

证明:
$f[x,x_0,x_1,...,x_k,x_{k＋1}]=\frac{f[x,x_0,x_1,...,x_k]-f[x_{k+1},x_0,x_1,...,x_k]}{x-x_{k+1}}$
$(x-x_{k+1})* f[x,x_0,x_1,...,x_k,x_{k＋1}]= f[x,x_0,x_1,...,x_k]-f[x_{k+1},x_0,x_1,...,x_k]$
$右端为m次多项式(多项式＋常数差商)，左端也为m次多项式$
$当x=x_{k+1}时，右式为0,故说明右式带有系数(x-x_{k＋1}),两边同除(x-x_{k＋1})$
$可得f[x,x_0,x_1,...,x_k,x_{k＋1}]=\frac{f[x,x_0,x_1,...,x_k]-f[x_{k+1},x_0,x_1,...,x_k]}{x-x_{k+1}}为m-1次多项式$

推论：若 $f(x)为n次多项式,则f[x,x_0,x_1,...,x_n]恒等于0。$

2.3.4 Newton插值公式

由差商的定义
$f(x)=f(x_0)+f[x,x_0](x-x_0)$
$f[x,x_0]=f[x_0,x_1]+f[x,x_0,x_1](x-x_1)$
...
$f[x,x_0,x_1,...,x_n]=f[x_0,x_1,...,x_n]+f[x,x_0,...,x_n](x-x_n)$

逐个带入，可知
$f(x)=f(x_0)+ f[x_0,x_1](x-x_0)+...+f[x_0,x_1,...,x_n](x-x_0)(x-x_1)...(x-x_{n－1})$
$+f[x,x_0,...,x_n](x-x_0)(x-x_1)...(x-x_n)$

故余项 $R_n(x)=f(x)-N_n(x)=f[x,x_0,...,x_n](x-x_0)(x-x_1)...(x-x_n)$
遗憾的是，这个公式中的差商 $f[x,x_0,...,x_n]$ 因带有 $f(x)$ 而不能计算，只能得到解析表达式

解决方法:
利用 $Langrange插值余项公式 R_n(x)=f(x)-p_n(x)=\frac{f^{n+1}(\xi)}{(n+1)!} \prod\limits_{i=0} ^n (x-x_i)$
和余项 $R_n(x)=f(x)-N_n(x)=f[x,x_0,...,x_n](x-x_0)(x-x_1)...(x-x_n)$
知，当 $f(x)在插值区间[a,b]上有n+1阶导数，且 \exists \xi \in[x_{i min},x_{i max}]$
使得 $\\f[x_0,x_1,...,x_n ]=\frac{f^{n}(\xi)}{n!}$
根据上述关系，可将Newton插值公式改写为
$N_n(x)=f(x_0)+f^{'}(\xi_1)(x-x_0)+\frac{f^{''}(\xi_2)}{2!}(x-x_0)(x-x_1)+......+\frac{f^{n}(\xi_n)}{n!}(x-x_0)(x-x_1)...(x-x_n)$

综上

牛顿插值的同式为 $\sum_{i=0} ^{n} \varphi_i(x)c_i$
$\varphi_0(x)=1 \qquad \varphi_n(x)=(x-x_0)(x-x_1)...(x-x_{n-1})$
可以利用差商的方法计算牛顿插值系数
$n阶差商$ $f[x_0,x_1,...,x_n]=\frac{f[x_0,x_1,...,x_n]-f[x_1,x_2,...,x_n]}{x_0-x_n}$
余项为 $R_n(x)=f(x)-N_n(x)=f[x,x_0,...,x_n](x-x_0)(x-x_1)...(x-x_n)$
遗憾的是，这个公式中的差商 $f[x,x_0,...,x_n]$ 因带有 $f(x)$ 而不能计算，只能得到解析表达式
知，当 $f(x)在插值区间[a,b]上有n+1阶导数，且 \exists \xi \in[x_{i min},x_{i max}]$
使得 $\\f[x_0,x_1,...,x_n ]=\frac{f^{n}(\xi)}{n!}$
根据上述关系，可将Newton插值公式改写为
$N_n(x)=f(x_0)+f^{'}(\xi_1)(x-x_0)+\frac{f^{''}(\xi_2)}{2!}(x-x_0)(x-x_1)+......+\frac{f^{n}(\xi_n)}{n!}(x-x_0)(x-x_1)...(x-x_n)$

引用

1.《计算方法　第二版》崔国华　许如初著

最后编辑于：2020.12.28 15:40:02

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

插值法和线性拟合　第二节

插值法和线性拟合　第二节

目录

2.1 插值多项式存在唯一性

2.2 Lagrange(拉格朗日)插值

2.3 Newton(牛顿)插值

2.4 Hermite(赫米特)插值

2.5 分段插值