计算方法插值法(均差与牛顿插值公式)
- 格式：ppt
- 大小：1.09 MB
- 文档页数：36
下载文档原格式
合集下载
计算方法-插值b
…………
2
f [ x , x 0 , x1 ]
x x1
f [ x , x 0 , ... , x n 1 ] f [ x 0 , ... , x n ] ( x x n ) f [ x , x 0 , ... , x n ]
n1
1
←
←
3
←……
←
n1
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 ) ...
(k+1)阶差商：
f [ x0 , x1 , ... , xk ] f [ x1 , ... , xk , xk 1 ] f [ x0 , ... , xk 1 ] x 0 x k 1 f [ x0 , ... , xk 1 , xk ] f [ x0 , ... , xk 1 , xk 1 ] x k x k 1
( )
实际计算过程为
x0 x1 x2 …
xn1 xn
k !
, ( x min , x max )
f (x0) f (x1) f (x2) … f (xn1) f (xn)
xn+1 f (xn+1)
f [x0, x1] f [x1, x2] …… …… f [xn1, xn] f [xn, xn+1]
f [x0, x1 , x2] …… …… f [xn2, xn1, xn] f [xn1, xn, xn+1]
f [x0, …, xn] f [x1, …, xn+1]
f [x0, …, xn+1]
6.2 牛顿插值多项式
一阶均差 二阶均差 三阶均差 n阶均差 阶均差
x1 f [ x1 ] f [ x0 , x1 ]
x2 f [ x2 ] f [ x1 , x2 ] f [ x0 , x1 , x2 ]
x3 f [ x 3 ]
… …… x f [ xn ]
n
f [ x2 , x3 ]
f [ x1 , x2 , x3 ]
N n ( x ) = a0 + a1 ( x − x0 ) + a2 ( x − x0 )( x − x1 ) + L + an ( x − x0 )( x − x1 )L ( x − xn−1 )
ak ( k = 0,1,L , n) 为待定系数 形如上式的插值 待定系数.
多项式称为牛顿 插值多项式. 多项式称为牛顿(Newton)插值多项式 牛顿 插值多项式 由插值条件 N n ( x j ) = f ( x j ) ( j = 0,1,L , n),
证毕. 证毕.
的离散数据如下表： 例 1 已知 f ( x ) = shx 的离散数据如下表：
xi
0.00
0.20 0.20134
0.30 0.30452
0.50 0.52110
f ( xi ) 0.00000
用 Newton插值多项式 计算 f (0.23) 的近似值并 插值多项式, 插值多项式 估计误差. 估计误差
解 均差计算的结果如下表
xi
0.00 0.20 0.30 0.50
f [ xi ]
0.00000 0.20134 0.30452 0.52110
一阶均差
二阶均差
三阶均差
1.0067 1.0318 1.0829
0.08367 0.17033
x1 f [ x1 ] f [ x0 , x1 ]
x2 f [ x2 ] f [ x1 , x2 ] f [ x0 , x1 , x2 ]
x3 f [ x 3 ]
… …… x f [ xn ]
n
f [ x2 , x3 ]
f [ x1 , x2 , x3 ]
N n ( x ) = a0 + a1 ( x − x0 ) + a2 ( x − x0 )( x − x1 ) + L + an ( x − x0 )( x − x1 )L ( x − xn−1 )
ak ( k = 0,1,L , n) 为待定系数 形如上式的插值 待定系数.
多项式称为牛顿 插值多项式. 多项式称为牛顿(Newton)插值多项式 牛顿 插值多项式 由插值条件 N n ( x j ) = f ( x j ) ( j = 0,1,L , n),
证毕. 证毕.
的离散数据如下表： 例 1 已知 f ( x ) = shx 的离散数据如下表：
xi
0.00
0.20 0.20134
0.30 0.30452
0.50 0.52110
f ( xi ) 0.00000
用 Newton插值多项式 计算 f (0.23) 的近似值并 插值多项式, 插值多项式 估计误差. 估计误差
解 均差计算的结果如下表
xi
0.00 0.20 0.30 0.50
f [ xi ]
0.00000 0.20134 0.30452 0.52110
一阶均差
二阶均差
三阶均差
1.0067 1.0318 1.0829
0.08367 0.17033
牛顿插值法原理及应用
牛顿插值法插值法是利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。
如果这特定函数是多项式，就称它为插值多项式。
当插值节点增减时全部插值基函数均要随之变化，这在实际计算中很不方便。
为了克服这一缺点，提出了牛顿插值。
牛顿插值通过求各阶差商，递推得到的一个公式：f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0 )...(x-xn-1)+Rn(x)。
插值函数插值函数的概念及相关性质[1]定义：设连续函数y-f(x) 在区间[a,b]上有定义，已知在n+1个互异的点x0,x1,…xn上取值分别为y0,y1,…yn （设a≤ x1≤x2……≤xn≤b)。
若在函数类中存在以简单函数P(x) ，使得P(xi)=yi,则称P(x) 为f(x)的插值函数.称x1,x2,…xn 为插值节点，称[a,b]为插值区间。
定理：n次代数插值问题的解存在且唯一。
牛顿插值法C程序程序框图#include<stdio.h>void main(){float x[11],y[11][11],xx,temp,newton;int i,j,n;printf("Newton插值:\n请输入要运算的值:x=");scanf("%f",&xx);printf("请输入插值的次数(n<11):n=");scanf("%d",&n);printf("请输入%d组值:\n",n+1);for(i=0;i<n+1;i++){ printf("x%d=",i);scanf("%f",&x[i]);printf("y%d=",i);scanf("%f",&y[0][i]);}for(i=1;i<n+1;i++)for(j=i;j<n+1;j++){ if(i>1)y[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-i]);elsey[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-1]);printf("%f\n",y[i][i]);}temp=1;newton=y[0][0];for(i=1;i<n+1;i++){ temp=temp*(xx-x[i-1]);newton=newton+y[i][i]*temp;}printf("求得的结果为:N(%.4f)=%9f\n",xx,newton);牛顿插值法Matlab程序function f = Newton(x,y,x0)syms t;if(length(x) == length(y))n = length(x);c(1:n) = 0.0;elsedisp('x和y的维数不相等！');return;endf = y(1);y1 = 0;l = 1;for(i=1:n-1)for(j=i+1:n)y1(j) = (y(j)-y(i))/(x(j)-x(i));endc(i) = y1(i+1);l = l*(t-x(i));f = f + c(i)*l;simplify(f);y = y1;if(i==n-1)if(nargin == 3)f = subs(f,'t',x0);elsef = collect(f); %将插值多项式展开f = vpa(f, 6);endend牛顿插值法摘要：值法利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。
数值计算方法插值法讲解
又因为lk1(xk1) 1，故a(xk1 xk )(xk1 xk1) 1，得：
a
(xk 1
xk
1 )( xk 1
xk1) ，从而lk1(x)
(x (xk 1
xk xk
)(x xk1) ， )(xk1 xk1)
lk
(x)
(x ( xk
问题的提出
插值问题的数学提法：已知函数y f (x)在n 1个 点x0 , x1, , xn上的函数值yi f (xi ), (i 0,1, , n), 求一 个多项式y P(x)，使其满足P(xi ) yi , (i 0,1, , n). 即要求该多项式的函数曲线要经过y f (x)上已知的
平面上两点 xk , yk , xk1, yk1 ，求一条直线过该已
知两点。
线性插值
插值函数和插值基函数
由直线的点斜式公式可知：
P1(x)
yk
yk 1 xk 1
yk xk
(x
xk )，把此式按照
yk和yk1写成两项:P 1(x)
x xk1 xk xk 1
由于li (xk ) 0,k i，故li (x)有因子：
(x x0 ) (x xi1)(x xi1) (x xn )，因其已经是n 次多项式，故而仅相差一个常数因子。令：
li (x) a(x x0 ) (x xi1)(x xi1) (x xn )
插值法的概念
已知函数在n+1个点x0 ,x1 ,…,xn 上的函数值 yi=f(xi ), (i=0,1,…,n) ，求一个简单函数y=P(x),使其满 足: P(xi )=yi ,(i=0,1,…,n) 。即要求该简单函数的 曲线要经过y=f(x)上已知的这个n+1个 点： (x0 ,y0 ),(x1 ,y1 ),…,(xn ,yn ),同时在其它 x∈[a,b]上要估计误差: R(x) = f(x) - P(x)
2.3均差与牛顿插值公式
可以进一步简化，计算也简单得多.
为了得到等距节点的插值公式，先介绍差分的概念.
设函数 y f ( x) 在等距节点 xk x0 kh (k 0,1,, n) 上
的值 f k f ( xk ) 为已知，这里 h 为常数，称为步长.
13
定义
记号 f k f k 1 f k ,
n j
（2）函数值可用差分表示，如 轾 n 骣 n j n n 犏 琪 f n+k = E f k = ( I +D ) fk = 邋 D fk = 琪 犏 j j =0 桫 臌
骣 n j 琪 D fk . 琪 j j =0 桫
n
15
f k 1 f k f k (3) 差商与差分关系，如： f [ xk , x k 1] , xk 1 xk h f [ xk 1, x k 2 ] f [ xk , x k 1] 2 f k f [ xk , x k 1, x k 2 ] , 2 xk 2 xk 2h
称为 f ( x) 在 x k处以 h 为步长的一阶（向前）差分. 利用一阶差分可定义二阶差分为
2 f k f k 1 f k f k 2 2 f k 1 f k .
一般地可定义 m 阶差分为
m f k m1 f k 1 m1 f k .
14
引进不变算子I：Ifk f k , 移位算子E : Ef k f k 1.
1 1 1 1 4 1 1 1 3 N 3 ( ) 1 2 2 ( 1) ( 1) ( 2) 2 2 2 2 2 3 2 2 2
4 x( x 1)( x 2) 3
12
2.3.3 差分与等距节点插值
为了得到等距节点的插值公式，先介绍差分的概念.
设函数 y f ( x) 在等距节点 xk x0 kh (k 0,1,, n) 上
的值 f k f ( xk ) 为已知，这里 h 为常数，称为步长.
13
定义
记号 f k f k 1 f k ,
n j
（2）函数值可用差分表示，如 轾 n 骣 n j n n 犏 琪 f n+k = E f k = ( I +D ) fk = 邋 D fk = 琪 犏 j j =0 桫 臌
骣 n j 琪 D fk . 琪 j j =0 桫
n
15
f k 1 f k f k (3) 差商与差分关系，如： f [ xk , x k 1] , xk 1 xk h f [ xk 1, x k 2 ] f [ xk , x k 1] 2 f k f [ xk , x k 1, x k 2 ] , 2 xk 2 xk 2h
称为 f ( x) 在 x k处以 h 为步长的一阶（向前）差分. 利用一阶差分可定义二阶差分为
2 f k f k 1 f k f k 2 2 f k 1 f k .
一般地可定义 m 阶差分为
m f k m1 f k 1 m1 f k .
14
引进不变算子I：Ifk f k , 移位算子E : Ef k f k 1.
1 1 1 1 4 1 1 1 3 N 3 ( ) 1 2 2 ( 1) ( 1) ( 2) 2 2 2 2 2 3 2 2 2
4 x( x 1)( x 2) 3
12
2.3.3 差分与等距节点插值
计算方法 3 牛顿插值
计算方法（2016/2017 第一学期） 贾飞 西南科技大学 制造科学与工程学院
2
分析
显然， L2 ( x0 ) y0，L2 ( x1 ) y1；利用插值 条件， L2 ( x2 ) y2 y1 y0 y 2 y0 ( x2 x0 ) a ( x2 x0 )( x2 x1 ) x1 x0 y2 y0 y1 y0 x2 x0 x1 x0 y1 y0 a L2 y0 ( x x0 ) x2 x1 x1 x0 y2 y0 y1 y0 x2 x0 x1 x0 ( x x0 )( x x1 ) x2 x1
计算方法（2016/2017 第一学期） 贾飞 西南科技大学 制造科学与工程学院
9
牛顿基本插值公式
其中，线性部分 N 1 ( x ) f ( x0 ) f [ x0 , x1 ]( x x0 ) 满足 N 1 ( x0 ) f ( x 0 ) f ( x1 ) f ( x0 ) N 1 ( x1 ) f ( x0 ) ( x1 x0 ) f ( x1 ) x1 x0 N 1 ( x ) 为 f ( x ) 以 x0，x1 为插值结点的 线性插值函数，即： N （ 1 x ) L1 ( x )
西南科技大学
制造科学与工程学院
16
解：构造差商表如下，
xi -2 0 f(xi ) 1阶 17 1 -8 1 17 3 8 1.25 2阶 3阶
1
2
2
19
N 3 ( x ) 17 8( x 2) 3( x 2) x 1.25( x 2) x ( x 1) f 0.9 N 3 (0.9) 1.30375, R3 0.9 1.25 0.9 2 0.9 0.9 1 0.9 2 0.358875
2
分析
显然， L2 ( x0 ) y0，L2 ( x1 ) y1；利用插值 条件， L2 ( x2 ) y2 y1 y0 y 2 y0 ( x2 x0 ) a ( x2 x0 )( x2 x1 ) x1 x0 y2 y0 y1 y0 x2 x0 x1 x0 y1 y0 a L2 y0 ( x x0 ) x2 x1 x1 x0 y2 y0 y1 y0 x2 x0 x1 x0 ( x x0 )( x x1 ) x2 x1
计算方法（2016/2017 第一学期） 贾飞 西南科技大学 制造科学与工程学院
9
牛顿基本插值公式
其中，线性部分 N 1 ( x ) f ( x0 ) f [ x0 , x1 ]( x x0 ) 满足 N 1 ( x0 ) f ( x 0 ) f ( x1 ) f ( x0 ) N 1 ( x1 ) f ( x0 ) ( x1 x0 ) f ( x1 ) x1 x0 N 1 ( x ) 为 f ( x ) 以 x0，x1 为插值结点的 线性插值函数，即： N （ 1 x ) L1 ( x )
西南科技大学
制造科学与工程学院
16
解：构造差商表如下，
xi -2 0 f(xi ) 1阶 17 1 -8 1 17 3 8 1.25 2阶 3阶
1
2
2
19
N 3 ( x ) 17 8( x 2) 3( x 2) x 1.25( x 2) x ( x 1) f 0.9 N 3 (0.9) 1.30375, R3 0.9 1.25 0.9 2 0.9 0.9 1 0.9 2 0.358875
计算方法与误差理论-4
插值法
n+1元线性方程组
根据插值多项式的定义，可得n+1个方程 组成的方程组
a 0 a1 x0 a n x y 0
n 0
a 0 a1 x1 a x y1
n n 1
a 0 a1 x n a n x y n
n n
插值法
定理1：满足条件Pn(xj)=yj(j=0,1,…,n)的 n次多项式Pn(x)=a0+a1x+a2x2+…+anxn 是存在而且唯一的 即：n+1个插值条件唯一确定一个n次多 项式 注意：如果不限制多项式的次数，插值 多项式并不唯一
L2 ( x)
( x x0 )(x x2 ) ( x x0 )(x x1 ) ( x x1 )(x x2 ) y0 y1 y2 ( x0 x1 )(x0 x2 ) ( x1 x0 )(x1 x2 ) ( x2 x0 )(x2 x1 )
零阶差商：f(xi)为f(x)关于节点xi的零阶差 商f[xi]
插值法—牛顿插值多项式
差商性质
k阶差商f[x0,x1,…xk]是由函数值f(x0),f(x1), f(x2),…f(xk)线性组合而成的，即：
f [ x0 , x1 ,, x k ]
k
f ( xm )
m 0
(x
i 0 im
k
m
xi )
插值法—牛顿插值多项式
差商性质
差商具有对称性，即在k阶差商f[x0,x1,…xk] 中任意调换2个节点xl和xm的顺序，其值不 变。（只改变求和次序） k阶差商和k阶导数之间有如下重要关系： (k ) f ( ) f [ x0 , x1 ,, xk ] k! (min{x0 , x1 ,, xk }, max{x0 , x1 ,, xk })
计算方法—插值法
2018/10/20
lk ( x) lk 1 ( x) 1
13
2.2 拉格朗日插值
Chapter2 插值法
L1(X)
L1(X)
∴ lg2.718 ≈L1 (2.718)=0.43428
2018/10/20 14
2.2 拉格朗日插值
2-2 线性插值与抛物插值
利用线性插值法对函数y=f(x) 进行逼近时，即用直线y=L1(x)代替 曲线y=f(x)。
Chapter2 插值法
显然当插值区间较大或曲线[x0,x1]凸凹变化大时，线 性插值的误差很大。 为了减小这种误差，我们用简单的曲线(抛物线)去近似
代替复杂曲线y=f(x) 。二次多项式函数的曲线为抛物线， 所以我们构造插值函数L2(x) ，即n=2。
2018/10/20 15
2.2 拉格朗日插值
5
2018/10/20
2.1 引言
多项式插值
Chapter2 插值法
对于n+1个基点的插值问题，如果要求插值函数是次 数不超过n的多项式，记为Pn(x)，则相应的问题就是多项 式插值，并且把Pn(x)称为插值多项式。 实际上，我们所考虑的插值函数通常都是多项式函数
或分段多项式函数。由于次数不超过n的多项式的一般形 式为： Pn(x)=a0+a1x+a2x2+…+anxn
当n=20,在109次/秒的计算机上计算需几万年！
2018/10/20 12
2.2 拉格朗日插值
2-2 线性插值与抛物插值 已知函数y=f(x)的函数 插值法
y yk
yk+1
求次数不超过1的多项式L1(x)=a0+a1x 满足插值条件L1(xk)=yk, L1(xk+1)=yk+1。
2.2 牛顿插值法
f ( x ) = f ( x 0 ) + f [ x 0 , x 1 ]( x - x 0 ) + f [ x , x 0 , x 1 ]( x - x 0 )( x - x 1 )
又
f [ x , x 0 , x1 , x 2 ] =
f [ x 0 , x1 , x 2 ] - f [ x , x 0 , x1 ] x2 - x
a2=
依次递推可得到a3, …, an. 为写出系数 ak的一般表达式, 均差定义
2.3.2 均差及其性质
1、均差的定义 称 f [ x0 , xk ] =
f ( xk ) - f ( x0 ) xk - x0
为 f ( x ) 关于点 x 0 , x k 的一阶差商。 称 f [ x 0 , x1 , x k ] =
注：均差与节点的排列次序无关——均差 的对称性
f[x0,x1,…,xn]= f[x1,x0,x2,…,xn]=… = f[x1, …, xn ,x0]
因此 f [ x 0 , x 1 , , x k ] = f [ x 1 , x k - 1 , x 0 , x k ]
= f [ x 1 , x 2 , , x k -1 , x k ] - f [ x 1 , x 2 , , x k -1 , x 0 ] xk - x0 f [ x 1 , x 2 , , x k -1 , x k ] - f [ x 0 , x 1 , x 2 , , x k -1 ] xk - x0
f (xj)
k
j=0
j=0
( x j - xi )
i=0 j i
1ºn 阶均差可表示为函数值f(x0), f(x1),…, f(xn) 的线性组合
数值计算方法插值法
f[x1,x2,x3] …
f[x0,x1,x2 ,x3]
例阶2.1差1商求值f(xi)= x3在节点 x=0, 2, 3, 5, 6上的各
解xi :
计算得如下表 f[xi] f[xi,xi+1]
f[xi,xi+1,xi+2 ]
f[xi,xi+1,xi+2 ,xi+2]
00
28
80 4 20
27 8 19 19 4 5
an x0 n an1x0 n1 a1x0 a0 f (x0 )
an x1n
an1
x n1 1
a1x1 a0
f (x1 )
an xn n an1xn n1 a1xn a0 f (xn )
这是惟一一个性关说于明待，定不参论数用何种方法来构a造的0，,n+也a11阶不, 线论性用, 方何an种形式来表示插值多项式,
由线性代数知,任何一个不高于n次的多项式, 都可以表示成函数
1, x x0 , (x x0 )(x x1 ),, (x x0 )(x x1 )(x xn1 )
的线性组合, 也就是说, 可以把满足插值条件 p(xi)=yi (i=0,1,…,n)的n次插值多项式, 写成如下形式
a0 a1(x x0) a2(x x0)(x x1) an (x x0)(x x1)(x xn1)
f[x0 , x1]=
f(x1)- f(x0) x1 – x0
f[x1 , x0]
f(x0)- f(x1) =
x0 – x1
f x0 , x1, x2 f x1, x2 , x0 f x0 , x2 , x1
性质3 若f[x, x0, x1 , …, xk ]是 x 的 m 次多项式, 则 f[x, x0, x1 ,…, xk , xk+1]是 x 的 m-1 次多项式
计算方法插值法(均差与牛顿插值公式)
为f ( x)关于节点 x0 , xk 一阶均差 (差商)
2018/11/7
5
2018/11/7
6
二、均差具有如下性质：
f [ x0 , x1 ,, xk 1 , xk ]
j 0
k
f (x j ) ( x j x0 )( x j x j 1 )(x j x j 1 )( x j xk )
2018/11/7
27
fk fk 1 fk 为f ( x)在 xk 处的二阶向前差分
2
依此类推
m f k m1 f k 1 m1 f k
为f ( x)在 xk 处的m阶向前差分
2018/11/7
28
差分表
xk f k 一阶差分 x0 f 0 x1 f 1 二阶差分 三阶差分 四阶差分
2018/11/7
31
等距节点插值公式
一、牛顿前插公式
2018/11/7
32
2018/11/7
33
二、牛顿插值公式与拉格朗日插值相比
牛顿插值法的优点是计算较简单,尤其是增加 节点时,计算只要增加一项,这是拉格朗日插值 无法比的. 但是牛顿插值仍然没有改变拉格朗日插值的 插值曲线在节点处有尖点，不光滑，插值多 项式在节点处不可导等缺点.
2018/11/7
25
2018/11/7
26
§
2.3.4 差分及其性质
一、差分
fk , 定义3. 设f ( x)在等距节点xk x0 kh 处的函数值为 k 0 ,1, , n , 称
f k f k 1 f k
k 0,1,, n 1
为f ( x)在 xk 处的一阶向前差分
Ch2(2)牛顿插值法
于是
f (0.596) N 4 (0.596) 0.63192,
17
截断误差
R4 ( x ) f [ x0 , , x5 ] 5 (0.596) 3.63 10 9.
差商具有如下性质(请同学们自证)：
(1) f ( x )的k阶差商f [ x0 , x1 , , xk 1 , xk ]可由函数值 f ( x0 ), f ( x1 ), , f ( xk )的线性组合表示, 且
6
f [ x0 Hale Waihona Puke x1 ,, xk 1 , xk ]
f ( xi ) i 0 ( xi x0 )( xi xi 1 )( xi xi 1 )( xi xk )
形式上太复杂,计算量很大,并且重复计算也很多 由线性代数的知识可知,任何一个n次多项式都可以表示成
1, x x0 , ( x x0 )( x x1 ), , ( x x0 )( x x1 )( x xn 1 )
共n+1个多项式的线性组合 那么，是否可以将这n+1个多项式作为插值基函数呢？
f [ x0 , x1 ,, xk ]
f
(k )
( ) k!
用余项的 相等证明
7
差商的计算方法(表格法):
xk x0 x1 x2 x3 x4
f ( xk ) 一阶均差 f ( x0 ) f ( x1 ) f ( x2 ) f ( x3 ) f ( x4 ) f [ x0 , x1 ] f [ x1 , x2 ] f [ x2 , x3 ] f [ x3 , x4 ]
二阶均差
三阶均差
四阶均差
f [ x0 , x1 , x2 ] f [ x1 , x2 , x3 ] f [ x 2 , x3 , x 4 ] f [ x0 , x1 , x2 , x3 ] f [ x1 , x2 , x3 , x4 ] f [ x0 , x1 , x2 , x3 , x4 ]
均差与牛顿插值jg3
其中,
,
N1 ( x) = f ( x0 ) + f [ x0 , x1 ]( x − x0 ) = y0 + y0 − y1 ( x − x0 ) x0 − x1
。
这就是牛顿一次插值多项式，也就是点斜式直线方程。 当 n=2 时,
f ( x) = f ( x0 ) + f [ x0 , x1 ]( x − x0 ) + f [ x 0 , x 1 , x 2 ]( x − x 0 )( x − x 1 ) + f [ x , x 0 , x 1 , x 2 ]( x − x 0 )( x − x 1 )( x − x 2 ) N2 ( x) = f ( x0 ) + f [ x0 , x1 ]( x − x0 ) + f [ x 0 , x 1 , x 2 ]( x − x 0 )( x − x 1 )
;
f [ x0 , x 1 , x 2 ] = = = =
y y y y 1 1 ( 0 + 1 )− ( 1 + 2 ) x0 − x2 x0 − x1 x1 − x0 x0 − x2 x1 − x2 x2 − x1
y0 y y2 1 1 + 1 ( − )+ (x0 −x1)(x0 −x2) x0 −x2 x1 −x0 x1 −x2 (x2 −x0)(x2 −x1) y0 y1 y2 + + (x0 − x1)(x0 − x2 ) (x1 − x0 )(x1 − x2 ) (x2 − x0 )(x2 − x1)
这就是牛顿二次插值多项式。 显然,
N2 ( x0 ) = f ( x0 )
,
N2 ( x1 ) = f ( x0 ) + N2 ( x2 ) = f ( x0 ) +
,
N1 ( x) = f ( x0 ) + f [ x0 , x1 ]( x − x0 ) = y0 + y0 − y1 ( x − x0 ) x0 − x1
。
这就是牛顿一次插值多项式，也就是点斜式直线方程。 当 n=2 时,
f ( x) = f ( x0 ) + f [ x0 , x1 ]( x − x0 ) + f [ x 0 , x 1 , x 2 ]( x − x 0 )( x − x 1 ) + f [ x , x 0 , x 1 , x 2 ]( x − x 0 )( x − x 1 )( x − x 2 ) N2 ( x) = f ( x0 ) + f [ x0 , x1 ]( x − x0 ) + f [ x 0 , x 1 , x 2 ]( x − x 0 )( x − x 1 )
;
f [ x0 , x 1 , x 2 ] = = = =
y y y y 1 1 ( 0 + 1 )− ( 1 + 2 ) x0 − x2 x0 − x1 x1 − x0 x0 − x2 x1 − x2 x2 − x1
y0 y y2 1 1 + 1 ( − )+ (x0 −x1)(x0 −x2) x0 −x2 x1 −x0 x1 −x2 (x2 −x0)(x2 −x1) y0 y1 y2 + + (x0 − x1)(x0 − x2 ) (x1 − x0 )(x1 − x2 ) (x2 − x0 )(x2 − x1)
这就是牛顿二次插值多项式。 显然,
N2 ( x0 ) = f ( x0 )
,
N2 ( x1 ) = f ( x0 ) + N2 ( x2 ) = f ( x0 ) +
计算方法插值法
1)
Rn ( x ) K ( x) ( x - xi )
i 0
n
考察 j ( t ) Rn ( t ) - K ( x ) ( t - x i )
i0
n
j(t)有 n+2 个不同的根 x0 …
f (n ( x ) - L(nn
1)
xn x， j ( n1) ( x ) 0, x (a, b)
x - x0 y x1 - x 0 1
l ( x) y
i 0 i
1
i
l0(x)
l1(x)
n1
希望找到li(x)，i = 0, …, n 使得 li(xj)=ij ；然后令
Pn ( x )
l (x) y
i0 i
n
i
，则显然有Pn(xi) = yi 。
每个 li 有 n 个根 x0 … xi-1， xi+1 … xn li ( x) Ci ( x - x j )
插值法 比较古老, 常用的方法。 当未知函数 y = f(x) 非常复杂时，在一系列节 点 x0 … xn 处测得函数值： y0 = f(x0) … yn = f(xn) 由此构造一个简单易算的近似函数 P(x) f(x)， 满足条件P(xi) = f(xi) (i = 0, … n)，称P(x) 为f(x) 的插值函数。 最常用的插值函数是多项式
项式是唯一存在的。 证明：
i 0, ... , n 的 n 阶插值多
若除了Ln(x) 外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 。 考察 Qn ( x) Pn ( x) - Ln ( x) , 则 Qn 的阶数 n 而 Qn 有 n + 1 个不同的根 x0 … xn
Rn ( x ) K ( x) ( x - xi )
i 0
n
考察 j ( t ) Rn ( t ) - K ( x ) ( t - x i )
i0
n
j(t)有 n+2 个不同的根 x0 …
f (n ( x ) - L(nn
1)
xn x， j ( n1) ( x ) 0, x (a, b)
x - x0 y x1 - x 0 1
l ( x) y
i 0 i
1
i
l0(x)
l1(x)
n1
希望找到li(x)，i = 0, …, n 使得 li(xj)=ij ；然后令
Pn ( x )
l (x) y
i0 i
n
i
，则显然有Pn(xi) = yi 。
每个 li 有 n 个根 x0 … xi-1， xi+1 … xn li ( x) Ci ( x - x j )
插值法 比较古老, 常用的方法。 当未知函数 y = f(x) 非常复杂时，在一系列节 点 x0 … xn 处测得函数值： y0 = f(x0) … yn = f(xn) 由此构造一个简单易算的近似函数 P(x) f(x)， 满足条件P(xi) = f(xi) (i = 0, … n)，称P(x) 为f(x) 的插值函数。 最常用的插值函数是多项式
项式是唯一存在的。 证明：
i 0, ... , n 的 n 阶插值多
若除了Ln(x) 外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 。 考察 Qn ( x) Pn ( x) - Ln ( x) , 则 Qn 的阶数 n 而 Qn 有 n + 1 个不同的根 x0 … xn
Ch2_3均差与牛顿插值
6
f [ x0 , x1 ,, xk 1 , xk ]
f ( xi ) i 0 ( xi x0 )( xi xi 1 )( xi xi 1 )( xi xk )
k
(2) 差商具有对称性,即任意调换节点的次序,差商的值不变
如
f [ x0 , x1 , x2 ] f [ x0 , x2 , x1 ] f [ x2 , x1 , x0 ]
kn
f ( n 1) ( ) 另外 f [ x , x0 , x1 ,, xn ] ( n 1)!
f ( k ) ( ) f [ x0 , x1 ,, xk ] k!
Newton插值 估计误差的 重要公式
15
例2
给出 f (x)的函数表（见表2-2），求4次牛顿插
值多项式，并由此计算 f (0.596) 的近似值.
x2的二次插值和x0,x1,x2,x3的三次插值多项式.
解
[x0,x1,x2,x3]=-1,于是有
N1(x)=5-2(x+2)=1-2x N2(x)=1-2x+3(x+2)(x+1)=3x2+7x+7 N3(x)=3x2+7x+7-(x+2)(x+1)(x-1)=-x3+x2+8x+9 i xi (xi) 0 -2 5 1 -1 3 2 1 17 3 2 21
为f ( x)关于xi , x j , xk的二阶差商
依此类推
5
f [ xi0 , xi1 ,, xik 1 , xik ]
f [ xi0 , xi1 ,, xik 1 ] f [ xi0 , xi1 ,, xik 2 , xik ] xik 1 xik
f [ x0 , x1 ,, xk 1 , xk ]
f ( xi ) i 0 ( xi x0 )( xi xi 1 )( xi xi 1 )( xi xk )
k
(2) 差商具有对称性,即任意调换节点的次序,差商的值不变
如
f [ x0 , x1 , x2 ] f [ x0 , x2 , x1 ] f [ x2 , x1 , x0 ]
kn
f ( n 1) ( ) 另外 f [ x , x0 , x1 ,, xn ] ( n 1)!
f ( k ) ( ) f [ x0 , x1 ,, xk ] k!
Newton插值 估计误差的 重要公式
15
例2
给出 f (x)的函数表（见表2-2），求4次牛顿插
值多项式，并由此计算 f (0.596) 的近似值.
x2的二次插值和x0,x1,x2,x3的三次插值多项式.
解
[x0,x1,x2,x3]=-1,于是有
N1(x)=5-2(x+2)=1-2x N2(x)=1-2x+3(x+2)(x+1)=3x2+7x+7 N3(x)=3x2+7x+7-(x+2)(x+1)(x-1)=-x3+x2+8x+9 i xi (xi) 0 -2 5 1 -1 3 2 1 17 3 2 21
为f ( x)关于xi , x j , xk的二阶差商
依此类推
5
f [ xi0 , xi1 ,, xik 1 , xik ]
f [ xi0 , xi1 ,, xik 1 ] f [ xi0 , xi1 ,, xik 2 , xik ] xik 1 xik
牛顿插值法原理及应用汇总
牛顿插值法插值法是利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。
如果这特定函数是多项式，就称它为插值多项式。
当插值节点增减时全部插值基函数均要随之变化，这在实际计算中很不方便。
为了克服这一缺点，提出了牛顿插值。
牛顿插值通过求各阶差商，递推得到的一个公式：f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0 )...(x-xn-1)+Rn(x)。
插值函数插值函数的概念及相关性质[1]定义：设连续函数y-f(x) 在区间[a,b]上有定义，已知在n+1个互异的点x0,x1,…xn上取值分别为y0,y1,…yn （设a≤ x1≤x2……≤xn≤b)。
若在函数类中存在以简单函数P(x) ，使得P(xi)=yi,则称P(x) 为f(x)的插值函数.称x1,x2,…xn 为插值节点，称[a,b]为插值区间。
定理：n次代数插值问题的解存在且唯一。
牛顿插值法C程序程序框图#include<stdio.h>void main(){float x[11],y[11][11],xx,temp,newton;int i,j,n;printf("Newton插值:\n请输入要运算的值:x=");scanf("%f",&xx);printf("请输入插值的次数(n<11):n=");scanf("%d",&n);printf("请输入%d组值:\n",n+1);for(i=0;i<n+1;i++){ printf("x%d=",i);scanf("%f",&x[i]);printf("y%d=",i);scanf("%f",&y[0][i]);}for(i=1;i<n+1;i++)for(j=i;j<n+1;j++){ if(i>1)y[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-i]);elsey[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-1]);printf("%f\n",y[i][i]);}temp=1;newton=y[0][0];for(i=1;i<n+1;i++){ temp=temp*(xx-x[i-1]);newton=newton+y[i][i]*temp;}printf("求得的结果为:N(%.4f)=%9f\n",xx,newton);牛顿插值法Matlab程序function f = Newton(x,y,x0)syms t;if(length(x) == length(y))n = length(x);c(1:n) = 0.0;elsedisp('x和y的维数不相等！');return;endf = y(1);y1 = 0;l = 1;for(i=1:n-1)for(j=i+1:n)y1(j) = (y(j)-y(i))/(x(j)-x(i));endc(i) = y1(i+1);l = l*(t-x(i));f = f + c(i)*l;simplify(f);y = y1;if(i==n-1)if(nargin == 3)f = subs(f,'t',x0);elsef = collect(f); %将插值多项式展开f = vpa(f, 6);endend牛顿插值法摘要：值法利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。
第5章 3.牛顿插值公式
满足 N 1 ( x0 ) = f ( x0 ) f ( x1 ) − f ( x0 ) N 1 ( x1 ) = f ( x0 ) + ( x1 − x0 ) = f ( x1 ) x1 − x0
∴ N 1 ( x )为f ( x )以x0 , x1为插值结点的线性插值 函数
即N（x ) = L1 ( x ) 1
一般地构造以下基函数 求作n 问题 求作n次多项式 N n ( x )
N n ( x ) = c0 ⋅ 1 + c1 ( x − x0 ) + c2 ( x − x0 )( x − x1 ) + L + cn ( x − x0 )( x − x1 )( x − x2 )L ( x − xn −1 )
将f [ x0 , x1 ]代入得
f ( x ) = f ( x0 ) + f [ x0 , x1 ]( x − x0 ) + f [ x0 , x1 , x ]( x − x0 )( x − x1 )
其中线性部分 N 1 ( x ) = f ( x0 ) + f [ x0 , x1 ]( x − x0 )
注意：均差表中，对角线上的均差是构造牛顿型插值公式的重要数据。 注意：均差表中，对角线上的均差是构造牛顿型插值公式的重要数据。
已知函数y=f(x)的观测数据如表， y=f(x)的观测数据如表 例 已知函数y=f(x)的观测数据如表，试构造差商 并求f[2,4,5] f[2,4,5,6]的值 f[2,4,5]及 的值。 表，并求f[2,4,5]及f[2,4,5,6]的值。x 0 2 4 5 解
1 2
n−1 −
…………
f [ x, x0 , ... , xn−1 ] = f [ x0 , ... , xn ] + ( x − xn ) f [ x, x0 , ... , xn ] n−
∴ N 1 ( x )为f ( x )以x0 , x1为插值结点的线性插值 函数
即N（x ) = L1 ( x ) 1
一般地构造以下基函数 求作n 问题 求作n次多项式 N n ( x )
N n ( x ) = c0 ⋅ 1 + c1 ( x − x0 ) + c2 ( x − x0 )( x − x1 ) + L + cn ( x − x0 )( x − x1 )( x − x2 )L ( x − xn −1 )
将f [ x0 , x1 ]代入得
f ( x ) = f ( x0 ) + f [ x0 , x1 ]( x − x0 ) + f [ x0 , x1 , x ]( x − x0 )( x − x1 )
其中线性部分 N 1 ( x ) = f ( x0 ) + f [ x0 , x1 ]( x − x0 )
注意：均差表中，对角线上的均差是构造牛顿型插值公式的重要数据。 注意：均差表中，对角线上的均差是构造牛顿型插值公式的重要数据。
已知函数y=f(x)的观测数据如表， y=f(x)的观测数据如表 例 已知函数y=f(x)的观测数据如表，试构造差商 并求f[2,4,5] f[2,4,5,6]的值 f[2,4,5]及 的值。 表，并求f[2,4,5]及f[2,4,5,6]的值。x 0 2 4 5 解
1 2
n−1 −
…………
f [ x, x0 , ... , xn−1 ] = f [ x0 , ... , xn ] + ( x − xn ) f [ x, x0 , ... , xn ] n−
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
x3
5 4
x2
x
l3 (x)
(x (4
0)(x 0)(4
1)( x 1)(4
2) 2)
1 24
x3
1 8
x2
1 12
x
Lagrange插值多项式为
L3(x) f (xi )li (x) l0 (x) 9l1(x) 23l2 (x) 3l3(x)
2020/8/18
11 x3 45 x2 1 x]上存在n阶导数，且节点
x0 , xn [a,b], 则n阶均差与导数关系如下：
2020/8/18
10
三、均差的计算方法(表格法): 均差表
xk f (xk ) 一阶差商 x0 f ( x0 )
f [ x0 , x1 ]
x1 f ( x1 )
f [x1 , x2 ]
l0 (x)
(x (0
1)( x 1)(0
2)(x 4) 2)(0 4)
1 8
x3
7 8
x2
7 4
x
1
l1 ( x)
(x 0)(x 2)(x 4) (1 0)(1 2)(1 4)
1 3
x3
2x2
8 3
x
l2 (x)
(x 0)(x (2 0)(2
1)(x 4) 1)(0 4)
1 4
4 42
21
（2）Newton插值多项式：建立差商表为
一阶差商 二阶差商 三阶差商
01
19
8
2 23
14
3
43
-10
-8
11
4
2020/8/18
22
Newton插值多项式为
N3
(
x)
1
8(
x
0)
3(
x
0)(
x
1)
11 4
(
x
0)(
x
1)(
x
2)
（3）唯一性验证：将Newton插值多项式按x幂次排列， 便得到
2020/8/18
3
Pn (x0 ) a0 f0
当
Pn
(
x2
)
a0
a1(x2
Pn (x1) a0 a1(x1 x0 ) x0 ) a2 (x2 x0 )(x2 x1)
f1 f2
a2
a0 f0
a1
f1 f0 x1 x0
f2 f0 f1 f0
x2 x0
x1 x0
P1 ( x)
f0
f1 x1
f0 x0
(x
x0 )
( fi f (xi ) yi )
出发，将它推广到具有n+1个插值点的情况，可把插值 多项式表示为
Pn (x) a0 a1(x x0 ) a2 (x x0 )(x x1) an (x x0 )(x x1)(x xn1)
2.3.2 牛顿插值公式
2020/8/18
13
2020/8/18
14
Rn(x)
f (x) Nn (x)
f (n1) ( )
(n 1)!
n1
(
x)
f [x, x0 , x1 ,, xn ]n1(x)
我们称 Nn(x) 为牛顿(Newton)均差插值多项式。
2020/8/18 称 Rn (x) 为牛顿均差插值多项式的截断误差。
x2 x1
依次可得到 a3, a4 , , an 。为写出系数的一般表达式，
2020/8/18
4
现引入差商（均差）定义。
一、差商(均差)
定义2. 设f (x)在互异的节点 xi 处的函数值为 fi ,i 0,1,, n 称
f [x0 , xk ]
f (xk ) f (x0 ) xk x0
N3
(x)
11 4
x3
45 4
x2
1 2
x
1
L3
(x)
2020/8/18
23
❖ 练习： 已知由数据(0，0)，(0.5，y)，(1，3)，(2，2) 构造出的三次插值多项式P3(x)的x3的系数是6， 试确定数据y。
f0
f1
f2
(x0 x1)(x0 x2 ) (x1 x0 )(x1 x2 ) (x2 x0 )(x2 x1)
2020/8/18
8
这个性质也表明差商与节点的排列顺序无关 (差商的对称性)。即
f [x0 , x1, , xk ] f [x1, x0 , x2 , , xk ] f [x1, x2 , , xk , x0 ]
例
f [x0 , x1]
f (x0 ) f (x1) x0 x1
f0 f1 x0 x1 x1 x0
f [x0 , x1 , x2 ]
f [x0 , x1 ] f [x0 , x2 ] x1 x2
1 ( f0 f1 ) 1 ( f0 f2 ) x1 x2 x0 x1 x1 x0 x1 x2 x0 x2 x2 x0
第二章 插值法
§ 2.3 均差与牛顿插值公式
2020/8/18
1
§ 2.3.1 均差及其性质
我们知道,拉格朗日插值多项式的插值基函数为
l j(x)
n i0
(x xi ) (x j xi )
i j
j 0,1,2,,n
形式上太复杂,计算量很大,并且重复计算也很多
2020/8/18
2
拉格朗日插值公式可看作直线方程两点式的推广，若从 直线方程点斜式
2020/8/18
规定函数值为零阶均差
四阶差商
f [x0 , x1 ,, x4 ]
11
例1:已知下表，计算三阶差商
xi 1 f (xi ) 0
347 2 15 12
解：列表计算
2020/8/18
xi
f (xi )
一阶差 商
二阶差商
三阶差 商
10
32 1
4 15 13
4
7 12 -1
-3.5
-1.25 12
二阶差商
f [x0 , x1 , x2 ]
三阶差商
f [x0 , x1 , x2 , x3 ]
x2 f ( x2 )
f [ x2 , x3 ]
x3 f ( x3 )
f [ x3 , x4 ]
x4 f (x4 )
f [x1 , x2 , x3 ] f [x2 , x3 , x4 ]
f [x1 , x2 , x3 , x4 ]
(k 0)
为f (x)关于节点 x0 , xk 一阶均差(差商)
2020/8/18
5
2020/8/18
6
二、均差具有如下性质：
f [x0 , x1 ,, xk 1 , xk ]
k j0
(xj
x0 )(x j
f (xj) x j1)(x j
x j1)(x j
xk )
2020/8/18
7
15
2020/8/18
16
2020/8/18
17
2020/8/18
18
显然：
2020/8/18
19
例2：依据如下函数值表建立不超过三次的Lagrange插值 多项式及Newton插值多项式，并验证插值多项式的唯一性。
x
0
f(x)
1
1
2
4
9
23
3
2020/8/18
20
解：(1)建立Lagrange插值多项式：基函数为