数值计算方法-插值法54页PPT

拉格朗日插值余项
设节点a x0 x1 xn b ，且 f 满足条件 f C n[a,b] , f (n1)在[a , b]内存在, 考察截断误差
Rn( x) f ( x) - Ln( x)
n
Rn(x) 至少有 n+1 个根
Rn( x) K(x) ( x - xi )
Pn ( xi ) yi , i 0, ... , n
条件：无重合节点，即 i j xi x j
n=1
已知 x0 , x1 ; y0 , y1 ，求 P1( x) a0 a1 x 使得
P1( x0 ) y0 , P1( x1 ) y1
可见 P1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。
li ( x )
i0
y i
，则显然有Pn(xi) = yi 。
每个 li 有 n 个根 x0 … xi-1， xi+1 … xn
li (x) Ci
(x-
ji
xj )
li (xi ) 1
Ci

ji
( xi
1 - xj)
li ( x)
n ji
(x- xj) (xi - x j )
3!
(x
-

6
)(
x
-

4
)(
x
-

3
)
;
1 2

cos x

3 2
0.00044

R2
5
18


0.00077
sin 50 = 0.7660444…
2次插值的实际误差 0.00061

证明 R n ( x i ) f ( x i ) n ( x i ) 0 ,
故 R n ( x ) K ( x ) x x ( 0 ) x x ( 1 ) ( x x n ).
其中 K (x)是与 x有关的待定函数.
如何求 K (x) ?
8
现把x看成是[a, b]上的固定点, 作辅助函数
x22
x2n
a2
f
(x2
)
1 xn xn2 xnnan f (xn)
系数矩阵A的行列式是Vandermonde行列式，其值为
n
deA t() (xj xi)
i,j0,ij
当插值节点xi (i=0, 1, 2, …, n)互不相同时，此行列
式不为0, 即系数矩阵A可逆. 因此ai (i=0, 1, 2, …, n),
11 2181.031 3 03.
抛物线插值. 取x0=11, x1=12, x1=13, 插值多项式为
L2(x)2.39((1 7x 1 91 1))2 21 x (( 111)3 )32.48((1 4x 2 91 1))1 11 x (( 211)3 )3 2.56(4x 91)1x (1)2 (1 31)11 ( 31)2
xx0xx11y0xx1xx00y1
x0
x1
l0 ( x)
xi x0 x1
1次多项式
10
l0 (x )y 0 l1 (x )y 1
l1( x)
xi x0 x1
1次多项式
01
13
➢ 二次插值多项式
已知
xi
x0 x1 x2
yi f(xi) y 0 y 1 y 2
求 L2(x)
(1) 至多2次多项式; (2) L 2 ( x i ) f ( x i ) y i ( i 0 , 1 , 2 ).

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

l0 (x) 9l1(x) 23l2 (x) 3l3 (x)
11 x3 45 x 2 1 x 1
4
4
2
为便于上机计算,常将拉格朗日插值多项式(6.8)改写成
Ln (x)
n k 0
yk
n
i0 ik
x xi xk xi
第16页/共81页
例6.5 已知f(x)的观测数据 x 1234
1 3
3 1
2
f (1.5) p(1.5) 1.25
第13页/共81页
例6.3 已知x=1, 4, 9 的平方根值,
7
用抛物插值公式, (x–x1)(x–x2)
(x–x0)(x–x2)
p2(x) =
y0
+
y1
求
(x0–x1)(x0–x2) (x–x0)(x–x1)
(x1–x0)(x1–x2)
+
第4页/共81页
这惟是一一性个说关明于，待不定论参用数何种a0方, a法1, 来构, a造n 的，n也+不1阶论线用性何方种 程组形,式其来系表数示矩插阵值行多列项式式为,只要满足插值条件(6.1)其结
果都是相互恒等的。
1 x0 x02 x0n
1 V
x1
x12
x1n
n i 1
i 1
(xi x j )
P(x) l0 (x) y0 l1(x) y1 ln (x) yn 事实上，由于每个插值基函数 lk (x)(k 0,1,, n) 都是n次值多项式,所以他们的线性组合
n
P(x) lk (x) yk k 0
（6.8）
是次数不超过n次的多项式 , 称形如（6.8）式的插
值多项式为n次拉格朗日插值多项式。并记为 Ln (x)

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

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)

