拉格朗日多項式、凡德孟矩陣

This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.

from lingeo import random_int_list
from linspace import vtop, ptov, lagrange_polynomials

Main idea

Consider the vector space \(\mathcal{P}_d\).
Let \(\alpha = \{1, \ldots, x^d\}\) be the standard basis of \(\mathcal{P}_d\).
Pick \(d+1\) distinct values \(\lambda_0,\ldots,\lambda_{d}\in\mathbb{R}\).
Define
\[f_i = \frac{ \displaystyle\prod_{\substack{k\in\{0,\ldots,d\} \\ k \neq i }} (x - \lambda_k) } { \displaystyle\prod_{\substack{k\in\{0,\ldots,d\} \\ k \neq i }} (\lambda_i - \lambda_k) }. \]
Thus, each \(f_i\) is a polynomial of degree \(d\) such that \(f_i(\lambda_i) = 1\) and \(f_i(\lambda_k) = 0\) for all \(k\neq i\).
A polynomial of this form is called a Lagrange polynomial.
Meanwhile, \(\beta = \{f_0,\ldots,f_d\}\) is a basis of \(\mathcal{P}_d\) and is called the Lagrange basis with respect to \(\lambda_0,\ldots,\lambda_d\).

Lagrange interpolation

Let \(\lambda_0,\ldots,\lambda_d\) be distinct real numbers and \(\beta = \{f_0,\ldots,f_d\}\) the corresponding Lagrange polynomials.
Then every polynomial \(p\) in \(\mathcal{P}_d\) has a unique way to be written as a linear combination of \(\beta\).
Indeed,
\[p = p(\lambda_0)f_0 + \cdots + p(\lambda_d)f_d.\]
In other words, \([p]_\beta = ( p(\lambda_0), \ldots, p(\lambda_d) )\) is the vector that records the evaluations of \(p\) at \(\lambda_0,\ldots,\lambda_d\).

Let \(\lambda_0,\ldots,\lambda_d\) be distinct real numbers.
A \((d+1)\times (d+1)\) matrix of the form
\[A = \begin{bmatrix} 1 & \lambda_0 & \cdots & \lambda_0^d \\ 1 & \lambda_1 & \cdots & \lambda_1^d \\ \vdots & \vdots & & \vdots \\ 1 & \lambda_d & \cdots & \lambda_d^d \\ \end{bmatrix} \]
is called a Vandermonde matrix.

When the considered space is \(\mathcal{P}_d\), \(\alpha\) is its standard basis, and
\(\beta\) is the Lagrange basis with respect to \(\lambda_0,\ldots,\lambda_d\),
the change of basis matrix \([\operatorname{id}]_\alpha^\beta\) is the Vandermonde matrix with respect to \(\lambda_0,\ldots,\lambda_d\).
Therefore, a Vandermonde matrix is always invertible.

Suppose the evaluations of a polynomial are known on \(\lambda_0,\ldots,\lambda_d\).
That is, \([p]_\beta = ( p(\lambda_0), \ldots, p(\lambda_d) )\) is known.
Then \(p = c_0 + c_1x + \cdots + c_dx^d\) is uniquely determined by
\([p]_\alpha = (c_0,\ldots,c_d)\) and \(([\operatorname{id}]_\alpha^\beta)^{-1}[p]_\beta\).

Side stories

• determinant of a Vandermonde matrix

Experiments

Exercise 1

執行以下程式碼。
令 \(\alpha\) 為 \(\mathcal{P}_2\) 的標準基底。
令 \(\beta\) 為下述 \(\lambda_0,\ldots,\lambda_2\) 的拉格朗日基底。

### code
set_random_seed(0)
print_ans = False
d = 2
v = vector(random_int_list(d+1))
p = vtop(v)
while True:
    lambdas = random_int_list(d+1, 3)
    if len(set(lambdas)) == len(lambdas):
        break

print("lambda_0, ..., lambda_%s ="%d + " " + ", ".join("%s"%lambdas[i] for i in range(d+1)))
print("p =", p)

if print_ans:
    print("[p]_alpha =", v)
    print("[p]_beta =", vector(p.subs(x=lambdas[i]) for i in range(d+1)))
    A = matrix.vandermonde(lambdas)
    print("A =")
    show(A)
    print("beta contains the following polynomials")
    beta = lagrange_polynomials(lambdas)
    for i in range(d+1):
        print(beta[i])
    print("A inverse =")
    show(A.inverse())

