当前位置：文档之家 › 第二章 函数的插值

第二章 函数的插值

  • 格式：pps
  • 大小：327.50 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

第二章 插值法

第二章 插值法
项式是唯一存在的。
证明：
yi , 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 注：若不将多项式次数限制为 n ，则插值多项式不唯一。 例如 P ( x ) = Ln ( x ) p( x ) ( x - x i ) 也是一个插值
sin 50 0 L2 ( 5 ) 0.76543 18
R2 ( x ) = - cos x ( x - )( x - )( x - ) ; 3! 6 4 3 1 cos 3 x 2 2
0.00044 R2 5 0.00077 18
=
x - x1 y + x 0 - x1 0
x - x0 y = x1 - x 0 1
l ( x) y
i =0 i
1
i
l0(x)
l1(x)
§1 Lagrange Polynomial
n1
希望找到li(x)，i = 0, …, n 使得 li(xj)=ij ；然后令
Pn ( x ) =
l (x) y
g(x) f(x)
x0
x1
x2
x
x3
x4
§1 拉格朗日多项式
Pn ( x i ) = y i ,
/* Lagrange Polynomial */
n 求 n 次多项式 Pn ( x ) = a0 a1 x an x 使得
i = 0 , ... , n

第二章插值法

第二章插值法

lk ( xk 1 ) 0
n=2的情况，假定插值节点为
xk 1 , xk , xk 1 , 要求一个二次插值多项式L2 ( x)，使它满足 L2 ( x j ) y j ( j k 1, k , k 1)
y L2 ( x)在几何上就是通过三点(xk-1 , yk 1 ),(xk , yk ),(xk+1, yk 1 )的抛物线
插值法
§2.1 §2.2 §2.3 §2.4 §2.5 §2.6 §2.7 引言 拉格朗日插值 均差与牛顿插值公式 差分与等距节点插值 埃尔米特插值 分段低次插值 三次样条插值
一、插值问题
或者函数本身只是 一组实验数据，很 难对函数的性质进 行分析
对函数f (x),其函数形式可能很复杂且不利于在计算机上 ,
设函数
y f ( x ) 在区间 [a, b] 上有定义，且已知在
a x0 x1 x2 xn b
f ( xi ) yi , i 0,1,, n
如果存在一个简单函数 P ( x )，使得
P( xi ) f ( xi ) yi , i 0,1,, n
xx x x
如函数y sin x, 若给定 0, ]上5个等分点 [
其插值函数的图象如图
对于被插函数 ( x)和插值函数 ( x) f P
在节点xi处的函数值必然相等
但在节点外 ( x)的值可能就会偏离 ( x) P f 因此P( x)近似代替 ( x)必然存在着误差 f
整体误差的大小反映了插值函数的好坏
成立，则称 P ( x ) 为 f ( x ) 的插值函数
称点 xi , i 0,1,2,, n为插值节点
称区间 a , b]为插值区间 [

第2章_插值法

第2章_插值法
56
13.214 285 71

175 13.228756555322952...
考虑通过 + 1个节点0 < 1 < ⋯ < 的次插值
多项式 ()，满足条件
= ,
= 0,1, … ,
希望找到 li(x)，i = 0, …, n, 使得
= ; = ,
n次插值多项式, 插值节点为{ xi }in 0 [ a , b],则x [ a , b],有
f ( n 1) ( )
Rn (x )
n 1 ( x)
Lagrange型余项
(n 1)!
n
其中 n 1 ( x ) ( x xi ) , ( a , b) , 且依赖于 x.
满足条件P(xi) = f(xi) (i = 0, … n)。 P(x) 称
为f(x) 的插值函数。
P(x) f(x)
x0
x1
x2
x
x3
x4
定理1：设插值节点 ≠ ( ≠ )，则满足条件
= , = 0,1, … , 的插值多项式
= 0 + 1 + ⋯ +
− , , + 线性无关。
二次插值多项式
= − − + + + + ()
满足 = ( = − , , + )
例1:
已知 f ( x )满足 f (144) 12 , f (169) 13, f ( 225) 15
i 0
一次及二次差值余项
1 ′′
1 = − 0 − 1 ,

计算方法—插值法 (课堂PPT)

计算方法—插值法 (课堂PPT)

7
1 1
2 5
4 25
8 125
aa32
4
35
则，
解方程组得a0=10,a1=5,a2=-10,a3=2 即P3(x)=10+5x-10x2+2x3
当n=20,在109次/秒的计算机上计算需几万年！
.
2020/4/2
12
2.2 拉格朗日插值
2-2 线性插值与抛物插值
Chapter2 插值法
第二章 插 值 法
（ Interpolation） 2.1 引言
2.2 拉格朗日插值
2.3 均差与牛顿插值公式
Chapter2 插值法
2.4 埃尔米特插值
2.5 分段低次插值
2.6 三次样条插值
.
2020/4/2
1
2.1 引言
Chapter2 插值法
表示两个变量x,y内在关系一般由函数式 y=f(x)表达。但在实际问题中的函数是多种多 样的,有下面两种情况：
几何意义:L2(x)为过三点(x0,y0), (x1,y1), (x2,y2)的抛物线。
方法：基函数法，构造基函数l0(x), l1(x), l2(x) (三个二次式)
使L2(x)= y0l0(x)+y1l1(x)+y2l2(x)满足插值条件。 6 4 4 4 4 4 4 7 4 4 4 4 4 48
.
2020/4/2
15
2.2 拉格朗日插值
Chapter2 插值法
问题的提法： 已知y=f(x)的函数表，x0, x1, x2为互异节
x x0 x1 x2 y y0 y1 y2
点，求一个次数不超过2的多项式 L2(x)=a0+a1x+a2x2 ：L2(x0)=y0, L2(x1)=y1, L2(x2)=y2

第二章插值与拟合

第二章插值与拟合

1 不为零。
xn
n xn xn
实 用 测 量 数 据 处 理 方 法
中 南 大 学
三、线性插值
假定已知区间[xk, xk+1] 的端点处的函数值 yk=f(xk), yk+1=f(xk+1),要求线性插值多项式 L1(x),使它满足 L1(xk)=yk
L1(xk+1)=yk+1
则L1(x)的表达式可按下式给出：
实 用 测 量 数 据 处 理 方 法
中 南 大 学
l k 1 ( x k 1 ) 1, l k 1 ( x j ) 0( j k , k 1) l k ( x k ) 1, l k ( x j ) 0( j k 1, k 1) (28) l k 1 ( x k 1 ) 1, l k 1 ( x j ) 0( j k 1, k ) 满足（28 ）式的插值基函数很容 易求出的，例如求 l k 1 ( x)，因为它有两个零点 k 和x k 1，故可表达为： x l k 1 ( x) A( x x k )(x x k 1 ) 其中A为待定系数可由 k 1 ( x k 1 ) 1定出： l 1 A ( x k 1 x k )(x k 1 x k 1 ) ( x x k )(x x k 1 ) 于是l k 1 ( x)＝ ，同理可得 ( x k 1 x k )(x k 1 x k 1 ) ( x x k－1 )(x x k 1 ) ( x x k 1 )(x x k ) l k ( x)＝ ，l k 1 ( x)＝ ( x k x k－1 )(x k x k 1 ) ( x k＋1 x k 1 )(x k 1 x k )
解：2、抛物插值

计算方法(2)-插值法

计算方法(2)-插值法



2
2
yk1 2

f (xk

h
2
),
y
k

1 2

f (xk

h) 2
21
3.牛顿向后插值公式
Nn (xn

th)

yn

tyn

t(t 1) 2!
2
yn



t(t

1)


(t n!

n

1)

n
yn
(t 0)
插值余项
Rn
(xn

th)

t(t
1) (t (n 1)!
Nn (x0

th)

y0

ty0

t(t 1) 2!
2
y0Leabharlann 插值余项t(t

1)


(t n!

n

1)
n
y0
Rn (x0

th)

t(t
1) (t (n 1)!
n)
h n1
f
(n1) ( ),
(x0 , xn )
20
二.向后差分与牛顿向后插值公式
杂.

根据f(x)函数表或复杂的解析表达式构
造某个简单函数P(x)作为f(x)的近似.
2
2.问题的提法
1)已知条件 设函数y f (x)在区间[a,b]上
连 续, 且 在n 1个不 同点a x0 , x1, , xn b 上 分 别 取 值y0 , y1, , yn

第二章插值法


线性插值的几何意义:用 通过点 A(x0 , f (x0 )) 和 B(x1, f (x1 )) 的直线近似地代替曲线 y=f(x)由解析几何知道, 这条直线用点斜式表示为
y=f(x)
p(x)=ax+b
A(x.0,f(x.0)) B(x.1,f(x.1))
p(x)
y0
y1 x1
y0 x0
(x
x0 )
解: 用待定系数法, 将各节点值依次代入所求多项式, 得
解上述方程, 将求出的a0, a1, a2 代入 p(x) = a0 + a1x + a2x2 即得所求二次多项式
例2.5 求过点(0,1)、(1,2)、(2,3)的三点插值多项式
P(x) an x n an1 x n1 a1x a0
满足
P(x) an x n an1 x n1 a1 x a0 P(xi ) f (xi ) (i 0,1,2, , n)
则称P(x)为f(x)的n次插值多项式。这种插值法通常称
为代数插值法。其几何意义如下图所示
y y=P(x) y=f(x)
lk ( xi ) ki
1 0
(i k ) (i k )
l0 (x) 与 l1(x) 称为线性插值基函数。且有
lk (x)
1 j0
x xj , xk x j
jk
k 0,1
于是线性插值函数可以表示为与基函数的线性组合
p(x) l0 (x) y0 l1 (x) y1
例2.1 已知 100 10 , 121 11 , 求 y 115
为已知 f (x0 ), f (x1), , f (xn ) ,即 yi f (xi ) 若存在一个
f(x)的近似函数 (x),满足

插值法


第一节 Lagrange插值
一、问题提出
设 x0 , x1 xn 为给定的节点，yi f ( xi )，i 0,1,n
为相应的函数值，求一个次数不超过 n 的多项式 Pn (x)， 使其满足
Pn ( xi ) yi，
i 0,1,n .
这类问题称为插值问题。 f ( x) 称为被插值函数，Pn ( x) 称 为插值函数， x0 , x1 xn 称为插值节点
差商
二阶差商
三阶差商 四阶差商
x0 f ( x0 ) x1 f ( x1 )
x2 f ( x2 )
f [ x0 , x1 ]
f [ x1 , x2 ]
f [ x0 , x1 , x2 ]
f [ x0 , x1 , x2 , x3 ]
1 2 3 4
0 1 2 3 4
x3
f ( x3 ) f [ x2 , x3 ] f [ x1 , x2 , x3 ]
评价
优点: Lagrange基函数容易构造,结构紧凑,便于理 论研究. 缺点: 当增加或减少插值结点时,基函数需要重新 构造,不便于实际的计算使用
第二节 Newton插值
一、差商定义及性质
1.差商定义 f ( x ) f ( x ) i j f [ xi , x j ] , i j 为 f ( x) 在 xi , x j 称 两点处的一阶差商.xi x j
( n1) ( ) f ( n1) ( )
f ( x) Pn ( x) (n 1)! 0 ( x)
由此得
. f ( n1) ( ) Rn ( x) f ( x) Pn ( x) n1 ( x) (n 1)! 定理得证.

《数值分析》第二讲插值法PPT课件


1 xn xn2 xnn Vandermonde行列式
即方程组（2）有唯一解 (a0, a1, , an)
所以插值多项式
P (x ) a 0 a 1 x a 2 x 2 a n x n
存在且唯一
第二章：插值
§2.2 Lagrange插值
y
数值分析
1、线性插值
P 即(x)ykx yk k 1 1 x yk k(xxk)
l k ( x k 1 ) 0 ,l k ( x k ) 1 ,l k ( x k 1 ) 0 l k 1 ( x k 1 ) 0 ,l k 1 ( x k ) 0 ,l k 1 ( x k 1 ) 1
lk1(x)(x(k x 1 x xk k))x x ((k 1x k x 1k )1) lk(x)((xx k x xk k 1 1))((x xkxx k k1)1)
第二章：插值
数值分析
3、Lagrange插值多项式
令 L n ( x ) y 0 l 0 ( x ) y 1 l 1 ( x ) y n l n ( x )
其中，基函数
lk (x ) (x ( k x x x 0 ) 0 ) (( x x k x x k k 1 1 ) )x x k ( ( x x k k 1 ) 1 ) (( x x k x n x )n )
因此 P (x ) lk (x )y k lk 1 (x )y k 1
且
P (x k ) y k P (x k 1 ) y k 1
lk(x), lk1(x) 称为一次插值基函数
数值分析
第二章：插值
2、抛物线插值 令
y (xk , yk )
f (x)
lk1(x)(x(k x 1 x xk k))x x ((k 1x k x 1k )1) p( x) (xk1,yk1)

计算方法 第二章插值法_20191105


下面两种办法常用来确定经验函数y=g(x)
（1）插值法
（2）拟合法
根据问题的不同，有时要用插值技术来解决， 有时则应该采用拟合的方法才合理。
（1）插值法的基本思想
已知数据表
xi x1 x2 … xn f(xi) f(x1) f(x2) … f(xn)
求一个经验函数y=g(x)，使g(xi)=f(xi), i=1,…n.
x)
b0
a0 a1 x a2 x2 b1 x b2 x2 b3 x3
n
一般地：F( x) cii( x) i=0
例：F(x) a bx csin x span1, x,sin x,
当插值函数是代数多项式时，插值问题称为代
代 数插值。
数 插
设 Pn(x)=a0+a1x+…+anxn ,
y2
n 次插值多项式 :求次数≤n的多项式Ln(x), 使其满足
Ln(x0)=y0 , Ln(x1)=y1 , ...... , Ln(xn)=yn
..(7)
令 Ln(x)=l0(x)y0 + l1(x)y1 +… +ln(x)yn
求n 次多项式 lj(x) ,(j=0,1,…,n)使其满足条件
容易求得
三角插值：取
spani(
n
x) i=0
a1x a0
=spansin x,cos x,sin 2x,cos 2x, ,sin nx,cos nx
例：取 spansin x,cos x,
F ( x) a sin x bcos x
有理插值：F( x)= Pm ( x) Qn ( x)
例：F (
二次插值 (n=2) 求次数≤2 的多项式L2(x), 使其满足条件 L2(x0)=y0 , L2(x1)=y1 , L2(x2)=y2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第二章函数的插值学习目标：掌握多项式插值的Lagrange插值公式、牛顿插值公式等，等距节点插值、差分、差商、重节点差商与埃米特插值。

重点是多项式插值方法。

§2.1 多项式插值一、插值问题的基本概念：设有函数 ，只知道它在n+1个不同的点上的函数值，y 是另外一点。

不知道，如何求它的近似值？插值就是一种办法，它的思想是：找一个简单的已知解析表达式的函数 ，使得（1）并且 容易计算，我们就用 来代替。

)(x f 121,,,+n x x x )(y f )(x p ,1,,2,1),()(+==n i x f x p i i )(y p )(y p )(y f 称为插值函数， 称为被插值函数， 称为节点或结点。

如果限制 为n 次多项式，那么上述问题称为多项式插值， 称为 的n 次插值多项式。

)(x p )(x f 121,,,+n x x x )(x p )(x p )(x f 本节主要介绍插值问题的基本概念、方法和理论。

对于多项式插值，我们主要讨论以下几个问题： 插值问题是否可解，如果有解，解是否唯一？ 插值多项式的常用构造方法有哪些？插值函数逼近的误差如何估计，即截断误差的估计； 当插值节点无限加密时，插值函数是否收敛于 。

本节主要讨论前三个问题。

二、多项式插值的方法令是n 次多项式：(1)考察（1）式，就有方程组： (2)nn nk k k x a x a a x a x p +++==∑= 100)(1,,2,1,0+==∑=n i f x a i nk ki k )(x p )(x f刚巧是一个具有n+1个未知量 ,n+1个方程的线性方程组，它的系数矩阵为：n a a a ,,,10 ⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=+++n n n n n nx x x x x x x x x A 121122221211111 而 恰为范德蒙达(Vandermonde) 行列式。

由线性代数知：)det(A 0)()det(11≠-=∏+≤<≤n j i i jx xA 因而方程组（2）有唯一解存在，也即由插值条件（1）可以唯一确定一个n 次多项式。

n a a a ,,,10定理1 由n+1个不同的点可以唯一确定一个n 次多项式 ，且满足条件（1）。

121,,,+n x x x )(x p 注意：定理1解决了n 次插值多项式的存在、唯一性。

以下我们主要讨论 的具体求法： )(x p （3）首先，从方程组（2），由克莱姆(Cram)法则我们知道：)det(A d a k k =其中是将系数矩阵A 的第k 列换为方程组（2）的右端向量形成的矩阵行列式 。

k d 从（3）式求，从而求得 ，从数学上来说是很清楚的，但从计算来看工作量太大了。

因为计算一个行列式是不容易的，花的代价较大。

以下我们介绍常用的求的方法 k a )(x p )(x p§1.1 拉格朗日途径考虑特殊的n 次多项式:)())(())(()())(())(()(1112111121++-++-----------=n k k k k k k k n k k k x x x x x x x x x x x x x x x x x x x x x q 它满足：⎩⎨⎧≠==ki ki x q i k ,0,1)(则： 若记 ∏+=-=11)()(n i i x x x w )()()()(k k k x w x x x w x q '-=由此看出多项式 ： ∑+=11)(n k k k x q f 是一个n 次多项式，在 处恰为 ix if ，因此满足条件（1），由定理1知的这种表示称为拉格朗日（Lagrange ）插值多项式，其中， (k=1,2,…,n+1)称为拉格朗日基本插值多项式。

∑+==11)()(n k k k x q f x P （4）)(x q k 例15)(,1)(,8)(,4,2,1321321======x f x f x f x x x 求二次插值多项式。

)(x P 211635)24)(14()2)(1(1)42)(12()4)(1(8)41)(21()4)(2()(2+-=----+----+----=x x x x x x x x x P 解 按拉格朗日方法，有：§1.2 内维尔途径内维尔途径是一种由两个n-1次插值多项式构造一个n 次插值多项式的方法。

记 是 在 上的一次插值多项式，同样 是 在 上的一次插值多项式，那么 上的二次插值多项式为)(2,1x P )(x f 21,x x )(3,2x P )(x f 32,x x 321,,x x x )()(1)()()(3,232,11133,21312,11333,2,1x P x x x P x x x x x P x x x x x P x x x x x P ---=--+--=这是很容易证明的。

因为 显然是二次多项式，且 ，由定理1就知道 是唯一的 在上的二次插值多项式。

)(3,2,1x P )(3,2,1x P )3,2,1)(()(3,2,1==i x f x P ii )(x f 321,,x x x一般地，若记 是 在 上的n-1次插值多项式， 是 在 上的n-1次插值多项式，那么 在 上 的n 次插值多项式为)(,,2,1x P n)(x f n x x x ,,,21 )(1,,,2x P n n + )(x f 121,,,,+n n x x x x )(x f 121,,,,+n n x x x x )()(1)()()(1..,3,21,,2,11111..,3,2111,,2,11111,,3,2,1x P x x x P x x x x x P x x x x x P x x x x x P n n n n n n n n n n n n ++++++++---=--+--= （5）这也是很容易验证的。

（5）有一个很重要的特点，就是，如果 ，那么，这意味着 是 和 的带权平均，且权系数是正的，这样得到的传播误差不会超过 和 两个误差中大的那一个，这在计算上是有好处11+≤≤n x x x ,0111≥--++x x x x n n 0111≥--+x x x x n )(1,,,2,1x P n n + )(,,2,1x P n )(1,,,2x P n n + )(,,2,1x P n )(1,,,2x P n n +例如，已知， 用内维尔方法求 的计算过程列表如下64)(,8)(,0)(,8)(,8,6,4,243214321===-=====x f x f x f x f x x x x )5(f ix )(i x f ix -54183241=--44143261=--12343281=---48101461=--220341481-=---2064381681-=----364 8 -18 6 10 4 3-8 2因此 1)5()5(=≈p f§1.3 牛顿途径对于n+1个不同的节点，考虑n 次多项式 121,,,+n x x x )())(())(()()(21212110n n x x x x x x c x x x x c x x c c x Q ---++--+-+=（6） 如果满足： ，那么它就是n+1个点上的n 次插值多项式，对于这样的，有 1,,,3,2,1,)()(+===n n i f x f x Q i i i )(x Q ⎪⎪⎪⎩⎪⎪⎪⎨⎧=---++-+==---++-+==-+===++++++--112111111011211110212102101)())(()()()())(()()()()()(n n n n n n n n n n n n n n n n f x x x x x x c x x c c x Q f x x x x x x c x x c c x Q f x x c c x Q f c x Q从可以求出 ，再从 可以求出 ，依次从 可以求出 ，最后从可以求出 。

)(1x Q 0c )(2x Q 1-n c )(1+n x Q 1c )(1+n x Q n c 例如，已知5)(,1)(,8)(,4,2,1321321======x f x f x f x x x 从，得 ， 101)(f c x Q ==80=c 从，得 212102)()(f x x c c x Q =-+=7)/()(12021-=--=x x c f c 再从 ，得，即： 32313213103))(()()(f x x x x c x x c c x Q =--+-+=32=c )2)(1(3)1(78)(--+--=x x x x Q 这样逐步获得，计算很方便。

n c c c ,,,10从的表达式（6）知道它的首项系数为 ，从上述计算过程还知道， 恰是两点 上一次插值的首项系数， 恰是3点上二次插值的首项系数，依次 恰是个i +1点 上i 次插值多项式 的首项系数。

的值取决于 )(x Q n c 2c 21,x x 1c 321,,x x x i c 121,,,+i x x x i c ,)),(,()),(,(2211 x f x x f x ))(,()),(,(11++i i i i x f x x f x 这i+1个平面上的点。

定义1在 上有定义，在其上确定的k 次多项式的首项系数称为在 上的k 阶差商，记为 )(x f 121,,,,+k k y y y y )(x f 121,,,,+k k y y y y ),,,,(121+k k y y y y f 推论1在 上的k 阶差商与 的次序无关。

即对任意一个的排列 ，都有 121,,,,+k k y y y y )(x f 121,,,,+k k y y y y 1,,,2,1+k k 121,,,+k i i i ),,,,(),,,,(121=+i i i i k k y y y y f y y y y f证明 由于在 上的k 次插值多项式与在上的k 次插值多项式是相同的，因而首项系数也是相同的。

)(x f 121,,,,+k k y y y y 121,,,,+k k i i i i y y y y 推论2在 上的k 阶差商为 )(x f 121,,,,+k k y y y y ∑+=++-+----=111111121)())(()()(),,,,(k i k i i i i i i i k k y y y y y y y y y f y y y y f (7) 证明 由拉格朗日插值公式知k 次插值多项式为：∑+=++-++---------=1111111111)())(()()())(()()()(k i k i i i i i i k i i i y y y y y y y y y x y x y x y x y f x P 它的首项系数就是（7）式的右边，因而（7）式成立。