P( x) an x an1 x
n
n1
a1 x a0
满足
P( xi ) f ( xi )
(i 0,1,2,, n)
计 则称P(x)为f(x)的n次插值多项式。这种插值法通常 算 称为代数插值法。其几何意义如下图所示 方 法 课 件 y=p(x)
y=f(x)
2016/12/27
算 l0 ( x0 ) 1, l0 ( x1 ) 0 , l0 ( x2 ) 0 方 法 这个问题容易求解。由上式的后两个条件知 : 课 件 x1 , x 2 是 l0 ( x) 的两个零点。于是
1 再由另一条件 l0 ( x0 ) 1 确定系数 c ( x0 x1 )(x0 x2 ) ( x x1 )(x x2 ) 从而导出 l0 ( x) ( x0 x1 )(jkhh x0 x 2 ) 2016/12/27 14
直接由插值条件决定，
y
计 即 a0 , a1 , a 2 满足下面 y0 算 的代数方程组： 方 O x0 法 课 2 a a x a x 0 1 0 2 0 y0 件 该三元一
y=L2(x) y1 x1 y1 x2 y=f(x) x
2 a a x a x 0 1 1 2 1 y1 2 a a x a x 2 2 y2 0 1 2
(i=0,1,2,…,n )
的便于使用的插值多项式P(x),先考察几种简单情形,
线性插值是代数插值的最简单形式。假设给定了函数 近似地代替f(x)。选
x1 的值， f(x)在两个互异的点 x0 ， y0 f ( x0 ), y1 f ( x1 )
,现要求用线性函数 p( x) ax b 择参数a和b, 使 p( xi ) f ( xi )(i 0,1) P(x) 为f(x)的线性插值函数 2016/12/27 jkhh 。

