习题16.5快速 Fourier变换 1.说明离散 Fourier变换X(/)=∑x(n)e2可以看成 Fourier变换 f(o)」f(x)eatr 的离散近似形式的推广。 解假设 ∫f(x)eadx∑f(n)e 取Ax使 Ax 1 记W=,则k为整数时 于是 f()=∑W"∑f(N+n)△)x, 记x(n)=∑f(kN+n)Ax)Ax,所以 X()=f(0)=∑W"x(n)=∑x(n)e 2.证明正交关系式 解显然,j=k时,∑ 下面考虑j≠k,不妨设j<k。根据当≠1是方程xN=1的一个根时, 有∑n=0,令5 则ξN=e2 于是 k-y) 0。 3.设N=四(p,q∈N),构造只需O(p+q)N)次运算的 Fourier变换习题 16.5 快速 Fourier 变换 1． 说明离散 Fourier 变换 X j x n i n j N n N ( ) = ( ) e − = − ∑ 2 0 1 π 可以看成 Fourier 变换 ∫ +∞ −∞ − f = f x dx iωx (ω) ( )e ˆ 的离散近似形式的推广。 解 假设ω > 0 2 ˆ 2 ( ) ( ) e x i f f x dx ω π ω π +∞ − −∞ = ∫ 2 ( ) 2 ( ) e n x i n f n x x ω π π +∞ ∆ − =−∞ ≈ ∑ ∆ ∆ ， 取∆x 使 1 2 x N ω π ∆ = ，记 2 e i W N π − = ，则k 为整数时，W kN +n = W n 。于是 1 0 ˆ( ) (( ) ) N n n k f ω W f kN n x − +∞ = =−∞ = + ∑ ∑ ∆ ∆x ， 记 ( ) (( ) ) k x n f kN n x +∞ =−∞ = ∑ + ∆ ∆x，所以 ˆ X ( )j f = ( jω) 1 0 ( ) N jn n W x n − = = ∑ 1 2 0 ( ) e N nj i N n x n π − − = = ∑ 。 2． 证明正交关系式 j k N nk i N n N n j i N , 2 1 0 2 e e 1 δ π π ∑ = − = − 。 解 显然， j = k 时， 1 2 2 0 1 e e N nk nk i i N N N n π π − − = ∑ =1。 下面考虑 j ≠ k ，不妨设 j < k 。根据当ξ ≠ 1是方程 的一个根时， 有 ，令 = 1 N x 0 1 0 ∑ = − = N n n ξ ( ) 2 e 1 k j i N π ξ − = ≠ ，则 2( ) e N k j π i ξ − = =1。于是 1 0 N n n ξ − = ∑ = 1 1 ( ) 2 2 2 0 0 1 1 e e e N N n j nk n k j i i i N N N N N n n π π π − − − − = = ∑ ∑ = = 0。 3． 设 N = pq（ p, q ∈N），构造只需O(( p + q)N) 次运算的 Fourier 变换 3