特殊矩陣 (8):Vandermonde 矩陣

本文的閱讀等級:初級

法國數學家范德蒙 (Alexandre-Théophile Vandermonde) 是行列式的奠基者之一,他在十八世紀提出行列式專有符號,將行列式應用於解線性方程組,並且對行列式理論進行了開創性的研究。兩百多年後,他的名字因為一個特殊矩陣而經常被提及。Vandermonde 矩陣具有以下形式:

A_n=\begin{bmatrix}    1&x_1&x_1^2&\cdots&x_1^{n-1}\\    1&x_2&x_2^2&\cdots&x_2^{n-1}\\    \vdots&\vdots&\vdots&\ddots&\vdots\\    1&x_n&x_n^2&\cdots&x_n^{n-1}    \end{bmatrix}

其中 A_n=[a_{ij}] 是一個 n\times n 階矩陣,各元為 a_{ij}=x_i^{j-1}。同樣地,A_n^T 也稱為 Vandermonde 矩陣。

 
下面我們推導 Vandermonde 矩陣的行列式。先看 2 階行列式

\det A_2=\begin{vmatrix}    1&x_1\\    1&x_2    \end{vmatrix}=x_2-x_1

接著,考慮 3 階行列式,以基本列運算化簡再用餘因子 (cofactor) 展開計算,可得

\begin{aligned}  \det A_3&=\begin{vmatrix}    1&x_1&x_1^2\\    1&x_2&x_2^2\\    1&x_3&x_3^2    \end{vmatrix}\\  &=\begin{vmatrix}    1&x_1&x_1^2\\    0&x_2-x_1&x_2^2-x_1^2\\    0&x_3-x_1&x_3^2-x_1^2    \end{vmatrix}\\    &=\begin{vmatrix}    x_2-x_1&x_2^2-x_1^2\\    x_3-x_1&x_3^2-x_1^2    \end{vmatrix}\\  &=(x_2-x_1)(x_3-x_2)(x_3-x_1).\end{aligned}

這時我們大膽猜測 n\times n 階 Vandermonde 矩陣的行列式計算公式如下:

\det A_n=\displaystyle\prod_{1\le j<i\le n}(x_i-x_j)

證明推導使用數學歸納法。假設 k 階 Vandermonde 行列式為

\det A_k=\displaystyle\prod_{1\le j<i\le k}(x_i-x_j)

我們要證明 k+1 階 Vandermonde 行列式也有相同的形式。將 A_{k+1} 的最末列替換為 1, x, x^2,\ldots, x^{k},設此矩陣的行列式為 f(x),亦即

f(x)=\begin{vmatrix}    1&x_1&x_1^2&\cdots&x_1^{k}\\    1&x_2&x_2^2&\cdots&x_2^{k}\\    \vdots&\vdots&\vdots&\ddots&\vdots\\    1&x_k&x_k^2&\cdots&x_k^{k}\\    1&x&x^2&\cdots&x^{k}    \end{vmatrix}

由最末列的餘因子展開式可知 f 為變數 xk 次多項式。若矩陣有相同的兩列,其行列式等於零,故 f(x_i)=0i=1,2,\ldots,k,也就是說 x_ii=1,2,\ldots,k,為多項式 f(x)k 個根,f(x) 可表示為

f(x)=\alpha(x-x_1)(x-x_2)\cdots(x-x_k)

上式中 \alpha 為非零常數,剩下的問題是決定 \alpha

 
f(x) 的餘因子展開式可得到 x^{k} 的係數,也就是 \alpha 的值,

\begin{vmatrix}    1&x_1&x_1^2&\cdots&x_1^{k-1}\\    1&x_2&x_2^2&\cdots&x_2^{k-1}\\    \vdots&\vdots&\vdots&\ddots&\vdots\\    1&x_k&x_k^2&\cdots&x_k^{k-1}    \end{vmatrix}

注意,上面的行列式即為 \mathrm{det}A_k。根據歸納法的假設,就有

f(x)=\displaystyle\left[\prod_{1\le j<i\le k}(x_i-x_j)\right](x-x_1)(x-x_2)\cdots(x-x_k)

還有一個不能錯過的事實:f(x_{k+1})=\mathrm{det}A_{k+1}。將 x=x_{k+1} 代入上式,

\det A_{k+1}=\displaystyle\left[\prod_{1\le j<i\le k}(x_i-x_j)\right](x_{k+1}-x_1)(x_{k+1}-x_2)\cdots(x_{k+1}-x_k)

