牛頓、拉格朗日多項式插值法與基底變換

在座標平面上要找出通過固定幾個點的函數會有很多種，通常可以用多項式函數來近似原本的函數，稱為插值多項式。在高中一年級的課程就有提到牛頓插值法(Newton’s interpolation)和拉格朗日插值法(Lagrange’s interpolation)。前幾天在跟其他老師聊天時，說到我對這些多項式插值法的感覺，一是將多項式採用不同基底的線性組合，另一則是將拉格朗日多項式與數論的中國剩餘定理(the Chinese Remainder Theorem, CRT)作連結。以下就以基底的線性組合的觀點來談這件事(關於CRT和Lagrange’s interpolation的關係以後有空再寫)：

以不同基底的概念來說，例如欲求在座標平面上通過(x₁, y₁)、(x₂, y₂)、(x₃, y₃)的多項式函數y＝f(x)，其中degf(x)≦2，則f(x)可作以下假設：

(1)一般式的假設：f(x)＝ax²＋bx＋c

(2)牛頓插值法的假設：f(x)＝A(x－x₁)(x－x₂)＋B(x－x₁)＋C

(3)拉格朗日插值法的假設：f(x)＝α(x－x₁)(x－x₂)＋β(x－x₂)(x－x₃)＋γ(x－x₁)(x－x₃)

這三個其實就是考慮所有deg≦2的多項式構成的向量空間，分別採用B₁={x², x, 1}、B₂={(x－x₁)(x－x₂), (x－x₁), 1}、B₃={(x－x₁)(x－x₂)、(x－x₂)(x－x₃)、(x－x₁)(x－x₃)}為基底的假設，所以這三種假設法都能得到唯一的係數，確實能表示滿足所需條件的多項式。

更仔細來說，基底的座標變換矩陣可以寫成

所以

例：欲求在座標平面上通過(1, 6)、(2, 14)、(3, 26)的二次函數y＝f(x)的一般式。
Sol：

利用牛頓插值法假設，可設f(x)＝A(x－1)(x－2)＋B(x－1)＋C，依次代入(1, 6)、(2, 14)、(3, 26)，可得C＝6，B＝8，A＝2，即f(x)＝2(x－1)(x－2)＋8(x－1)＋6，若利用座標變換矩陣可得

 即f(x)＝2x²＋2x＋2。

若利用拉格朗日插值法，我們可以直接寫出

 利用座標變換矩陣可得

即f(x)＝2x²＋2x＋2。

當然上面兩種方法，直接將f(x)＝2(x－1)(x－2)＋8(x－1)＋6或f(x)＝13(x－1)(x－2)＋3(x－2)(x－3)－14(x－1)(x－3)展開都會比較容易。

