1. 激活谷首页
  2. 激活谷笔记

fft算法的原理_FFT原理通俗易懂

• 激活谷笔记

fft算法的原理_FFT原理通俗易懂让我给你讲清楚 快速傅里叶变换(FFT)(一): 数学原理详解大家好啊, 今天我们来学习一个非常伟大和美丽的算法. 快速傅里叶变换.0.为什么要用快速傅里叶变换想象一个需求, 你需要对两个多项式, 或者一个超大的整数进行乘法运算.

让我给你讲清楚 快速傅里叶变换(FFT)(一): 数学原理详解 　　大家好啊, 今天我们来学习一个非常伟大和美丽的算法. 快速傅里叶变换. 　　0.为什么要用快速傅里叶变换 　　想象一个需求, 你需要对两个多项式, 或者一个超大的整数进行乘法运算. 最自然的, 肯定是直接将多项式或者整数的每一位和另一个多项式或整数的每一位相乘. 这种方法叫朴素乘法, 不难看出, 朴素乘法的复杂度是
O(n^2) 　　当两个多项式或整数的长度为
1048576 的时候, 这个算法要进行
1099511627776\approx1.0995\times10^{12} 次乘法运算, 效率实在是太低了. 　　有没有什么方法可以减少运算量呢?
O(n^2) 实在是太大了, 如果能优化到
Q(n\log n) 就好了. 　　这就是我们今天要讲的快速傅里叶变换, Fast Fourier Transform. 　　1.多项式的系数表示法 　　我们知道, 对任意的多项式, 都可以表示为 　　
A_{n}(x)=a_0x^0+a_1x^1+a_2x^{2}+\cdots+a_nx^{n} 　　这个方法也可以表示任意进制的整数, 例如, 就有 　　
\texttt{0x7FFF0080}=0\times16^{0}+8\times16^1+0\times16^{3}+\cdots+\texttt{F}\times16^{6}+7\times16^{7} 　　为了方便讲解, 我们之后仅提及多项式, 因为对于大整数的处理和多项式完全一样 　　对于多项式
A_n(x) , 我们又有向量表示法, 即: 　　
\begin{align}A_n(x)&=[a_0,a_1,a_2,\cdots,a_n][x^0,x^1,x^2,\cdots,x^n]^T\\&=AP^T\end{align} 　　如果省略
P^T , 我们就只需要用向量
A=[a_0,a_1,a_2,\cdots,a_n] 表示多项式
A_n(x) , 这就是多项式的系数表示法. 　　2.多项式的点值表示法 　　实际上, 多项式还可以用点值表示, 对于任意的多项式
A_n(x) , 如果带入
(n+1) 个不同的点, 必定得到
(n+1) 个值, 即带入 　　
X=[x_0,x_1,x_2,\cdots,x_n] 　　就能得到 　　
Y=[A_n(x_0),A_n(x_1),A_n(x_2),\cdots,A_n(x_n)] 　　现在, 我们来讨论一个问题, 能否在仅知道
(X,Y) 向量的情况下, 确定多项式
A_n(x) , 换言之, 能否通过多项式的在各个点的值, 来确定多项式. 　　这个是可以的, 但是为什么? 　　如果我们写出
Y 的矩阵方程形式, 就有, 　　
Y^T= \left[\begin{matrix}1&x_0&x_0^2&\cdots&x_0^n\\1&x_1&x_1^2&\cdots&x_1^n\\\cdots\\1&x_n&x_n^2&\cdots&x_n^n \end{matrix}\right]\left[\begin{matrix}a_0\\a_1\\\cdots\\a_n\end{matrix}\right] 　　所以有, 　　
Y^T\left[\begin{matrix}1&x_0&x_0^2&\cdots&x_0^n\\1&x_1&x_1^2&\cdots&x_1^n\\\cdots\\1&x_n&x_n^2&\cdots&x_n^n \end{matrix}\right]^{-1}= \left[\begin{matrix}a_0\\a_1\\\cdots\\a_n\end{matrix}\right] 　　很明显, 这个矩阵的行列式是个范德蒙行列式(的转置), 而范德蒙行列式一定可逆, 所以这个矩阵方程只有唯一解, 所以
(n+1) 个不同的点所确定的
(n+1) 个值必定能唯一确定多项式
A_n(x) 　　3.多项式乘积的点值表示. 　　假设现在有一个
A_n(x) 和一个多项式
B_n(x) , 其对应点值向量
(X,Y_A) ,
(X,Y_B) , 那么假设
C_n(x)=A_n(x)\cdot B_n(x) , 就有
C_n(x) 的点值表示
(X,Y_C)=(X,(Y_A\times Y_B)) 　　
(Y_A\times Y_B) 表示向量的按素相乘, 值写回原位置. 　　即 　　
\begin{align} &[C_n(x_0),C_n(x_1),C_n(x_2),\cdots,C_n(x_n)]\\\\=&[A_n(x_0)\times B_n(x_0),A_n(x_1)\times B_n(x_1),A_n(x_2)\times B_n(x_2),\cdots,A_n(x_n)\times B_n(x_n)] \end{align}
fft算法的原理_FFT原理通俗易懂
fft算法的原理_FFT原理通俗易懂 　　因此, 从
A_n(x) 的点值表示到
B_n(x) 的点值表示仅需要
(n+1) 次乘法, 因此复杂度是
O(n) 　　我们好像看到一点希望了, 我们现在来捋一下思路如果我们能将两个多项式的系数表示转为其各自点值表示再将这两个多项式的对应点值相乘再将相乘后的点值表示转回系数表示我们就得到了两个多项式相乘的结果, 并且是系数表示的 　　不错不错, 思路就是这样, 但是有几个问题怎么将系数表示转换为点值表示怎么将点值表示转回系数表示 　　我们下面就来研究这两个问题 　　接下来, 也是这个算法最美妙的部分. 　　4.系数表示转点值表示 　　很自然的, 我们想到可以带入自然数列
[1,2,3,\cdots,(n+1)] 到
A_n(x) 和
B_n(x) , 这样就得到了
A_n(x) 和
B_n(x) 的点值表示. 　　但是有个问题, 这个算法对于一个多项式, 一共要做
(n+1)n 次加法, 还要做至少
(n+1)n 次乘法, 因此这个算法的时间复杂度还是
O(n^2) 　　我们试着优化一下. 　　我们注意到, 一个多项式一定会有奇数次项, 例如
x^1,x^7,x^{771},x^{775} , 　　和偶数次项, 例如
x^0,x^8,x^{1002},x^{1048576} . 　　而对于奇数次项来说, 一定有
(-x)^n=-x^n 　　而对于偶数次项来说, 一定有
(-x)^n=x^n 　　那么对于只有奇数项或者只有偶数项的多项式来说, 我们只需要求出 　　
[A_n(x_0),A_n(x_1),A_n(x_2),\cdots,A_n(x_{\frac{n-1}{2}})] 这
\frac{n+1}{2} 个点的值, 我们就能按照函数的奇偶性求出 　　
[A_n(-x_0),A_n(-x_1),A_n(-x_2),\cdots,A_n(-x_{\frac{n-1}{2}})] , 这样一来, 我们只需要求
\frac{n+1}{2} 个点的值, 就能确定
(n+1) 个点的值. 　　但是具体要怎么做呢? 　　现在, 我们再将
n 阶多项式(意思是
x 的最高次是
x^n ), 扩增到
x^{2^k-1} 阶.
2^{k}-1\geqslant n , 原来不存在的要补成
fft算法的原理_FFT原理通俗易懂0 　　例如 　　
\begin{align} A_6(x)&=9+7x+6x^2+6x^3+5x^4\\&=9+7x+6x^2+6x^3+5x^4+0x^6+0x^7 \end{align} 　　现在我们将
A_n(x) 分成奇数次项和偶数次项. 即: 　　
\begin{align} A_n(x)&=(a_0x^0+a_2x^2+\cdots+a_{n-1}x^{n-1})+(a_1x^1+a_3x^3+\cdots+a_{n}x^{n})\\\\ &=(a_0x^0+a_2x^2+\cdots+a_{n-1}x^{n-1})+x(a_1x^0+a_3x^2+\cdots+a_{n}x^{n-1})\\\\ &= \left[\begin{matrix}a_0\\ a_2\\\cdots\\a_{n-1}\end{matrix}\right]^T\left[\begin{matrix}x^0\\x^2\\ \cdots\\x^{n-1}\end{matrix}\right]+ x\left[\begin{matrix}a_1\\a_3\\\cdots\\a_{n}\end{matrix}\right]^T\left[\begin{matrix}x^0\\x^2\\\cdots\\x^{n-1}\end{matrix}\right]\\\\ &= \left[\begin{matrix}a_0\\ a_2\\\cdots\\a_{n-1}\end{matrix}\right]^T\left[\begin{matrix}(x^2)^0\\(x^2)^1\\ \cdots\\(x^2)^{\frac{n-1}{2}}\end{matrix}\right]+ x\left[\begin{matrix}a_1\\a_3\\\cdots\\a_{n}\end{matrix}\right]^T\left[\begin{matrix}(x^2)^0\\(x^2)^1\\ \cdots\\(x^2)^{\frac{n-1}{2}}\end{matrix}\right]\\\\ &=A1_n(x^2)+xA2_n(x^2) \end{align}
fft算法的原理_FFT原理通俗易懂
fft算法的原理_FFT原理通俗易懂 　　而对于任意的
x_0 来说, 一旦我们知道了
[x_0^0,x_0^2,\cdots,x_0^{n-1}] , 　　我们就能在
O(\frac{n}{2}) 的时间内知道
A1_n(x_0^2)=(a_0x^0_0+a_2x^2_0+\cdots+a_{n-1}x^{n-1}_0) , 　　同样, 我们也能在
O(\frac{n}{2}) 的时间里知道
A2_n(x_0^2)=(a_1x^0_0+a_3x^2_0+\cdots+a_{n}x^{n-1}_0) 　　之后, 我们计算
x(a_1x^0+a_3x^2+\cdots+a_{n}x^{n-1}) 只需要
O(1) 的时间 　　因此, 我们能在
O(n) 的时间里面知道
A_n(x_0) , 而这时候 　　
\begin{align} A_n(x_0) &= \left[\begin{matrix}a_0\\ a_2\\\cdots\\a_{n-1}\end{matrix}\right]^T\left[\begin{matrix}(x^2_0)^0\\(x^2_0)^1\\ \cdots\\(x^2_0)^{\frac{n-1}{2}}\end{matrix}\right]+ x_0\left[\begin{matrix}a_1\\a_3\\\cdots\\a_{n}\end{matrix}\right]^T\left[\begin{matrix}(x^2_0)^0\\(x^2_0)^1\\ \cdots\\(x^2_0)^{\frac{n-1}{2}}\end{matrix}\right]\\\\ &=A1_n(x_0^2)+x_0A2_n(x_0^2) \end{align} 　　
\begin{align} A_n(-x_0) &= \left[\begin{matrix}a_0\\ a_2\\\cdots\\a_{n-1}\end{matrix}\right]^T\left[\begin{matrix}(x^2_0)^0\\(x^2_0)^1\\ \cdots\\(x^2_0)^{\frac{n-1}{2}}\end{matrix}\right]- x_0\left[\begin{matrix}a_1\\a_3\\\cdots\\a_{n}\end{matrix}\right]^T\left[\begin{matrix}(x^2)^0\\(x^2)^1\\ \cdots\\(x^2)^{\frac{n-1}{2}}\end{matrix}\right]\\\\ &=A1_n(x_0^2)-x_0A2_n(x_0^2) \end{align} 　　所以一旦我们求出了
A1_n(x_0^2) 和
A2_n(x_0^2) , 我们就求出了
A_n(x_0) 和
A_n(-x_0) . 　　而求
A1_n(x_0^2) 和
A2_n(x_0^2) 都是求
A_n(x_0) 需要花费的时间的一半, 这样一来, 我们花费的时间和求
A_n(x_0) 相同, 但是同时我们又能求出
A_n(-x_0) , 　　相当于花了原来一半的时间就能求出
A_n(x_0) 　　如果我们将这个过程递归下去, 假设原来需要花
T 的时间求解
A_n(x_0) , 现在最终只需要花
\log T 的时间. 　　是的, 这时候, 我们又可以将
A1_n(x_0^2) 视作一个新的多项式函数, 　　则有 　　
\begin{align} A1_n(x_0^2)&= \left[\begin{matrix}a_0\\ a_4\\\cdots\\a_{n-3}\end{matrix}\right]^T\left[\begin{matrix}(x^4_0)^0\\(x^4_0)^1\\ \cdots\\(x^4_0)^{\frac{n-3}{4}}\end{matrix}\right]+ x_0^2\left[\begin{matrix}a_2\\a_6\\\cdots\\a_{n-1}\end{matrix}\right]^T\left[\begin{matrix}(x^4_0)^0\\(x^4_0)^1\\ \cdots\\(x^4_0)^{\frac{n-3}{4}}\end{matrix}\right]\\\\ &=A11_n(x_0^4)+x_0^2A21_n(x_0^4) \end{align} 　　
\begin{align} A1_n(-x_0^2)&= \left[\begin{matrix}a_0\\ a_4\\\cdots\\a_{n-3}\end{matrix}\right]^T\left[\begin{matrix}(x^4_0)^0\\(x^4_0)^1\\ \cdots\\(x^4_0)^{\frac{n-3}{4}}\end{matrix}\right]- x_0^2\left[\begin{matrix}a_2\\a_6\\\cdots\\a_{n-1}\end{matrix}\right]^T\left[\begin{matrix}(x^4_0)^0\\(x^4_0)^1\\ \cdots\\(x^4_0)^{\frac{n-3}{4}}\end{matrix}\right]\\\\ &=A11_n(x_0^4)-x_0^2A21_n(x_0^4) \end{align} 　　同样对于
A2_n(-x_0^2) , 有 　　
\begin{align} A2_n(x_0^2)&= \left[\begin{matrix}a_1\\ a_5\\\cdots\\a_{n-2}\end{matrix}\right]^T\left[\begin{matrix}(x^4_0)^0\\(x^4_0)^1\\ \cdots\\(x^4_0)^{\frac{n-3}{4}}\end{matrix}\right]+ x_0^2\left[\begin{matrix}a_3\\a_7\\\cdots\\a_{n}\end{matrix}\right]^T\left[\begin{matrix}(x^4_0)^0\\(x^4_0)^1\\ \cdots\\(x^4_0)^{\frac{n-3}{4}}\end{matrix}\right]\\\\ &=A21_n(x_0^4)+x_0^2A22_n(x_0^4) \end{align} 　　
\begin{align} A2_n(-x_0^2)&= \left[\begin{matrix}a_1\\ a_5\\\cdots\\a_{n-2}\end{matrix}\right]^T\left[\begin{matrix}(x^4_0)^0\\(x^4_0)^1\\ \cdots\\(x^4_0)^{\frac{n-3}{4}}\end{matrix}\right]- x_0^2\left[\begin{matrix}a_3\\a_7\\\cdots\\a_{n}\end{matrix}\right]^T\left[\begin{matrix}(x^4_0)^0\\(x^4_0)^1\\ \cdots\\(x^4_0)^{\frac{n-3}{4}}\end{matrix}\right]\\\\ &=A21_n(x_0^4)-x_0^2A22_n(x_0^4) \end{align} 　　如果这个过程能够正常递归下去, 我们就能将原来需要花
T 的时间求解
A_n(x_0) , 优化到最终只需要花
\log T 的时间. 　　但是这里有点问题 　　第一次递归的时候, 我们需要求出的是 　　
[A_n(\pm x_0),A_n(\pm x_1),A_n(\pm x_2),\cdots,A_n(\pm x_{\frac{n-1}{2}})] 　　这要求
[\pm x_0,\pm x_1,\pm x_2,\cdots,\pm x_{\frac{n-1}{2}}] 是正负配对的. 这个容易做到. 　　但是第二次递归, 我们需要求出的是 　　
[A1_n(x_0^2),A1_n(x_1^2),A1_n(x_2^2),\cdots,A1_n(x_{\frac{n-1}{2}}^2)] 和 　　
[A2_n(x_0^2),A2_n(x_1^2),A2_n(x_2^2),\cdots,A2_n(x_{\frac{n-1}{2}}^2)] 　　这要求由
[\pm x_0,\pm x_1,\pm x_2,\cdots,\pm x_{\frac{n+1}{2}}] 平方之后的数也要是正负配对的, 这个就有点难做到了 　　更一般的, 如果我们要递归到最后一层, 那么就要求
[x_0^{\frac{n+1}{2}},x_1^{\frac{n+1}{2}},x_2^{\frac{n+1}{2}},\cdots,x_{\frac{n-1}{2}}^{\frac{n+1}{2}}] 都是正负配对的. 　　这个问题要怎么解决? 如果解决不了, 我们的递归就进行不下去. 　　5.复数的引入 　　不难发现, 为了解决以上的问题, 我们必须要引入复数. 　　但是这个
[\pm x_0,\pm x_1,\pm x_2,\cdots,\pm x_{\frac{n-1}{2}}] 要怎么设计才能让其每次平方都能达到正负配对的结果? 　　注意到有欧拉公式, 世界上最漂亮的公式 　　
\begin{align} e^{i\pi}+1=0 \end{align} 　　所以有 　　
\begin{align} e^{i\pi}=-1 \end{align} 　　
\begin{align} e^{2i\pi}=1 \end{align} 　　所以有 　　
\begin{align} -e^{2i\pi\frac{m}{n}}&=e^{2i\pi\frac{\frac{n}{2}+m}{n}}\\ &=e^{2i\pi\frac{m}{n}}\cdot e^{2i\pi\frac{\frac{n}{2}}{n}}\\ &=e^{2i\pi\frac{m}{n}}\cdot e^{i\pi}\\ &=-e^{2i\pi\frac{m}{n}} \end{align} 　　所以, 我们注意到对任意的
n+1=2^{k} , 如果选取 　　
\begin{align} &[x_0,x_1,x_2,\cdots,\color{red}{x_{\frac{n-1}{2}}},\color{blue}{-x_0},-x_1,-x_2,\cdots,-x_{\frac{n-1}{2}}]\\ =&\left[e^{2i\pi\frac{0}{n+1}},e^{2i\pi\frac{1}{n+1}},\cdots,\color{red}{e^{2i\pi\frac{\frac{n+1}{2}-1}{n+1}}},\color{blue}{e^{2i\pi\frac{\frac{n+1}{2}}{n+1}}},\cdots,e^{2i\pi\frac{n}{n+1}}\right] \end{align} 　　那么对这些数平方之后还是能达到正负配对的效果, 为什么? 　　我们现在只看
[x_0,x_1,x_2,\cdots,x_{\frac{n-1}{2}}] , 如果选取 　　
\begin{align} &[x_0,x_1,x_2,\cdots,x_{\frac{n-1}{2}}]\\ =&\left[e^{2i\pi\frac{0}{n+1}},e^{2i\pi\frac{1}{n+1}},e^{2i\pi\frac{2}{n+1}},\cdots,e^{2i\pi\frac{\frac{n+1}{2}}{n+1}}\right] \end{align} 　　对于任意的
\begin{align} e^{2i\pi\frac{m}{n+1}} \end{align} , 都有
\begin{align} -e^{2i\pi\frac{m}{n+1}}=e^{2i\pi\frac{\frac{n+1}{2}+m}{n+1}} \end{align} , 这个在前面已经证明. 　　而他们平方之后, 不过是由
m 变成了
2m , 不会影响正负配对的特性. 　　所以, 如果我们设
\omega=e^{2i\pi\frac{1}{n+1}} , 那么就有 　　
[x_0,x_1,x_2,\cdots,x_{{n}}]=[\omega^0,\omega^1,\cdots,\omega^n] 　　所以, 我们要求的点值向量, 就变成了求 　　
[A_n(\omega^0),A_n(\omega^1),A_n(\omega^2),\cdots,A_n(\omega^n)] , 而求这个向量的方法, 就是之前提到的分治法. 　　即 　　
\begin{align} A_n(\omega^{a})&=A1_n(\omega^{2a})+\omega ^a A2_n(\omega^{2a})\\ A_n(\omega^{a+\frac{n+1}{2}})&=A1_n(\omega^{2a})-\omega ^a A2_n(\omega^{2a})\\ \end{align} 　　不过这个
\omega 具体要怎么在计算机中表示呢? 　　实际上, 根据欧拉公式
e^{ix}=\cos x+i\sin x , 我们就有 　　
\begin{align} \omega^k&=e^{2i\pi\frac{k}{n+1}}\\ &=\cos\frac{2k\pi}{n+1}+i\sin\frac{2k\pi}{n+1} \end{align} 　　这就可以用C/C++中中定义的或者 表示了. 　　6.点值表示转回系数表示 　　虽然上面讲的分治法一般用递归写比较方便, 但是在实际工程中, 我们一般不用递归的方法. 不过我们现在假设我们已经求出了. 　　
[A_n(\omega^0),A_n(\omega^1),A_n(\omega^2),\cdots,A_n(\omega^n)] 和 　　
[B_n(\omega^0),B_n(\omega^1),B_n(\omega^2),\cdots,B_n(\omega^n)] 　　那么我们就得到了
C_n(x)的点值向量
[C_n(\omega^0),C_n(\omega^1),C_n(\omega^2),\cdots,C_n(\omega^n)] . 　　不过这种点值向量不是人眼能够看的, 我们需要将其转回系数向量. 也就是研究多项式点值表示转回系数表示. 　　同样, 我们写出
C_n(x) 的点值向量的矩阵方程形式. 　　
Y^T= \left[\begin{matrix}1&x_0&x_0^2&\cdots&x_0^n\\1&x_1&x_1^2&\cdots&x_1^n\\\cdots\\1&x_n&x_n^2&\cdots&x_n^n \end{matrix}\right]\left[\begin{matrix}c_0\\c_1\\\cdots\\c_n\end{matrix}\right] 　　其中,
[x_0,x_1,\cdots,x_{{n}}]=[\omega^0,\omega^1,\cdots,\omega^n] 　　因此 　　
Y^T\left[\begin{matrix}1&x_0&x_0^2&\cdots&x_0^n\\1&x_1&x_1^2&\cdots&x_1^n\\\cdots\\1&x_n&x_n^2&\cdots&x_n^n \end{matrix}\right]^{-1}= \left[\begin{matrix}c_0\\c_1\\\cdots\\c_n\end{matrix}\right] 　　那么这个 　　
\left[\begin{matrix}1&x_0&x_0^2&\cdots&x_0^n\\1&x_1&x_1^2&\cdots&x_1^n\\\cdots\\1&x_n&x_n^2&\cdots&x_n^n \end{matrix}\right]^{-1} 等于什么? 　　我们令其为
Q 矩阵, 则有
Q^{-1}Q=E , 而对于任意的
E_{a,a} 有,
E_{a,a}=1 , 对于任意的
a\ne b ,
E_{a,b}=0 而 　　
\begin{align} E_{a,a}&=\sum_{m=0}^{n}Q^{-1}_{a,m}Q_{m,a}\\ &=\sum_{m=0}^{n}Q^{-1}_{a,m}\,\omega^{ma} \end{align} , 　　这时候我们发现, 如果取
Q^{-1}_{a,m}=\omega^{-ma} , 那么就有
\begin{align} \sum_{m=0}^{n}Q^{-1}_{a,m}\,\omega^{ma}=n+1 \end{align} 而同时, 　　对于任意
a\ne b , 都有 　　
\begin{align} E_{a,b}&=\sum_{m=0}^{n}Q^{-1}_{a,m}Q_{b,m}\\ &=\sum_{m=0}^{n}\omega^{-ma}\,\omega^{mb}\\ &=\sum_{m=0}^{n}\omega^{mb-ma}\\ &=\sum_{m=0}^{n}(\omega^{b-a})^m\\ \end{align} 　　又因为
n 次方和和
n 次方差公式 　　
\begin{align} x^{n+1}-1=(x-1)\sum_{m=0}^{n}{x^m} \end{align} 　　对任意
a\ne b (本文仅讨论
a,b\in[0,n] 的情况), 都有
\omega^{b-a}\ne1 , 所以 　　
\begin{align} \sum_{m=0}^{n}(\omega^{b-a})^m&=\frac{(\omega^{b-a})^{n+1}-1}{\omega^{b-a}-1}\\ &=0 \end{align} 　　所以
\begin{align} Q^{-1}_{a,m}=\frac{\omega^{-ma}}{n+1} \end{align} 所刻画的矩阵是矩阵方程
Q^{-1}Q=E 的一个解, 而又因为对于可逆矩阵来说, 该矩阵方程仅有一个解 　　所以
\begin{align} Q^{-1}_{a,m}=\frac{\omega^{-ma}}{n+1} \end{align} 所刻画的矩阵是矩阵
Q 的逆矩阵. 　　而这个逆矩阵到底长什么样呢? 　　注意到
\omega^{-ma} 是
\omega^{ma} 的共轭复数. 　　所以这个逆矩阵就是 　　
\begin{align} Q^{-1}=\frac{1}{n+1}\left[\begin{matrix}\overline1&\overline{x_0}&\overline{x_0^2}&\cdots&\overline{x_0^n}\\\overline 1&\overline x_1&\overline{x_1^2}&\cdots&\overline {x_1^n}\\\cdots\\\overline 1&\overline x_n&\overline {x_n^2}&\cdots&\overline{x_n^n} \end{matrix}\right] \end{align} 　　也就是说, 　　
\begin{align} Q_{m,a}=\cos\frac{2ma\pi}{n+1}+i\sin\frac{2ma\pi}{n+1} \end{align} , 那么 　　
\begin{align} Q_{m,a}^{-1}=\frac{1}{n+1}\Big(\cos\frac{2ma\pi}{n+1}-i\sin\frac{2ma\pi}{n+1}\Big) \end{align} 　　就这么简单 　　所以, 我们在将点值表示转回系数表示只需要将 　　
\begin{align} \omega^k&=e^{2i\pi\frac{k}{n+1}}\\ &=\cos\frac{2k\pi}{n+1}+i\sin\frac{2k\pi}{n+1} \end{align} 改为 　　
\begin{align} \omega^k&=e^{-2i\pi\frac{k}{n+1}}\\ &=\cos\frac{2k\pi}{n+1}-i\sin\frac{2k\pi}{n+1} \end{align} 　　之后, 再将得到的结果除以
n+1 就是最终的结果了. 　　至此, 我们就求出了
C_n(x)=A_n(x)B_n(x) 的结果. 　　以上就是快速傅里叶变换, Fast Fourier Transform的全过程. 　　这个算法的时间复杂度是
O(n\log n) , 在长度为一百万的时候, 所需时间只相当于朴素乘法的五万分之一. 　　本文只是对快速傅里叶变换的数学原理的详细解释, 下篇文章我们讲一讲具体怎么用代码, C语言, 实现快速傅里叶. 　　不过注意我只讲迭代版本, 也就是蝶变版本的, 递归版本的不是特别实用而且速度较慢. 　　下下篇文章讲什么呢? 　　当然是讲快速傅里叶变换的并行实现啊. 　　(也许吧, 可能鸽了) 　　第二篇文章:Pandora Eartha：让我给你讲清楚 快速傅里叶变换(FFT)(二): C语言实现迭代版本(蝶变操作)+超大整数乘法 　　第三篇文章估计得等等了. 　　文章封面(AI生成): 　　絵画のような蛍ちゃん(原神) 　　原图太大了,
4096\times4096 分辨率的, 知乎不让上传.
fft算法的原理_FFT原理通俗易懂
fft算法的原理_FFT原理通俗易懂

2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/52629.html

赞 (0)
0
上一篇 2024年 9月 2日
下一篇 2024年 9月 2日

相关推荐

关注微信