当前位置：文档之家 › 演示课件第二章牛顿插值法.ppt

演示课件第二章牛顿插值法.ppt

  • 格式：ppt
  • 大小：1.65 MB
  • 文档页数：33

下载文档原格式

  / 33

合集下载

6.2 牛顿插值多项式

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

牛顿插值法ppt课件

牛顿插值法ppt课件

为 在点
处的二阶差商
称
f[x 0 ,x 1 , x n ] f[x 0 ,x 1 , ,x x n 0 1 ] x n f[x 1 ,x 2 , x n ]
为f (x)在点
处的n阶差商。
--
9
差商表
x
f(x)
一阶差 商
二阶差商
三阶差商
x0
f(x0)
x1
f(x1) f [x0,x1]
x2
f(x2) f [x1,x2] f [x0,x1,x2]
--
14
例题分析（续1）
f
(x0, x1)
y1 x1
y0 x0
12 1(1)
1 2
f
(x1,
x2)
y2 x2
y1 x1
11 21
0
f
(x0, x1, x2)
f
(x1,x2) f (x0,x1) x2 x0
02（(1/12)）
1 6
--
15
例题分析（续2）
f (x)N2(x) f (x0)f[x0,x1](xx0)
令 xx0得： Nn(x0)c0y0f(x0); 令 xx1得： Nn(x1)c0c1(x1x0)y1f(x1); 由此可c0解 ,c1;c出 i 依： 次类推。
--
6
具有承袭性的插值公式
线性插值公式可以写成如下形式：
其中
p 1 x p 0 x c 1 x x 0
p0xfx0，其修正项的系数 c1
f
x1f x0
x1 x0
再修正 p1 x 可以进一步得到拋物插值公式
p 2 x p 1 x c 2 x x 0 x x 1
其中

第二讲牛顿插值与分段线性插值

第二讲牛顿插值与分段线性插值

四、分段线性插值
我们已经知道插值有多种方法, 我们已经知道插值有多种方法 例 插值、 插值等. 如, Lagrange插值、 Newton插值等 插值 插值 插值等 的目的就是数值逼近的一种手段, 而数值逼近为 的目的就是数值逼近的一种手段 的是得到一个数学问题的精确解或足够的精确解, 的是得到一个数学问题的精确解或足够的精确解 那么是否插值多项式的次数越高, 那么是否插值多项式的次数越高 越能达到这个目 的呢? 观察n次插值多项式的余项 的呢 观察 次插值多项式的余项 f ( n +1) (ξ ) n
差商表
xi x0 x1 x2 x3 x4 ┊ f(xi) 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(x2,x3,x4 ) ┊ 1阶 阶 2阶 阶 3阶 阶 4阶 阶
∆ 3 f ( x1 ) = ∆(∆ 2 f ( x1 )) = ∆ 2 f ( x2 ) − ∆ 2 f ( x1 )
∆3f(x0) ∆3f(x1) ┊ ∆4f(x0) ┊
……
计算规律: 任一个k(≥1) 阶差分的数值等于所求 计算规律 任一个 差分左侧的数减去左上侧的数. 差分左侧的数减去左上侧的数 注意: 差分表中, 注意 差分表中 对角线上的差分是构造差分形 式的牛顿插值公式的重要数据. 式的牛顿插值公式的重要数据
+ an ( x − x0 )( x − x1 ) ⋅⋅⋅ ( x − xn−1 ).
它满足递推性: 它满足递推性
Pn ( x ) = Pn −1 ( x ) + an ( x − x0 )( x − x1 )L ( x − xn −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

计算方法(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

计算方法插值法(均差与牛顿插值公式)

计算方法插值法(均差与牛顿插值公式)

为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 处的一阶向前差分

2.牛顿插值法



x x2 x1 x 2
计算方法四③
x )( x x )......( x x ) T ………… 用for循环语句(对k) ( x x )( x x )......( x x )
0 1 2 1 n
if k~=j
3/58
L
j=0,1,2,…,n 外层循环 L=0
n
( x)
上节课内容回顾
1)构造 n 次插值基函数 lj (x) : (j=0,1, ..., n)
1/58
拉格朗日(Lagrange)插值多项式 Ln(x)的构造:
l
j
( x)
( x x 0 )( x x 1 )...( x x j 1 )( x x j 1 )...( x x n ) ( x j x 0 )( x j x 1 )...( x j x j 1 )( x j x j 1 )...( x j x n )
f [ x1 , x 3 ] f [ x 0 , x1 ]
x2 x0
f [ x1 , x 2 , x 3 ]
f [ x 0 , x 1 , , x n ]
f [ x 2 , x 3 ] f [ x1 , x 2 ] x 3 x1
xn x0
x3 x0
……
f [ x 1 , , x n ] f [ x 0 , , x n - 1 ]
j 1 n j j 1 j
)...( x
n
)
j=0,1,2,…,n 内层循环
j=1 x x0 T=1 T T
(x
1
T=T*(x-xk)/(xj-xk) k=0,1,2,...,j-1, j+1,...,n

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 ]

