当前位置：文档之家 › 研究生数值分析(15)插商与牛顿(Newton)插值多项式

研究生数值分析(15)插商与牛顿(Newton)插值多项式

  • 格式：ppt
  • 大小：541.00 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

§2.4 差商与Newton插值公式

§2.4 差商与Newton插值公式

称为函数f (x)在x0、x1 、xk 点的二阶差商.
© 2009, Henan Polytechnic University §4 差商与Newton插值公式
6 6
第二章 插值法
一般地，k-1阶差商的差商
f [ x0 ,, xk 2 , xk ] f [ x0 , x1 ,, xk 1 ] f [ x0 , x1 ,, xk ] x k x k 1
© 2009, Henan Polytechnic University §4 差商与Newton插值公式
1010
第二章 插值法
性质3 若f(x)在[a,b]上存在n阶导数, 且节点x0 , x1 ,…,
xn∈[a,b] ,则至少存在一点 [a, b] 满足下式
f ( n ) ( ) f [ x0 , x1 ,, xn ] n!
f ( x 3 ) f ( x0 ) 1 1 a3 a a 1 2 x x x3 x2 x x 3 0 3 1

© 2009, Henan Polytechnic University §4 差商与Newton插值公式
© 2009, Henan Polytechnic University §4 差商与Newton插值公式
1212
第二章 插值法
2.4.2 牛顿插值公式 N n ( x) a0 a1 ( x x0 ) an ( x x0 )( x xn1 )
a0 f ( x0 )
1616
第二章 插值法
f ( x ) f ( x0 ) f [ x, x0 ]( x x0 )
f [ x , x0 ] f [ x0 , x1 ] f [ x , x0 , x1 ]( x x1 )

53第三节 Newton插值多项式

53第三节 Newton插值多项式

利用N2(x)又可得过前四点的三次牛顿插值多项式 N3( x) N2( x) 0.1970( x 0.40)(x 0.55)(x 0.65)
故 f (0.596) N3(0.596) 0.6319145 f [x0 , , x4 ] 0.0344 可得N3(x)的截断误差
f [x, x0 ,L , xn1] f [x0 , x1,L , xn] f [x, x0,L , xn]( x xn ) 依次把后式代入前式，最后得
f ( x) f ( x0 ) f [x, x0 ]( x x0 ) f ( x0 ) f [ x0 , x1]( x x0 ) f [x, x0 , x1]( x x0 )( x x1 ) f ( x0 ) f [ x0 , x1]( x x0 ) f [x0 , x1, x2 ]( x x0 )( x x1 ) f [x, x0 , x1, x2 ]( x x0 )( x x1 )( x x2 )
1
数学学院 信息与计算科学系
分析“承袭性”，先考察的n=1情形，此时线
性插值多项式记为P1(x), 它满足插值条件 P1(x0)=f(x0), P1(x1)=f(x1), 用(2.1)式的点斜式表示为
P1( x)
f ( x0 )
f
(
x1 ) x1

f( x0
x0 )
(
x

x0
),
它可看成是零次多项式的修正P0(x)=f(x0)，即
则Pn(x)可表示为
Pn( x) a0 a1( x x0 ) L an( x x0 )L ( x xn1),
其中a0,a1,…, an为待定系数，可由条件(3.1)确定. 与 拉格朗日插值不同，这里的Pn(x)是由基函数{1,x-x0, …,(x-x0)…(x-xn-1)}逐次递推得到的. 为了给出系数 ai(i=0,1, …,n)的表达式，需引进差商(即均差)的定义.

计算方法 Newton插值

计算方法 Newton插值

