※ 引述《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