相關文章：中國剩餘定理(the CRT)與拉格朗日插值法(Lagrange's interpolation)

兩道簡單的幾何題目

好久沒經營這個blog了，把前陣子校內競賽自己設計覺得還蠻喜歡的預選題(可惜沒被選上)放一些上來。

【題】設為一圓的直徑，A₁、A₂、…、A_n為圓上的點，對於所有的i＝1～n，作，其中D_i為垂足，若，試證：

Pf:

對於所有的i＝1～n，因為A_i在圓上，所以∠PA_iQ＝90°，故，且由母子相似性質知，，，及已知條件，可得

由於，i＝1～n，所以。故

 

 得證□

其實命題時上面這個題目的想法是從猜拳輸、贏的平方和與標準差出來的，簡單對照一下，就可以發現它的關聯了。

【題】設三角形ABC的邊長分別為a、b、c，外接圓半徑長為R，內切圓半徑長為r，三角形DEF的三邊長分別為a＋b、b＋c、c＋a，試求三角形DEF的內切圓半徑長。

Sol:

設三角形DEF的內切圓半徑為r’，則三角形DEF的面積等於(a＋b＋c) r’，又由海龍公式可知三角形DEF的面積等於，所以。又因三角形ABC面積等於移項得，所以。

10個餘弦定理的證明

正、餘弦定理為幾何的三角習題中常會利用到的公式，這裡針對餘弦定理整理出10種不同的證明方法，10種方式分類如下：
(1)利用投影公式證明
(2)直接利用商高定理證明
(3)坐標化計算兩點之間的距離
(4)利用向量內積來證明
(5)利用Heron面積公式來證明
(6) 利用複數來證明
(7)利用正弦定理證明
(8)利用圓內冪性質、圓外冪性質來證明
(9)觀察圖形
(10)類似歐幾里得《幾何原本》第一卷第47命題證明畢氏定理的方式來證明


以下證明均令、、。

(1)利用投影公式證明
如圖，令為上的高，其中D為垂足。若∠A≦π/2，則，若∠A＞π/2，則，這些情況都可以表示為c＝acosB＋bcosA，同理，a＝bcosC＋ccosB、b＝acosC＋ccosA。
因此由

利用Cramer’s Rule可解得

(2)直接利用商高定理證明
仍參考上圖。不失一般性，假設∠B和∠C為銳角。令為上的高，其中D為垂足。

若∠A為直角，A點與D點重合，由畢氏定理有a²＝b²＋c²＝b²＋c²－2bccosA。
若∠A為銳角，

若∠A為鈍角，

這裡用到。

(3)坐標化計算兩點之間的距離

如下圖左，將ΔABC的三頂點坐標化，令A(0, 0), B(ccosA, csinA), C(b, 0)，則

(4)利用向量內積來證明

如上圖右，

，即a²＝b²＋c²－2bccosA。
 

(5)利用Heron面積公式來證明
Heron公式為，其中s＝(a＋b＋c)/2。若ΔABC的內切圓半徑為r，切點分別為D、E、F，如圖，令，，，則可將Heron公式改寫成，且顯然Δ＝r(x＋y＋z)，因此，xyz(x＋y＋z)＝r²(x＋y＋z)²，又將代入化簡後可得

(6) 利用複數來證明

將ΔABC放在複數平面上，令A(0), B(z₁), C(z₂)，則,,,。因此，

(7)利用正弦定理證明

由正弦定理知a＝2RsinA，b＝2RsinB，c＝2RsinC，其中R為ΔABC的外接圓半徑，故

             a²＝4R²sin²A

             ＝4R²sin²(∠B＋∠C)

             ＝4R²(sinBcosC＋cosBsinC)²

             ＝4R²(sin²Bcos²C＋cos²Bsin²C＋2 sinBsinCcosBcosC)

             ＝4R²(sin²B(1－sin²C)＋sin²C (1－sin²B)＋2 sinBsinCcosBcosC)

             ＝4R²(sin²B＋sin²C－2sin²B sin²C＋2 sinBsinCcosBcosC)

             ＝4R²sin²B＋4R²sin²C＋8R²sinBsinC(cosBcosC－sinBsinC)

             ＝b²＋c²＋2bccos(∠B＋∠C)

             ＝b²＋c²－2bccosA

(8)利用圓內冪性質、圓外冪性質來證明
不失一般性，先假設∠B與∠C均為銳角。以B點為圓心，c＝為半徑畫圓，不外乎下圖三種情形：
(i)最左圖是∠A為銳角，且c為最長邊；
(ii)中間的圖∠A是為銳角，但c不為最長邊；
(iii)最右圖為∠A為鈍角的情形。
可以注意到，若∠A為直角，則為通過A點的切線，運用中間的圖及以下的證明方式，也可推導出畢氏定理。

令與圓交於D點，與圓交於E、F兩點，弦。由圓內冪及圓外冪性質知：

(i)∠A為銳角，且c為最長邊時，，即b×(2ccosA－b)＝(a＋c)×(c－a)，化簡移項得即得a²＝b²＋c²－2bccosA。

(ii)∠A為銳角，且c不為最長邊時，，即b×(b－2ccosA)＝(a＋c)×(a－c)，化簡移項得即得a²＝b²＋c²－2bccosA。若∠A為直角，則A、D重合，上式即為切割線性質的運用。

(iii)∠A為鈍角時，，即b×(b－2ccosA)＝(a＋c)×(a－c)，化簡移項得即得a²＝b²＋c²－2bccosA。

 (9)觀察圖形
不失一般性，我們可以假設∠B與∠C均為銳角。若∠A為直角，即可由cosA＝0及畢氏定理得a²＝b²＋c²－2bccosA之結果。因此只需考慮∠A為銳角以及鈍角的情形。如圖，作正方形BCDE、正方形ACHP，再以和為邊作平行四邊形BAPG，再作正方形PGEF。則顯然ΔABC≅ΔFED≅ΔHDC≅ΔGEB，且平行四邊形BAPG≅平行四邊形HDFP。
若∠A為鈍角，如左圖，因為ΔABC≅ΔFED，ΔHDC≅ΔGEB，所以
正方形BCDE面積＝正方形ACHP面積＋正方形PGEF面積＋平行四邊形BAPG面積＋平行四邊形HDFP面積，
又正方形BCDE面積＝a²，正方形ACHP面積＝b²，正方形PGEF面積＝c²，
平行四邊形BAPG面積＋平行四邊形HDFP面積＝2bcsin∠BAP＝2bcsin(3π/2－∠BAC)＝－2bccos∠BAC，
故得a²＝b²＋c²－2bccosA。

若∠A為銳角，如右圖，因為ΔABC≅ΔFED，ΔHDC≅ΔGEB，所以
正方形面積BCDE
＝(五邊形BCHPA面積＋五邊形BGPFE面積－平行四邊形BAPG面積)－(平行四邊形HDFP面積＋ΔHDC面積＋ΔFED面積)
＝(五邊形BCHPA面積－ΔABC面積)＋(五邊形BGPFE面積－ΔGEB面積)－平行四邊形BAPG面積－平行四邊形HDFP面積
＝正方形ACHP面積＋正方形PGEF面積－平行四邊形BAPG面積－平行四邊形HDFP面積。
又正方形BCDE面積＝a²，正方形ACHP面積＝b²，正方形PGEF面積＝c²，
平行四邊形BAPG面積＋平行四邊形HDFP面積＝2bcsin∠BAP＝2bcsin(π/2＋∠BAC)＝2bccos∠BAC，
故得a²＝b²＋c²－2bccosA。

其實，若B、G、A、P四點共線，則∠BAC為直角，亦可利用此圖形來證明畢氏定理。

(10)類似歐幾里得《幾何原本》第一卷第47命題證明畢氏定理的方式來證明

分別自ΔABC的三邊各作正方形BCDE、ACFG、ABHI，作交於J，交於P，作交於K，交於Q，作交於L，交於R。

不失一般性，假設∠B與∠C均為銳角。

矩形BLRH面積矩形BEPJ面積，同理矩形CFQK面積＝矩形CDPJ面積。

矩形AIRL面積矩形ACQK面積。即矩形AIRL面積＝矩形ACQK面積。

顯然，若∠A為直角，則Q、G兩點重合，I、R兩點重合，則矩形AIRL面積與矩形ACQK面積均為0，故正方形BCDE面積＝正方形ACFG面積＋正方形ABHI面積，即a²＝b²＋c²，此為畢氏定理之證明。

若∠A為銳角，則正方形BCDE面積＝正方形ACFG面積＋正方形ABHI面積－(矩形AIRL面積＋矩形ACQK面積)，即a²＝b²＋c²－2bccosA。

若∠A為鈍角，則正方形BCDE面積＝正方形ACFG面積＋正方形ABHI面積＋(矩形AIRL面積＋矩形ACQK面積)，即a²＝b²＋c²＋2bc∣cosA∣＝b²＋c²－2bccosA。