或者表示成
f[x0 , x1..., xn]
n k0
f(xk ) , ω(xk )
其中ω(xk
)
n
(xk
i0
xi)
ik
以上公式可以利用如下的表达式直接验证
n
ω(x) (xk xi ) i0
应理解：右端分母中，xk-xk 项永远不出现。
这种求解差商的方法的优点是直接使用公式， 缺点是计算量较大。
计算方法 (Numerical Analysis)
第2次 Newton 插值
1. 牛顿插值多项式的概念 2. 差商及其性质 3. 牛顿插值多项式的系数与误差余项的导出 4. 利用牛顿插值多项式近似求解的例子
牛顿插值多项式的概念
§3 均差与牛顿插值多项式
拉格朗日插值多项式的优点与缺点
➢ 优点：结构对称，使用方便。
无x n ,将出现在系数中 （3.12）
其中ak (k=0,1,2,…,n)为待定系数。
它满足以下的递推公式：
Nn(x) Nn1(x) an(x x0 )(x x1) …(x xn1)
➢ 牛顿插值多项式Nn(x)是插值多项式p(x)的另 一种表示形式,
➢ 与Lagrange多项式相比 • 它克服了“增加一个节点时整个计算工作重 新开始”的缺点, • 节省乘除法运算次数, • 在Newton插值多项式中用到的差商等概念， 又与数值计算的其他方面有密切的关系.
a2
f( x2 ) f( x0 ) a1( x2 x0 ) ( x2 x 0 ) ( x2 x1)
f[x0, x 2 ] f[x0, x1] ( x2 x1)
f[x0, x 2 ] f[x1, x0 ] ( x2 x1)
f[x1, x 0, x 2 ]

数值分析2-3(牛顿插值法)差商和与牛顿插值

数值分析2-3(牛顿插值法)差商和与牛顿插值

确定插值多项式的次数
根据已知数据点的数量确定插值多项式的最高次 数。
计算插值多项式
利用差商表，通过拉格朗日插值公式计算插值多 项式。
3
进行插值
将需要插值的x值代入插值多项式中，得到对应 的y值。
05
牛顿插值法的优缺点分析
优点
计算简单
局部性质好
相比于其他多项式插值方法，牛顿插 值法的计算过程相对简单，不需要求 解高阶方程，降低了计算的复杂度。
数值分析2-3：牛顿 插值法、差商和
目录
• 引言 • 牛顿插值法的基本概念 • 差商的计算方法 • 牛顿插值法的实现步骤 • 牛顿插值法的优缺点分析 • 实际应用案例 • 总结与展望
01
引言
主题简介
数值分析是数学的一个重要分支，主 要研究如何用数值方法解决各种数学 问题。
本章节将介绍牛顿插值法、差商和的 概念及其应用。
03
差商的计算方法
差商的递推公式
差商的递推公式
$f[x_0, x_1, ldots, x_n] = frac{f[x_1, ldots, x_n] - f[x_0, x_1, ldots, x_{n-1}]}{x_n - x_0}$
应用
通过递推公式，我们可以计算任意点之间的差商，从而得到插值多项式的导数。
在数据点附近，牛顿插值具有较好的 局部性质，能够提供较为准确的插值 结果。
适用性强
牛顿插值法适用于各种数据分布情况， 无论是线性还是非线性数据，都能得 到较好的插值结果。
缺点
全局误差较大
由于牛顿插值多项式的构造方式， 其全局误差通常较大，尤其是在 数据点较少的情况下。
对数据点敏感
如果数据点发生微小的变动，牛 顿插值多项式可能会发生较大的 变化，导致插值结果不稳定。

差商及其性质

差商及其性质

f
x0 , x1
f (x1 ) f (x0 ) x1 x0
(1)可用归纳法证明。(2)利用(1)很容易得到。只证(1)
证明：（1）当k =1时, f x0 , x1
假设当k n时成立，即有
f
(x1 )
f
(
x0
)
f (x0 )
f (x1 )
x1 x0
x0 x1 x1 x0
f [x0，x1，xn]
的线性组合，即
f
x0 , x1,, xk
k j0
(xj
x0 )(x j
x1)( x j
f (xj) x j1 )(x j
x j1 )( x j
xk )
k
j0
k
f (xj)
k
f (xj)
( x j xi ) j0 k 1 ( x j )
i0
（2）k
阶差商
f
x0
,
x1
i j
,, xk
关于节点
x0
,
x1
,,
xk
是对称的，或说
均差与节点顺序无关，即
f x0, x1,, xk f x1, x0,, xk f xk , xk1,, x0
例如：f xi , x j , xk f xi , xk , x j , f x j , xi , xk f x j , xk , xi
f (xj) xj1)(x j
x j1)( x j
xn )
f
[ x1，x2， xn1 ]
n1 j 1
(
xj
x1)( x j
f (xj) xj1)(xj
x j1)(
xj
xn1 )