整理等號右端,得到

\det A_{k+1}=\displaystyle\prod_{1\le j<i\le k+1}(x_i-x_j)

故證明所求。

 
Vandermonde 矩陣常見於數值分析的內插 (interpolation) 問題。給出 n 個資料點 (x_i,y_i)i=1,2,\ldots,n,求 (n-1) 次多項式

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

滿足

\begin{aligned}  p(x_1)&=a_0+a_1x_1+\cdots+a_{n-1}x_1^{n-1}=y_1\\    p(x_2)&=a_0+a_1x_2+\cdots+a_{n-1}x_2^{n-1}=y_2\\    &\vdots\\    p(x_n)&=a_0+a_1x_n+\cdots+a_{n-1}x_n^{n-1}=y_n.\end{aligned}

將上面的線性方程組寫為矩陣形式 A\mathbf{a}=\mathbf{y},其中 An\times n 階 Vandermonde 矩陣。內插問題就是要解出係數向量 \mathbf{a}=\begin{bmatrix}    a_0&a_1&\cdots&a_{n-1}\end{bmatrix}^T。如果 n 個參數 x_1,x_2,\ldots,x_n 彼此相異,推知 \mathrm{det}A_n\neq 0A 是可逆的,方程式必定存在唯一解。

 
通常我們不直接解出 a_i,而是將多項式 p(x) 表示為特殊 Lagrange 內插多項式,如下:

L_i(x)=\displaystyle\frac{\prod_{j=1,j\neq i}^n(x-x_j)}{\prod_{j=1,j\neq i}^n(x_i-x_j)},~~i=1,2,\ldots,n

每個多項式 L_i(x) 都是 (n-1) 次,若 j\neq iL_i(x_j)=0,但 L_i(x_i)=1。利用上述條件,可得 Lagrange 內插公式

p(x)=y_1L_1(x)+y_2L_2(x)+\cdots+y_nL_n(x)

顯然,(n-1) 次多項式 p(x) 滿足前面給定的 n 個內插條件,p(x_i)=y_ii=1,2,\ldots,n

繼續閱讀:
This entry was posted in 特殊矩陣, 線性代數專欄 and tagged , , , . Bookmark the permalink.

7 則回應給 特殊矩陣 (8):Vandermonde 矩陣

  1. VtripleV 說:

    看到這個Vandermonde矩陣,瞬間回想到DFT開放課程中,印度老師的解說過程(http://www.youtube.com/watch?v=GDFTb-BwA0o ,第9分鐘之後)
    對一個有限長度取樣信號sequence x(n) ,n=0…N-1, 對該訊號取fourier transform => X(e^jw)=x(0)+x(1)e^(-jw)+…+X(N-1)e^(-j(N-1)w)
    上式的LHS基本上可以視為e^(-jw)的N-1次多項式,有N個係數,所以該N-1次多項式由N個係數唯一決定,或是從此N-1次多項式函數中N個相異的取樣值決定(在time-space(or domain)或是w-space(domain)取樣)。也就是可以對X(e^jw)函數於w-space進行N點取樣,就足夠描述X(e^jw), 於是 X(e^jw) sample X(e^jw) at N points==> X(e^jwk),k=0…N-1,簡單的取樣就是2pi等N分取樣, 於是就誕生了DFT X(k)=DFT[x(n)], DFT矩陣跟反矩陣正好是Vandermonde 矩陣長像.

  2. ccjou 說:

    你應該會有興趣閱讀
    特殊矩陣(七):循環矩陣
    https://ccjou.wordpress.com/2009/10/23/%E7%89%B9%E6%AE%8A%E7%9F%A9%E9%99%A3%E4%B8%83%EF%BC%9A%E5%BE%AA%E7%92%B0%E7%9F%A9%E9%99%A3/

    最近垃圾分檢系統常有誤判情況,我將請管理員研究改善方案。

  3. vtriplev 說:

    P^0=P^N=I (對應於W^0=W^N=1)
    複數跟矩陣性質真的好類似啊

  4. 熊大帥 說:

    好複雜,我只是預習高二下範圍,上網找資料,只是好複雜,還是死記等人教到再聽如何證的好了

  5. 陳易聖 說:

    請問這是否也是最小平方法的求法呢?

    • ccjou 說:

      你是說上文的內插問題嗎?給出n個資料點(限制條件),n-1次多項式有n個係數(未知數),因此有唯一解,不需要使用最小平方法求近似解。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s