線性世界的根基──疊加原理

本文的閱讀等級:初級

多項式插值 (polynomial interpolation) 是一個典型的數值分析問題,其目的在尋找通過一組採樣數據的多項式,詳述於下:給定一組 n+1 個數據點 (t_i,y_i)i=0,1,\ldots,n,其中 t_i 彼此相異,求一最小次多項式 f(x) 滿足

f(t_i)=y_i,~~i=0,1,\ldots,n

最直接的作法是設 f(x) 為一 n 次多項式:

f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_1x+a_0

將已知條件代入 f 就得到未知數為 a_i 的線性方程,以矩陣形式表達如下:

\begin{bmatrix}    1&t_0&t_0^2&\cdots&t_0^n\\    1&t_1&t_1^2&\cdots&t_1^n\\    \vdots&\vdots&\vdots&\ddots&\vdots\\    1&t_n&t_n^2&\cdots&t_n^n    \end{bmatrix}\begin{bmatrix}    a_{0}\\    a_{1}\\    a_{2}\\    \vdots\\    a_n    \end{bmatrix}=\begin{bmatrix}    y_0\\    y_1\\    y_2\\    \vdots\\    y_n    \end{bmatrix}

上面的係數矩陣稱為 Vandermonde 矩陣,相異的 t_i 保證係數矩陣是可逆的 (見“特殊矩陣(8):Vandermonde 矩陣”),此線性方程解即為所求的多項式係數。接下來我們要討論的是另一個多項式插值法,稱為 Lagrange 內插多項式,並由此展開線性世界的尋根之旅。

 
如果不解線性方程,還有什麼其他方法?「改變數據點」是一個有效的探索方法。譬如,我們可以考慮這個簡單情況:y_1=1y_0=y_2=y_3=\cdots=y_n=0。此時多項式 fn 個相異根 t_0, t_2, t_3,\ldots,t_n,為便於區分,以 p_1 代表滿足上述條件的特殊多項式,n 次多項式 p_1 必定有以下形式:

p_1(x)=c(x-t_0)(x-t_2)(x-t_3)\cdots(x-t_n)

其中 c 為一常數。另外還有一筆資料尚未使用,將對應 t_1 的數據 y_1=1 代入上式,就有

p_1(t_1)=c(t_1-t_0)(t_1-t_2)(t_1-t_3)\cdots(t_1-t_n)=y_1=1

解出 c,便得到

\displaystyle p_1(x)=\frac{(x-t_0)(x-t_2)(x-t_3)\cdots(x-t_n)}{(t_1-t_0)(t_1-t_2)(t_1-t_3)\cdots(t_1-t_n)}

因為 t_i 相異,上式分母不為零。推導多項式 p_1(x) 的過程使用了所有給定的資訊,因此斷定我們已經成功地得到了一個「特解」。隨意指定的數據點 y_1 並無任何奇特之處,同樣地,我們可令其餘 y_i 重複上述步驟,於是共計得到 n+1 個形式相仿的多項式:對於 i=0,1,\ldots,n

\begin{aligned}  p_i(x)&=\displaystyle\frac{(x-t_0)\cdots(x-t_{i-1})(x-t_{i+1})\cdots(x-t_n)}{ (t_i-t_0)\cdots(t_i-t_{i-1})(t_i-t_{i+1})\cdots(t_i-t_n)}\\  &=\prod_{j\neq i}\left(\frac{x-t_j}{t_i-t_j}\right)\end{aligned}

 
下一個步驟只要再把上述特例做些微變更即可應付更為廣泛的情況。考慮任意數據點 y_i (不必等於 1),其餘 n 個數據點仍為零 (y_j=0j\neq i),重複上述分析步驟,可得滿足給定條件的多項式:

\displaystyle y_ip_i(x)=y_i\prod_{j\neq i}\left(\frac{x-t_j}{t_i-t_j}\right)

如何將上述特解推廣至一般情況,也就是說,對於每個 iy_i 為任意值?很簡單,唯一要做的事只是將這些同形式的特殊多項式加在一起而已,如下:

\begin{aligned}  f(x)&=y_0p_0(x)+y_1p_1(x)+\cdots+y_np_n(x)\\  &=\displaystyle y_0\prod_{j\neq 0}\left(\frac{x-t_j}{t_0-t_j}\right)+ y_1\prod_{j\neq 1}\left(\frac{x-t_j}{t_1-t_j}\right)+\cdots+ y_n\prod_{j\neq n}\left(\frac{x-t_j}{t_n-t_j}\right)\end{aligned}

此即為 Lagrange 內插多項式,特殊多項式 p_i(x) 滿足 p_i(t_i)=1,若 j\neq ip_i(t_j)=0,或直接表示為 Kronecker 函數:p_i(t_j)=\delta_{ij},若 i=j\delta_{ij}=1,否則 \delta_{ij}=0。故確認 Lagrange 內插多項式滿足 f(t_i)=y_ii=0,1,\ldots,n

 
比較多項式 f 的兩種表達式,標準多項式:

f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_1x+a_0

和 Lagrange 內插多項式:

f(x)= y_0p_0(x)+y_1p_1(x)+\cdots+y_np_n(x)