差分形式的牛顿插值公式

差分形式的牛顿插值公式

差分形式的牛顿插值公式一、牛顿插值公式的引入在数值计算和插值问题中，牛顿插值公式是一种常用的插值方法。

它通过已知的数据点，构造一个函数，使得这个函数通过这些数据点，并且在其他位置也有较好的逼近效果。

牛顿插值公式有两种形式，一种是差商形式，另一种是拉格朗日形式。

本文主要介绍差商形式的牛顿插值公式。

差分形式的牛顿插值公式是通过对已知数据点进行差分运算，得到一组差商系数，然后利用这些差商系数构造插值多项式。

具体来说，设有n+1个数据点(x0, y0)，(x1, y1)，...(xn, yn)，其中xi和yi分别表示第i个数据点的横坐标和纵坐标。

差商形式的牛顿插值多项式可以表示为：P(x) = y0 + (x-x0)Δy0 + (x-x0)(x-x1)Δ^2y0 + ... + (x-x0)(x-x1)...(x-xn)Δ^n y0其中Δy0表示一阶差商，Δ^2y0表示二阶差商，以此类推。

差商的计算可以通过递推公式得到，具体计算方法如下：Δy0 = y1 - y0Δ^2y0 = Δy1 - Δy0 = y2 - 2y1 + y0Δ^3y0 = Δ^2y1 - Δ^2y0 = y3 - 3y2 + 3y1 - y0...通过递推计算可以得到所有的差商系数，进而构造出插值多项式。

三、差分形式的牛顿插值公式的应用差分形式的牛顿插值公式在实际问题中有广泛的应用。

下面以两个具体的例子来说明其应用：1. 数据的插值逼近假设我们有一组离散的数据点，现在需要根据这些数据点来估计其他位置的数据。

差分形式的牛顿插值公式可以通过构造插值多项式来实现这个目标。

我们可以利用已知的数据点，计算出差分系数，并将其代入插值多项式中，从而得到我们所需位置的数据估计值。

2. 数据的平滑处理在一些实际问题中，我们可能会遇到数据中存在噪声或异常值的情况。

差分形式的牛顿插值公式可以通过对数据进行插值逼近，从而平滑处理这些噪声或异常值。

我们可以利用已知的数据点，构造插值多项式，并利用该多项式来估计数据中存在噪声或异常值的位置，从而得到平滑后的数据。

差商与牛顿插值多项式


⇒ f [x, x0 ,⋯, xn−1 ] = f [x0 , x1 ,⋯, xn ] + f [ x, x0 ,⋯, xn ]( x − xn ) (d )
f x x x ] x − xx f [ x,, x00]]= f [ x0 , x1 ] + f [x,, x00,,x11(]( x − 1 )1 ) (b) x
f ( x0 ) f ( x1 ) f ( x1 ) − f ( x0 ) f [ x0，x1 ] = + =1时 当k =1时, ⇐ f [x0 , x1 ] = x0 − x1 x1 − x0 x1 − x0 利用(1)很容易得到。 (1)可用归纳法证明。(2)利用(1)很容易得到。只证(1) )可用归纳法证明。(2)利用(1)很容易得到 只证(1) f ( x1 ) − f ( x0 ) f ( x0 ) f ( x1 ) （ =1时 = + 证明： ） 证明： 1）当k =1时, f [x0 , x1 ] = x1 − x0 x0 − x1 x1 − x0
f [x2 , x3 ] f [x1, x2 , x3 ] f [x3 , x4 ] f [x2 , x3 , x4 ]
⋮ ⋮ f [xk−1, xk ] f [xk−2 , xk−1, xk ]
f [x0 , x1, x2 , x3 ] f [x1, x2 , x3 , x4 ]
⋮ ⋱
f ( x4 )
f [x0 , x1 ,⋯, xk ] = ∑
k j =0
f (xj )
( x j − x0 )(x j − x1 )⋯( x j − x j−1 )(x j − x j+1 )⋯( x j − xk ) k k f (xj) f (x j ) =∑ k =∑ j =0 ′ Π ( x j − x i ) j = 0 ω k +1 ( x j )

