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

Posted on 06/15/2012 by ccjou

本文的閱讀等級：中級

考慮 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}=1 若 i=k，\delta_{ik}=0 若 i\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)=0 若 p\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_r 是 x_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.

Leave a comment