Re: [中學] 有關插值多項式

[yhliu (老怪物)]

※ 引述《wa007123456 (大笨羊)》之銘言：
: 不好意思...又來發文章了..@@
: as title
: 我看了課本許久 還是無法理解他的原理
: 上網google 只查到更複雜的講法
: 我只記得上學期我是用比較特別的方法做的
: 但是 這樣下去不是辦法
: 畢竟那個特別的辦法只適用在3次以下的f(x)
: 因為我晚了別人一年 所以重讀後..還是高一生的程度..
: 希望有高手能夠以比較容易理解的講法揭露出他的原理
: 小弟在此感激不盡!
: ps:抑或是背下公式就好，不必去瞭解他的原理呢?


多項式的插值主要有兩種, 一種是適用所給的點其橫座標
(x 座標) 是等距的, 公式稱 "牛頓插值公式"; 另一種則
不論所給點 x 座標是否等距都適用, 公式為 "拉格朗吉"
(Lagrange) 插值公式.

設函數 y=f(x) 的圖形通過 (x_1,y_1),...,(x_n,y_n),
其中 x_1,...,x_n 兩兩不等. 一個至多 n-1 階多項式足
以描述這些資料點, 也就是說:一個至多 n-1 階多項式函
數 y=g(x) 的圖形也通過這些點, 其中

                 (x-x_2)...(x-x_n)
  g(x) = y_1 * --------------------- +
               (x_1-x_2)...(x_1-x_n)
                  (x-x_1)(x-x_3)...(x-x_n)
         y_2 * ------------------------------ +
               (x_2-x_1)(x_2-x_3)...(x_2-x_n)

          . . . +

                  (x-x_1)(x-x_2)...(x-x_{n-1})
         y_n * ----------------------------------.
               (x_n-x_1)(x_n-x_2)...(x_n-x_{n-1})


這公式可以這麼想:

(1) 多項式 g(x) 至多 n-1 階. 我們可以考慮下列 n 個
    n-1 階多項式的線性組合 (加權和, 也就是各多項式
    分別乘以一個常數再加總):
      g_1(x) = (x-x_2)...(x-x_n),
      g_2(x) = (x-x_1)(x-x_3)...(x-x_n),
        ...,
      g_n(x) = (x-x_1)(x-x_2)...(x-x_{n-1}).
    而 g(x) = c_1*g_1(x)+...+c_n*g_n(x).

(2) 因 y=g(x) 通過 (x_i,y_i), i=1,...,n.
    故 y_i=g(x_i). 但由前述 g(x) 的表現式
    g(x) = c_1*g_1(x)+...+c_n*g_n(x) 很容易得到
      g(x_i) = c_i(x_i-x_1)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_i-x_n)
    因此,
      c_i = y_i/[(x_i-x_1)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_i-x_n)]

(3) 更進一步 (或許在較後面的課程) 可以證明上述g(x)
    的表現式是唯一的. 當然, 不甚嚴謹地說, 由於 (2)
    中的 c_i 是唯一解, 可保證 (1) 中 g(x) 的表現式
    中諸 c_i 的唯一性.


如果 x_i = a+i*h, 也就是 x_1,...,x_n 是等距的,以 h
為間距, 上述 Lagrange 多項式(插值公式)的結果固然可
以化簡, 但有另外的方法可以找到多項式 g(x).

首先, 若 g(x) = mx+b, 則 g(x+h)-g(x) = mh 是常數.
若 g(x)=(x-b)(x-b-h), 則
  g(x+h)-g(x) = (x+h-b)(x+h-b-h)-(x-b)(x-b-h)
              = (x-b)(2h)
是直線函數.

一般,設 g(x)=(x-b)[x-(b+h)]...[x-(b+kh)], 這是一個
k+1 階多項式, 則
   g(x+h)-g(x) = (x-b)[x-(b+h)]...{x-[b+(k-1)h]}[(k+1)h]
是 x 的 k 階多項式.