newton插值多项式

xi f ( xi ) 一阶差商 二阶差商 x0 f ( x0 ) x1 f ( x1 ) x3 f ( x3 ) x 4 f ( x4 )

三阶差商
Newton公式 Newton优点
四阶差商
f [ x0 , x1 ]
x 2 f ( x2 ) f [ x1 , x2 ] f [ x0 , x1 , x2 ]
N k 1 ( x) N k ( x) f [ x0 ,, xk , xk 1 ]( x x0 )( x x1 )( x xk )
17
一次Newton插值多项式
N1(x)= f(x0)+f[x0,x1](x-x0)
二次Newton插值多项式
N2(x)= f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)
f [ x0 , x1 , , xn ] f
(n)
( ) n!
7
例 已知 f(x) = x7+ x4+ 3x+ 1 求 f [20, 21, … 27 ] 及 f [20, 21, … 27, 28 ] 分析：本题 f(x)是一个多项式, 故应利用差商的性
质
解: 由差商与导数之间的关系
8
差商的计算-差商表
9
例
已知
xi
f ( xi )
计算三阶差商 解：列表计算
xi
f [1, 2,4,7]
f ( xi )
f [1, 2, 4, 7] 1 / 2
10
二 Newton 插值多项式
根据差商的定义，把
f [ x, x0 ]
x 看成[a,b]上的一点，可得：
f ( x) f ( x0 ) x x0

第一章 第二节 Newton 插值多项式


从而有，
f ( x ) = Pn+1 ( x ) = Pn ( x ) + f ( x, x0 , x1 ,, xn ) n+1 ( x )
因此，对所有 x = xi , i = 0,1,, n ，有
Rn ( x ) = f ( x ) Pn ( x ) = f ( x, x0 ,, xn ) n+1 ( x )
算过的结果不能利用，需要全部重新算起，这在实际计算中
是非常不利的。 由此引入新的插值公式。
二、差商及其性质
1、差商的概念
设在 n + 1 个互异点 x0 , x1 ,L xn上的函数值为已知，我们称
f ( xi , x j ) = f ( xi ) f ( x j ) xi x j , (i j )
为 f (x) 的一阶差商。
一般地，我们把一阶差商的一阶差商
f ( xi , x j , xk ) = f ( xi , x j ) f ( x j , xk ) xi xk ,(i k )
称为 f (x) 的二阶差商。
把 n 1阶差商的一阶差商
f ( x0 , x1 ,, xn ) = f ( x0 , x1 ,, xn 1 ) f ( x1 , x2 , xn ) x0 xn
（2）对称性
即当任意调换 xi 的位置时，不改变差商值，如
f ( x0 , x1 , x2 ) = f ( x1 , x0 , x2 ) = f ( x2 , x1 , x0 )
（3）、若
F ( x) = f ( x) g ( x)
则
F ( xi ,, xi + k ) = f ( xi ,, xr ) g ( xr , xi + k )

第3节 差商及Newton插值多项式


为n次Newton插值多项式。 Newton插值多项式 插值多项式。 如果 f(x) ≈ Nn(x),则误差为： 则误差为：

