Finite Playground

To verify is human; to prove, divine.

Linear algebra and Lagrange interpolation formula

2 Comments

最近在重讀線性代數, 對這門科目有了些新的認識!
前幾天讀到 dual space and dual basis, 發現高中時整天在算它的行列式, 卻一直不知道有什麼用處的 Vandermonde 矩陣:

\displaystyle{  A = \begin{bmatrix}  \alpha_0^0 & \alpha_0^1 & \cdots & \alpha_0^n \\  \alpha_1^0 & \alpha_1^1 & \cdots & \alpha_1^n \\  \vdots & \vdots & & \vdots \\  \alpha_n^0 & \alpha_n^1 & \cdots & \alpha_n^n  \end{bmatrix}  },

突然變得非常清晰!

考慮一個體F上的n+1維向量空間V, 令V^* = L(V,F)為其對偶空間, 也就是那些從V打到F的線性函數所形成的向量空間. 令B = (e_0,\ldots,e_n)V的一基底, 則我們在V^*中會有對偶基底B^* = (e^0,\ldots,e^n), 滿足

\displaystyle{  e^j e_i = [i = j]  },

其中[i=j]值為1如果i=j, 不然就是0. 可以想像基底跟對偶基底只要是不同國 (不同 index) 就會 “相殺”, 這樣就好想多了.

用一些例子來看這個對偶基底: 令F=\mathbb{C}為複數, V=F^{\leq n}[x]為所有係數為複數的n次多項式所形成的向量空間. (檢查!) 這時我們會發現V的維度是n+1, 也就是說基底大小會是n+1. 按照我們對多項式的 “直覺”, 應該會猜B = (x^0,\ldots,x^n)是一組V的基底. (的確如此!) 那麼跟它對應的對偶基底是誰呢? 應該要是那些能滿足相殺性質的線性函數. 令B^* = ([x^0],\ldots,[x^n]), 其中[x^i] : V \to F是取多項式中x^i項係數的函數(因此[x^i]\in V^*); 也就是說對於某個V中的多項式f(x) = \sum_{i=0}^n \beta_i x^i,

\displaystyle{  [x^i](\sum_{i=0}^n \beta_i x^i) = \beta_i  }.

因此,BB^*滿足相殺性質, 所以取係數函數B^*B的對偶基底.

而除了取係數函數, 我們還有什麼在V上很自然的線性函數呢? 當然就是取值函數了: 我們隨便取n+1個不一樣的複數(\alpha_0,\ldots,\alpha_n), 令B_L^* = ([\alpha_0],\ldots,[\alpha_n]), 其中[\alpha_j] : V \to F是將多項式中所有x代入\alpha_j的函數; 因此對於某個V中的多項式f(x) = \sum_{i=0}^n \beta_i x^i,

\displaystyle{  [\alpha_j](f(x)) = [\alpha_j](\sum_{i=0}^n \beta_i x^i) = \sum_{i=0}^n \beta_i \alpha_j^i = f(\alpha_j)  }.

我們可以證明B_L^*是個V^*中的基底. 那麼它的對偶基底應該要是誰呢? 為了要滿足相殺性質, 經過一陣努力後我們發現應該是底下這組多項式. 令B_L = (L_0(x),\ldots,L_n(x)), 其中

\displaystyle{  L_i(x) = \prod_{j=0 \atop j \neq i}^n \frac{x-\alpha_j}{\alpha_i-\alpha_j}  }.

我們稱這些多項式為 Lagrange 多項式. 它們擁有的性質, 正好就是當你將\alpha_i帶入這些多項式時, 會滿足

\displaystyle{  [\alpha_j]L_i(x) = L_i(\alpha_j) = [i = j]  }

這樣的相殺性質! 因此我們知道 Lagrange 多項式B_L是取值函數B_L^*的對偶基底.

等等!

我們要怎麼證明 Lagrange 多項式B_L的確會是V的一組基底呢? 他們不像B = (x^0,\ldots,x^n)看起來這麼和藹可親; 不過, 根據對偶基底的性質, 我們有以下等式: 對於V中的任意多項式f,

\displaystyle{  f = \sum_{i=0}^n (e^i f) e_i  }.

因此在我們的例子中, 我們將f依序代入所有B基底中的x^j:

\displaystyle{  x^j = \sum_{i=0}^n ([\alpha_i]x^j) L_i(x) = \sum_{i=0}^n \alpha_i^j L_i(x)  },

我們發現這是一組線性方程, 也就是一個從B_LB的線性變換. 將這個線性變換寫成矩陣的形式, 我們很驚訝的發現這個矩陣恰巧就是Vandermonde 矩陣!!

\displaystyle{  A = \begin{bmatrix}  \alpha_0^0 & \alpha_0^1 & \cdots & \alpha_0^n \\  \alpha_1^0 & \alpha_1^1 & \cdots & \alpha_1^n \\  \vdots & \vdots & & \vdots \\  \alpha_n^0 & \alpha_n^1 & \cdots & \alpha_n^n  \end{bmatrix}  }

而我們高中時計算 Vandermonde 矩陣的行列式值不為零, 完全就是在說這個線性變換是個V上的自同構映射 (automorphism), 而B_L的的確確是個基底. 我們稱這組線性方程為 Lagrange 插值公式 (Lagrange interpolation formula), 它的用途在於能夠回答底下這個問題:

給定兩組n+1個不一樣的複數(\alpha_0,\ldots,\alpha_n)(\beta_0,\ldots,\beta_n), 求一個n次多項式f滿足f(\alpha_i) = \beta_i.

要怎麼得到這個多項式f呢? 若是用基底B來思考就會很困難, 但改用基底B_L, 很容易我們就可以看出令

\displaystyle{  f(x) = \sum_{i=0}^n \beta_i L_i(x)  }

就行了.

原以為故事到這裡就告一段落了, 沒想到在看後面的矩陣對角化時, 前面說的事情可以帶來更新一層的感受… 待續!!

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

2 thoughts on “Linear algebra and Lagrange interpolation formula

  1. 倒数段落里的“Lagrange差值公式”是否应为“Lagrange插值公式”呢?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s