浅谈范德蒙德(Vandermonde)方阵的逆矩阵与拉格朗日(Lagrange)插值的关系以及快速傅里叶变换(FFT)中IDFT的原理
标签： 行列式 矩阵 线性代数 FFT 拉格朗日插值
只要稍微看过一点线性代数的应该都知道范德蒙德行列式。
[V(x_0,x_1,cdots ,x_{n-1})=egin{bmatrix}
{1}&{1}&{cdots}&{1}\
{x_{0}}&{x_{1}}&{cdots}&{x_{n-1}}\
{x_{0}^2}&{x_{1}^2}&{cdots}&{x_{n-1}^2}\
{vdots}&{vdots}&{}&{vdots}\
{x_{0}^{n-1}}&{x_{1}^{n-1}}&{cdots}&{x_{n-1}^{n-1}}\
end{bmatrix} ]
而范德蒙德行列式由于其本身的特殊性，具有通项公式:
[V(x_0,x_1,cdots ,x_{n-1})=prod _{n > i > j geq 0}(x _{i}-x _{j})
]
我们同样可以把行列式中的项写到矩阵中来，即范德蒙德方阵
[V=egin{pmatrix}
{1}&{1}&{cdots}&{1}\
{x_{0}}&{x_{1}}&{cdots}&{x_{n-1}}\
{x_{0}^2}&{x_{1}^2}&{cdots}&{x_{n-1}^2}\
{vdots}&{vdots}&{}&{vdots}\
{x_{0}^{n-1}}&{x_{1}^{n-1}}&{cdots}&{x_{n-1}^{n-1}}\
end{pmatrix}]
考虑范德蒙德方阵的逆矩阵，我们可以借助伴随矩阵来计算。
对于(V)的伴随矩阵(V^*)
[(V^*)_{ij}=c_{ij}
]
其中(c_{ij})为(V)的代数余子式
有(V^{-1}={V* over det(V)})
那么对于每一项，有((V^{-1})_{ij}={c_{ij} over det(V)})
我们只需要知道每一个代数余子式其与行列式的商即可。
而然这种方法比较复杂，尤其对于缺失了一行的范德蒙德行列式难以计算，而本文的重点并不在此，如果想找详细的证明可以去看这篇博客Vandermonde 矩陣的逆矩陣公式
最后可以得到
[(V^{-1})_{ij}=(-1)^{j+1}{ sumlimits_{0 leq p_1<cdots < p_{n-j} < n; p_1,p_2,cdots p_{n-j}
e i} x_{p_1} x_{p_2} cdots x_{p_{n-j}} over prodlimits_{0 leq k < n; k
e i} (x_k-x_i)}
]
上面的方法太过复杂，接下来我们考虑范德蒙德方阵的实际意义进行思考。
重新审视方阵，发现乘上一个范德蒙德方阵相当于带进了(n)个点进行求值，即
[{egin{pmatrix}
{a_0}\
{a_1}\
{a_2}\
{vdots}\
{a_{n-1}}\
end{pmatrix}
}^Tegin{pmatrix}
{1}&{1}&{cdots}&{1}\
{x_{0}}&{x_{1}}&{cdots}&{x_{n-1}}\
{x_{0}^2}&{x_{1}^2}&{cdots}&{x_{n-1}^2}\
{vdots}&{vdots}&{}&{vdots}\
{x_{0}^{n-1}}&{x_{1}^{n-1}}&{cdots}&{x_{n-1}^{n-1}}\
end{pmatrix}={
egin{pmatrix}
{y_0}\
{y_1}\
{y_2}\
{vdots}\
{y_{n-1}}
end{pmatrix}}^T
]
相当于有多项式(f(x)=sum_{i=0}^{n-1} a_ix^i),其中(y_i=f(x_i))
乘上范德蒙德方阵相当于带入(n)个点求值，反过来，乘上其逆矩阵就应该是用(n)个点插值。
即
[{egin{pmatrix}
{a_0}\
{a_1}\
{a_2}\
{vdots}\
{a_{n-1}}\
end{pmatrix}}^T
={egin{pmatrix}
{y_0}\
{y_1}\
{y_2}\
{vdots}\
{y_{n-1}}
end{pmatrix}}^T
egin{pmatrix}
{1}&{1}&{cdots}&{1}\
{x_{0}}&{x_{1}}&{cdots}&{x_{n-1}}\
{x_{0}^2}&{x_{1}^2}&{cdots}&{x_{n-1}^2}\
{vdots}&{vdots}&{}&{vdots}\
{x_{0}^{n-1}}&{x_{1}^{n-1}}&{cdots}&{x_{n-1}^{n-1}}\
end{pmatrix}^{-1} ]
那么我们考虑拉格朗日插值，有
[f(x)=sum_{i}y_iprod_{j
e i} {x-x_j over x_i-x_j}
]
显然，((V^{-1})_{ij})为(prodlimits_{k
e i} {x-x_k over x_i-x_k})在(x^{j-1})项的系数。
快速傅立叶变换的核心思想也是将系数向量迅速变换为点值向量，再迅速的将点值向量还原成系数向量，其中还原的操作我们称之为(IDFT)。
用(1)的(n)次复根(w),如果没有特别说明，以下本文中的(w)都为(e^{2pi over n})
在做快速傅立叶变换的时候，我们乘上了一个(V(w_0,w_1,cdots,w_{n-1}))的矩阵。
而在(IDFT)时，我们需要乘上(V(w_0,w_1,cdots,w_{n-1})^{-1})，但是在实际应用中，我们会直接乘上$ {1 over n}V(w_0,w_{-1},cdots,w_{-n+1}) $。接下来笔者将证明这两个矩阵是相同的。（当然我们默认n为2的次幂）
[prodlimits_{j
e i} {(x-w^j) over (w^i-w^j)}={prodlimits_{j
e i} (x-w^j) over prodlimits_{j
e i} (w^i-w^j)}
]
不妨令$$G(x)=prod_{0 leq j < n} (x-w^j)$$
而(w^{0},w^1,cdots,w^{n-1})都是1的n次复根，根据代数基本定理，显然有$$G(x)=x^n-1$$
那么考虑原式分母$$prodlimits_{j
e i} (w^i-w^j) = lim _{x o w^i}{G(x) over {x-w^i}}$$
根据洛必达法则，这个极限的值相当于上下部分求导的商。
[lim _{x o w^i}{G(x) over {x-w^i}}=lim _{x o w^i} G'(x)=n imes w^{i(n-1)}=n imes w^{-i}
]
原式分子
[{prodlimits_{j
e i} (x-w^j)}={G(x) over {x-w^i}}={1-x^n over {w^i-x}}\
=w^{-i} imes egin{pmatrix}{1 over 1- x w^{-i}}-{x^n over 1-xw^{-i}}end{pmatrix}\
=w^{-i} imes egin{pmatrix}{sum_{j=0}^{infty} w^{-ij}x^j -sum_{j=n}^{infty} w^{-i(j-n)}x^j} end{pmatrix}\
=w^{-i} imes sum_{j=0}^{n-1} w^{-ij} x^j
]
分子除以分母，得
[原式={w^{-i} imes sumlimits_{j=0}^{n-1} w^{-ij} x^j over n imes w^{-i}}\
=sum_{j=0}^{n-1} {w^{-ij} over n}x^j]
对比各项系数，不难得出两矩阵相同，即
[egin{pmatrix}
{1}&{1}&{cdots}&{1}\
{1}&{w^{1}}&{cdots}&{w^{n-1}}\
{1}&{w^{2}}&{cdots}&{w^{(n-1)2}}\
{vdots}&{vdots}&{}&{vdots}\
{1}&{w^{n-1}}&{cdots}&{w^{(n-1)(n-1)}}\
end{pmatrix}^{-1}
={1 over n}egin{pmatrix}
{1}&{1}&{cdots}&{1}\
{1}&{w^{-1}}&{cdots}&{w^{-(n-1)}}\
{1}&{w^{-2}}&{cdots}&{w^{-(n-1)2}}\
{vdots}&{vdots}&{}&{vdots}\
{1}&{w^{-(n-1)}}&{cdots}&{w^{-(n-1)(n-1)}}\
end{pmatrix}
]