数值计算方法 第 4 章 插 值 法 4.4 Newton 插值法

上一讲的简单回顾 ● 插值多项式的存在惟一性: 满足插值条件 Pn(xi)=f(xi), ( i=0,1,2,…,n) n次插值多项式Pn(x)=a0+a1x+a2x2+……+anxn 存在而且惟一. ● 插值余项: Rn(x)= f(x)- Pn(x)= , ● Lagrange插值多项式 ,i =0,1,…,n 其中 称为Lagrange插值基函数

本讲主要内容: 缺点: 不具有承袭性,即每当增加一个节点时,不仅要增加求 和的项数,而且以前的各项也必须重新计算. 优点: 具有严格的规律性,便于记忆. 缺点: 不具有承袭性,即每当增加一个节点时,不仅要增加求 和的项数,而且以前的各项也必须重新计算. 为了克服这一缺点,本讲将建立具有承袭性的插值公式— Newton插值公式. 本讲主要内容: ● Newton插值多项式的构造 ● 差商的定义及性质 ● 差分的定义及性质 ● 等距节点Newton插值公式

一 基函数 问题1 求作n次多项式 使满足 (1) (2) 为了使 的形式得到简化,引入如下记号 (3)

称为Newton插值的以x0,,x1,…,xn为节点的基函数,即 可以证明,这样选取的基函数是线性无关的,由此得 出的问题4.1的解便于求值,而且新增加一个节点 xn+1时 只需加一个新项 即 而 (4)

依据条件(2),可以依次确定系数c0,c1,…,cn..例如, 取x=x0,,得 取x=x1 ,得

. 为了得到计算系数ci的一般方法,下面引进差商的概念.

二 差商的定义 给定[a,b]中互不相同的点x0,x1,x2,…,以及f(x)在这些点处相 二 差商的定义 给定[a,b]中互不相同的点x0,x1,x2,…,以及f(x)在这些点处相 应的函数值f(x0),f(x1),f(x2),…,用记号 表示f(x)在x0及x1两点的一阶差商. 用记号 表示f(x)在x0,x1,x2三点的二阶差商. 一般地,有了k-1阶差商之后, 可以定义f(x)在x0,x1,..,xk的k阶差商

三 Newton插值公式 由差商定义,有 f(x)= f[x0]+(x-x0)f[x,x0] f[x,x0]= f[x0,x1]+(x-x1)f[x,x0,x1] f[x,x0,x1]= f[x0,x1,x2]+(x-x2)f[x,x0,x1,x2] ……….. f[x,x0,…xn-1]= f[x0,…,xn]+(x-xn)f[x,x0,….,xn] 将以上各式，由下而上逐步代入，得到 　f(x)= f(x0)+(x-x0) f[x0,x1]+(x-x0)(x-x1) f[x0,x1,x2] +…+(x-x0)…(x-xn-1) f[x0,…,xn] (5) +(x-x0)…(x-xn-1)(x-xn)f[x,x0,…xn]

记 Nn(x)= f(x0)+(x-x0) f[x0,x1]+(x-x0)(x-x1) f[x0,x1,x2] +…+(x-x0)…(x-xn-1) f[x0,…,xn] (6) Rn(x)= (x-x0)…(x-xn) f[x,x0,…,xn]= f[x,x0,…,xn]wn+1(x) (7) 则(5)可表示为 f(x)= Nn(x)+ Rn(x) (8) 显然, Nn(x)是次数不超过n的多项式,且有 Rn(xi)= f[x,x0,…,xn]wn+1(xi)=0, i=0,1,…,n 即 Nn(xi)= f(xi) , i=0,1,…,n 由此可知,如此构造的函数Nn(x)就是问题1的解,且 ci =f[x0,…,xi] , i=0,1,…,n (9)

公式(6)称为函数f(x)在节点x0,…,xn上的n阶Newton 插值公式, (7)式称为Newton插值公式余项,即截断误差.注 意到,余项表达式(7)只要求被插值函数f(x)在插值区间[a,b] 上连续. 由函数f(x)的插值多项式的惟一性,函数f(x) 的Newton 插值多项式与Lagrange插值多项式实为同一个多项式,即 Nn(x) ≡ Ln(x) 两者不过是表现形式不同而已.由此有: 若f(x)∈Cn+1[a,b], 则有 Rn(x)= f[x,x0,…,xn]wn+1(x)= (10) ,

四 差商的性质 性质1(差商与函数值的关系) 证明： 性质2(对称性) 其中i0,…,ik是0,1,…k的任排列. 证明: 由性质1可知.

