计算方法第四章 插值法

Pn ( x) = f ( x0 ) f ( x0 )( x x0 ) f ( x)
f ( n ) ( x0 ) ( x x0 ) n n!
第4章 插值法
多项式插值


（待定系数法）
代数多项式形式简单，便于计算，
且在某些情况下与给定的函数有较好的逼近的特性 y y 0） （ x0， 1个点插值 x
i=0 n
n
说明： Pn( xk ) = yi l i ( x k )
i=0
满足插值条件 φ n ( xi )= y i ，i =0，1， …, n
第4章 插值法
关键是 : l i ( x )= ？
但是将 x i 代入， 此式不等于
注意到 l i ( x j )=0 j ≠ i 说明 l i ( x ) 中定有因子：
第4章 插值法
例： 利用y =
x在1， 4， 9处的值建立拉格朗日多项式并
近似求 3，6，同时给出误差
《 计 算 方 法 》
解：
( x 4)( x 9) ( x 1)( x 9) , l1 ( x) = (1 4)(1 9) (4 1)(4 9) ( x 1)( x 4) l2 ( x) = (9 4)(9 1) l0 ( x) =
( x – x 0 )( x – x 1 ) … ( x – x i- 1 )( x – x i+ 1) … ( x – x n )
《 计 算 方 法 》
即：x j ，j ≠ i 是 l i ( x ) 的根
再注意到 l i ( xi )=1， 说明 l i ( x ) 的分母中有因子
( x i – x 0 )( x i – x 1 ) … ( x i – x i-1 )( x i – x i+ 1) … ( x i – x n ) 故有 li ( x ) = P
( )
( n 1)!

n 1
( x)
max
f
( n 1)
( )
( n 1)!

