习题16.4Fourier变换和Fourier积分1.求下列定义在(-o,+o)的函数的Fourier变换：A 0<x<8.(1)f(x)=(2) (x)=e-al,a>0;{o，其它;Te-2x,x≥0,(3) f(x)=e-ax, α>0;(4)f(x)=0,x<0,[Acosoox, Ix,0±0是常数，8=元(5)f(x)=0.1x>0o[Aeo*dx=(1-e-o)解(1) (o)=[ f(x)e-*dx=]io(2) F(o)= ft f(x)e-odx = ft e-(ao)dx+ [e(a-i0)dx20a+io a-io"a+?(3) (o)= f(x)e-iox dx = [ e-ar-ioxdx= Je-arcoswxdxot.dt（利用例15.2.8的结果）cOsVa"Va)ENaVa(4) F(0)= J f(x)e-ior dx= J" e-(2+o)dx = 2+i0(5) F(0)=f f(x)e*dx=f, Acos 0xe-o* dxAcosxcoswxdx（虚部为奇函数，积分为0）,[cos(o -0)x + cos(0 +0)x]dxsin(0-0.)8, sin(0+0)8(0-0)(0+0)2.求f(x)=e-a（xe[0,+)，α>0）的正弦变换和余弦变换。解正弦变换：F(o)= J, (x)sin oxdx = f, e" sin oxdx =α2+0?余弦变换：
习题 16.4 Fourier 变换和 Fourier 积分 1．求下列定义在(−∞,+∞) 的函数的 Fourier 变换： ⑴ ⎩ ⎨ ⎧ < < = 0, ; , 0 , ( ) 其它 A x δ f x ⑵ f x a x ( ) e | | = − ， a > 0 ; ⑶ f x a x ( ) = e− 2 ， a > 0 ; ⑷ ⎩ ⎨ ⎧ < ≥ = − 0, 0; e , 0, ( ) 2 x x f x x ⑸ ⎩ ⎨ ⎧ > ≤ = 0, | | ; cos , | | , ( ) 0 δ ω δ x A x x f x ω0 ≠ 0是常数， ω0 π δ = 。 解 （1） ( ) ( ) i x f f x e dx ω ω +∞ − −∞ = ∫ 0 i x Ae dx δ − ω = ∫ = (1 ) ωδ ω i e i A − − 。 （2） ( ) ( ) i x f f x e dx ω ω +∞ − −∞ = ∫ 0 ( ) ( ) 0 a i x a i x e dx e ω ω +∞ − + − −∞ = + ∫ ∫ dx 1 1 a iω a iω = + + − = 2 2 2 a +ω a 。 （3） ( ) ( ) i x f f x e dx ω ω +∞ − −∞ = ∫ 2 ax i x e dx ω +∞ − − −∞ = = ∫ 2 cos ax e x ω +∞ − ∫−∞ dx 2 0 2 cos t t t e d a a +∞ − ω = ∫ (利用例 15.2.8 的结果) 2 2 a e a ω π ⎛ ⎞ −⎜ ⎟ ⎝ ⎠ = = a e a 4 2 ω π − 。 （4） ( ) ( ) i x f f x e dx ω ω +∞ − −∞ = ∫ (2 ) 0 i x e dx ω +∞ − + = = ∫ 2 + iω 1 。 （5） ( ) ( ) i x f f x e dx ω ω +∞ − −∞ = ∫ = 0 cos i x A xe dx δ ω δ ω − ∫− 0 Acos x cos x δ δ ω ω − = ∫ dx（虚部为奇函数，积分为 0） 0 0 [cos( ) cos( ) ] 2 A x x dx δ δ ω ω ω ω − = − + + ∫ ＝ 0 0 0 0 sin( ) sin( ) ( ) ( ) A ω ω δ ω ω δ ω ω ω ω ⎡ − + ⎤ ⎢ + ⎥ ⎣ − + ⎦ 。 2．求 f x( ) = e− ax（ x ∈[0,+∞)，a > 0）的正弦变换和余弦变换。 解 正弦变换： 0 f ( ) ω ω f x( )sin xdx +∞ = ∫ 0 sin ax e xdx 2 2 ω ω a + ω , +∞ − = = ∫ 余弦变换： 1
aF(o)= f f(x)cos wxdx = f e" cos oxdx =α?+0?元Je, x≥0,Jsinx,0≤x≤3. 设()=[4<0 /(a)=求f *f,(x)。2[o,[0,其它,解记F(x)=f*f;(x)=f,*f(x)=[,sin(1)f(x-1)dt,考虑te[0,)当x≤0时，f(x-t)=0，所以F(x)=0;当x>时，(x-t)=e-(-)，所以2Tre sin()d =le(+)F(x)=e-x2[e-(x-), x>1,当0<时，J(x-1)=所以2[o,x≤tF(x) = e-e' sin(t)dt =-(sinx-cosx+e-*)。2于是x≤0,0,(sinx-cosx+e),0<x≤fi *f2(x) =2元元>le-*(1+e?),222
0 f ( ) ω ω f x( ) cos xdx +∞ = ∫ 0 cos ax e xdx 2 2 a +ω a ω 。 +∞ − = = ∫ 3．设 ⎩ ⎨ ⎧ < ≥ = − 0, 0, e , 0, ( ) 1 x x f x x ⎪⎩ ⎪ ⎨ ⎧ ≤ ≤ = 0, , , 2 sin , 0 ( ) 2 其它 π x x f x 求 ( ) 1 2 f ∗ f x 。 解 记F x( ) = 2 1 2 2 1 1 0 f f x( ) f f ( ) x sin(t) f (x t)dt π ∗ = ∗ = − ∫ ，考虑 [0, ] 2 t π ∈ ， 当 x ≤ 0时， 1f x( ) − t = 0，所以F x( ) = 0； 当 2 x π > 时， f x 1( ) − = t e− − ( x t) ，所以 2 2 0 1 ( ) sin( ) (1 ) 2 x t x F x e e t dt e e π π − − = = ∫ + ； 当0 2 x π < ≤ 时， ( ) 1 , ( ) 0, x t e x f x t t x t − − ⎧ > − = ⎨ ⎩ ≤ ，所以 0 1 ( ) sin( ) (sin cos ) 2 x x t x F x e e t dt x x e − − = = − ∫ + 。 于是 ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ + > − + < ≤ ≤ ∗ = − − . 2 (1 ), 2 1 , 2 (sin cos ), 0 2 1 0, 0, ( ) 2 1 2 π π π e e x x x e x x f f x x x 2
习题16.5快速Fourier变换N-I1．说明离散Fourier变换X(i)=2x(n)e/%可以看成Fourier 变换f(o)-f f(x)e-o dx的离散近似形式的推广。解假设の>0-i(o)=[t f(x)e_ dx ~Sf(nAr)eAr7==002元i取A使，则k为整数时，w+n=W"。于是记W=eNN2元(o)=w"f(kN +n)Ar)Ax,n=0k=of(kN +n)Ar)Ax，所以记x(n)=ka-Ne-2m%Zwx(n) =)X()= f(jo) =n=0n=02.证明正交关系式2/hk1-2元%Ze=oikNO-2.nk2元/nkI解显然，j=k时，Ne=1YZ0下面考虑j+k，不妨设j<k。根据当+1是方程x=1的一个根时，2元;(k-)N-1令=e则=N=e2(k-)x=1。于是有"=0，去1，#m=0*-NNe=09e"ZNLn=03.设N=pq（p,qeN），构造只需o(p+q)N)次运算的Fourier变换3
习题 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
算法。2元1解令W=e，则k为整数时，wk+"=W"。假设j= jq+Jo, Jj, =0,1,.,p-1, J=0,1,.,q-1,n=np+no,n, =0,1,..-,q-1, no=0,1,",p-1。N!Zx(n)wnEx(n)e-2%X(i)=Nn=0h=0nZx(np+ng)wj(mp+n)20=0m=0FwmgEx(np+n)wnip。m=0no=0固定」，计算艺x(mp+n)wmp需要q-1次乘法（n=0不需要做乘n=0x(mpP+n)Wp是相同的，无需重复计算，所法），对于相同的j。，420有此类和式共需q(q-1)次乘法。对n.求和需要(p-1)N次乘法，所以，总共需要q(q-1)+(p-1)N=O(p+q)N)次乘法。4．对N=23，具体写出以2为底的FFT的计算流程。2元ini解记W=e=e-，则w4=-1,W=l。可得计算公式X()-Zx(n)W", j=,1,..,7.n=0=[x(0) +(-1) x(4)) + W' [x(1) +(-1) x(5)]+W2j ([x(2)+(-1) x(6))+ W'[x(3)+ (-1) x(7)]) 。计算流程第一步：x(i) = x(i)+ x(i+ 4),x(i+ 4)=W'[x(i)-x(i+ 4)],i=0,1,2,34
算法。 解 令 2 e i W N π − = ，则k 为整数时，W kN +n = W n 。假设 1 0 1 0 j j = +q j , 0 j = ,1," " , p −1, j = 0,1, , q −1, 1 0 1 0 n n = + p n , n = 0,1," " , q −1, n = 0,1, , p −1。 X j x n i n j N n N ( ) = ( ) e − = − ∑ 2 0 1 π 1 0 ( ) N jn n x n W − = = ∑ 1 0 0 1 1 1 ( ) 1 0 0 0 ( ) p q j n p n n n x n p n W − − + = = = + ∑ ∑ 0 1 0 1 1 1 1 0 0 0 ( ) p q jn n j p n n W x n p n W − − = = = + ∑ ∑ 0 。 固定 j ，计算 1 0 需要 1 1 1 0 0 ( ) q n j p n x n p n W − = ∑ + q −1次乘法（ 1 n = 0不需要做乘 法），对于相同的 ， 是相同的，无需重复计算，所 有此类和式共需 次乘法。对 求和需要 0 j 1 0 1 1 1 0 0 ( ) q n j p n x n p n W − = ∑ + q q( −1) 0 n ( p −1)N 次乘法，所以， 总共需要q q( 1− +) ( p −1)N = O(( p + q)N) 次乘法。 4． 对 N = 23，具体写出以 2 为底的 FFT 的计算流程。 解 记 2 8 4 e e i i W π π − − = = ，则 4 8 W = −1,W =1。可得计算公式 7 0 ( ) ( ) , 0,1, ,7. jn n X j x n W j = = = ∑ " [ (0) ( 1) (4)] [ (1) ( 1) (5)] j j j = + x x − +W x + − x 2 {[ (2) ( 1) (6)] [ (3) ( 1) (7)]} j j j j + + W x − x +W x + − x 。 . 计算流程 第一步： 1 1 ( ) ( ) ( 4), ( 4) [ ( ) ( 4)], 0,1, 2,3 i x i x i x i x i W x i x i i = + + + = − + = 4
第二步：x(i) = x(i)+ x,(i+ 2),x(i+2)= W2[x,(i)-x(i+2)],i= 0,1,4,5第三步：X(i)= x2(i)+ x2(i+1),X(i+4)= x(i)-x(i+1),i=0,2,X(i)= x (i+3)+ x(i+4),X(i+ 4) = x (i+3) -x,(i+ 4),i = 1,35
第二步： 2 1 1 2 2 1 1 ( ) ( ) ( 2), ( 2) [ ( ) ( 2)], 0,1, 4,5 i x i x i x i x i W x i x i i . = + + + = − + = 第三步： 2 2 2 2 2 2 2 2 ( ) ( ) ( 1), ( 4) ( ) ( 1), 0, 2, ( ) ( 3) ( 4), ( 4) ( 3) ( 4), 1,3 X i x i x i X i x i x i i X i x i x i X i x i x i i . = + + + = − + = = + + + + = + − + = 5