由於 n 次多項式 f(x) 可以寫為單項式 \{1,x,x^2,\ldots,x^n\} 的組合,f(x) 也可以表示為特殊解 \{p_0(x),p_1(x),\ldots,p_n(x)\} 的組合,我們說 \{1,x,x^2,\ldots,x^n\}\{p_0(x),p_1(x),\ldots,p_n(x)\} 是所有 n 次多項式構成的集合的兩組基底 (參閱“基底與維數常見問答集”)。從另一個角度來看,n+1 階 Vandermonde 矩陣聯繫了標準多項式的係數 a_0,a_1,\ldots,a_n 和 Lagrange 內插多項式的組合係數 y_0,y_1,\ldots,y_n,由於 Vandermonde 矩陣是可逆的,有序係數 (a_0,a_1,\ldots,a_n) 對應唯一的組合係數 (y_0,y_1,\ldots,y_n),換句話說,兩組係數彼此之間存在著一對一的對應關係。

 
至此問題已經解決了,但如果我們對結果再仔細思考一番或將有意想不到的收穫。推導 Lagrange 內插多項式的過程浮現出一種解題模式,它包含兩個步驟:第一,我們的運氣頗佳,睥見了不很困難的特殊情況,並找到特解;其次,藉由組合這些特解,我們得到適用於普通情況的通解。特殊解的組合方式通常可透過代數運算實現,Lagrange 內插多項式將 n+1 個特解分別乘以給定常數 y_i,再將結果相加即組成通解。我們稱這個代數運算為線性組合或疊加 (superposition),線性組合是線性代數中最重要的代數運算,而疊加一詞則較常使用於其他線性世界,如物理、工程系統和微分方程。

 
下面我們討論疊加原理於齊次常微分方程的應用。考慮

y^{(n)}+a_1y^{(n-1)}+\cdots+a_{n-1}y^{\prime}+a_ny=0

其中 a_1,a_2,\ldots,a_n 為給定純量,y 為獨立變數 x 的函數,而 y^{\prime},y^{\prime\prime},\ldots,y^{(n)} 代表 y 的一次至 n 次導數。任何滿足上述微分方程的函數 y 都稱為特解。設 y_1y_2 為微分方程的兩個特解,c 為一純量,利用導數法則,可得

\begin{aligned}  \displaystyle\frac{d^k}{dx^k}[cy_1]=c\frac{d^k}{dx^k}[y_1]=cy_1^{(k)}\end{aligned}

\begin{aligned}  \displaystyle\frac{d^k}{dx^k}[y_1+y_2]=\frac{d^k}{dx^k}[y_1]+\frac{d^k}{dx^k}[y_2]=y_1^{(k)}+y_2^{(k)}\end{aligned}

由此推論 cy_1y_1+y_2 亦為原微分方程的解,所以特解的任意線性組合也是合法解,這是疊加原理最明顯的一種表現。

 
接著我們又問:如何求得微分方程的特解?考慮簡單情況,y^{\prime}=ay,從基礎微積分知識不難猜出一解:y=e^{ax},這暗示我們特解或許也具有 y=e^{rx} 的形式,於是將它代入上述齊次常微分方程式,

\begin{aligned}  0&=(e^{rx})^{(n)}+a_1(e^{rx})^{(n-1)}+\cdots+a_{n-1}(e^{rx})^{\prime}+a_n(e^{rx})\\  &=r^ne^{rx}+a_1r^{n-1}e^{rx}+\cdots+a_{n-1}re^{rx}+a_ne^{rx}\\  &=(r^n+a_1r^{n-1}+\cdots+a_{n-1}r+a_n)e^{rx}\end{aligned}

因為 e^{rx}\neq 0,推得未知數 r 必須滿足

r^n+a_1r^{n-1}+\cdots+a_{n-1}r+a_n=0

我們稱上式為特徵多項式,設 r_1,r_2,\ldots,r_n 為此 n 次特徵多項式的相異根,下列特解便構成了微分方程的解基 (basis of solutions):

\{e^{r_1x},e^{r_2x},\ldots,e^{r_nx}\}

通解即由解基疊加 (線性組合) 而成:

y=c_1e^{r_1x}+c_2e^{r_2x}+\cdots+c_ne^{r_nx}

 
疊加原理適用於任何的線性世界,但是線性世界的外表變化多端,它可能由數字、函數、向量或訊號所形成,因此我們需要一個普遍化的定義。設 \mathbf{v}_1,\ldots,\mathbf{v}_nn 個具有相同屬性的數學物件,它們有定義良好的加法運算 \mathbf{v}_1+\mathbf{v}_2 和純量乘法運算 c_1\mathbf{v}_1,如果它們的線性組合

c_1\mathbf{v}_1+c_2\mathbf{v}_2+\cdots+c_n\mathbf{v}_n

仍保有相同屬性,我們稱 \mathbf{v}_i 為「向量」,而它們所隸屬的集合則稱為「向量空間」或「線性空間」。由此可知,向量不僅僅是連接幾何座標系統中兩端點 AB,頭上頂著箭頭的 \overrightarrow{AB},向量其實是線性世界所處理的基本數學物件的通稱。 更令人驚訝的是:任何佈於相同數系且具有相同 (有限) 維數的向量空間都是同構的,亦即它們之間存在一對一的對應關係。欲進一步了解此主題的讀者,請參閱“同構的向量空間”。

 
本文參考:
George Polya, Mathematical Discovery, Volume 1, 1962.

This entry was posted in 線性代數專欄, 向量空間 and tagged , , , , . Bookmark the permalink.

2 則回應給 線性世界的根基──疊加原理

  1. vtriplev 說:

    網路上的老師說過Lagrange內插多項式就是韓信點兵問題的多項式版本
    http://episte.math.ntu.edu.tw/articles/sm/sm_29_09_1/page5.html
    所以說,韓信點兵問題應該也可以說是疊加原理之祖啊

  2. ccjou 說:

    蔡聰明教授在該文結語中引用 Feynman 的話並改為:
    數學家老是在傳授解題的技巧,而不是從數學的精神層面來啟發學生。
    他最後又問:有沒有辦法既學到技巧又掌握精神呢?

    我想這應該是可以實現的,不過前提是教學兩方面都很有耐性,不急著看到表面的"具體成果"。

發表迴響

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

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s