我在做高代作业的时候走了条错路，但发现这个错路其实很有意思，所以下面的推导多半不是最简洁的推导方法。

$V$ 指范德蒙矩阵 $\begin{pmatrix} 1&x_1&x_1^2&\cdots&x_1^{n-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^{n-1}\\ \end{pmatrix}$ ，众所周知 $\det{V}=\prod_{i\lt j}(x_j-x_i)$ 。

$A_{ij}$ 指 $\begin{pmatrix}x_1&x_1^2&\cdots&x_1^{n}\\ \vdots&\vdots&\ddots&\vdots\\ x_n&x_n^2&\cdots&x_n^{n}\end{pmatrix}$ 的第 $i$ 行 $j$ 列的代数余子式。

下面通过按行求和与按列求和的方式分别求 $\sum_{i=1}^{n}\sum_{j=1}^{n}a^jA_{ij}$ 。

按列求和

考虑求 $\sum_{i=1}^{n}A_{ik}$ ，这相当于求将 $A$ 的第 $k$ 列替换成全 $1$ 后的行列式。显然 $\sum_{i=1}^{n}A_{in}=(-1)^{n-1}\det V$ 。下设 $k\lt n$ 。

将第 $k$ 列前移到第 $1$ 列，再把第 $n$ 列移到第 $k$ 列剩下的缝隙，可以得到 $\sum_{i=1}^{n}A_{ik}=(-1)^{k-1}(-1)^{n-(k+1)}V_{k}=(-1)^{n}V_{k+1}$ ，其中的 $V_k$ 指将 $V$ 的第 $k$ 列替换成 $(x_1^{n},x_2^n,\cdots,x_n^n)^T$ 的行列式。

使用Cramer法则，可以得到 $V_k=\boldsymbol{x}_{k}\det V$ ，其中的 $\boldsymbol{x}$ 为 $V\boldsymbol{x}=(x_1^{n},x_2^n,\cdots,x_n^n)^T$ 的解。

考虑 $V\boldsymbol{x}=(x_1^{n},x_2^n,\cdots,x_n^n)^T$ 这个线性方程组的意义：这是在用待定系数法寻找以全体 $x_k$ 为根的首一多项式的系数。但显然这个多项式就是 $\prod\limits_{k=1}^{n}(x-x_k)$ ，因此 $\boldsymbol{x}_i=-[x^{i-1}]\prod\limits_{k=1}^{n}(x-x_k)$ （ $[x^k]P(x)$ 表示 $P(x)$ 的 $x^k$ 项系数）

因此

$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}a^jA_{ij}&=a^n(-1)^{n-1}\det V+\sum_{j=1}^{n-1}a^j\sum_{i=1}^{n}A_{ij}\\ &=a^n(-1)^{n-1}\det V+(-1)^n\sum_{i=1}^{n-1}a^iV_{i+1}\\ &=(-1)^n\det V\left(-a^n+\sum_{i=2}^{n}a^{i-1}\boldsymbol{x}_i\right)\\ &=(-1)^{n-1}\det V\left(a^n+\sum_{i=1}^{n-1}a^i[x^{i}]\prod_{k=1}^{n}(x-x_k)\right)\\ &=(-1)^{n-1}\det V\left(\sum_{i=0}^{n}a^i[x^{i}]\prod_{k=1}^{n}(x-x_k)-\prod_{k=1}^{n}(-x_k)\right)\\ &=\prod_{i\lt j}(x_j-x_i)\left(\prod_{k=1}^{n}x_k+(-1)^{n-1}\prod_{k=1}^{n}(a-x_k)\right)\\ &=\prod_{i\lt j}(x_j-x_i)\left(\prod_{k=1}^{n}x_k-\prod_{k=1}^{n}(x_k-a)\right) \end{aligned}$

按行求和

考虑 $\sum\limits_{i=1}^{n}a^iA_{ki}$ ，可以把它写成 $\begin{vmatrix} x_1&x_1^2&\cdots&x_1^{n}\\ \vdots&\vdots&\ddots&\vdots\\ x_{k-1}&x_{k-1}^2&\cdots&x_{k-1}^{n}\\ a&a^2&\cdots&a^n\\ x_{k+1}&x_{k+1}^2&\cdots&x_{k+1}^{n}\\ \vdots&\vdots&\ddots&\vdots\\ x_n&x_n^2&\cdots&x_n^{n}\\ \end{vmatrix}$ ，这还是范德蒙行列式（乘上 $a\prod_{i\ne k}x_i$ ），即

$\begin{aligned} \sum\limits_{i=1}^{n}a^iA_{ki}&=a(-1)^{k+1}\prod_{i\ne k}x_i(x_i-a)\prod_{i\lt j;i,j\ne k}(x_j-x_i) \end{aligned}$

因此

$\sum_{i=1}^{n}\sum_{j=1}^{n}a^jA_{ij}=a\sum_{k=1}^{n}(-1)^{k+1}\prod_{i\ne k}x_i(x_i-a)\prod_{i\lt j;i,j\ne k}(x_j-x_i)$

如果 $x_k$ 两两不等，~~实际上这个变形总是正确的，因为交错多项式必有范德蒙行列式为因式~~

$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}a^jA_{ij}&=a\prod_{i\lt j}(x_j-x_i)\left(\sum_{k=1}^{n}\prod_{i\ne k}\frac{x_i(x_i-a)}{x_i-x_k}\right)\\ &=a\prod_{i\lt j}(x_j-x_i)\prod_{k=1}^{n}x_k\left(\sum_{k=1}^{n}\frac{1}{x_k}\prod_{i\ne k}\frac{a-x_i}{x_k-x_i}\right) \end{aligned}$

因此

$\begin{aligned} \sum_{k=1}^{n}\frac{1}{x_k}\prod_{i\ne k}\frac{a-x_i}{x_k-x_i}&=\frac{\prod_{k=1}^{n}x_k-\prod_{k=1}^{n}(x_k-a)}{a\prod_{k=1}^{n}x_k}\\ &=\frac{1}{a}\left(1-\prod_{k=1}^{n}(1-\frac{a}{x_k})\right) \end{aligned}$

很容易验证这是一个 $a$ 的多项式，并且在 $a=x_k$ 时取值 $\dfrac{1}{x_k}$ 。但肯定大家都想简化下这个推导过程。

简单的想法

想要构造一个这样的多项式，显然只需要构造一个在全部 $x_k$ 处取值为 $1$ ，并且没有常数项的多项式，然后除以 $x$ 就行了；而这只需要构造一个在全部 $x_k$ 处取值为 $0$ 且常数项是 $1$ 的多项式，然后用 $1$ 减掉就行了；最后这个构造是显然的， $P(x)=\prod\limits_{k=1}^{n}(1-\frac{x}{x_k})$ 。

但这个结果没有太大意义，毕竟无论是求单点值还是求多点值，貌似复杂度都不会比暴力插值更优 $\dots$

0 comments

Anonymous

Markdown is supported

Be the first person to leave a comment!

当你试图用拉格朗日插值去插1/x

按列求和

按行求和

简单的想法

CATALOG

FEATURED TAGS

FRIENDS