计算方法第二章ppt


当方程组的系数矩阵为非奇异 矩阵（即满秩矩阵）时，高斯 消元法可求得唯一解。
列主元高斯消元法
列主元高斯消元法的 基本思想
在高斯消元法的基础上，每次选取列 中绝对值最大的元素作为主元进行消 元，以避免出现小主元导致的误差放 大问题。
列主元高斯消元法的 步骤
首先选取第一列中绝对值最大的元素 作为主元，通过行交换将其移到第一 行第一列位置，然后进行高斯消元。 在后续的消元过程中，每次均选取当 前列中绝对值最大的元素作为主元进 行消元。
100%
数值解法
通过计算机求解常微分方程的近 似解的方法，主要包括欧拉方法 和龙格-库塔方法等。
80%
离散化与步长
将连续的时间或空间域离散化， 取离散点上的函数值作为近似解 ，步长是相邻离散点间的距离。
欧拉方法
显式欧拉法
一种简单的数值解法，通过前 一步的函数值及其导数来推算 下一步的函数值。
隐式欧拉法
通过求解一个非线性方程来得 到下一步的函数值，具有较高 的精度和稳定性。
改进欧拉法
结合显式欧拉法和隐式欧拉法 的优点，提高算法的精度和效 率。
龙格-库塔方法
龙格-库塔法基本思想
自适应步长龙格-库塔法
通过多步计算并利用泰勒级数展开式， 得到更高精度的近似解。
根据误差估计自动调整步长，实现精 度和计算效率的动态平衡。
标准四阶龙格-库塔法
一种常用的高精度数值解法，具有局 部截断误差为$O(h^5)$的优点。
常微分方程数值解法误差分析
局部截断误差
数值解法在单步计算中所产生的误差，可以通过泰勒级数展开式进行估计。
全局误差
数值解法在整个计算过程中所产生的累积误差，与算法稳定性、步长选择等因素有关。

插值法(lagrange插值,牛顿插值)概要

2018/10/23 21
对n=1及n=2时的情况前面已经讨论，用类
似的推导方法，可得到n次插值基函数为：
( x x0 )(x x1 ) ( x xk 1 )(x xk 1 ) ( x xn ) lk ( x ) ( xk x0 )(xk x1 ) ( xk xk 1 )(xk xk 1 ) ( xk xn )
拉格朗日（ Lagrange ）插值公式 ( 以下统称 • 此插值问题可表述为如下： n 多项式 Lagrange 插值公式 ) 的基本思想是，把 Ln ( x) ，使满足条件 • 为 问题 求作次数 Ln xi yi , (i 0,1,, n) pn(x) 的构造问题转化为 n+1 个插值基函数
且满足
Pn ( xi ) yi
i 0,1,2 ,, n
其中 a i为实数，就称P(x)为插值多项式，相应的插值法 称为多项式插值；若P(x)为分段的多项式，就称为分段 插值；若P(x)为三角多项式，就称为三角插值。
本章只讨论多项式插值与分段插值
2018/10/23 10
§ 2.2
拉格朗日插值
本章主要介绍有关插值法的一些基本概念， 及多项式插值的基础理论和几个常用的插 值方法：拉格朗日插值、分段线性插值、 牛顿插值、埃尔米特插值和三次样条插值.
2018/10/23
3
§ 2.1 引言
一、插值问题
对函数f ( x),其函数形式可能很复杂 , 且不利于在计算机上
运算, 假如可以通过实验或测 量, 可以获得f ( x)在区间 [ a , b] 上的一组n 1个不同的点
--------(2) --------(3)
7
且满足
2018/10/23
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

