Lagrange polynomials and Vandermonde matrix
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\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
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$.
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$.
執行以下程式碼。
令 $\alpha$ 為 $\mathcal{P}_2$ 的標準基底。
令 $\beta$ 為下述 $\lambda_0,\ldots,\lambda_2$ 的拉格朗日基底。
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$.
### 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())
求出 $[p]_\alpha$ 及 $[p]_\beta$ 並驗證 $A[p]_\alpha = [p]_\beta$。
Find $[p]_\alpha$ and $[p]_\beta$. Then verify that $A[p]_\alpha = [p]_\beta$.
寫出相對應的拉格朗日基底 $\beta$、並求出凡德孟矩陣的反矩陣。
Find the Lagrange basis $\beta$ and the inverse of the Vandermonde matrix.
以下小題說明給定一個次數小於等於 $d$ 的多項式 $p$
以及它在 $d+1$ 個相異點 $\lambda_0,\ldots,\lambda_d$ 上的函數值 $p(\lambda_0),\ldots,p(\lambda_d)$﹐
可以唯一決定多項式 $p$。
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.
令 $p = c_0 + c_1x + c_2x^2$ 為一多項式。
已知 $p(1) = 1$, $p(2) = 2$, $p(3) = 3$。
說明這些條件等同於
並解出 $p$。
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$.
令 $\lambda_0,\ldots,\lambda_d$ 為 $d+1$ 個相異實數。
令 $y_0,\ldots, y_d$ 任意 $d+1$ 個實數(可能相等)。
利用凡德孟矩陣可逆的性質﹐證明方程組
必定有唯一解。
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.
依照以下步驟說明拉格朗日基底確實一組基底。
考慮向量空間 $\mathcal{P}_d$。
給定 $d+1$ 個相異實數 $\lambda_0,\ldots,\lambda_d$。
令 $\beta = \{f_0, \ldots, f_d\}$ 為其對應的拉格基底。
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.
令 $p\in\mathcal{P}_d$。
說明 $p$ 可以寫成 $\beta$ 的線性組合。
Let $p$ be an arbitrary polynomial in $\mathcal{P}_d$. Show that $p$ can be written as a linear combination of $\beta$.
證明 $\beta$ 線性獨立。
(令 $c_0f_0 + \cdots + c_df_d = 0$﹐
依序將等號兩側代入 $x = \lambda_0,\ldots, \lambda_d$。)
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$.
考慮向量空間 $\mathcal{P}_d$。
令 $\alpha$ 和 $\beta$ 分別為其標準基底和拉格朗日基底。
令 $A = [\idmap]_\alpha^\beta$。
說明 $A^{-1}$ 的各行向量就是把 $\beta$ 中的各多項式展開的係數。
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$.
令 $\lambda_1,\ldots,\lambda_n$ 為 $n$ 個相異實數。
令 $V$ 為一向量空間而 $\gamma = \{\bu_1, \ldots, \bu_n\}$ 為任意 $n$ 個非零向量。
假設已知
證明 $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$。)
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.
若 $A$ 是相異實數 $\lambda_0,\ldots,\lambda_d$ 對應的凡德孟矩陣。
證明當 $d = 1,2$ 時﹐
(實際上這個公式對所有大小的凡德孟矩陣都對。)
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$.