数值分析教学课件

1、第二章 插值 /* Interpolation */,当精确函数 y = f(x) 非常复杂或未知时，在一系列节点 x0 xn 处测得函数值 y0 = f(x0), yn = f(xn)，由此构造一个简单易算的近似函数 g(x) f(x)，满足条件g(xi) = f(xi) (i = 0, n)。这里的 g(x) 称为f(x) 的插值函数。最常用的插值函数是 ?,多项式,g(x) f(x),f(x),g(x),由于代数多项式的结构简单，数值近似和理论分析都方便，实用中常取代数多项式 作为插值函数，称其为n次插值多项式/* n-degree Interpolating polynomial */

2、 ，求Pn(x)的过程也叫做拉格朗日插值/* Lagrange Interpolation */ 。,点斜式,2.1 拉格朗日插值 /* Lagrange Interpolation */,n = 1 线性插值,可见 L1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。,称为拉氏基函数 /* Lagrange Basis */， 满足条件 li(xj)=ij /* Kronecker Delta */,n = 2 抛物线插值,已知 x0 , x1 , x2 ; y0 , y1 , y2 ，求L2(x)=a0+a1x + a2x2, 使得L2(xi)= yi , i=

3、0,1,2.,用基函数表示,其中l0(x)、l1(x)、l2(x)为二次式，且满足以下条件,li(xj)=ij,n 1,每个 li 有 n 个零点 x0 xi xn,Lagrange Polynomial,与 有关，而与 无关,节点,f,Quiz: 给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是 l2(x)的图像？,证明： 由插值条件可知，插值多项式Ln(x)的系数ai满足线性方程组,其系数行列式是n+1阶范德蒙(Vandermonde)行列式,因为xixj，于是V0，方程组的解存在且唯一, 插值余项 /* Remainder */,Rolles Theor

4、em: 若 充分光滑， ，则 存在 使得 。,推广：若,使得,Rn(x) 至少有 个根,n+1,(t)有 n+2 个不同的根 x0 xn x,注意这里是对 t 求导,例：已知,分别利用 sin x 的1次、2次 Lagrange 插值计算 sin 50 并估计误差。,解：,n = 1,分别利用x0, x1 以及 x1, x2 计算,利用,而,sin 50 = 0.7660444,外推 /* extrapolation */的实际误差 0.01001,利用,内插/* interpolation */ 的实际误差 0.00596,内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。

5、,n = 2,sin 50 = 0.7660444,2次插值的实际误差 0.00061,高次插值通常优于低次插值,但绝对不是次数越高就越好，嘿嘿,插值误差的实用估计法,设Ln(x) 和Ln*(x)分别是以x0，x1,xn和x1, x2,xn1为节点的插值多项式。则,Ln(x) 和Ln*(x)只相差一个节点，可以设想f(n+1)() f(n+1) (*),程序设计,因此， ()的零点为 =., =.;,解：由二次插值,例 已知二次式f(x)在x=0,1,2的值分别为-0.81,0.19, 3.19, 求f(x)的零点、极值点、x=1处导数和积分 .,极值点 x=0;, =;, .,例 设 , ,

6、 是互不相同的节点， ()是拉格朗日插值基函数，求证：,证明(1)：设 = , =, 求()的次拉格朗日插值多项式，得到,例 设 , , 是互不相同的节点， ()是拉格朗日插值基函数，求证：,证明(2)：,例 设 , , 是互不相同的节点， ()是拉格朗日插值基函数，求证：,令x=0, 则有,另设 = + , ()的次拉格朗日插值多项式为,(n+1)!,证明(3): 利用式(1), 令x=0, 则有,例 设 = =, 在a,b上 ，求证：,0,证明: 设节点 =, =, 由插值理论有,因为|(x-a)(x-b)|有极大值(b-a)2/4,并且 ，因此有,2.2 牛顿插值 /* Newtons

7、Interpolation */, 差商(亦称均差) /* divided difference */,1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */,2阶差商,(k+1)阶差商：,差商的值与 xi 的顺序无关！, 牛顿插值 /* Newtons Interpolation */, ,Nn(x),Rn(x),ai =,f x0, , xi , ,=Nn(x)+Rn(x),?,Nn(x) Ln(x),注： 由唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其余项也相同，即, 实际计算过程为,f (x0) f (x1)

8、f (x2) f (xn1) f (xn),f x0, x1 f x1, x2 f xn1, xn,f x0, x1 , x2 f xn2, xn1, xn,f x0, , xn,f (xn+1) f x0, , xn+1,x0 x1 x2 xn1 xn,xn+1,sin 50 = 0.7660444,1/2 1/2 3/2 ,xi f (xi) f xi, xj f xi, xj , xk,/6 / 4 / 3 ,解一：取 构造差商表,解二：取 构造差商表,注：构造差商表时，插值节点要以距计算点由近到远的次序排列。,2.3 埃尔米特插值 /* Hermite Interpolation */

9、带导数的插值,不仅要求函数值重合，而且要求若干阶导数也重合。 即：要求插值函数 (x) 满足 (xi) = f (xi), (xi) = f (xi), , (m) (xi) = f (m) (xi).,注： N 个条件可以确定 阶多项式。,N 1,一般只考虑 f 与f 的值。,其中基函数0(x),1(x),0(x),1(x)都是三次多项式，并满足,0(x)=,(x-1)2,由条件0(0) = 1 和0(0) = 0 可解A和B ,同理,解：假设x0=0, x1=1,且,例：求三次多项式H3(x)，使满足插值条件H3(x0)=y0 ,H3 (x0)=y0, H3(x1)=y1 ,H3 (x1)

10、=y1, 并估计误差。, 基函数法,(Ax+B),0 (x)=,x(x-1)2 C,由条件0(0) = 1 可解C ,例：试用下表建立不超过3次的插值多项式。, 推广牛顿插值法,解：构造差商表,C=1,C,2.4 分段低次插值 /* piecewise polynomial approximation */,例：在5, 5上考察 的Ln(x)。取,n 越大， 端点附近抖动 越大，称为 Runge 现象, 分段线性插值 /* piecewise linear interpolation */, 分段抛物线插值 /* piecewise parabolic interpolation */,在每个

11、区间 上，用2次式 逼近 f (x):, 分段Hermite插值 /* Hermite piecewise polynomials */,为了保证xi-1, xi, xi+1, 是距x最近的三个节点,xi-1, xi, xi+1并不 一定是距x最近 的三个节点,2.5 三次样条 /* Cubic Spline */,定义,设 。三次样条函数 , 且在每个 上为三次多项式 /* cubic polynomial */。若它同时还满足 ，则称为 f 的三次样条插值函数 /* cubic spline interpolant */.,注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身

12、光滑，不需要知道 f 的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f 在所有插值点的导数值。,f(x),H(x),S(x),三弯矩法 /* method of bending moment */, 构造三次样条插值函数,S(x)是分段三次多项式，它在第i个子区间xi-1, xi上的表达式用Si(x)表示。假设Si(xi-1)=mi-1, Si(xi)=mi, hi= xi- xi-1 ,则,S(x)满足整个区间内C1连续吗？,如何选取mi的值，使S(x)二阶导数也连续？,两边乘以 ，并令,1. 第一类边界条件：,2. 第二类边界条件：,3. 第三类边界条件(当y=f(x)是周期函数)：,边界条件/* boundary conditions */,S(x