计算方法插值b 2013年最新西安交通大学《数值分析》ppt课件

3.2 牛顿插值 /* Newtons Interpolation */ Lagrange 插值虽然易算，但若要增加一个节点时， 全部基函数 li(x) 都需重新算过。 将 Ln(x) 改写成 的形式，希望每加一个节点时， 只附加一项上去即可。 ? ? 差商(亦称均差) /* divided difference */ 1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */ 2阶差商 3.2 Newtons Interpolation 1 11010 10 1110 10 ,.,., ,.,., ,., + + + + + = = kk kkkk k kkk k xx xxxfxxxf xx xxxfxxxf xxf (k+1)阶差商： 事实上 其中 差商的值与 xi 的顺序无关！ 3 牛顿插值 /* Newtons Interpolation */ 1 2 n1 1 2 Nn(x) Rn(x)ai = f x0, , xi n1 3.2 Newtons Interpolation 3 =Nn(x)+Rn(x) ? Nn(x) Ln(x) 注： 由唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其 余项也相同，即 实际计算过程为 f (x0) f (x1) f (x2) f (xn1) f (xn) f x0, x1 f x1, x2 f xn1, xn f x0, x1 , x2 f xn2, xn1, xnf x0, , xn f (xn+1) f x0, , xn+1 f xn, xn+1 f xn1, xn, xn+1 f x1, , xn+1 x0 x1 x2 xn1 xn xn+1 3.2 Newtons Interpolation 例：已知 分别利用 1次、2次 Newton 插值公式计算 sin 50。 sin 50 = 0.7660444 1/2 1/2 3/2 0.79110 0.60703 -0.35155 xi f (xi) f xi, xj f xi, xj , xk /6 / 4 / 3 解一：取 构造差商表 1/2 3/2 1/2 0.60703 0.69906 -0.024094 xi f (xi) f xi, xj f xi, xj , xk / 4 / 3 /6 解二：取 构造差商表 注：构造差商表时， 插值节点要以距计算 点由近到远的次序 排列。 3.2 Newtons Interpolation 3.3 埃尔米特插值 /* Hermite Interpolation */带导数的插值 不仅要求函数值重合，而且要求若干阶导数也重合。 即：要求插值函数 (x) 满足 (xi) = f (xi), (xi) = f (xi), , (m) (xi) = f (m) (xi). 注： N 个条件可以确定 阶多项式。N 1 要求在1个节点 x0 处直到m 阶导数都重合的插值 多项式即为Taylor多项式 其余项为 一般只考虑 f 与f 的值。 3.3 Hermite Interpolation 其中基函数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)=y1, 并估计误差。 基函数法 (Ax+B) 0 (x)= x(x-1)2 C由条件0(0) = 1 可解C 同理 对于任意x0、 x1 ,记 x1 - x0 =h，则有 例：试用下表建立不超过3次的插值多项式。 推广牛顿插值法 x 0 1 2 f(x) 1 2 9 f(x) 3 解：构造差商表 1 2 9 1 73 0 1 2 xi f (xi) f xi, xi+1 f xi, xi+1 , xi+2 C=1 C 3.3 Hermite Interpolation 3.4 分段低次插值 /* piecewise polynomial approximation */ Remember what I have said? Increasing the degree of interpolating polynomial will NOT guarantee a good result, since high-degree polynomials are oscillating. 例：在5, 5上考察 的Ln(x)。取 -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大， 端点附近抖动 越大，称为 Runge 现象 Ln(x) f (x) 分段低次插值 L5(x) L2(x) L10(x) 3.4 Piecewise Polynomial Approximation 分段线性插值 /* piecewise linear interpolation */ -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 L10(x) P1(x) 设 把a, b分成n个小区间 xi-1, xi, i=1,2,n，在每个区间上，用1次式 逼近 f (x): 分段抛物线插值 /* piecewise parabolic interpolation */ 在每个区间 上，用2次式 逼近 f (x): 失去了原函数的光滑性。 分段Hermite插值 /* Hermite piecewise polynomials */ 给定 在 上利用两点的 y 及 y 构造3次Hermite函数 导数一般不易得到。 How can we make a smooth interpolation without aski