我有一个关于离散傅里叶变换的小问题。如果我理解正确，我们所做的是将多项式转换为其点值表示，对于一个最高次数为n-1的多项式，需要n个点。但为什么我们必须在单位根处进行评估呢？难道任何其他n个点都不能唯一地标识这个多项式，并且更简单吗？
理解离散傅里叶变换
4
- dodger
1
傅里叶变换定义在复数空间上。德莫佛定理有助于确定根。每个根代表正弦函数的一个分量，可以用来近似信号。 - Rajesh Swarnkar
4个回答
2
任意的n个点能唯一确定这个多项式并且更简单吗？答案是否定的。首先，没有保证任意n个点都能起作用；其次，使用n个点来确定多项式要比使用单位根更加复杂。反过来想：你为什么反对使用单位根呢？
- MarkusQ
7
这就是明确而彻底的拒绝（我希望我能尖叫）。假设f，g是不同的n-1次多项式，并且在n个点上相同，则它们的差F在n个点上为0。太好了！你刚刚找到了一个具有n个根的n-1次多项式。 - David Lehavi
@David Lehavi -- 你可以让它适用于其他（精心选择的）点集（考虑到表示法的前后变化或使用备选的正交基函数集），但_总的来说_，它不会起作用。 - MarkusQ
@MarkusQ -- 要得到FFT所能提供的好处，您需要一个复数的有限子群。唯一的这种子群是具有给定阶数的单位根集合。 - David Lehavi
@David Lehavi--通过一些任意因子和角度关于原点缩放和旋转，你将得到一组可以使用（尽管不太方便）且不是单位根的集合。这很混乱和愚蠢，但FT的整个重点就在于它可以经受住这样的变换。 - MarkusQ
@David Lehavi -- 请注意，这个问题是关于DFT而不是FFT的。 - MarkusQ
显示剩余2条评论
2
应用理论的主要原因包括：
- 波变成单项式。
- 时间空间上的乘积在相位空间上是卷积，反之亦然（所以您可以将两个n次多项式相乘，时间复杂度为O（n log n））。
- 时间空间上的导数在相位空间上是x乘积，反之亦然。
对于随机点，这些属性都不存在，直觉上说，这是因为它们不能形成一个群。还有许多理论上的原因（以及一些其他实际应用的原因）。
- David Lehavi
1
@Dave Lehavi — 这是怎么回事？你发表了一个答案，虽然用技术术语描述得更准确，但实质上与我的观点基本一致，却对我进行了负分评价，然后又在另一个无关的问题上对我进行了负分评价？你有没有考虑过戒掉咖啡因？ - MarkusQ
0
这里有两个“直观”的离散傅里叶变换解释。它们不会直接跳入方程式，而是以一种“但愿早些时候有人告诉我这个”的方式引导您逐步理解。
- curryage
0
不，不完全是。这与多项式无关。
它是关于将向量（初始数字序列）分解为不同基础的问题。只是这个基础具有一系列非常有用的属性：
（1）它是正交的——向量不混合，确定回到原始基础的转换非常简单。
（2）傅里叶基础向量是移位（或循环移位，对于离散情况）操作的特征向量——傅里叶基础函数在移动向量索引后仍然是相同的函数（乘以一个数字）。这就是为什么在傅里叶空间中卷积和解决大类微分方程非常简单的原因。
（3）最后，条目是单位根——这导致了快速傅里叶变换（FFT），这是有史以来发现的最优雅的算法之一，将需要进行N^2次操作的基础更改减少到N log N。
（1）它是正交的——向量不混合，确定回到原始基础的转换非常简单。
（2）傅里叶基础向量是移位（或循环移位，对于离散情况）操作的特征向量——傅里叶基础函数在移动向量索引后仍然是相同的函数（乘以一个数字）。这就是为什么在傅里叶空间中卷积和解决大类微分方程非常简单的原因。
（3）最后，条目是单位根——这导致了快速傅里叶变换（FFT），这是有史以来发现的最优雅的算法之一，将需要进行N^2次操作的基础更改减少到N log N。
- ackb
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接