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

Lagrange polynomials and Vandermonde matrix

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

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

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 $[\idmap]_\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 $([\idmap]_\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$ 的拉格朗日基底。

<!-- eng start -->
Run the code below. Let $\alpha$ be the standard basis of $\mathcal{P}_2$. Let $\beta$ be the Lagrange basis with respect to $\lambda_0, \ldots, \lambda_2$.
<!-- eng end -->

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

<!-- eng start -->
Find the corresponding Vandermonde matrix $A$.
<!-- eng end -->

##### Exercise 1(b)

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

<!-- eng start -->
Find $[p]_\alpha$ and $[p]_\beta$. Then verify that $A[p]_\alpha = [p]_\beta$.
<!-- eng end -->

##### Exercise 1(c)

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

<!-- eng start -->
Find the Lagrange basis $\beta$ and the inverse of the Vandermonde matrix.
<!-- eng end -->

## Exercises

##### Exercise 2

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

<!-- eng start -->
The following problems studies the intuitive fact: Given a polynomial of degree at mosst $d$ and its function values $p(\lambda_0),\ldots,p(\lambda_d)$ on $d + 1$ distinct points $\lambda_0,\ldots,\lambda_d$, the polynomial $p$ is uniquely determined.
<!-- eng end -->

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

<!-- eng start -->
Let $p = c_0 + c_1x + c_2x^2$ be a polynomial. Suppose $p(1) = 1$, $p(2) = 2$, and $p(3) = 3$. Show that these conditions are equivalent to

$$
\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}
$$

and use them to solve $p$.
<!-- eng end -->

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

必定有唯一解。

<!-- eng start -->
Let $\lambda_0,\ldots,\lambda_d$ be $d + 1$ distinct real numbers. Let $y_0,\ldots, y_d$ be any $d + 1$ (not necessarily distinct) real numbers. Use the properties of Vandermonde matrices to show that the system of linear equations

$$
\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}
$$

has a unique solution.
<!-- eng end -->

##### Exercise 3

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

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

<!-- eng start -->
Use the given instructions to show that the Lagrange basis is indeed a basis.

Consider the vector space $\mathcal{P}_d$. Fix $d + 1$ distinct real numbers $\lambda_0, \ldots, \lambda_d$. Let $\beta = \{f_0, \ldots, f_d\}$ be the Lagrange basis with respect to the given numbers.
<!-- eng end -->

##### Exercise 3(a)

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

<!-- eng start -->
Let $p$ be an arbitrary polynomial in $\mathcal{P}_d$. Show that $p$ can be written as a linear combination of $\beta$.
<!-- eng end -->

##### Exercise 3(b)

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

<!-- eng start -->
Show that $\beta$ is linearly independent.

Hint: Suppose $c_0f_0 + \cdots + c_df_d = 0$. Then inductively substitute $x$ with $\lambda_0, \ldots, \lambda_d$.
<!-- eng end -->

##### Exercise 4

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

<!-- eng start -->
Consider the vector space $\mathcal{P}_d$. Let $\alpha$ and $\beta$ be the standard basis and the Lagrange basis of $\mathcal{P}_d$, respectively. Let $A = [\idmap]_\alpha^\beta$. Verify and give some intuition to that $A^{-1}$ is the matrix whose columns are the vectors recording the polynomials in $\beta$.
<!-- eng end -->

##### Exercise 5

令 $\lambda_1,\ldots,\lambda_n$ 為 $n$ 個相異實數。
令 $V$ 為一向量空間而 $\gamma = \{\bu_1, \ldots, \bu_n\}$ 為任意 $n$ 個非零向量。
假設已知

$$
\begin{array}{rcl}
c_1\bu_1 + \cdots + c_n\bu_n &= &\bzero, \\
&\vdots & \\
c_1\lambda_1^{n-1}\bu_1 + \cdots + c_n\lambda_n^{n-1}\bu_d &= &\bzero. \\
\end{array}
$$

證明 $c_1 = \cdots = c_n = 0$。
（找一個多項式 $f$ 使得 $f(\lambda_1) = 1$ 且對所有的 $k\neq 1$ 都有 $f(\lambda_k) = 0$。
將 $f$ 展開寫成 $f = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}$。
從最上面往下﹐每一列分別乘以 $a_0,\ldots, a_n$ 後加起來﹐藉此得到 $c_1 = 0$。
用類似手法說明其它係數也是 $0$。）

<!-- eng start -->
Let $\lambda_1,\ldots,\lambda_n$ be $n$ distinct real numbers. Let $V$ be a vector space and $\gamma = \{\bu_1, \ldots, \bu_n\}$ some nonzero vectors in $V$. Suppose

$$
\begin{array}{rcl}
c_1\bu_1 + \cdots + c_n\bu_n &= &\bzero, \\
&\vdots & \\
c_1\lambda_1^{n-1}\bu_1 + \cdots + c_n\lambda_n^{n-1}\bu_d &= &\bzero. \\
\end{array}
$$

Show that $c_1 = \cdots = c_n = 0$.

Hint: Find a polynomial $f$ such that $f(\lambda_1) = 1$ and $f(\lambda_k) = 0$ for all $k\neq 1$. Let $f = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}$. From top to the bottom, multiply each given condition by $a_0, \ldots, a_n$ and take the sum of them. This lead to the conclusion that $c_1 = 0$. You may show other coefficients are also zero by similar arguments.
<!-- eng end -->

##### Exercise 6

若 $A$ 是相異實數 $\lambda_0,\ldots,\lambda_d$ 對應的凡德孟矩陣。
證明當 $d = 1,2$ 時﹐

$$
\det(A) = \prod_{i<j}(\lambda_i - \lambda_j).
$$

（實際上這個公式對所有大小的凡德孟矩陣都對。）

<!-- eng start -->
Let $A$ be the Vandermonde matrix with respect to distinct real numbers $\lambda_0,\ldots,\lambda_d$. For $d = 1,2$, prove that

$$
\det(A) = \prod_{i<j}(\lambda_i - \lambda_j).
$$

In fact, this formula is true for any positive integer $d$.
<!-- eng end -->