Exercise 1(a)

寫出相對應的凡德孟矩陣 \(A\)。

以 seed(0) 為例：

由 \(\lambda_0 , ... ,\lambda_3 = 3,1,-2\) 可寫出相對應的凡德孟矩陣 \(A\) ，

\(\begin{aligned} A = \begin{bmatrix} 1 & 3 & 9 \\ 1 & 1 & 1 \\ 1 & -2 & 4 \end{bmatrix} \end{aligned}\)

Exercise 1(b)

求出 \([p]_\alpha\) 及 \([p]_\beta\) 並驗證 \(A[p]_\alpha = [p]_\beta\)。

以 seed(0) 為例：
由 \(\alpha = \{1,x,x^2\}\) , \(\beta = \{3,1,-2\}\)
可得出 \([p]_\alpha\) 和 \([p]_\beta\) 分別為：

\([p]_\alpha = \begin{bmatrix} -4\\ 3\\ 5 \end{bmatrix}\), \([p]_\beta = \begin{bmatrix} p(3)\\ p(1)\\ p(-2) \end{bmatrix}= \begin{bmatrix} 50\\ 4\\ 10 \end{bmatrix}\)

以下驗證 \(A[p]_\alpha=[p]_\beta\) :

\(A[p]_\alpha = \left[\begin{array}{ccc} 1 & 3 & 9 \\ 1 & 1 & 1 \\ 1 & -2 & 4 \\ \end{array}\right]\times \left[\begin{array}{c} -4 \\ 3 \\ 5 \\ \end{array}\right]= \left[\begin{array}{c} 50\\ 4\\ 10\\ \end{array}\right] = [p]_\beta\)

Exercise 1©

寫出相對應的拉格朗日基底 \(\beta\)、並求出凡德孟矩陣的反矩陣。

根據定義可求出拉格朗日基底\(\beta\)：
\(\beta = \{\dfrac{1}{10}(x+2)(x-1),\dfrac{-1}{6}(x+2)(x-3),\dfrac{1}{15}(x-1)(x-3)\}\)

將凡德孟矩陣 \(A\) 用增廣矩陣（另一邊放單位矩陣）可得： \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 3 & 9 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & -2 & 4 \end{array}\right] \] 經過列運算後可得此增廣矩陣：

\[\left[\begin{array}{ccc|ccc} \dfrac{-1}{5} & 1 & \dfrac{1}{5} & 1 & 0 & 0 \\ \dfrac{1}{10} & \dfrac{1}{6} & \dfrac{-4}{15} & 0 & 1 & 0 \\ \dfrac{1}{10} & \dfrac{-1}{6} & \dfrac{1}{15} & 0 & 0 & 1 \end{array}\right] \] 由結果可知 \(A^{-1}\) 為： \begin{bmatrix} \dfrac{-1}{5} & 1 & \dfrac{1}{5} \\ \dfrac{1}{10} & \dfrac{1}{6} & \dfrac{-4}{15} \\ \dfrac{1}{10} & \dfrac{-1}{6} & \dfrac{1}{15} \end{bmatrix}

Exercises

Exercise 2

以下小題說明給定一個次數小於等於 \(d\) 的多項式 \(p\)
以及它在 \(d+1\) 個相異點 \(\lambda_0,\ldots,\lambda_d\) 上的函數值 \(p(\lambda_0),\ldots,p(\lambda_d)\)﹐
可以唯一決定多項式 \(p\)。

Exercise 2(a)

令 \(p = c_0 + c_1x + c_2x^2\) 為一多項式。
已知 \(p(1) = 1\), \(p(2) = 2\), \(p(3) = 3\)。
說明這些條件等同於
\[\begin{aligned} c_0 + c_1 + c_2 &= 1, \\ c_0 + 2c_1 + 4c_2 &= 2, \\ c_0 + 3c_1 + 9c_2 &= 3, \\ \end{aligned} \]
並解出 \(p\)。

分別將 \(x = 1,2,3\) 帶入 \(p = c_0 + c_1x + c_2x^2\) : \[\begin{aligned} c_0+c_1+c_2 &= 1 = p(1) \\ c_0 + 2c_1 + 4c_2 &= 2 = p(2) \\ c_0 + 3c_1 + 9c_2 &= 3 =p(3) \end{aligned} \] 由上面式子可解出 \(c_0,c_1,c_2\):
\(c_0 = 0,c_1=1,c_2=0\) , 得 \[p = x\] 。

