傅里叶计算.ppt

1、1,12 . 3 傅立叶(Fourier)变换方法,（一）由连续傅立叶变换到离散傅立叶变换,实函数,其连续傅立叶变换 为 的谱，它是定义在 的复连续函数。反之，,若 以L为周期，则仅当 时 才非0：,这也可视为区间0, L上的变换，即在有限区间上定义的f (x) 具有分离谱,反变换为,2,反之， 中等间隔 离散函数 的傅立叶变换为,可见： ， n为任意整数,离散函数 的谱是周期谱,即 为 k 空间中以 为周期的函数。,其逆变换为,3,在 k 空间中以 为间隔可划分无限多个周期带。我们称不同周期带中的模 互为重影 (aliasing)。,模和 模互为重影，两个模在离散点上具有相同行为，无法由离散

2、采样加以区分,重影的产生源于离散化过程中丢失了信息，虚线所含信息超出了能提供的信息，应舍弃，通常取,称为本带，之外所有周期带称为短波带。,截止波长为,4,注意：无限区间的离散函数的谱为本带中的连续谱。,若 以N为周期，即 ，则谱在本带中为离散值。,其中,相应地，,即为定义在有限空间（或周期）离散函数 的傅立叶变换,由于 ，可见 既具有离散性，也具有周期性。其离散性是由 的周期性决定，其周期性是由 的离散性决定。,5,傅立叶变换：,可推广到多维（如2D）,逆变换：,求和上下限的变化利用了其周期性,对一维，其计算量约N2个复运算，采用FFT， 则降为Nlog2N。故N=2m。,6,（二）傅立叶方法

3、,若系数是均匀的，则可对上式快速直接求解,均匀问题：所有系数与 j, l 无关 半均匀问题：所有系数仅与 j 或仅与 l 有关,o,S,W,N,E,7,如矩形解域、均匀网格下常系数线性椭圆型方程,1 均匀问题,例： 若采用正方形网格,则,边界条件,(1)固定边界：,(2)自由边界：,(3)周期边界：,或,分为单周期和双周期边界条件,8,当 和 不为0，则称为非齐次边界条件，否则为齐次边界条件。,非齐次问题很容易化为齐次边界条件，方法如下：,任取一离散函数， 它在边界上的取值为 令 ，则 满足齐次方程及如下差分方程,其中,特别地，若 很小，可简单地取 的内点值为0,非边界邻点处 ，边界邻点处,9

4、,在其两边分别乘 ，再对下标 j (1 M)及l (1 N)求和,其中,1.1 双周期边界条件,其反变换为,10,1 通过快速傅立叶变换由 求 利用 求 通过快速傅立叶反变换由 求,计算量为,计算步骤,当,时，,11,周期边界条件,以1D齐次边界条件为例,第一类边界条件,1.2 第一类边界条件,源的反对称延拓,12,周期边界条件,第二类边界条件,1.2 第二类边界条件,源的对称延拓,13,2 半均匀问题,如x方向非均匀网格,对每一个分量 n ，上式给出一个沿 x 方向的三对角方程组， 采用追赶法即可将 解出，再通过 l 方向的傅立叶反变换将 求出。,由于上式各系数与 l 无关，可在 y 方向进

5、行傅立叶变换,此法也可用于均匀问题，特别是对单周期边界条件，可在具有周期边条的方向进行傅立叶变换，而另一方向采用追赶法。,14,12 . 4 循环约化方法的思想,对2D可分离变量椭圆型方程或非均匀网格下的常系数方程,它不可使用傅立叶方法，但可使用循环约化法，要求格点数,15,其中,因此，我们将所有格点写成块三角形式,循环约化方法的基本思想,（以一元三对角矩阵为例）,16,连续写出三个相邻的方程,由第一、三式解出 后代入第二式,其中,这样做后，方程数大致减至一半,17,对上式继续约化，至第 r 步 （rk）,当进行至第k-1步，则仅剩一个未知数, i.e., 解出 后上式逐步回代。,其中,可由递推公式得出。,18,例子,对一非均匀N元三对角代数方程组，此法约需6N次除，8N次乘和6N次加，为通常追赶法的2倍，但对均匀情况，各系数与脚标无关，却比追赶法更有效，且节约内存。,1 2 3 4 5 6 7,12 123 234 345 456 567 67,24 246 46,4,取n=3，则对应7个点,Swarztranfer, P. N. 1974, SIAM J. on N