L数值分析ecture 7[教学类别]

1、Newton Interpolate 牛顿插值方法 Numerical Methods 1应用2 Newton Polynomials 1 00 ( )() nN Nnk nk Pxaxx 1010 ( )()P xaa xx 2010201 ( )()()()P xaa xxaxxxx 30102013012 ( )()()()()()()P xaa xxaxxxxa xxxxxx 1 0102013012 0 . ( )()()()()()().() N NNk k Pxaa xxaxxxxa xxxxxxaxx Is said to be Newton polynomial with N

2、 centers ，and 0121 ,., N x x xx Have the nodes 。 0121 ,., NN x x xxx 如何计算Newton Polynomials 1 0102013012 0 ( )()()()()()().() N NNk k Pxaa xxaxxxxa xxxxxxaxx 4010201301240123 433221100 ( )()()()()()()()()()() () ()()()() P xaa xxaxxxxa xxxxxxaxxxxxxxx axxaxxaxxaxxa 111 0100 () . () NN NNNN Sa SSxxa

3、SSxxa Newton 插值数学问题 Newton插值问题插值问题：已知在一组互异节点 上的函数值 ，求一个 尽可能低的Newton多项式 ，使得： 即： ( )(0,1,2, ) ii p xyin bxxxa n . 10 插值问题的解是唯一的， 区别仅是表达方式的不同！ Lagrange插值多项式的优缺点 1.当节点固定不变时，很容易计算多个不同点x 出的Lagrange插值多项式的值。 2.计算高阶（n）插值多项式，不能利用已计算 出的低阶插值多项式。 3.Newton插值方法是对Lagrange插值方法的一 个补充。特别适合于计算一个点上的各种阶 数的插值多项式的值。 低阶Newt

4、on插值问题的解法 n=0时： 000 ( )()Pxafx n=1时： 1010 ( )()Pxaaxx 00 01101 () ()() afx aaxxfx 10 101 10 ()() , fxfx afxx xx 2010201 ( )()()()Pxaaxxaxxxx n=2时： 00 01101 0120220212 () ()() ()()()() afx aaxxfx aaxxaxxxxfx 00 10 101 10 () ()() , af x f xf x af x x xx 低级Newton插值问题的解法 20120 2 2021 10 2020 10 2021 201

5、01020 202110 2110102 20 ()() ()() ()() ()()() 1 ()()()() ()1 ()()()() (1 f xaa xx a xxxx f xf x f xf xxx xx xxxx f xf xxxf xf xxx xxxxxx f xf xxxf xf xxx xx 1 2110 1021 202110 1201 012 20 ) ()()()()1 , , xxxx f xf xf xf x xxxxxx f x xf x x f x x x xx Divided difference 00 ()f xf x 10 01 10 , f xf x

6、f x x xx 1201 012 20 , , f x xf x x f x x x xx 12011 012 0 ,.,., ,., kk k k f x xxf x xx f x x xx xx 1211 12 ,.,., ,., kjkjkkjkjk kjkjkjk kkj f xxxf xxx f xxxx xx Newton Interpolate Polynomial 012 ,., kk af x x xx 1 0102013012 0 ( )()()()()()().() N NNk k Pxaa xxaxxxxa xxxxxxaxx (),0,1,2,., Nkk Pxy

7、kN Theorem 3.6 定义 则 满足( ) N Px Newton Interpolate Polynomial 300330 030101331 013012012332 333 ()(),() ,() ,() ()() f xf xf x xxx f x xf x xf x x xxx f x x xf x x xf x x x xxx f xP x 我们以N=3为例来说明Theorem 3.6的 证明思想。 30010012010123012 ( )(),(),()(),()()()P xf xf x xxxf x x xxxxxf x x x xxxxxxx 300 31001

8、101 320012001220212 330013001230310123303132 ()() ()(),()() ()(),(),()()() ()(),(),()(),()()()( P xf x P xf xf x xxxf x P xf xf x xxxf x x xxxxxf x P xf xf x xxxf x x xxxxxf x x x xxxxxxxf x 3) Exercise 0210102210101221 20022000120012202132 , , ,(),() ()(),()(),(),()()() f x xf x xf x x xxxf x xf x

9、x xxx f xf xf x xxxf xf x xxxf x x xxxxxP x 误差估计 由于插值多项式的唯一性，按照Newton插值公 式计算出来的多项式与按照Lagrangre插值公 式计算出来的多项式相同，误差也相同。 (1) 1 ( ) ( )( )( )( ) (1)! N NNN f Exf xPxx N 其中 。 ( , )a b 均差与导数的关系 (1) 1 ( ) ( )( )( )( ) (1)! N NNN f Exf xPxx N 以N=3为例： 000 001011 010120122 012012301233 ( )() ,() , ,() , ,() ,

10、,() f xf xf x xxx f x xf x xf x x xxx f x x xf x x xf x x x xxx f x x x xf x x x xf x x x x xxx 001001201 0123012 01234 01234 ( )(),(),()() ,()()() ,( ) ( ) ,( ) N f xf xf x xxxf x x xxxxx f x x x xxxxxxx f x x x x xx Pxf x x x x xx (4) 0123 ( ) , 4! f f x x x x x 算法 Example 3.12 Example 3.13 Chebys

11、hev Polynomial (1) 1 ( ) ( )( )( )( ) (1)! N NNN f Exf xPxx N 目标：调整节点，使得误差估计达到最小！ (1) 1 1 1 ( ) ( )( )( )( ) (1)! ( ) (1)! N NNN N N f Exf xPxx N M x N 目标：调整节点，使得 最小！ 1( )N x Chebyshev Polynomial Properties of Chebyshev Polynomial 定义： 0 1 12 ( )1 ( ) ( )2( )( ) kkk T x T xx T xxTxTx Property 2： 的首项系数为 ( ) k T x 1 2k Property 3（奇偶性） Property 3（三角表示） ( )cos(arccos( ) N TxNx cos(arccos( )cos(2)arccos(