性质3(差商与导数的关系) f(x)∈Ck[a,b], 证明: 由式(10)即得. 性质4(多项式的差商)设f(x)为n次多项式,则其一阶差商 是x的n-1次多项式 证明: 推论 n次多项式pn(x)的k阶差商pn[x0,…xk],当k≤n时 是n-k次多项式,当k>n时恒为0

运用Newton插值公式(6)进行计算时,先计算f(x)关于 节点x0,…,xn的各阶差商.计算过程如下表所示 . xk f(xk) 一阶差商 二阶差商 三阶差商 n 阶差商

计算Nn(x)时,常采用秦九韶算法,即 . 下面给出Newton插值法的计算机算法.开始时,f(k)存放函数值f(xk),运算完毕f(k)存放k阶差商f[x0,…,xk]

Newton插值算法 (1) 输入: xi, fi; di=fi (i=0,1,…,n); 计算差商 对i=1,2,…,n 做 (3.1) 对j=i,i+1,…,n 做 fj=(dj-dj-1)/(xj-xj-i); (3.2) 对j=i,i+1,…,n 做 dj=fj; (4) 计算插值N(u) (4.1)输入插值点u; (4.2) v=0; (4.3) 对i=n,n-1,…,1,0 做 v=v(u-xi)+fi; (5) 输出u,v.

五 等距节点的Newton插值公式与差分 (6)可以简化. 当插值节点x0,…,xn为等距分布时,Newton插值公式 (6)可以简化. 设插值节点xj=x0+jh, j=0,1,…,n; h=(b-a)/n称为步长,且 x0=a, xn=b. 令x=x0+th,则当x0≤x≤xn时,0≤t≤n. 基函数 此时差商也可进一步化简,为此引进差分的概念. 定义 称 △f(xi)=f(xi+h)-f(xi) 和 ▽f(xi)= f(xi)-f(xi-h) 分别为函数f(x)在点xi处的一阶向前差分和一阶向后差分.

一般地,称k阶差分的差分为k+1阶差分,如二阶向前和向 后差分分别为 计算各阶差分可按如下差分表进行.

向前差分表

性质3(多项式的差分)若f(x)∈Pn(n次多项式类), 则 差分具有如下性质: . 性质1(差分与函数值的关系) 各阶差分均可表示为函值 fj=f(xj)的线性组合: 性质2(前差与后差的关系): 性质3(多项式的差分)若f(x)∈Pn(n次多项式类), 则 其中

性质4(差分与差商的关系): 性质5(差分与导数的关系 利用这些性质,可将Newton公式 Nn(x)= f(x0)+(x-x0) f[x0,x1]+(x-x0)(x-x1) f[x0,x1,x2] +…+(x-x0)…(x-xn-1) f[x0,…,xn] 进一步简化

(11) 称公式(11)为Newton向前差分插值公式,其余项为 (12) 如果将式(6)改为按节点xn,xn-1,…,x0的次序排列的Newton插 值公式,即

令x=xn-th, 则当x0≤x≤xn时,0≤t≤n.利用差商与向后 差分的关系, 式(13)可简化为 (13) (14) 称式(14)为Newton向后差分插值公式,其余项为

若要计算的插值点x较靠近点x0,则用向前插值公式(4. 8),这时t=(x-x0)/n的值较小,数值稳定性较好 若要计算的插值点x较靠近点x0,则用向前插值公式(4.8),这时t=(x-x0)/n的值较小,数值稳定性较好.反之,若x靠近xn,,,则用向后插值公式(14). 利用向前与向后差分的关系(差分性质2): 式(14)可表示成 (15) 这样,计算靠近x0或xn的点的值时,都只需构造向前差分表

例 给定f(x)在等距节点上的函数值表如下: xi 0.4 0.6 0.8 1.0 f(xi) 1.5 1.8 2.2 2.8 分别用Newton向前和向后差分公式,求f(0.5)及f(0.9)的近似值. 解 先构造向前差分表如下: xi fi △fi △2fi △3fi 0.4 1.5 0.6 1.8 0.3 0.8 2.2 0.4 0.1 1.0 2.8 0.6 0.2 0.1 x0=0.4, h=0.2, x3=1.0. 由(4.8)和(4.12),分别用差分表中对角线上的值和最后一行的值,得Newton向前和向后插值公式如 下:

(1) (2) 当 x=0.5时,用公式(1),这时t=(x-x0)/h=0.5. 将t=0.5代入(1),得 f (0.5)≈N3(0.5)=1.64375. 当x=0.9时, 用公式(2), 这时t=(x3-x)/h=0.5. 将t=0.5代入(2), 得 f (0.9)≈N3(0.9)=2.46875.

课后练习题 P217: 第2题, 第4题, P219: 第11题.