因此, 令通過 (x_i,y_i), i=1,...,n, 其中 x_i=a+ih,
的多項式函數 y=g(x) 為

  y = g(x)

    = c_0 + c_1(x-x_1) + c_2(x-x_1)(x-x_2)
            + . . . + c_{n-1}(x-x_1)...(x-x_{n-1})

則
  g(x+h)-g(x) = c_1*h + c_2*(2h)*(x-x_1) + ... +
                  c_{n-1}*[(n-1)h]*(x-x_1)...(x-x_{n-2})
  [g(x+2h)-g(x+h)]-[g(x+h)-g(x)]
    = g(x+2h)-2g(x+h)+g(x)
    = c_2*(2h)*h + c_3*(3h)*(2h)*(x-x_1)+...+
        c_{n-1}*[(n-1)h]*[(n-2)h]*(x-x_1)...(x-x_{n-3})
以此類推.

因此, 得
  g(x_1) = c_0                          <-- g(x) 之 x 代以 x_1
  g(x_2)-g(x_1) = c_1*h                 <-- g(x+h)-g(x) 之 x 代以 x_1
  g(x_3)-2g(x_2)+g(x_1) = c_2*(2!)h^2   <-- g(x+2h)-2g(x+h)+g(x) 之 x=x_1
以此類推, 一般式
  g(x_k)-C(k-1,1)g(x_{k-1))+...+(-1)^{k-1}g(x_1)
                     = c_{k-1}*(k-1)!*h^{k-1}, k=2,...,n.

故
  c_0 = g(x_1) = y_1,
  c_1 = (y_2-y_1)/h = (y_2-y_1)/(x_2-x_1)
  c_2 = (y_3-2*y_2+y_1)/(2!*h^2) = (y_3-2*y_2+y_1)/[(x_2-x_1)(x_3-x_1)]
  c_3 = (y_4-3*y_3+3*y_2-y_1)/(3!*h^3)
      = (y_4-3*y_3+3*y_2-y_1)/[(x_2-x_1)(x_3-x_1)(x_4-x_1)]
以此類推. 即

  g(x) = y_1 + (y_2-y_1)(x-x_1)/(x_2-x_1)
             + (y_3-2y_2+y_1)(x-x_1)(x-x_2)/[(x_2-x_1)(x_3-x_1)]
             +  ...
                                                      (x-x_1)...(x-x_{n-1})
             + [y_n-(n-1)y_{n-1}+...+(-1)^{n-1}y_1]*-------------------------
                                                    (x_2-x_1)...(x_n-x_{n-1})

以上是牛頓插值公式.




--
嗨! 你好! 祝事事如意, 天天 happy!  有統計問題? 歡迎光臨統計專業版! :)
 交大資訊次世代 telnet://bs2.twbbs.org      Statistics  (統計與機率)           
 成大計中站     telnet://bbs.ncku.edu.tw    Statistics  (統計方法及學理討論區) 
 盈月與繁星     telnet://ms.twbbs.org       Statistics  (統計：讓數字說話)     
我們強調專業的統計方法、實務及學習討論, 只想要題解的就抱歉了!


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 125.233.153.222
推 BRIANKUO    :牛頓插值不等距沒辦法用嗎?
推 wa007123456 :謝謝你 囧
→ yhliu       :不等距會有困難. 如果 x_1, x_2, x_3 不是等距的,
→ yhliu       :例如 g(x)=a+bx+cx^2, 則
→ yhliu       :y_3-2y_2+y_1=b(x_3-2x_2+x_1)+c(x_3^2-2x_2^2+x_1^2
→ yhliu       :太複雜. 考慮越高階, 複雜度越高.
→ BRIANKUO    :就設g(x) = c_0 + c_1(x-x_1) + c_2(x-x_1)(x-x_2)+.
→ BRIANKUO    :分別代入x_1.x_2...分別解出c_1.c_2...
推 jacky7987   :牛頓還有兩兩合成的演算法可以用
推 afflic      :現在高中教這個...哪裡用的上呀@@?
→ BRIANKUO    :這有很多種類型題目