范德蒙德矩阵 : \(\bm{V}=\left[ \begin{array}{ccc}1 & x_0 & x_0^2 & \cdots & x_0^{n-1} \\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-1} & x_{n-1}^2 &\cdots & x_{n-1}^{n-1} \\ \end{array} \right]\)
\(\bm{V}:=[v_{i,j}]=(x_i)^j\)
(有些地方的记法可能会转置一下或者指标从1开始,对推导没有实质影响)
范德蒙德矩阵的直观意义是其表示了从多项式到点值的变换(求值).
考虑不超过 \(n-1\) 次的多项式 \(f(z)=\sum\limits_{k=0}^{n-1} a_kz^k\) .
你们记 \([z^k]f(z)=a_k\) .
不妨记 \(\bm{F}=\left[ \begin{array}{ccc}a_0\\a_1\\\vdots\\a_{n-1} \end{array} \right]\)
我们有 \(\bm{V}\bm{F}=\left[ \begin{array}{ccc}f(x_0)\\f(x_1)\\\vdots\\f(x_{n-1}) \end{array} \right]\)
值得一提的是, 范德蒙德矩阵的行列式被称为范德蒙德行列式, 其具有非常好的形式.
范德蒙德行列式 : \(\det \bm{V}=\prod\limits_{i\lt j}(x_j-x_i)\)
proof
更规范的, 你们记 \(\det\bm{V}=\Delta(x_0,x_1\dots x_{n-1})\)
对于 \(n\) 阶的范德蒙德矩阵, 你们对其施以初等列变换.
(从后往前的)将每列减去前一列的 \(x_0\) 倍, 我们得到
\(\Delta(x_0,x_1\dots x_{n-1})=\det\left[ \begin{array}{ccc}1 & 0 & 0 & \cdots & 0 \\1 & x_1-x_0 & x_1^2-x_1x_0 & \cdots & x_1^{n-1}-x_1^{n-2}x_0 \\1 & x_2-x_0 & x_2^2-x_2x_0 & \cdots & x_2^{n-1}-x_2^{n-2}x_0 \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & x_{n-1}-x_0 & x_{n-1}^2-x_{n-1}x_0 &\cdots & x_{n-1}^{n-1}-x_{n-1}^{n-2}x_0 \\ \end{array} \right]\)
对其按第一行展开得到
\(=\det\left[ \begin{array}{ccc}(x_1-x_0) & x_1(x_1-x_0) & \cdots & x_1^{n-2}(x_1-x_0) \\(x_2-x_0) & x_2(x_2-x_0) & \cdots & x_2^{n-2}(x_2-x_0) \\\vdots & \vdots & \ddots & \vdots \\(x_{n-1}-x_0) & x_{n-1}(x_{n-1}-x_0) &\cdots & x_{n-1}^{n-2}(x_{n-1}-x_0) \\ \end{array} \right]\)
从第 \(i\) 行提取出 \(x_i-x_0\) 的系数得到,
\(=\prod\limits_{i=1}^{n-1}(x_i-x_0)\det\left[ \begin{array}{ccc}1 & x_1 & \cdots & x_1^{n-2} \\1 & x_2 & \cdots & x_2^{n-2} \\\vdots & \vdots & \ddots & \vdots \\1 & x_{n-1} &\cdots & x_{n-1}^{n-2} \\ \end{array} \right]\)
这就是 \(n-1\) 阶的范德蒙德行列式, 即
\(\Delta(x_0,x_1\dots x_{n-1})=\prod\limits_{i=1}^{n-1}(x_i-x_0)\Delta(x_1,x_2\dots x_{n-1})\)
因此由对最后一项因子施以数学归纳法, 我们得到
\(\det\bm{V}=\prod\limits_{i=0}^{n-1}\prod\limits_{j=0}^{i-1}(x_i-x_j)=\prod\limits_{i\lt j}(x_j-x_i)\)
你们来考虑其逆矩阵, 既然范德蒙德矩阵表示多项式求值, 那么其逆矩阵自然就表示多项式插值.
其逆矩阵同样具有封闭形式.
\(\bm{V}^{-1}=[\overset{\sim}{v}_{i,j}]\)
\(\overset{\sim}{v}_{i,j}=\frac{1}{\prod\limits_{k=0,k\neq j}^{n-1}(x_j-x_k)}[z^i]\prod\limits_{k=0,k\neq j}^{n-1}(z-x_k)\)
更常见的形式是 \(\overset{\sim}{v}_{i,j}=\frac{1}{\prod\limits_{k=0,k\neq j}^{n-1}(x_k-x_j)}(-1)^i\sum\limits_{p_0\lt p_1\cdots p_{n-i-1},p_k\neq j}\prod\limits_{k=0}^{n-i-1}(x_{p_k})\)
proof
你们先推导一下两个形式的等价性 .
\(\overset{\sim}{v}_{i,j}=\frac{1}{\prod\limits_{k=0,k\neq j}^{n-1}(x_j-x_k)}[z^i]\prod\limits_{k=0,k\neq j}^{n-1}(z-x_k)=\frac{1}{\prod\limits_{k=0,k\neq j}^{n-1}(x_k-x_j)}(-1)^i[z^i]\prod\limits_{k=0,k\neq j}^{n-1}(x_k+z)=\frac{1}{\prod\limits_{k=0,k\neq j}^{n-1}(x_k-x_j)}(-1)^i\sum\limits_{p_0\lt p_1\cdots p_{n-i-1},p_k\neq j}\prod\limits_{k=0}^{n-i-1}(x_{p_k})\)
由于几个证明方法均较具启发性故均记录于此
拉格朗日插值
你们有拉格朗日插值公式 :
\(f(z)=\sum\limits_{i=0}^{n-1}f(x_i)\dfrac{\prod\limits_{j=0,j\neq i}^{n-1}(z-x_j)}{\prod\limits_{j=0,j\neq i}^{n-1}(x_i-x_j)}\)
考虑 \(\bm{V}^{-1}\left[ \begin{array}{ccc}f(x_0)\\f(x_1)\\\vdots\\f(x_{n-1}) \end{array} \right]=\bm{F}\) , 你们有 \([z^k]f(z)=\sum\limits_{i=0}^{n-1}f(x_i)\overset{\sim}{v}_{k,i}\)
这个式子看起来有点让你们过载, 不要忘记你们手里最锋利的武器, 线性性.
不妨考虑 \(f(x_j)=1,f(x_i)=0(i\neq j)\) 的情况, 显然一般情况为其线性叠加故若其成立则一般情况总是成立
此时有 \([z^k]f(z)=f(x_j)\overset{\sim}{v}_{k,j}\Rightarrow f(z)=\sum\overset{\sim}{v}_{k,j}z^k\) 带回原式即可得到 \(\overset{\sim}{v}_{k,i}=\dfrac{[z^k]\prod\limits_{j=0,j\neq i}^{n-1}(z-x_j)}{\prod\limits_{j=0,j\neq i}^{n-1}(x_i-x_j)}\)
伴随矩阵
你们知道 \(\bm{V}^{-1}=\frac{1}{\det \bm{V}}\bm{V}^*\)
不妨记
\(\Delta_j(x_0,x_1,x_2\dots x_{n-1})=\det\left[ \begin{array}{ccc}1 & x_0 & \cdots & x_0^{j-1} & x_0^{j+1} & \cdots & x_0^{n} \\1 & x_1 & \cdots & x_1^{j-1} & x_1^{j+1} & \cdots & x_1^{n} \\1 & x_2 &\cdots & x_2^{j-1} & x_2^{j+1} & \cdots & x_2^{n} \\\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\1 & x_{n-1} &\cdots & x_{n-1}^{j-1} & x_{n-1}^{j+1} &\cdots & x_{n-1}^{n} \\ \end{array} \right]\)
那么有 \(\bm{A}^*_{j,i}=A_{i,j}=(-1)^{i+j}M_{i,j}=(-1)^{i+j}\Delta_j(x_0,x_1,\cdots,x_{i-1},x_{i+1},\cdots,x_{n-1})\)
那么主要难点就是去掉(一行)一列的范德蒙德矩阵行列式怎么算.
你们有一个巧妙的思路(天哪这是怎么想到的) .
你们引入一个形式变元 \(z\) 再对去掉它的一行作展开, 也就是
\(\Delta(z,x_0,x_1...x_{n-1})=\sum\limits_{i=0}^{n-1}z^i(-1)^i\Delta_i(x_0,x_1,x_2\dots x_{n-1})+z^n(-1)^n\Delta(x_0,x_1...x_{n-1})\)
对两边展开并提取系数.
\([z^i]\Delta(z,x_0,x_1...x_{n-1})=(-1)^i\Delta_i(x_0,x_1,x_2\dots x_{n-1})\)
对左边按范德蒙德行列式展开
\([z^i]\prod\limits_{i\lt j}(x_j-x_i)\prod\limits(x_i-z)=(-1)^i\Delta_i(x_0,x_1,x_2\dots x_{n-1})\)
带回原式即可得到
\(\overset{\sim}{v}_{i,j}=\frac{1}{\det \bm{V}}\bm{A}^*_{i,j}=\dfrac{(-1)^{i+j}M_{j,i}}{\prod\limits_{i'\lt j'}(x_{j'}-x_{i'})}\)
\(=\dfrac{(-1)^{i+j}\Delta_i(x_0,x_1,\cdots,x_{j-1},x_{j+1},\cdots,x_{n-1})}{\prod\limits_{i'\lt j'}(x_{j'}-x_{i'})}\)
\(=\dfrac{(-1)^j[z^i]\prod\limits_{i'\neq j}(x_{i'}-z)\prod\limits_{i'\lt j',i'\neq j,j'\neq j}(x_{j'}-x_{i'})}{\prod\limits_{i'\lt j'}(x_{j'}-x_{i'})}\)
\(=\dfrac{(-1)^j[z^i]\prod\limits_{i'\neq j}(x_{i'}-z)\prod\limits_{i'\lt j',i'\neq j,j'\neq j}(x_{j'}-x_{i'})}{\prod\limits_{i'\lt j',i'\neq j,j'\neq j}(x_{j'}-x_{i'})\prod\limits_{i'\lt j}(x_j-x_{i'})\prod\limits_{j\lt i'}(x_{i'}-x_{j})}\)
\(=\dfrac{(-1)^j[z^i]\prod\limits_{i'\neq j}(x_{i'}-z)}{\prod\limits_{i'\lt j}(x_j-x_{i'})\prod\limits_{j\lt i'}(x_{i'}-x_{j})}\)
\(=\dfrac{(-1)^j[z^i](-1)^{n-1}\prod\limits_{i'\neq j}(z-x_{i'})}{\prod\limits_{i'\lt j}(x_j-x_{i'})(-1)^{n-1-j}\prod\limits_{j\lt i'}(x_{j}-x_{i'})}\)
\(=\dfrac{[z^i]\prod\limits_{i'\neq j}(z-x_{i'})}{\prod\limits_{i'\neq j}(x_j-x_{i'})}\)
你们来尝试推广这个东西, 这要如何推广呢, 从信息考虑插值和求值似乎已经完备.
你们考虑多项式求值的另一个思路, \(f(c)=f(z)\mod (z-c)\)
由代数基本定理 \(f(z)=\prod (z-x_i)\) 但其存在重根, 这启发我们思考 \(f(z) \mod (z-c)^{k}\) 是什么东西呢 ?
先做一个换元, 令 \(t=z-c,z=t+c\) 原式就是 \(f(c+t)\mod t^k \circ (g(t)=z-c)\) 这某种意义上可以看成对 \(f(c)\) 邻域情况的表达.
这种推广同样是关于多项式系数的线性变换, 因此你们可以得到一个 “推广” 的矩阵, 我们定义
\(\bm{\overline{M}}_{k,n}(t)=\left[ \begin{array}{ccc}1 & t & t^2 & \cdots & t^{n-1} \\0 & 1 & \binom{2}{1}t & \cdots & \binom{n-1}{1}t^{n-2} \\0 & 0 & 1 & \cdots & \binom{n-1}{2}t^{n-3} \\\vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 &\cdots & \binom{n-1}{k-1}t^{n-k} \\ \end{array} \right]\)
\(\bm{\overline{M}}_{k,n}(t):=[\overline{M}_{k,n}(t)_{i,j}]=\binom{j}{i}t^{j-i}\)
\(\bm{\overline{V}}_n(x_0,k_0,x_1,k_1,x_2,k_2,\dots,x_{c},k_c)=\left[ \begin{array}{ccc}\bm{\overline{M}}_{k_0,n}(x_0) \\\bm{\overline{M}}_{k_1,n}(x_1) \\\bm{\overline{M}}_{k_2,n}(x_2) \\\vdots \\\bm{\overline{M}}_{k_c,n}(x_c) \end{array} \right]\)
其中 \(\sum k_i=n\)
当 \(k_0=k_1=k_2=\cdots=k_c=1\) 时我们就回到一般的范德蒙德矩阵
关于它的行列式同样有良好的封闭形式 \(\prod\limits_{i\lt j}(x_j-x_i)^{k_ik_j}\)
proof
考虑类似范德蒙德行列式的思路, 施以初等列变换, (从后往前)将每一列减去前一列的 \(x_0\) 倍
我们分两部分处理, \(\bm{\overline{M}}_{k_0,n}(x_0)\) 和 \(\bm{\overline{M}}_{k_i,n}(x_i)\)
第一部分 : 你们得到
由加法恒等式 \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\)
\(\bm{\overline{M}}_{k_0,n}(x_0)\overset{-x_0C_i+C_{i+1}}{\longrightarrow}\left[ \begin{array}{ccc}1 & 0 & 0 & \cdots & 0 \\0 & 1 & x_0 & \cdots & x_0^{n-2} \\0 & 0 & 1 & \cdots & \binom{n-2}{1}x_0^{n-3} \\\vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 &\cdots & \binom{n-2}{k_0-2}t^{n-1-k_0} \\ \end{array} \right]\)
去掉第一行第一列之后, 这就是 \(\bm{\overline{M}}_{k_0-1,n-1}(x_0)\) 我们已经得到了较好的形式.
第二部分 : 你们得到
\(\bm{\overline{M}}_{k_i,n}(x_i)\overset{-x_0C_i+C_{i+1}}{\longrightarrow}\left[ \begin{array}{ccc}1 & x_i-x_0 & x_i^2-x_ix_0 & \cdots & x_i^{n-1}-x_i^{n-2}x_0 \\0 & 1 & \binom{2}{1}x_i-x_0 & \cdots & \binom{n-1}{1}x_i^{n-2}-\binom{n-2}{1}x_i^{n-3}x_0 \\0 & 0 & 1 & \cdots & \binom{n-1}{2}x_i^{n-3}-\binom{n-2}{2}x_i^{n-4}x_0 \\\vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 &\cdots & \binom{n-1}{k_i-1}x_i^{n-k_i}-\binom{n-2}{k_i-1}x_i^{n-k_i-1}x_0 \\ \end{array} \right]\)
到这你们似乎不太有好的效果, 接下来你们再施以行变换, (从上到下)将每一行减去上一行的 \(\frac{1}{x_i-x_0}\) 倍
你们得到
\(\overset{\frac{-1}{x_i-x_0}R_k+R_{k+1}}{\longrightarrow}\left[ \begin{array}{ccc}1 & x_i-x_0 & x_i(x_i-x_0) & \cdots & x_i^{n-2}(x_i-x_0) \\0 & 0 & x_i-x_0 & \cdots & \binom{n-2}{1}x_i^{n-3}(x_i-x_0) \\0 & 0 & 0 & \cdots & \binom{n-2}{2}x_i^{n-4}(x_i-x_0) \\\vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 &\cdots & \binom{n-2}{k_i-1}x_i^{n-k_i-1}(x_i-x_0) \\ \end{array} \right]\)
其去掉第一列后, 即为 \((x_i-x_0)\bm{\overline{M}}_{k_i,n-1}(x_i)\) 你们已经得到了较好的形式.
对于你们得到的这个新的矩阵, 其行列式显然不变, 你们对第一行作按行展开.
由于第一行只有第一个元素不为 \(0\) ,因此其行列式就等于去掉第一行第一列的结果.
也就是说 \(\det\bm{\overline{V}}_n(x_0,k_0,x_1,k_1,x_2,k_2,\dots,x_{c},k_c)=\det\left[ \begin{array}{ccc}\bm{\overline{M}}_{k_0-1,n-1}(x_0) \\(x_1-x_0)\bm{\overline{M}}_{k_1,n-1}(x_1) \\(x_2-x_0)\bm{\overline{M}}_{k_2,n-1}(x_2) \\\vdots \\(x_c-x_0)\bm{\overline{M}}_{k_c,n-1}(x_c) \end{array} \right]=\prod\limits_{i=1}^c(x_i-x_0)^{k_i}\det\bm{\overline{V}}_{n-1}(x_0,k_0-1,x_1,k_1,x_2,k_2,\dots,x_{c},k_c)\)
对于 \(k_0\) 施以数学归纳法得到
\(\det\bm{\overline{V}}_n(x_0,k_0,x_1,k_1,x_2,k_2,\dots,x_{c},k_c)=\prod\limits_{i=1}^c(x_i-x_0)^{k_0k_i}\det\bm{\overline{V}}_{n-k_0}(x_1,k_1,x_2,k_2,\dots,x_{c},k_c)\)
再进一步对变量施以数学归纳法, 你们就得到了封闭形式 \(\prod\limits_{i\lt j}(x_j-x_i)^{k_ik_j}\)