n 1
( x)
第4章 插值法 由上面定理有一下几点结论: (1) 插值多项式只与插值基点及基点上的函数值有关，与函数f(x) 没有关系。但余项Rn(x)却与f(x)联系很紧。 《 计 算 方 法 》 (2) 若f(x)即为次数不超过n的多项式，那么以n+1个点为基点 的插值多项式就一定是其本身，即P n (x) ≡ f (x)。
《 计 算 方 法 》
第4章 插值法
系数行列式为范德蒙特(
Vander Monde
2 x0 n x0
)行列式
1 x0
《 计 算 方 法 》
V ( x0 , x1 ,
, xn ) = 1 x1 1 xn
x12
2 xn
x1n
n xn
由于插值基点xi (I = 0，1，…，n)为互异,故 V(x0，x1，…，xn)≠0 方程组有唯一的一组解a0，a1，…，an Pn(x)存在且唯一。
《 计 算 方 法 》
4
3
xi 4 yi 2
9 16 3 4
2
0
4
7
9
16
第4章 插值法
应用背景
造函数表：三角函数、对数 预测：鸡蛋价格、城市用水量
《 计 算 方 法 》
数控加工：造船、飞机机翼骨架、服装 样片、模具加工、刀具 计算机辅助设计：潜水艇、汽车造型
服装样片
第4章 插值法
实际问题中，f (x)多样，复杂，通常只能观测到一些离散 数据；或者f (x)过于复杂而难以运算。这时我们要用近似函数 φ(x)来逼近f (x)。
第4章 插值法
§4 代数多项式的余项
φ (x) f (x)
《 计 算 方 法 》
x0
x1
x2
x
x3
x4
一般说来 , 对插值区间［ a ， b ］上插值基点 xi (i=0 ，1 ， 2，…，n)以外的点，P n (x) ≠f (x)。若令：
R n (x) = f (x) –P n(x)
则： f (x) = P n (x) +R n (x)
n
x xj xi x j
j=0 ji
, i = 0 ,1 , L , n 称为 Lagerange 插值基
第4章 插值法
当 n=1 , Lagerange 插值
《 计 算 方 法 》
x x1 x x0 l 0 (x) = , l1 (x) = x0 x1 x1 x0
x x1 x x0 y(x) = y0 y1 x0 x1 x1 x0
l2 ( x) =
( x x0 )( x x1 ) ( x2 x0 )( x2 x1 )
y ( 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 )
y1 y0 ( x) = P ( x x0 ) 1 ( x) = y0 x1 x0
x x1 x x0 P y0 y1 1 ( x) = x0 x1 x1 x0
《 计 算 方 法 》
第4章 插值法
2.2 二次插值
二次插值又称为抛物线插值,也是常用的代数多项 式插值之一。设已知函数f(x)的三个互异插值基点x0，
第4章 插值法
第 4章
§1 插值问题
§2 线性插值与二次插值
《 计 算 方 法 》
插值法
§3 代数多项式插值的存在唯一性
§4 代数多项式的余项
§5 拉格朗日插值多项式 §6 牛顿均差插值多项式 §7 牛顿前差和后差插值多项式 §8 三次样条插值 §9 数值微分 §10 曲线拟合法
第4章 插值法
7 =?
(3)
当点x位于x0，x1，…，xn的中部时，|ωn+1(x)|比较小，误
差小些，而位于两端时，误差要更大些。
第4章 插值法
§5 拉格朗日插值多项式
构造 l i ( x ) 为 n 次多项 式，满足：
《 计 算 方 法 》
l i ( x j )=
0 1
j≠ i
j = i
于是： Pn( xk ) = yi l i ( x k ) = y k
φ(x)=P1(x)=ax+b 近似地代替f (x)。按照插值原则，有：
《 计 算 方 法 》
ax0 b = y0 ax1 b = y1
因为x0≠x1,所以a，b可唯一确定，且有
y1 y0 a= x1 x0 y1 y0 b = y0 x0 x1 x0
第4章 插值法
第4章 插值法
根据插值原则式，代数多项式中的各个系数 a0 ， a1，…，an应满足下列n+1阶线性方程组
2 n Pn ( x0 ) = a0 a1 x0 a2 x0 an x0 = y0 2 n P ( x ) = a a x a x a x n 1 0 1 1 2 1 n 1 = y1 P ( x ) = a a x a x2 a xn = y n n 0 1 n 2 n n n n
满足φ ( x i)= y i ，i=0,1, … , n 称这个问题为曲线插值问题。
x i , i=0,1, … , n 为 插值节点； φ ( x )为插值函数； f ( x )被插值函数；
φ ( x i)= y i插值条件或插值原则。
第4章 插值法
yi }， 数学模型：已知 { x i ， 求一条光滑曲线满足 φ ( x i )= yi 。
计 算 方 法 》
Rn ( x ) = f ( x ) Pn ( x ) =
f
( n 1)
( )
( n 1)!

证明见书 P145
n 1
( x)
其中：
n1( x) = ( x x0 )( x x1 )...( x xn )
插值的绝对误差限为:
Rn ( x ) =
f
( n 1)
《 计 算 方 法 》
x1，x2的函数值分别为y0，y1，y2,见下表所示:
（3点插值）
x y
x0 y0
x1 y1
x2 y2
第4章 Βιβλιοθήκη Baidu值法
现要构造一个二次函数
φ(x)=P2(x)=ax2+bx+c 近似地代替f (x)，并满足插值原则
《 计 算 方 法 》
P2(xi)=yi， i=0，1，2，…
2 ax0 bx0 c = y0 2 ax1 bx1 c = y1 ax 2 bx c = y 2 2 2
《 计 算 方 法 》
理论问题： 1 数学描述； 2 误差估计；
第4章 插值法
多项式插值
（待定系数法）
若仅限于求函数在x=x0的近似函数，一个熟知的 办法就是将f(x)在x=x0处展成泰勒级数，即
《 计 f ( n ) ( x0 ) f ( n1) ( ) n n 1 f ( x ) = f ( x ) f ( x )( x x ) ( x x ) ( x x ) 算 0 0 0 0 0 n ! ( n 1)! 方 法 取前n+1项的部分和Pn(x)作为f (x)的近似式，也即： 》
第4章 插值法
2 x0
x0 1 x1 1 0 x2 1
x12
2 x2
《 计 算 方 法 》
x0，x1，x2互异，a，b，c可唯一地确定。
二次函数P2(x)也唯一地被确定。
第4章 插值法
§3 代数多项式插值的存在唯一性
《 计 算 方 法 》
对于一般的代数插值问题，就是寻求一个 n 次的 代数多项式： Pn(x)=a0+a1x+a2x2+…+anxn 使其在给定的n+1个互异的插值基点上满足插值原则 Pn(xi)=yi，i=0，1，…，n
《 计 算 方 法 》
φ (x)= y0
第4章 插值法
§2 线性插值与二次插值
2.1 线性插值
线性插值是代数多项式插值的最简单的形式。假设
《 计 算 方 法 》
给定了函数f (x)在两个互异点x0，x1的值,即
x x0 x1
y
y0
y1
（2点插值）
y y0 x0
y1
x1
x
第4章 插值法
现要用一线性函数
第4章 插值法
已知函数y=f(x)的观测数据为
x
《 计 算 方 法 》
0
1
2
y
解：
1
2
3
试求拉格朗日插值多项式。
( x 1)( x 2) ( x 0)( x 2) p2 ( x ) = 1 2 (0 1)(0 2) (1 0)(1 2) ( x 0)( x 1) 3 (2 0)(2 1) = x 1
插值多项式 Pn (x)的余项
第4章 插值法
插值的截断误差 定理: 设Pn(x)是过点x0 ，x1 ，x2 ，…，xn的f(x)的n 次插 值多项式，f(x) ∈Cn+1[a,b] ，其中[a，b]是包含点x0 ，x1 ， x2 ，…，xn的区间，则对任意给定的x[a，b]，总存在一点 《（a，b）（依赖于x）使：
满足插值条件：
y( xi ) = yi , i = 0,1, 2
22
第4章 插值法 例：已知函数 y=f (x)的观测数据为
x
《 计 算 方 法 》
1 0
2 -5
3 -6
4 3
y
试求拉格朗日插值多项式。
第4章 插值法
《 计 算 方 法 》
( x 2)( x 3)( x 4) 解 ：p3 ( x ) = 0 (1 2)(1 3)(1 4) ( x 1)( x 3)( x 4) ( 5) (2 1)(2 3)(2 4) ( x 1)( x 2)( x 4) ( 6) (3 1)(3 2)(3 4) ( x 1)( x 2)( x 3) 3 (4 1)(4 2)(4 3) = x3 4 x2 3
y y0 x0 y1 x1
x
第4章 插值法
当n=2 时，Lagerange插值为：
l0 ( x) =
《 计 算 方 法 》
( x x1 )( x x2 ) ( x0 x1 )( x0 x2 )
l1 ( x) =
( x x0 )( x x2 ) ( x1 x0 )( x1 x2 )
《 计 算 方 法 》
自然地，希望φ(x)通过所有的离散点。
φ (x) f (x)
x0
x1
x2
x
x3
x4
第4章 插值法
§1 插值问题
已知 { x i， y i} ， i=0,1, … ,n 是函数 y=f ( x ) 的离散点， 求 φ ( x ) ∈φ 为 y=f ( x )的近似函数。
《 计 算 方 法 》