另外的方法
也可以將拉格朗日多項式相加後可得此多項式 \(p\) 為： \[\dfrac{(x-2)(x-3)}{(1-2)(1-3)} + \dfrac{(x-1)(x-3)}{(2-1)(2-3)} \times 2+ \dfrac{(x-1)(x-2)}{(3-1)(3-2)}\times 3 = x \]

Exercise 2(b)

令 \(\lambda_0,\ldots,\lambda_d\) 為 \(d+1\) 個相異實數。
令 \(y_0,\ldots, y_d\) 任意\(d+1\) 個實數（可能相等）。
利用凡德孟矩陣可逆的性質﹐證明方程組
\[\begin{array}{rcl} c_0 + \lambda_0c_1 + \cdots + \lambda_0^dc_d &= &y_0 \\ c_0 + \lambda_1c_1 + \cdots + \lambda_1^dc_d &= &y_1 \\ &\vdots & \\ c_0 + \lambda_dc_1 + \cdots + \lambda_d^dc_d &= &y_d \\ \end{array} \] 必定有唯一解。

令
\[A = \begin{bmatrix} 1 & \lambda_0 & \cdots & \lambda_0^d \\ 1 & \lambda_1 & \cdots & \lambda_1^d \\ \vdots & \vdots & & \vdots \\ 1 & \lambda_d & \cdots & \lambda_d^d \\ \end{bmatrix} \]

\(\ c = \{c_0, \ldots, c_d\}\) , \(\ y = \{y_0, \ldots, y_d\}\) 。

且
\[\begin{aligned}\\\det(A) &&=\prod_{2\le i\le j}(\lambda_i - \lambda_1)\end{aligned} \] 不等於0
所以 \(A\) 有反矩陣\(A^{-1}\)
使得方程組 \(Ac=y\)
有唯一解\(c=A^{-1}y\)

Exercise 3

依照以下步驟說明拉格朗日基底確實一組基底。

考慮向量空間 \(\mathcal{P}_d\)。
給定 \(d+1\) 個相異實數 \(\lambda_0,\ldots,\lambda_d\)。
令 \(\beta = \{f_0, \ldots, f_d\}\) 為其對應的拉格基底。

Exercise 3(a)

令 \(p\in\mathcal{P}_d\)。
說明 \(p\) 可以寫成 \(\beta\) 的線性組合。

先定義
\[f_i = \frac{ \displaystyle\prod_{\substack{k\in\{0,\ldots,d\} \\ k \neq i }} (x - \lambda_k) } { \displaystyle\prod_{\substack{k\in\{0,\ldots,d\} \\ k \neq i }} (\lambda_i - \lambda_k) }, \] \({\bf y}_i\) 為 \(x=i\) 時的函數值
根據拉格朗日插值法
\[p=f_0{\bf y}_0 + \cdots + f_d{\bf y}_d \] 所以\(p\) 可以寫成 \(\beta\) 的線性組合。

Exercise 3(b)

證明 \(\beta\) 線性獨立。
（令 \(c_0f_0 + \cdots + c_df_d = 0\)﹐
依序將等號兩側代入 \(x = \lambda_0,\ldots, \lambda_d\)。）

令 \(c_0f_0 + \cdots + c_df_d = 0\)
因為\[f_i = \frac{ \displaystyle\prod_{\substack{k\in\{0,\ldots,d\} \\ k \neq i }} (x - \lambda_k) } { \displaystyle\prod_{\substack{k\in\{0,\ldots,d\} \\ k \neq i }} (\lambda_i - \lambda_k) }\] 所以當 \(k=0\) , \(x = \lambda_0\) 時 \(f_0=1\) , \(f_1=f_2=\ldots=f_d=0\)
多項式 \(c_0f_0 + \cdots + c_df_d =c_0=0\)
當 \(k=1\) , \(x = \lambda_1\) 時 \(f_1=1\) , \(f_0=f_2=\ldots=f_d=0\)
多項式 \(c_0f_0 + \cdots + c_df_d =c_1=0\)
以此類推可得\(c_0=c_1=\ldots=c_d=0\)
所以 \(\beta\) 線性獨立。

Exercise 4

