插值法和线性拟合　第一节

共分五次
第一次　线性插值的唯一性和拉格朗日插值
第二次　牛顿插值
第三次　赫米特插值
第四次　分段插值
第五次　习题课和小结

$\Large\mathbf{第一节多项式插值的唯一性和拉格朗日插值}$

$\large\mathbf{多项式插值的唯一性}$

一.多项式插值引言

实际问题中，对离散点的函数拟合，以及对函数表达式复杂的函数 $y=f(x)$ 可以使用一个简单的连续函数 $g(x)$ 来近似替代，以简化问题。其中 $f(x)$ 为被逼近函数， $g(x)$ 为逼近函数。
如果要求构造的函数 $g(x)$ 取给定的离散数据，即 $g(x_i)=f(x_i) (i=1, 2,3,...,n)$ ,当 $g(x)$ 为代数多项式时，与之对应的插值逼近称为代数多项式插值。

$\large{多项式插值问题:}$
确定一个次数不高于n的多项式，
$p_n(x)=a_0+a_1x+a_2x^2+...a_nx^n\tag{2.1}$
使其满足
$p_n(x_i)=y_i \qquad i=0,1,2,...,n \tag{2.2}$
点 $x_i(i=0,1,2,...)$ 互异,称为插值节点，包含插值节点的区间 $[a,b]$ 称为插值区间。
从几何上看，多项式插值问题即是求作一条曲线 $y=f(x)$ 上给定的n+1个点的n次代数曲线 $y=p_n(x)$ 作为 $y=f(x)$ 的近似。

这样的多项式的是唯一的，下面给出证明:

证明:

该多项式满足

$\begin{equation} \left\{ \begin{array}{lr} a_0+a_1x_0+a_2x_0^2+...+a_nx_0^n=y_0\\ a_0+a_1x_1+a_2x_1^2+...+a_nx_1^n=y_1\\ ...\\ a_0+a_1x_n+a_2x_n^2+...+a_nx_n^n=y_n\\ \end{array} \right. \end{equation}$

可以写成形如 $AX=b$ 的形式,其中 $X=[a_0,a_1,a_2,...,a_n]^T\quad b=[y_0,y_1,y_2,...y_n]$
其系数矩阵
$A=\left[ \begin{array}{1} 1 & x_0 & x_0^2 & ... & x_0^n \\ 1 & x_1 & x_1^2 & ... & x_1^n \\ .\\ .\\ .\\ 1 & x_n & x_n^2 & ... & x_n^n \end{array} \right]$

根据线性代数中的非齐次线性方程组的有解性，以及 $x_i \neq x_j (i \neq j)$ 可知系数矩阵A是一个满秩的范德蒙行列式，故解唯一，即插值多项式存在且唯一。

结论:
对于给定了互异的n+1个插值节点n次代数多项式插值，其n次代数多项式是存在且唯一的，其形式为 $p_n(x)=a_0+a_1x+a_2x^2+...a_nx^n$

$\Large \mathbf{拉格朗日插值}$

2.2.1 线性插值

[引入] $\begin{equation} 函数y=f(x)给定两点(x_0,y_0),(x_1,y_1)求一个次数小于1的多项式 \end{equation}$
$p_1(x)=a_0+a_1x$
使它满足
$p_1(x_i)=y_i\qquad i=0,1$
形如此类构造即为线性插值。

特别的，这种构造可以写成基函数的形式，对插值点有基函数 $l_i(x_i)=1, l_i(x_j)=0 (i\neq j),$
这样就可以构造 $l_i(x)=\frac{ {\prod\limits_{ j=0, i\neq j}^n}(x-x_j)}{{\prod\limits_{ j=0, i\neq j}^n}(x_i-x_j)}$ 这样的话，只有基函数对应的插值点时值为1,否则为0。

2.2.2 抛物插值

虽然直线插值简单方便，但是由于它是用直线代替曲线，基于导数推导的知识我们知道，这种方法只适合插值区间 $[x_0,x_1]$ 较小的情况，且 $f(x)$ 在插值区间上变化平稳，否则误差可能很大。
为了克服这一问题，考虑用更高次的多项式来近似地替代。
(更高次替代更准确的原因类比泰勒展开，函数的特征在于增减性和函数值，在这两个要素上越接近，逼近函数越契合被逼近函数，但是这是已知函数解析式的情况下，对于插值，高次拟合会产生runge现象，后面会提到)

类似的，利用基函数来构造
$\begin{equation} l_0(x_0)=1\qquad l_1(x_1)=1\qquad l_2(x_2)=1\\ \end{equation}$
其余不对应的基函数值为0。
这样，我们构造出
$\begin{equation} 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)}\\ l_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}\\ \end{equation}$
得到的抛物构造函数为 $p_2(x)=\sum\limits_{i=0}^2 l_i(x)*y_i$