第14页，共68页。
三次样条插值
对于待定系数a j ,bj , c j .d j j 1,2,...n,即4n个未知系数， 而插值条件为4n 2个，还缺两个，因此须给出两个 条件称为边界条件，有以下三类： 第一类 已知两端点的一阶导数
s( s(
x0 xn
) )
f (x0 ) m0 f (xn ) mn
第12页，共68页。
4.4.2 三次样条插值
定义 设函数f (x)是区间[a,b]上的二次连续可微函数， 在区间[a，b]上给出一个划分
：a x0 x1 ... xn1 xn b 如果函数s( x)满足条件
（1）s(x j ) f (x j ) ( j 0,1,2,...n); (2) 在每个小区间[x j1, x j ]( j 1,2,..., n)上s(x)是不超过
Mi 2!
( xi 1
xi )2
M i1 3!
Mi
( xi 1
xi )2
解得
s(xi )
yi1 yi xi1 xi
(
1 6
M
i 1
2 6
M
i
)( xi 1
xi
)
(1)
第18页，共68页。
三次样条插值
同理在[xi1, xi ]上讨论得
s(xi )
yi xi
yi1 xi1
(
2 6
M
i
1 6 M i1)(xi
第21页，共68页。
三次样条插值
第一类边界条件：s(x0 ) f (x0 ) s(xn ) f (xn )
(1) 式中令i 0得
s(x0 )
y1 x1
y0 x0
(1 6

54.859 55.439 // 57.602 57.766 51.891 36.464
先用 MATLAB 画出水流速散点图。
2024/1/2
差值方法
t=[0 0.921 1.843 2.949 3.871 4.978 5.9 7.006 7.982 8.967 10.954 12.032 12.954 13.875 14.982 15.903 16.826 17.931 19.037 19.959 20.839 22.958 23.88 24.986 25.908]; r=[54.516 42.320 38.085 41.679 33.297 37.814 30.748 38.455 32.122 41.718 73.686 76.434 71.686 60.19 68.333 59.217 52.011 56.626 63.023 54.859 55.439 57.602 57.766 51.891 36.464];
2024/1/2
差值方法
例 1、已知欧洲一个国家的地图，为了算出它的国土 面积，对地图作了如下测量：以由西向东方向为 x 轴，由南向北方向为 y 轴，选择方便的原点，并将 从最西边界点到最东边界点在 x 轴上的区间适当的 分为若干段，在每个分点的 y 方向测出南边界点和北 边界点的 y 坐标 y1 和 y2，这样就得到下表的数据（单 位：mm）。
3、样条插值
这是最常用的插值方法。数学上所说的样条，实质上
是指分段多项式的光滑连接。设有
a x0 x1 xn b
称分段函数 S(x) 为 k 次样条函数,若它满足
(1) S(x) 在每个小区间上是次数不超过 k 次的多项式;
(2) S(x) 在[a,b] 上具有直到 k 1阶的连续导数。 用样条函数作出的插值称为样条插值。工程上广泛采用三

同理 l1(x)((xx1 xx00))((xx1xx22))
构造3次多项式L3(x) 逼近 Erf(x)
设
L3(x)= a0 + a1x +a2x2 + a3x3,
令
L3(xi)=Erf(xi)
a0 0
得
a0 0.6a1 (0.6)2 a2 (0.6)3 a3 0.6039
a0
1.2a1
(1.2)2 a2
(1.2)3 a3
0.9103
a0 1.8a1 (1.8)2 a2 (1.8)3 a3 0.9891
两点式: L1(x)x x1 x x0 0y1x x11 x x0y0
由两点式可以看出， L1 (x)是由两个线性函数
l0(x)x x11 x x0,l1(x)x x1 x x0 0
的线性组合得到，其系数分别为y0， y1。即
L 1(x)l0(x)y0 l1(x)y1
显然， l0 (x)及l1 (x)也是线性插值多项式，在节 点x0,x1上满足条件：
满足: Ln(xi)= yi (k = 0,1,…,n)
(4.1) (4.2)
则称 (4.1)为满足插值条件(4.2)的代数插值。
定理4.1 若插值结点x0,x1,…,xn 是(n+1)个互异
点,则满足插值条件 Ln(xi)= yi (k = 0,1,…,n) 的n次插值多项式
Ln(x)=a0 + a1x +……+ anxn 存在而且是唯一的。
即
1 lk(xj)0
j k (j,k=0,1,2)
j k
满足上式的插值基函数很容易求出。如求l0(x), 因x1, x2 为其零点，故可表为
l0(x)A (x x 1)x ( x2)

数值分析课件-第02章插值法
目录
• 插值法基本概念与原理 • 拉格朗日插值法 • 牛顿插值法 • 分段插值法 • 样条插值法 • 多元函数插值法简介
01 插值法基本概念与原理
插值法定义及作用
插值法定义
插值法是一种数学方法，用于通过已知的一系列数据点，构造一个新的函数， 使得该函数在已知点上取值与给定数据点相符，并可以用来估计未知点的函数 值。
06 多元函数插值法简介
二元函数插值基本概念和方法
插值定义
通过已知离散数据点构造一个连 续函数，使得该函数在已知点处
取值与给定数据相符。
插值方法分类
根据构造插值函数的方式不同， 可分为多项式插值、分段插值、
样条插值等。
二元函数插值
针对二元函数，在平面上给定一 组离散点，构造一个二元函数通 过这些点，并满足一定的光滑性
差商性质分析
分析差商的性质，如差商 的对称性、差商的差分表 示等，以便更好地理解和 应用差商。
差商与导数关系
探讨差商与原函数导数之 间的关系，以及如何利用 差商近似计算导数。
牛顿插值法优缺点比较
构造简单
牛顿插值多项式构造过程相对简 单，易于理解和实现。
差商可重用
对于新增的插值节点，只需计算 新增节点处的差商，原有差商可 重用，节省了计算量。
要求。
多元函数插值方法举例
多项式插值
分段插值
样条插值
利用多项式作为插值函数，通 过已知点构造多项式，使得多 项式在已知点处取值与给定数 据相符。该方法简单直观，但 高阶多项式可能导致Runge现 象。
将整个定义域划分为若干个子 区间，在每个子区间上分别构 造插值函数。该方法可以避免 高阶多项式插值的Runge现象 ，但可能导致分段点处的不连 续性。