利用 Lagrange 內插多項式推導 Vandermonde 矩陣的逆矩陣

本文的閱讀等級:中級

考慮 n\times n 階 Vandermonde 矩陣

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

其中 x_1,\ldots,x_n 互異。我們曾利用伴隨 (adjugate) 矩陣及行列式公式導出 V 的逆矩陣公式 (見“Vandermonde 矩陣的逆矩陣”),但由於涉及行列式運算,推演過程因而相當繁複。本文介紹另一個較簡潔的逆矩陣推導方法──Lagrange 內插多項式 (參見“利用 Lagrange 內插多項式推導 Cauchy 矩陣的逆矩陣”)。

 
n\times n 階矩陣 Z=[z_{ij}] 代表 Vandermonde 矩陣 V=[v_{ij}] 的逆矩陣,即 ZV=I。對於任意 1\le i,k\le n,就有

\displaystyle  \sum_{j=1}^nz_{ij}v_{jk}=\sum_{j=1}^nz_{ij}x_k^{j-1}=\delta_{ik}

其中 \delta_{ik} 是 Kronecker 函數:\delta_{ik}=1i=k\delta_{ik}=0i\neq k。考慮定義於 \{x_1,\ldots,x_n\}n-1 次 Lagrange 特殊多項式

\displaystyle\begin{aligned}  L_i(t)&=\frac{(t-x_1)\cdots(t-x_{i-1})(t-x_{i+1})\cdots(t-x_n)}{(x_i-x_1)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)}\\  &=\prod_{1\le p\le n\atop p\neq i}(t-x_p)\bigg/\prod_{1\le p\le n\atop p\neq i}(x_i-x_p).\end{aligned}

因為 L_i(x_i)=1,且 L_i(x_p)=0p\neq i,推得 L_i(x_k)=\delta_{ik}。與前一式比較,對於
t\in\{x_1,\ldots,x_n\},就有

\displaystyle  L_i(t)=\sum_{j=1}^nz_{ij}t^{j-1}

z_{ij} 可唯一決定 (因為 \{x_1,\ldots,x_n\} 互異,共有 n 個條件方程)。剩下的工作是從上式解出 z_{ij}

 
展開 L_i(t) 的分子,

\displaystyle\begin{aligned}  \prod_{1\le p\le n\atop p\neq i}(t-x_p)&=S_0t^{n-1}-S_1t^{n-2}+\cdots+(-1)^{n-1}S_{n-1}\\  &=\sum_{q=1}^n(-1)^{q-1}S_{q-1}t^{n-q}\\  &=\sum_{j=1}^n(-1)^{n-j}S_{n-j}t^{j-1},\end{aligned}

其中 S_rx_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n 的基本對稱函數 (elementary symmetric function,見“特徵多項式預藏的訊息”),如下:

\displaystyle  S_r(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_{n})=\sum_{1\le p_1<\cdots<p_r\le n\atop p_1,\ldots,p_r\neq i}x_{p_1}x_{p_2}\cdots x_{p_r},~~~r=1,\ldots,n-1

並定義 S_0(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n)\equiv 1。所以,

\displaystyle   L_i(t)=\sum_{j=1}^n(-1)^{n-j}S_{n-j}(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n)t^{j-1}\bigg/\prod_{1\le p\le n\atop p\neq i}(x_i-x_p)

上式中,t^{j-1} 的係數即為所求:

\displaystyle\begin{aligned}  z_{ij}&=(-1)^{n-j}S_{n-j}(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n)\bigg/\prod_{1\le p\le n\atop p\neq i}(x_i-x_p)\\  &=(-1)^{j+1}S_{n-j}(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n)\bigg/\prod_{1\le p\le n\atop p\neq i}(x_p-x_i)\\  &=(-1)^{j+1}{\sum_{1\le p_1<\cdots<p_{n-j}\le n\atop p_1,\ldots,p_{n-j}\neq i}x_{p_1}x_{p_2}\cdots x_{p_{n-j}}}\bigg/{\prod_{1\le p\le n\atop p\neq i}(x_p-x_i)}.\end{aligned}

This entry was posted in 線性方程, 線性代數專欄 and tagged , , , , . Bookmark the permalink.

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s