1、2 /* Newtons Interpolation */Lagrange 插值雖然易算，但若要增加一個節點時，全部基函數 li(x) 都需重新算過。將 Ln(x) 改寫成的形式，希望每加一個節點，只附加一項上去即可。? 差商(亦稱均差) /* divided difference */1階差商 /* the 1st divided difference of f w.r.t. xi and xj */2階差商12 Newtons Interpolation11101010111010,.,.,.,.,.,+-+-=-=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+

2、1)階差商 (k+1)th divided difference事實上其中 Warning: my head is explodingWhat is the point of this formula?差商的值與 xi 的順序無關！22 Newtons Interpolation 牛頓插值 /* Newtons Interpolation */12 n11+ (x x0) 2+ + (x x0)(x xn1) n1Nn(x)Rn(x)ai = f x0, , xi 32 Newtons Interpolation注： 由唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其余項也相同，即 實

3、際計算過程為(P124 table 3.7)f (x0)f (x1)f (x2)f (xn1)f (xn)f x0, x1f x1, x2 f xn1, xnf x0, x1 , x2 f xn2, xn1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn1, xn, xn+1 f x1, , xn+1 f x0, , xn+142 Newtons Interpolation 等距節點公式 /* Formulae with Equal Spacing */向前差分 /* forward difference */iiifff-=+1ikikikikffff1111)

4、(-+-=向后差分 /* backward difference */111-=ikikikfffi1iifff-=中心差分 /* centered difference */其中當節點等距分布時:More given on p.113-114.52 Newtons Interpolation 差分的重要性質： 線性：例如 若 f (x)是 m 次多項式，則 是 次多項式，而 差分值可由函數值算出：=-+-=Dnjjknjknfjnf0)1(=-+-=njnjkjnknfjnf0)1(其中/* binomial coefficients */ 函數值可由差分值算出：kjnjknfjnfD=+=

5、0kkkhkfxxf!,.,00D=knkknnnhkfxxxf!,.,1=-kkkhff0)()(D=x由 Rn 表達式62 Newtons Interpolation牛頓公式 牛頓前差公式 /* Newtons forward-difference formula */P126 牛頓后差公式 /* Newtons backward-difference formula */P127將節點順序倒置：設，則)()()(000 xfkthtxNxNknknn=+=設，則)()1()()(0nknkknnnxfkthtxNxN-=+=注：一般當 x 靠近 x0 時用前插，靠近 xn 時用后插，故兩

6、種公式亦稱為表初公式和表末公式。7Homework P131. 483 厄米插值 /* Hermite Interpolation */不僅要求函數值重合，而且要求若干階導數也重合。即：要求插值函數 (x) 滿足 (xi) = f (xi), (xi) = f (xi), (mi) (xi) = f (mi) (xi).注： N 個條件可以確定 階多項式。N 1要求在1個節點 x0 處直到m0 階導數都重合的插值多項式即為Taylor多項式其余項為一般只考慮 f 與f 的值。93 Hermite Interpolation例：設 x0 x1 x2, 已知 f(x0)、 f(x1)、 f(x2)

7、 和 f (x1), 求多項式 P(x) 滿足 P(xi) = f (xi)，i = 0, 1, 2，且 P(x1) = f (x1), 并估計誤差。模仿 Lagrange 多項式的思想，設解：首先，P 的階數 =3+=213)()()()()(=0iiixhx1f xhxfxPh0(x)有根x1, x2，且 h0(x1) = 0 x1 是重根。)()()(22100 xxxxCxh-=又: h0(x0) = 1 C0 h2(x)h1(x)有根 x0, x2 )()()(201xxxxBAxxh-+=由余下條件 h1(x1) = 1 和 h1(x1) = 0 可解。與h0(x) 完全類似。 (

8、x)h1有根 x0, x1, x2 h1)()()(2101xxxxxxCx-=h1又: (x1) = 1 C1 可解。其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x1) = 1h1h1與 Lagrange 分析完全類似103 Hermite Interpolation一般地，已知 x0 , , xn 處有 y0 , , yn 和 y0 , , yn ，求 H2n+1(x) 滿足 H2n+1(xi) = yi ， H2n+1(xi) = yi。解：設+=ni)()()(=0iixhxhyixH2n+1n=0iyi其中 hi(xj) = ij , hi(xj)

9、 = 0, (xj) = 0, (xj) = ij hihihi(x)有根 x0 , , xi , , xn且都是2重根 )()()(2xlBxAxhiiii+=由余下條件 hi(xi) = 1 和 hi(xi) = 0 可解Ai 和 Bi (x)hi有根 x0 , , xn, 除了xi 外都是2重根 hi)()(iili2(x)xxCx-=hi又: (xi) = 1 Ci = 1hi)(x)(ili2(x)xx-=設則這樣的Hermite 插值唯一113 Hermite Interpolation 求Hermite多項式的基本步驟： 寫出相應于條件的hi(x)、 hi(x) 的組合形式； 對

10、每一個hi(x)、 hi(x) 找出盡可能多的條件給出的根； 根據多項式的總階數和根的個數寫出表達式； 根據尚未利用的條件解出表達式中的待定系數； 最后完整寫出H(x)。12Use divided difference table to solve Hermite interpolation problemsSee P137-P138See example 2.H.W. P140. 3134 分段低次插值 /* piecewise polynomial approximation */Remember what I have said? Increasing the degree of int

11、erpolating polynomial will NOT guarantee a good result, since high-degree polynomials are oscillating.例：在5, 5上考察 的Ln(x)。取-5-4-3-2-1012345-0.500.511.522.5n 越大，端點附近抖動越大，稱為Runge 現象Ln(x) f (x)分段低次插值144 Piecewise Polynomial Approximation 分段線性插值 /* piecewise linear interpolation */在每個區間 上，用1階多項式 (直線) 逼近 f (x):記 ，易證：當 時，一致失去了原函數