在叙述 \(n\) 次单位根这件事情的时候,我们是将复数单位圆 \(n\) 等分之后得到单位根,这样来看的话,显然\(w_n^1\)的辐角是 \(\theta=\frac{2\pi}{n}\), 那么\(w_n^k=(w_n^1)^k\) ,那么\(w_n^k\)的辐角就是 \(k\theta\),我们知道在普通二维平面上单位圆上的点表示为\((cos\theta,sin\theta)\),类比到复平面,就会得到 \(w_n^k=cos\theta+sin\theta\ i \ \ \ \ (\theta=\frac{2\pi}n)\)
至此,我们已经了解单位根的性质及其表示,然而我们还不知道为什么要介绍这么一个东西。下面我们会了解的。
2 多项式的点值表示法及其点值表示法的乘法 一开始,我们做介绍时设了两个多项式
\(A(x)=a_0+a_1x+a_2x^2+\ldots+a_nx^n\)
\(B(x)=b_0+b_1x+b_2x^2+\ldots+b_mx^m\)
仔细看的话,我们发现这两个多项式像什么?没错，像函数,实际上它完全可以当成一个函数表达式。
即\(y=A(x)\)
我们知道,求解一次函数只需要知道两个点的坐标,求解二次函数只需要知道三个点的坐标,那么我们可以换个说法,两个点确定了一个一次函数,三个点确定了一个二次函数,同样的,我们可以说 \(n+1\) 个点确定了一个 \(n\) 次函数,确定的方法很简单,我们带入联立即可(想想我们是怎么通过两个点确定一条直线的)。
现在我们把名词换一下,”函数“变成“多项式”,就可以改成说 \(n+1\) 个不同点确定一个 \(n\) 次多项式。
即点集\(((x_0,y_0),(x_1,y_1),\ldots ,(x_n,y_n))\) 能够确定一个 \(n\) 次多项式。
代入\(y=A(x)\)看的形象一点 ，我们解下边的方程组(点是我们已知且在函数上的),就能够求出来所有的系数 \(a\) (就是和求函数解析式一样的概念),如果用高斯消元来解这样一个方程组,复杂度是 \(O(n^3)\)的，这个过程被称作离散傅里叶逆/反变换(IDFT) 。
\[\begin{cases} y_0=a_0+a_1x_0+a_2x_0^2+\ldots+a_nx_0^n \\ y_1=a_0+a_1x_1+a_2x_1^2+\ldots+a_nx_1^n\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ y_n=a_0+a_1x_n+a_2x_n^2+\ldots+a_nx_n^n \end{cases} \]