Quod Erat Demonstrandum

2008/09/20

利用插值法找餘式

Filed under: Additional / Applied Mathematics,HKALE,Pure Mathematics — johnmayhk @ 2:33 下午

近日,中六純數課談的是餘式定理,中七的應數課談的是插值法,恰巧,兩者有一點點關聯。

這是一道常見的題

多項式 p(x),被 (x - 1), (x - 2)(x - 3) 除,餘式(remainder)是分別是 6, -18,若 p(x)(x - 1)(x - 2)(x - 3) 除時,餘式是什麼?

常見手法是設

p(x) \equiv (x - 1)(x - 2)(x - 3)Q(x) + Ax^2 + Bx + C – – – – – – (*)

[注:同學,我們可以如此假設,因為除式 (x - 1)(x - 2)(x - 3) 是 degree 3 的多項式,進行帶餘除法後,餘式多項式的 degree 最多是 3 – 1 = 2,故把餘式設成 Ax^2 + Bx + C。]

再根據題意,即

p(1) = 6
p(2) = -1
p(3) = 8

代入 (*),得三條等式,以解出三個未知數 A, BC。嗯,三條 (linear) equations,三個 unknowns,修純數的同學或許想到 Cramer’s Rule 啦,Gaussian Elimination 啦;但修應數的同學,感到上述問題面熟嗎?我們要求的餘式,豈不是可以利用拉格朗日插值多項式( Lagrange Interpolating Polynomial ),一步得出嗎?

讓我詳表如下。

設餘式為 f(x)(即 (*) 中的 Ax^2 + Bx + C),根據題意,我們有

f(1) = 6
f(2) = -1
f(3) = 8

利用插值法,立即得到

f(x) \equiv (6)\frac{(x - 2)(x - 3)}{(1 - 2)(1 - 3)} + (-1)\frac{(x - 1)(x - 3)}{(2 - 1)(2 - 3)} + (8)\frac{(x - 1)(x - 2)}{(3 - 1)(3 - 2)}
\equiv 3(x - 1)(x - 2) + (x - 1)(x - 3) + 4(x - 2)(x - 3) – – – – – – (**)
\equiv 8x^2 - 31x + 29

可能不少香港中學同學沒有學過插值法,不打緊,只要看看上式 (**),可以給同學一點啟示。

就是,我們設餘式的時候,不是如 (*) 般設立,而是設成

f(x) \equiv D(x - 1)(x - 2) + E(x - 1)(x - 3) + F(x - 2)(x - 3)

那麼,上式便是二次多項式(精確地:degree at most 2),且要找出未知數 D, E, F 是極其容易,只要輸入 x = 1, 23,立時找到,無須解三條聯合方程。

後話

青出於藍經常是我的心願,不少濟記同學其實不錯,數學功力一定可以在我之上。

(F.7 case)
那天剛剛開始討論計算有關 Interpolating polynomial 誤差的式子,見下

|E(x)| = \frac{|f^{(n)}(\xi)|}{n!}|(x - x_1)(x - x_2)\dots (x - x_n)|

其中 \xi \in [x_1 , x_n] (設 x_1 < x_2 \dots < x_n)

黃同學很快問,\xi 是否和 x 有關。是呀,所以把 \xi 寫成 \xi_x 可能比較清楚。起碼比教科書寫的清楚。

(F.6 case)
另外,我上純數堂是頗互動,(某些)同學不時回應並提出口頭解答,氣氛不錯。最欣喜以前我教過的一位陳同學問了一個問題,值得全班同學想的:

「利用餘式定理可證 (x + y)^n - x^n - y^n (n 是正奇數)分別可被 x, y(x + y) 整除,但如何保證它也可被 xy(x + y) 整除?」

(F.4 case)
部份同學也懂得解 EQ (Easy Questions 是也),比如 f(x + \frac{1}{x}) = x^2 + \frac{1}{x^2},求 f(2008) 之類問題。

1 則迴響 »


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: