计算方法 第三章插值法和最小二乘法 §34 Newton插值法
第三章 插值法和最小二乘法 §3.4 Newton插值法
§34 Newton插值法 我们知道, Lagrange插值多项式的插值基函数为 1(x)=I X-X j=0,1,2,…,n 形式上太复杂计算量很大并且重复计算也很多 由线性代数的知识可知任何一个n次多项式都可以表示成 1,x-x0,(x-x0)(x-x1)…,(x-x0)(x-x1)…(x-xn-1) 共n+1个多项式的线性组合 那么,是否可以将这n+1个多项式作为插值基函数呢?
§3.4 Newton插值法 l (x) j Õ ¹ = - - = n i j i j i i x x x x 0 ( ) ( ) j = 0,1,2,L,n 我们知道,Lagrange插值多项式的插值基函数为 形式上太复杂,计算量很大,并且重复计算也很多 由线性代数的知识可知,任何一个n次多项式都可以表示成 1, , 0 x - x ( )( ), 0 1 x - x x - x ( )( ) ( ) - 0 - 1 - n-1 L, x x x x L x x 共n+1个多项式的线性组合 那么，是否可以将这n+1个多项式作为插值基函数呢？
显然,多项式组 X-X x-Xo(X-x X X-x X-X 线性无关,因此,可以作为插值基函数 设插值节点为x,函数值为f,i=01…,m h=x+1-x,=0,1,2…,n-1h=maxh 插值条件为P(x)=f,i 设插值多项式P(x)具有如下形式 (x)=ao+a1(x-x)+a2(x-x0)(x-x1)+… +an(x-x0)(x-x1)…(x-xn1)
1, , 0 x - x ( )( ), 0 1 x - x x - x ( )( ) ( ) - 0 - 1 - n-1 L, x x x x L x x 显然，多项式组 线性无关，因此，可以作为插值基函数 , i 设插值节点为 x 函数值为 f i , i = 0,1,L,n hi = xi+1 - xi , i = 0,1,2,L,n - 1 i i h = maxh 插值条件为 P(xi ) = f i , i = 0,1,L,n ( )( ) ( ) ( ) ( ) ( )( ) 0 1 1 0 1 0 2 0 1 + - - - - = + - + - - + n n a x x x x x x P x a a x x a x x x x L L 设插值多项式P(x)具有如下形式
P(x)应满足插值条件P(x)=f,i=0,1…,n 有P(x)=f P(x1)=f1=ao+a1(x1-x0) P(x2)=f2=ao+an1(x2-x)+a2(x2-x)(x2-x1) f2-fo fi-fo x2-x0x1-x0 再继续下去待定系数的形式将更复杂 为此引入差商和差分的概念
P(x)应满足插值条件 P(xi ) = f i , i = 0,1,L,n 0 0 0 有 P(x ) = f = a ( ) ( ) 1 1 0 1 1 0 P x = f = a + a x - x 0 0 a = f 1 0 1 0 1 x x f f a - - = ( ) ( ) ( )( ) 2 2 0 1 2 0 2 2 0 2 1 P x = f = a + a x - x + a x - x x - x 2 1 1 0 1 0 2 0 2 0 2 x x x x f f x x f f a - - - - - - = 再继续下去待定系数的形式将更复杂 为此引入差商和差分的概念
、差商(均差) 定义1.设f(x)在互异的节点x处的函数值为/,1=0,1…n 称 f x 为(x)关于节点x,x一阶差商(均差) f[r,x,,xxI fLxxk-frx,x,] (≠j≠k 为f(x)关于x,x,x的二阶差商 依此类推
一、差商(均差) 定义1. f x x f i n i i 设 ( )在互异的节点 处的函数值为 , = 0,1,L, 称 [ , ] (i j) x x f f f x x i j i j i j ¹ - - = 为 ( )关于节点 , 一阶差商(均差) i j f x x x ( ) [ , ] [ , ] [ , , ] i j k x x f x x f x x f x x x k j i k i j i j k ¹ ¹ - - = 为f (x)关于xi , xj , xk的二阶差商 依此类推
f[x,x1灬…,x,]-f flx k-1 为f(x)关于节点x,x,…,x,x的阶差商 显然 八,x,…,x1,x]=/xx灬2- 0/41//~k x 差商具有如下性质 (1)f(x)的阶差商[0,x1八…,xk1x由函数值 f(x)f(x1)…,f(xk)的线性组合表示,且
[ , , , , ] 0 1 k 1 k i i i i f x x x x L - 为f (x)关于节点xi0 , xi1 ,L, xi k-1 , xi k 的k阶差商 [ , , , , ] 0 1 k 1 k f x x x x L - 差商具有如下性质 的线性组合表示 且 的 阶差商 可由函数值 ( ), ( ), , ( ) , (1) ( ) [ , , , , ] 0 1 0 1 1 k k k f x f x f x f x k f x x x x L L - 显然 k k k k k i i i i i i i i i x x f x x x f x x x x - - = - - - 1 0 1 1 0 1 2 [ , ,L, ] [ , ,L, , ] k k k k k x x f x x x f x x x x - - = - - - 1 0 1 1 0 1 2 [ , ,L, ] [ , ,L, , ]
f[x0,x1八…,x=1xk ∑ (x1-x0)…(x1-x-1)(x1-x1+1)…(x1-xk) (2)差商具有对称性即任意调换节点的次序差商的值不变 如 fL 0厂1 0 ]=f[ 241/0 (3)当(x)在包含节点x0,x1…,x的区间存在时, 在x,x1…,x之间必存在一点ξ,使得 几[x,x,…,x]=( k!
[ , , , , ] 0 1 k 1 k f x x x x L - å= - - - - + - = k i i i i i i i k i x x x x x x x x f x 0 0 1 1 ( ) ( )( ) ( ) ( ) L L (2) 差商具有对称性,即任意调换节点的次序,差商的值不变 [ , , ] 0 1 2 f x x x [ , , ] 0 2 1 = f x x x [ , , ] 2 1 0 如 = f x x x (3) ( ) , , , , 0 1 当f （k ) x 在包含节点x x L xk的区间存在时 在x0 , x1 ,L, xk之间必存在一点x ,使得 [ , , , ] 0 1 k f x x L x ! ( ) ( ) k f k x =
差商的计算方法(表格法)差商表 Chashang. m xf(x)阶差商二阶差商三阶差商四阶差商 xo f(xo) x1|f(x1) 冫f[ Roux. flo Xux 0/1 x2f(2) 243 01 /[x2,x 1/42434 x3(x3) fl x4 f (4) 规定函数值为零阶差商
( ) ( ) ( ) ( ) ( ) ( ) 4 4 3 3 2 2 1 1 0 0 x f x x f x x f x x f x x f x x f x k k 一阶差商 二阶差商 三阶差商 四阶差商 差商的计算方法(表格法): [ , ] 0 1 f x x [ , ] 1 2 f x x [ , ] 2 3 f x x [ , ] 3 4 f x x [ , , ] 0 1 2 f x x x [ , , ] 1 2 3 f x x x [ , , ] 2 3 4 f x x x [ , , , ] 0 1 2 3 f x x x x [ , , , ] 1 2 3 4 f x x x x [ , , , ] 0 1 4 f x x L x 规定函数值为零阶差商 差商表 Chashang.m
二、差分 定义2.设f(x)在等距节点x4=x+M处的函数值为k k=0,1 称 k k k=01,…,n-1 为f(x)在x处的一阶向前差分 了k=fk k-1 k=1,2 为f(x)在x处的一阶向后差分 Afk=4k+1-4k为f(x)在x处的二阶向前差分 V2f=V-V1为f(x)在xk处的二阶向后差分
二、差分 定义2. 称 设 在等距节点 处的函数值为 0,1, , , ( ) , 0 k n f x x x kh f k k = L = + k k k Df = f - f +1 为f (x)在 xk 处的一阶向前差分 k = 0,1,L,n - 1 Ñ k = k - k -1 f f f 为f (x)在 xk 处的一阶向后差分 k = 1,2,L, n k k k D f = Df - Df +1 2 为f (x)在 xk 处的二阶向前差分 1 2 Ñ k = Ñ k - Ñ k - f f f 为f (x)在 xk 处的二阶向后差分
依此类推 AA=△11-4为(x)在x处的m价向前差分 V"f=Vm1f-Vm1fk1为(x)在xk处的m价向后差分 可以证明 A"JK k+m 如 k Vf= fk-fu △ fk=△fk+1-△fk k+2 Vfk2= Vr2-Vfi △ k+3
k m k m k m f f f 1 1 1 - + - D = D - D 为f (x)在 xk 处的m阶向前差分 为f (x)在 xk 处的m阶向后差分 依此类推 1 1 1 - - - Ñ = Ñ - Ñ k m k m k m f f f 可以证明 k m m k m f f D = Ñ + D k = Ñ k +1 f f 2 2 2 D k = Ñ k + f f 3 3 3 D k = Ñ k + f f 如 k k k D f = f - f +1 k k k Ñ f = f - f + 1 + 1 k k k D f = D f - D f +1 2 2 2 1 2 Ñ k+ = Ñ k+ - Ñ k+ f f f