yk 1 (两点式）
考虑点斜式，两点为((x0,y0)(x1,y1)):
P1( x)
y0
y1 x1
y0 x0
(x
x0 )
在此基础上增加一个节点(x2,y2)，则过这三个点 的插值多项式
P2 (x) P1(x) c( x)
C(x)应是一个二次多项式。
.,
3
P2 (x) P1(x) c( x)
C(x)应是一个二次多项式。根据插值条件
P2 (x0 ) P1(x0 ) y0
P2 (x1) P1(x1) y1
所以有 c(x0 ) c(x1) 0 , 所以
c(x) a(x x0 )(x x1)
根据插值条件：P2 (x2 ) y2
可以a 求 出p2：( x2 ) p1( x2 ) y2 p1(x2 )
( x2 x1 )( x2 x0 ) ( x2 x1 )( x2 x0 )
重新写p2(x)：
.,
4
P2 (x) P1(x) c(x)
y0
y1 x1
y0 x0
(x
x0 )
y2 P1( x2 ) ( x ( x2 x0 )( x2 ( x x0 ) a2 (x x0 )(x x1) 其中
xk f (xk ) 一阶差商 x0 f ( x0 )
x1 f ( x1 )
f [x0 , x1 ] f [x1 , x2 ]
x2 f ( x2 )
f [x2 , x3 ]
x3 f ( x3 )
f [x3 , x4 ]
x4 f (x4 )
二阶差商
f [x0 , x1 , x2 ] f [x1 , x2 , x3 ] f [x2 , x3 , x4 ]
f [x0 , x1 , , xk 1 , xk ]
k
f ( xi )
i0 ( xi x0 ) ( xi xi1 )( xi xi1 ) ( xi xk )
Wh差Wat商airsn的tihne值gp: om与inytxhoiefa的tdh顺iiss fe序oxrpm无loud关lian?！g…
数值分析
第二章 插值法
均差与牛顿插值公式
.,
1
Lagrange插值多项式的缺点
我们知道,Lagrange插值多项式的插值基函数为
l j(x)
n i0
(x xi ) (x j xi )
i j
j 0,1,2, ,n
理论分析中很方便，但是当插值节点增减时全部插值
基函数就要随之变化，整个公式也将发生变化，这在
(i j, xi x j )
1阶差商 /* the 1st
divided difference of f w.r.t. xi and xj */
f [xi
, xj
, xk ]
f [xi
, x j ] f [x j , xk ] xi xk
(i k)
2阶差商
f [ x0 , ... , xk1]
设插值多项式 P(x)具有如下形式
P(x) a0 a1(x x0 ) a2(x x0 )(x x1 ) an(x x0 )(x x1 ) (x xn1 )
其中a0 , a1,……an为待定系数
.,
6
P(x) a0 a1(x x0 ) a2(x x0 )(x x1 ) an(x x0 )(x x1 ) (x xn1 )
三阶差商 四阶差商
f [x0 , x1 , x2 , x3 ]
f [x0 , x1 , , x4 ]
f [x1 , x2 , x3 , x4 ]
规定函数值为., 零阶差商
9
.,
10
差商具有如下性质:
(1) f (x)的k阶差商f [x0 , x1 , , xk1 , xk ]可由函数值 f (x0 ), f (x1 ), , f (xk )的线性组合表示,且
。。。。。。
f2 f0 f1 f0
a2
x2
x0 x2
x1 x0 x1
为此引入差商和.,差分的概念
7
差商(亦称均差)/* divided difference */
定义2. 设f (x)在互异的节点 xi 处的函数值为 fi ,i 0,1, , n
f [xi , x j ]
f ( xi ) f ( x j ) xi x j
f [ x0 , x1, ... , xk ] f [ x1, ... , xk , xk1] x0 xk1
f [ x0 , ... , xk1 , xk ] f [ x0 , ... , xk1, xk1 ] x., k xk1
(k+1) 阶 差 商
8
差商的计算方法(表格法): 差商表
P(x)应满足插值条件 P(xi ) fi , i 0,1, , n
有 P(x0 ) f0 a0
a0 f0
P(x1 ) f1 a0 a1(x1 x0 )
a1
f1 x1
f0 x0
P(x2 ) f2 a0 a1(x2 x0 ) a2(x2 x0 )( x2 x1 )
再继续下去待定系 数的形式将更复杂
实际计算中是很不方便的；
Lagrange 插值虽然易算，但若要增加一个节点时， 全部基函数 li(x) 都需重新算过。
.,
2
两点直线公式((xk,yk)(xk+1,yk+1))
L1 ( x)
yk
yk 1 xk 1
yk xk
(x
xk )(点斜式）
L1(x)
xk1 x xk1 xk
yk
x xk xk1 xk
a0 y0
a1
y1 x1
y0 x0
a2
( x2
y2 P1( x2 ) x0 )( x2 x1 )
.,
5
基函数
设插值节点为 xi , 函数值为 fi , i 0,1, , n
hi xi1 xi , i 0,1,2, , n 1
h
max i
hi
插值条件为 P(xi ) fi , i 0,1, , n
.,
11
Newton插值公式及其余 项
.,
12
Newton插值公式及其余
项f ( x) f ( x0 ) ( x x0 ) f [x, x0 ]
1
f [ x, x0 ] f [ x0 , x1] ( x x1 ) f [ x, x0 , x1]
2
…………
f [ x, x0 , ... , xn1] f [ x0 , ... , xn ] ( x xn ) f [ x, x0 , ... , xn ] n+1