习题164 Fourier变换和 Fourier积分 1.求下列定义在(-∞,+∞)的函数的 Fourier变换 A,0<x<δ, (1)f(x) 0,其 (2)f(x)=e a>0 (4)f(x)= x≥0, x=e a>0 0,x<0, (5)f(x)= Acos ox,xsS, 0,/珍d≠0是常数,6=x 解(1)1()=[(x)=-=4mb=40-c (2)f(o)=/(r)e" ax=o e-laiodxL"dx (3)J(o)=/()e"dx=[e a -iea dr=e"a cosoxdx (利用例15.2.8的结果) (4)f(o)=f(x)e-r= 2+ (5)f(o)=f(r)e-ie x=.A dx Acos @xcos oxdx(虚部为奇函数,积分为0) A [cos(@o-o)x+cos(@o+o)x]d n(@-@o)8 sin(@+@o)8 (O+@o 2.求f(x)=ea(x∈[0+∞),a>0)的正弦变换和余弦变换。 解正弦变换: f(o)= f(x)sin odx= e- sin oxdx= 余弦变换
习题 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
f(o)= f()cosoxdx= e cos oxdx +o 3.设f( rQJ(y=sinx,0≤rs3 xx≥0 求几*f2(x) 0,其它, 解记F()=f*(x)=*()1smO)0(x-0m,考虑∈D.2 当x≤0时,f(x-D=0,所以F(x)=0; 当x>z时,f(x-1)=,所以 F(x)=eesin(t)dt=e"(1+e2); 当0<x≤x时,f(x-0)= 所以 0, t F(x)= e- esin(Mhs、 sIn x-cosx+e 于是 ≤0 f *f2(x)=-(sinx-cosx +e),0<xs 2
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变换 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
算法 解令W=eN,则k为整数时,W=W。假设 j=jq+j,方=0 l,j=0,1,…q-1, n=nP+n,n1=0,1,…,q-1,n=0,1,…,P-1。 X()=2xex以=∑x(mWm ∑xp+n)W W∑x(nP+n形 nJop 固定,计算xnp+mW需要q-1次乘法(n=0不需要做乘 法,对于相同的,∑x(mP+n1M是相同的,无需重复计算,所 有此类和式共需q(q-1)次乘法。对m求和需要(p-1)N次乘法,所以, 总共需要q(q-1)+(p-1)N=O(p+q)N)次乘法。 4.对N=23,具体写出以2为底的FFT的计算流程。 解记W=e8=e4,则W4=-1,W8=1。可得计算公式 X()=∑x(mWm,j=0,1…7 =[x(0)+(-1)x(4)+W[x(1)+(-1)x(5) +2/{[x(2)+(-1)yx(6)+W[x(3)+(-1)yx(7)]}。 计算流程 第一步: x1()=x(1)+x(+4) x1(+4)=W[x()-x(+4)]i=0,1,2,3
算法。 解 令 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
第二步: (1)=x()+x1(i+2) x2(i+2)=W2{x(i)-x(i+2)]i=0,1,45 第三步 X()=x2()+x2(i+1) X(+4)=x2()-x2(i+1,=0,2 X()=x2(+3)+x2(+4) X(+4)=x2(+3)-x2(+4),i=1,3
第二步： 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