特殊矩陣 (八)：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}$$。

 

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

$$\mathrm{det}A_2=\begin{vmatrix}

1&x_1\\

1&x_2

\end{vmatrix}=x_2-x_1$$

接著，考慮 3 階行列式，先以基本列運算化簡再用共因子展開計算

$$\mathrm{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)$$

這時我們可以大膽猜測 $$n\times n$$ 階 Vandermonde 矩陣的行列式計算公式：

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

 

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

$$\mathrm{det}A_k=\prod_{1\le j<i\le k}^{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$$ 為 變數 $$x$$ 的 $$k$$ 階多項式。若矩陣有相同的兩列，其行列式等於零，故 $$f(x_i)=0$$，$$i=1,2,\ldots,k$$。因此得知 $$x_i$$，$$i=1,2,\ldots,k$$，為多項式 $$f(x)$$ 的 $$k$$ 個根，$$f(x)$$ 可被因式 $$(x-x_1),(x-x_2),\ldots,(x-x_k)$$ 整除，根據代數學基本定理，就有

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

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

 

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

$$\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)=\left[\prod_{1\le j<i\le k}^{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}$$ 代入上式，

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

整理等號右端，得到

$$\mathrm{det}A_{k+1}=\prod_{1\le j<i\le k+1}^{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$$

滿足

$$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$$

將上面的線性方程式組寫為矩陣形式 $$A\mathbf{a}=\mathbf{y}$$，其中 $$A$$ 為 $$n\times n$$ 階 Vandermonde 矩陣。內差問題就是要解出係數向量 $$\mathbf{a}=\begin{bmatrix}

a_0&a_1&\cdots&a_{n-1}\end{bmatrix}$$。如果 $$n$$ 個參數 $$x_1,x_2,\ldots,x_n$$ 彼此相異，推知 $$\mathrm{det}A_n\neq 0$$，$$A$$ 是可逆的，方程式必定存在唯一解。

 

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

$$L_i(x)=\left(\prod_{j=1,j\neq i}^n(x-x_j)\right)/\left(\prod_{j=1,j\neq i}^n(x_i-x_j)\right)$$，$$i=1,2,\ldots,n$$

每個多項式 $$L_i(x)$$ 都是 $$(n-1)$$ 階，若 $$j\neq i$$，$$L_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_i$$，$$i=1,2,\ldots,n$$。