## 每週問題 September 30, 2013

Given a set of $n$ points $S=\{(x_1,y_1,),(x_2,y_2),\ldots,(x_n,y_n)\}$ in which the $x_i$’s are distinct, prove that there is a unique polynomial

$\displaystyle p(t)=c_0+c_1t+c_2t^2+\cdots+c_{n-1}t^{n-1}$

of degree $n-1$ that passes through each point in $S$.

\displaystyle\begin{aligned} c_1+c_1x_1+c_2x_1^2+\cdots+c_{n-1}x_1^{n-1}&=p(x_1)=y_1\\ c_1+c_1x_2+c_2x_2^2+\cdots+c_{n-1}x_2^{n-1}&=p(x_2)=y_2\\ &\vdots\\ c_1+c_1x_n+c_2x_n^2+\cdots+c_{n-1}x_n^{n-1}&=p(x_n)=y_n. \end{aligned}

$\displaystyle \begin{bmatrix} 1&x_1&x_1^2&\cdots&x_1^{n-1}\\ 1&x_2&x_2^2&\cdots&x_2^{n-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^{n-1} \end{bmatrix}\begin{bmatrix} c_0\\ c_1\\ \vdots\\ c_{n-1} \end{bmatrix}=\begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_n \end{bmatrix}$

$\displaystyle \det A=\prod_{1\le j

$x_1,x_2,\ldots,x_n$ 是相異的 $n$ 個數，則 $\det A\neq 0$，表示 Vandermonde 矩陣 $A$ 可逆，故存在唯一的 $n-1$ 階多項式 $p(t)$ 穿越給定的 $n$ 個點。