考慮向量空間 \(\mathcal{P}_d\)。
令 \(\alpha\) 和 \(\beta\) 分別為其標準基底和拉格朗日基底。
令 \(A = [\operatorname{id}]_\alpha^\beta\)。
說明 \(A^{-1}\) 的各行向量就是把 \(\beta\) 中的各多項式展開的係數。

答:

由於
\(\alpha = \{1, \ldots, x^d\}\)，
\(\beta = \{f_0,\ldots,f_d\}\)。
且由 \(A = [\operatorname{id}]_\alpha^\beta\) ， 得知\(A^{-1} = [\operatorname{id}]_\beta^\alpha\)。
則

\([\operatorname{id}]_\beta^\alpha = \begin{bmatrix} | & ~ & | \\ [f_0]_\alpha & \cdots & [f_d]_\alpha \\ | & ~ & | \\ \end{bmatrix}\)

若把 \(f_0\) 用 \(\alpha\) 表示成 \(c_0 + c_1x + c_2x^2 + ... + c_dx^d\) 的形式，
則 \([\operatorname{id}]_\beta^\alpha\) 的第一個行向量為 \((c_0,c_1,...,c_d)\) 。
再觀察 \(f_0\) 以 \(\beta\) 表示，則 \([f_0]_\beta = (1,0,0,...,0)\) 。
則 \([\operatorname{id}]_\beta^\alpha[f_0]_\beta = c_0 + c_1x + c_2x^2 + ... + c_dx^d\) ，相當於 \(f_0\) 展開後各項的係數。
同樣地，其它行分別是將 \(f_i\) 展開並將 \(x_k\) 的各項係數依序記錄下來。

Exercise 5

令 \(\lambda_1,\ldots,\lambda_n\) 為 \(n\) 個相異實數。
令 \(V\) 為一向量空間而 \(\gamma = \{{\bf u}_1, \ldots, {\bf u}_n\}\) 為任意 \(n\) 個非零向量。
假設已知
\[\begin{array}{rcl} c_1{\bf u}_1 + \cdots + c_n{\bf u}_n &= &{\bf 0}, \\ &\vdots & \\ c_1\lambda_1^{n-1}{\bf u}_1 + \cdots + c_n\lambda_n^{n-1}{\bf u}_d &= &{\bf 0}. \\ \end{array} \] 證明 \(c_1 = \cdots = c_n = 0\)。
（找一個多項式 \(f\) 使得 \(f(\lambda_1) = 1\) 且對所有的 \(k\neq 1\) 都有 \(f(\lambda_k) = 0\)。
將 \(f\) 展開寫成 \(f_0 = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}\)。
從最上面往下﹐每一列分別乘以 \(a_0,\ldots, a_n\) 後加起來﹐藉此得到 \(c_1 = 0\)。
用類似手法說明其它係數也是 \(0\)。）

答:

令
\(f\) 使得 \(f(\lambda_1) = 1\) 且對所有的 \(k\neq 1\) 都有 \(f(\lambda_k) = 0\)。
將 \(f\) 展開寫成 \(f_0 = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}\)。
\(\begin{aligned} &a_0*(c_1{\bf u}_1 + \cdots + c_n{\bf u}_n &= {\bf 0})\\ &a_1*(c_1\lambda_1 {\bf u}_1 + \cdots + c_n\lambda_{n} {\bf u}_n &= {\bf 0})\\ &\vdots\\ +)&a_{n-1}*(c_1\lambda_{1} {\bf u}_1 + \cdots + c_n\lambda_{n}^{n-1}{\bf u}_n &= {\bf 0})\\ \hline &f(\lambda_1)c_1 {\bf u_1} +\dots+f(\lambda_{n})c_1{\bf u_n}&={\bf 0} \end{aligned}\)
而對所有的 \(k\neq 1\) 都有 \(f(\lambda_k) = 0\) ，所以 \(f(\lambda_1)c_1 {\bf u_1}= {\bf 0}\) ， 其中 \(f(\lambda_1) = 1 ,{\bf u_1} \neq0\) 推得 \(c_1=0\) 。
令
\(f\) 使得 \(f(\lambda_2) = 1\) 且對所有的 \(k\neq 2\) 都有 \(f(\lambda_k) = 0\)。
將 \(f\) 展開寫成 \(f_0 = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}\)。
\(\begin{aligned} &a_0*(c_1{\bf u}_1 + \cdots + c_n{\bf u}_n &= {\bf 0})\\ &a_1*(c_1\lambda_1 {\bf u}_1 + \cdots + c_n\lambda_{n} {\bf u}_n &= {\bf 0})\\ &\vdots\\ +)&a_{n-1}*(c_1\lambda_{1} {\bf u}_1 + \cdots + c_n\lambda_{n}^{n-1}{\bf u}_n &= {\bf 0})\\ \hline &f(\lambda_1)c_1 {\bf u_1} +\dots+f(\lambda_{n})c_1{\bf u_n}&={\bf 0} \end{aligned}\)
而對所有的 \(k\neq 2\) 都有 \(f(\lambda_k) = 0\) ，所以 \(f(\lambda_2)c_2 {\bf u_2}= {\bf 0}\) ， 其中 \(f(\lambda_2) = 1 ,{\bf u_2} \neq0\) 推得 \(c_2=0\) 。
用以上觀點推廣對所有 \(k = 1,\ldots, n\) 都有 \(c_n=0\)，得證。

