均差与牛顿插值多项式.ppt

When you start writing the program, you will find how easy it is to calculate the Lagrange polynomial. Oh yeah? What if I find the current interpolation not accurate enough? Then you might want to take more interpolating points into account. Right. Then all the Lagrange basis, li(x), will have to be re-calculated. Excellent point ! We will come to discuss this problem. 2.3均差与牛顿插值多项式 我们知道,Lagrange插值多项式的插值基函数为 形式上太复杂,计算量很大,并且重复计算也很多 由线性代数的知识可知,任何一个n次多项式都可以表示成 共n+1个多项式的线性组合 那么，是否可以将这n+1个多项式作为插值基函数呢？ 显然，多项式组 线性无关， 因此，可以作为插值基函数 有 再继续下去待定系数的形式将更复杂 牛顿插值 /* Newton’s Interpolation */ Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x) 都需重新算过。 将 Ln(x) 改写成 的形式，希望每加一个节点时， 只附加一项上去即可。 ? ? ? ? ? 差商(亦称均差) /* divided difference */ 1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */ 2阶差商 1 1 1 0 1 0 1 0 1 1 1 0 1 0 ] , , ... , [ ] , , ... , [ ] , , ... , [ ] , ... , , [ ] , ... , [ + + - - + + + - - = - - = k k k k k k k k k k k x x x x x f x x x f x x x x x f x x x f x x f (k+1)阶差商： 事实上 其中 Warning: my head is exploding… What is the point of this formula? 差商的值与 xi 的顺序无关！ 差商具有如下性质(请同学们自证)： (2) 差商具有对称性,即任意调换节点的次序,差商的值不变 如 差商的计算方法(表格法): 规定函数值为零阶差商 差商表 ? 牛顿插值 /* Newton’s Interpolation */ 1 2 … … … … n?1 Nn(x) Rn(x) ai = f [ x0, …, xi ] 把后一式带入前一式 注：? 由唯一性可知 Nn(x) ? Ln(x)， 只是算法不同，故其余项也相同，即 ? 实际计算过程为 f (x0) f (x1) f (x2) … f (xn?1) f (xn) f [x0, x1] f [x1, x2] … … … … f [xn?1, xn] f [x0, x1 , x2] … … … … f [xn?2, xn?1, xn] f [x0, …, xn] f (xn+1) f [xn, xn+1] f [xn?1, xn, xn+1] f [x1, …, xn+1] f [x0, …, xn+1]