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

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

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())

:::warning
- 記錄你的 `seed` 和題目給的數字，參考別組怎麼寫
:::

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

:::warning

- [x] 說明你怎麼得到答案的
- [x] 加上文字敘述
- [x] 等號加到數學式裡
:::
以 `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(c)

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

- [x] $\beta$ 寫錯，應該是一群多項式
- [x] 寫出怎麼求出反矩陣的
:::
根據定義可求出拉格朗日基底$\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$。

:::warning
將 $x = 1$ 代入，得到條件 $c_0 + c_1 + c_2 = p(1) = 1$。
...
因此得到題目中的三個等式。

解方程式後可得 ...，因此 $p = ...$。

- [x] $\dfrac{(x-2)(x-3)}{(1-2)(1-3)} = p(1)$ <-- 左邊有 $x$ 右邊沒有，怎麼可能等於
:::

分別將 $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}
$$
必定有唯一解。

:::warning

- [ ] $\ c = \{c_0, \ldots, c_d\}$ ,
$\ y = \{y_0, \ldots, y_d\}$ 。
-->
$\bc = (c_0, \ldots, c_d)$ ,
$\by = (y_0, \ldots, y_d)$。
大刮號是集合在用的。
- [ ] $\det(A)$ 那行不用 `aligned`
- [ ] 不等於0 --> 不等於 $0$
- [ ] 標點
- [ ] 向量粗體
:::

令
$$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$ 的線性組合。

:::warning

- [ ] $y_i$ 是純量不用粗體
- [ ] $x = i$ --> $x = \lambda_i$
- [ ] 中英數空格
- [ ] 插值法裡 $f_iy_i$ 改成 $y_if_i$
- [ ] 標點
:::

先定義
$$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$。）

:::warning

- [ ] 標點
:::

令 $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$ 中的各多項式展開的係數。

:::warning

- [x] 標點
- [x] 向量不是用大刮號
- [x] 則 $[\operatorname{id}]_\beta^\alpha$ 那行後面加：同樣地，其它行分別是將 $f_i$ 展開並將 $x_k$ 的各項係數依序記錄下來。
:::

答:

由於
$\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$。）

:::warning

- [x] 用以上觀點推廣 $c_n=0,\forall \in \mathbb{N}$ ，得證 --> 用以上觀點推廣對所有 $k = 1,\ldots, n$ 都有 $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}$。
$\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).$$
（實際上這個公式對所有大小的凡德孟矩陣都對。）

:::warning
格式可以改善，但整體而言沒問題
:::

答:
<**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$ 時的情況

:::info
目前分數 6.5
:::