2.2.3 Lagrange插值公式

[引入] 设 $y=f(x)$ 在给定的互异节点 $x_0,x_1,x_2,...,x_n$ 上的函数值为 $y_0,y_1,y_2,...y_n$ ,求作一个次数小于n的多项式。
$\\p_n(x)=a_0+a_1x+a_2x^2+...a_nx^n$
使它满足
$\\p_n(x_i)=y_i \qquad i= 0,1,2,...,n$
类似的，我们以基函数构造 $p_n(x)=\sum\limits_{i=0} ^n l_i(x)*y_i \tag{2.3 拉格朗日插值公式}$
其中 $l_i(x)是一个n次多项式，满足多项式次数条件，且由于l_i(x)的对性，也满足p_n(xi)=y_i$
构造完毕，这就是拉格朗日插值公式，基于基函数的构造方法。
注: $l_i(x)=\frac{ {\prod\limits_{ j=0, i\neq j}^n}(x-x_j)}{{\prod\limits_{ j=0, i\neq j}^n}(x_i-x_j)}$
$对插值区间[a,b]\forall x \in [a,b],\quad\sum l_i(x)=1。$

2.2.4插值余项

了解了插值拟合方法，也需要确定插值的精度，此时结合 $R_n(x)=f(x)-p_n(x)$ 计算n次代数多项式插值的截断误差，也是插值余项。

证明有两种，一种是本教材的证明，另外一种是《数值分析　第五版》李庆杨著中的证法，考虑到证明的自然性，这里先使用李书中的证法。

证法一:
由构造方法知道，当x取值在插值点时是没有误差的，故可以构造下列式子，其根包含所有插值点
$R_n(x)=K(x)*(x-x_0)(x-x_1)(x-x_2)...(x-x_n)$
其中, $K(x)$ 是与 $x$ 有关的待定系数，现在把 $x$ 看作是 $[a,b]$ 上的一个固定点，K(x)是一个常量,作函数

$\varphi(t)=f(t)-p_n(t)-K(x)*(t-x_0)(t-x_1)(t-x_2)...(t-x_n)$
$取t=x 则\qquad \varphi(x)=f(x)-p_n(x)-R_n(x)=0$
$另外的，对于t=x_i \quad (i=0,1,...,n) \quad \varphi(t)=0$
故 $\varphi(t)有n+2个零点，分别为x,x_0,x_1,...,x_n,由Rolle(罗尔)定理，使用n+1次可得$
$\varphi^{(n+1)}(\xi)= f^{(n+1)}(\xi)-K(x)*(n+1)!=0$
$\therefore K(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}$
$\therefore R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}*\prod\limits_{i=0} ^{n} (x-x_i) \qquad \xi \in[a,b]$
这样就可以给出拉格朗日插值余项的解析解，但是 $\xi$ 是区间上的某点，不能准确获得，所以类似的，采用误差限的方式，我们求取插值余项的误差限。

证法二:
暂时🕊了，计算方法第二版可见原证明。

引用

1.《计算方法　第二版》崔国华　许如初著
2.《数值分析　第五版》李庆杨著

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念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 分段插值

一.多项式插值引言

2.2.1 线性插值

2.2.2 抛物插值

2.2.3 Lagrange插值公式

2.2.4插值余项

引用

推荐阅读更多精彩内容

插值法和线性拟合 第一节

目录

2.1 插值多项式存在唯一性

2.2 Lagrange(拉格朗日)插值

2.3 Newton(牛顿)插值

2.4 Hermite(赫米特)插值

2.5 分段插值

一.多项式插值引言

2.2.1 线性插值

2.2.2 抛物插值

2.2.3 Lagrange插值公式

2.2.4插值余项

引用

推荐阅读更多精彩内容

插值法和线性拟合　第一节