Rn ( x) = ( x − x0 )( x − x1 )L( x − xn ) f [ x, x0 , x1 ,L, xn ]
☆
验证
Nn ( xi ) = f ( xi ), i = 0,1,L, n
得到
f [ x0 , x1 , x2 ] =
f [ x0 , x1 ] − f [ x1 , x2 ] x0 − x2 f ( x0 ) f ( x1 ) f ( x2 ) = + + ( x0 − x1 )( x0 − x2 ) ( x1 − x0 )( x1 − x2 ) ( x2 − x0 )( x2 − x1 )
f [ x, x0 ] = f ( x) − f ( x0 ) x −x0
f [ x, x0 ] − f [ x0 , x1 ] f [ x, x0 , x1 ] = x −x1 f [ x, x0 , x1 ] − f [ x0 , x1 , x2 ] f [ x, x0 , x1 , x2 ] = x −x2 L L L L L L L L L L L L L L L L L L f [ x, x0 ,L, xn−1 ] − f [ x0 , x1 ,L, xn ] f [ x, x0 , x1 ,L, xn ] = x −xn
f ( x0 ) = 2, f ( x1 ) = 3.2, f ( x2 ) = 4
2 − 3.2 1.2 = =6 0.1− 0.3 0.2
可以求得
f [ x0 , x1] =
f [ x1 , x2 ] =
3.2 − 4 0.8 = =4 0.3 − 0.5 0.2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
插商与牛顿(Newton)插值多项式 构造拉格朗日插值多项式
( x x0 ) ( x xk 1 )( x xk 1 ) ( x xn ) Ln ( x) yk lk ( x) yk ( xk x0 ) ( xk xk 1 )( xk xk 1 ) ( xk xn ) k 0
即
f [ xi , x j , xk ]
f [ x j , xk ] f [ xi , x j ] xk xi
一般地，称 m-1 阶差商的差商
f [ x1 , x2 , , xm ] f [ x0 , x1,, xm1 ] f [ x0 , x1 , , xm ] xm x0
用牛顿二次、三次插值多项式近似计算f(1.46)
的值，并估计牛顿二次插值多项式近似计算的截断
误差，说明牛顿二次多项式近似计算结果的有效数 字。
f [ x0 , x1 , , xk ]
j 0 k
f (x j ) ( x j x0 ) ( x j x j 1 )( x j x j 1 ) ( x j xk )
性质2 差商具有对称性，即在k阶差商
f [ x0 , x1 ,, xk ] 中任意调换2个节点
xi
R2 (115) f [ x0 , x1 , x2 , x3 ]3 (115) 0.0000003138 (115 100)(115 121)(115 144) 0.00082
与实际误差
115 N 2 (115) 0.001 相当接近。
练习：给定数据如下：
x f(x) 1 1.25 1.5 2.50 0 1.00 2 5.50
例3 已知函数表
x
x
… …
100 10
121 11
144 12
169 13
… …
试用牛顿线性插值与抛物线插值求 115 的近似值，并估计截断误差。
解：先构造差商表，取 x0 100, x1 121, x2 144, x3 169
x
100
x
一阶差商
二阶差商
三阶差商
10 0.047619
所求近似值为
115 N 2 (115 ) 10 0.047169 (115 100 ) 0.00009411 (115 100 )(115 121) 10.7228
由插值余项公式
f ( n1) ( ) Rn ( x) n1 ( x) f [ x0 , x1 ,, xn1 ]n1 ( x) (n 1)!
牛顿线性插值多项式为
N1 ( x) 10 0.047169 ( x 100 )
所求近似值为
115 N1 (115 ) 10 0.047169 (115 100 ) 10.7143
牛顿抛物线插值多项式为
N 2 ( x) 10 0.047169 ( x 100 ) 0.00009411 ( x 100 )( x 121)
N n ( xi ) yi
(i 0,1,, n)
为此我们引入差商概念： 定义1 设函数f(x)在点 x0 , x1 , x2 , 上的值依次为 f ( x j ) f ( xi ) (i j ) 为f(x)在点 f ( x0 ), f ( x1 ), f ( x2 ), 称 x j xi
可知近似值 N1 (115) 与 N 2 (115) 的截断误差分别为
R1 (115) 0.01125 ，
R2 (115) 0.0017
在实际计算中，特别是在函数f(x)的高阶导数
比较复杂或f(x)的表达式没有给出时，由性质3， 我们可以用差商表示的余项公式
Rn ( x) f [ x0 , x1 ,, xn , x]n 1 ( x)
这种形式的插值多项式称为n次牛顿插值多项式。 记为 N n ( x) ，即
N n ( x) a0 a1 ( x x0 ) a2 ( x x0 )( x x1 ) an ( x x0 )( x xn1 )
其中系数
⑧
ai
(i 0,1,, n)
可由插值条件 确定。
n
其形式具有对称性，即便于记忆， 又便于应用与编制程序。 由于公式中的 lk ( x )
(k 0,1,, n)
都依赖于全部插值节点在增加或减少节点时， 必须全部重新计算。
为克服这个缺点，把插值多项式构造成如下形式
a0 a1 ( x x0 ) a2 ( x x0 )( x x1 ) an ( x x0 )( x xn1 )
一般地，可以证明有 于是，满足插值条件
ak f [ x0 , x1 ,, xk ]
(i 0,1, 2,, n)
N n ( xi ) f ( xi )
的n次牛顿插值多项式为
N n ( x) f [ x0 ] f [ x0 , x1 ]( x x0 ) f [ x0 , x1 , x2 ]( x x0 )( x x1 ) f [ x0 , x1 , , xn ]( x x0 )( x x1 ) ( x xn 1 )
a0 f ( x0 ) f [ x0 ]
由插值条件 N n ( x1 ) f ( x1 ) ，可得
f ( x1 ) f ( x0 ) a1 f [ x0 , x1 ] x1 x0
由插值条件 N n ( x2 ) f ( x2 ) ，可得
f ( x2 ) f ( x0 ) f [ x0 , x1 ] f ( x2 ) f ( x0 ) f [ x0 , x1 ]( x2 x0 ) x2 x0 a2 ( x2 x0 )( x2 x1 ) x2 x1 f [ x0 , x2 ] f [ x0 , x1 ] f [ x1 , x0 , x2 ] f [ x0 , x1 , x2 ] x2 x1
有了差商的概念和性质后，我们就可以用差商
来表示牛顿差值多项式中的系数。
N n ( x) a0 a1 ( x x0 ) a2 ( x x0 )( x x1 ) an ( x x0 )( x xn1 )
由插值条件 N n ( x0 ) f ( x0 ) ，可得
121
11
-0.00009411
0.043478
144 12 0.040000 169 13 -0.00007246
0.0000003138
由差商表，牛顿插值多项式的系数依次为
f [ x0 ] 10, f [ x0 , x1 ] 0.047169, f [ x0 , x1 , x2 ] 0.00009411,
xi , x j
处的一阶差商，记为 f [ xi , x j ] ，即 f ( x j ) f ( xi ) f [ xi , x j ] x j xi
f [ x j , xk ] f [ xi , x j ] xk xi
称一阶差商的差商
（ i, j , k 互异）
为f(x)在 xi , x j , xk 处的二阶差商，记为 f [ xi , x j , xk ]
为 f(x) 在点 x0 , x1 ,, xm 处的m阶差商。
特别地，规定零阶差商 f [ xi ] f ( xi )
为便于应用，通常采用差商表，例如
xk
x0
f [ xk ]
一阶差商
二阶差商
三阶差商
f [ x0 ]
f [ x0 , x1 ]
x1
f [ ห้องสมุดไป่ตู้1 ]
f [ x0 , x1 , x2 ]
和 xj
的顺序，其值不变。
性质3 k阶差商 f [ x0 , x1 ,, xk ] 和 k 阶导数
f
(k )
( x) 之间有如下重要关系：
f
(k )
( ) f [ x0 , x1 ,, xk ] k! (min{x0 , x1 , , xk }, max{x0 , x1 , , xk })
f [ x1 , x2 ]
x2
f [ x2 ]
f [ x0 , x1 , x2 , x3 ]
f [ x1 , x2 , x3 ]
f [ x2 , x3 ]
x3
f [ x3 ]
差商有如下性质： 性质1 k阶差商 f [ x0 , x1 ,, xk ] 是由函数值
f ( x0 ), f ( x1 ),, f ( xk ) 线性组合而成的，即
来估计截断误差。 实际计算中，当n+1阶差商变化不激烈时，可用
f [ x0 , x1 ,, xn , xn1 ] 近似代替 f [ x0 , x1 , , xn , x]
取
Rn ( x) f [ x0 , x1 ,, xn , xn1 ]n1 ( x)
例3中，若用此方法估计截断误差，则有