Exercise 6

若 \(A\) 是實數 \(\lambda_0,\ldots,\lambda_d\) 對應的凡德孟矩陣。
證明當 \(d = 1,2\) 時﹐
\[\det(A) = \prod_{i<j}(\lambda_i - \lambda_j).\] （實際上這個公式對所有大小的凡德孟矩陣都對。）

答:
<i> 當 \(d=1\) ,
\(\begin{aligned}\\ \det(A) &=\det(\begin{bmatrix} 1 &\lambda_0 \\ 1 &\lambda_1 \end{bmatrix})\\ &=_{\rho_2:-\rho_1} \det(\begin{bmatrix} 1& \lambda_0\\ 0& \lambda_1-\lambda_0 \end{bmatrix})\\ &=1*(\lambda_1-\lambda_0)-0*(\lambda_0)\\ &=\prod_{0\le i<j \le 1}(\lambda_i - \lambda_j) \end{aligned}\)

得證當 \(d=1\) 時的情況

<ii> 當 \(d=2\) ,
\(\begin{aligned}\\ \det(A) &=\det(\begin{bmatrix} 1 &\lambda_0 &\lambda_0^2 \\ 1 &\lambda_1 &\lambda_1^2 \\ 1 &\lambda_2 &\lambda_2^2 \end{bmatrix})\\ &=_{(\rho_3:-\rho_2,\rho_2:-\rho_1)} \det(\begin{bmatrix} 1& \lambda_0 &\lambda_0^2\\ 0& \lambda_1-\lambda_0 &\lambda_1^2 -\lambda_0^2\\ 0& \lambda_2-\lambda_1 &\lambda_2^2 -\lambda_1^2 \end{bmatrix})\\ &=_{(降階)}1* \det\begin{bmatrix} \lambda_1-\lambda_0 &\lambda_1^2 -\lambda_0^2\\ \lambda_2-\lambda_1 &\lambda_2^2 -\lambda_1^2 \end{bmatrix} -\lambda_0* \overbrace{\det\begin{bmatrix} 0& \lambda_1^2 -\lambda_0^2\\ 0& \lambda_2^2 -\lambda_1^2 \end{bmatrix}}^{=0} +\lambda_0^2* \overbrace{\det( \begin{bmatrix} 0& \lambda_1-\lambda_0 &\\ 0& \lambda_2-\lambda_1 & \end{bmatrix})}^{=0}\\ &= (\lambda_1-\lambda_0)*(\lambda_2^2 -\lambda_1^2)- (\lambda_2-\lambda_1)*(\lambda_1^2 -\lambda_0^2)\\ &= (\lambda_1-\lambda_0)*(\lambda_2 -\lambda_1)*(\lambda_2 +\lambda_1)- (\lambda_2-\lambda_1)*(\lambda_1 -\lambda_0)*(\lambda_1 +\lambda_0)\\ &=_{(同類項合併)} (\lambda_1-\lambda_0)*(\lambda_2 -\lambda_1)*(\lambda_2-\lambda_0)\\ &=_{(整理)} (\lambda_2-\lambda_0)*(\lambda_2 -\lambda_1)*(\lambda_1-\lambda_0)\\ &=\prod_{0 \le i<j \le 2}(\lambda_i - \lambda_j) \end{aligned}\)

得證當 \(d=2\) 時的情況