傅里葉計(jì)算.ppt

1、1,12 . 3 傅立葉(Fourier)變換方法,（一）由連續(xù)傅立葉變換到離散傅立葉變換,實(shí)函數(shù),其連續(xù)傅立葉變換 為 的譜，它是定義在 的復(fù)連續(xù)函數(shù)。反之，,若 以L為周期，則僅當(dāng) 時(shí) 才非0：,這也可視為區(qū)間0, L上的變換，即在有限區(qū)間上定義的f (x) 具有分離譜,反變換為,2,反之， 中等間隔 離散函數(shù) 的傅立葉變換為,可見(jiàn)： ， n為任意整數(shù),離散函數(shù) 的譜是周期譜,即 為 k 空間中以 為周期的函數(shù)。,其逆變換為,3,在 k 空間中以 為間隔可劃分無(wú)限多個(gè)周期帶。我們稱不同周期帶中的模 互為重影 (aliasing)。,模和 ?；橹赜?，兩個(gè)模在離散點(diǎn)上具有相同行為，無(wú)法由離散

2、采樣加以區(qū)分,重影的產(chǎn)生源于離散化過(guò)程中丟失了信息，虛線所含信息超出了能提供的信息，應(yīng)舍棄，通常取,稱為本帶，之外所有周期帶稱為短波帶。,截止波長(zhǎng)為,4,注意：無(wú)限區(qū)間的離散函數(shù)的譜為本帶中的連續(xù)譜。,若 以N為周期，即 ，則譜在本帶中為離散值。,其中,相應(yīng)地，,即為定義在有限空間（或周期）離散函數(shù) 的傅立葉變換,由于 ，可見(jiàn) 既具有離散性，也具有周期性。其離散性是由 的周期性決定，其周期性是由 的離散性決定。,5,傅立葉變換：,可推廣到多維（如2D）,逆變換：,求和上下限的變化利用了其周期性,對(duì)一維，其計(jì)算量約N2個(gè)復(fù)運(yùn)算，采用FFT， 則降為Nlog2N。故N=2m。,6,（二）傅立葉方法

3、,若系數(shù)是均勻的，則可對(duì)上式快速直接求解,均勻問(wèn)題：所有系數(shù)與 j, l 無(wú)關(guān) 半均勻問(wèn)題：所有系數(shù)僅與 j 或僅與 l 有關(guān),o,S,W,N,E,7,如矩形解域、均勻網(wǎng)格下常系數(shù)線性橢圓型方程,1 均勻問(wèn)題,例： 若采用正方形網(wǎng)格,則,邊界條件,(1)固定邊界：,(2)自由邊界：,(3)周期邊界：,或,分為單周期和雙周期邊界條件,8,當(dāng) 和 不為0，則稱為非齊次邊界條件，否則為齊次邊界條件。,非齊次問(wèn)題很容易化為齊次邊界條件，方法如下：,任取一離散函數(shù)， 它在邊界上的取值為 令 ，則 滿足齊次方程及如下差分方程,其中,特別地，若 很小，可簡(jiǎn)單地取 的內(nèi)點(diǎn)值為0,非邊界鄰點(diǎn)處 ，邊界鄰點(diǎn)處,9

4、,在其兩邊分別乘 ，再對(duì)下標(biāo) j (1 M)及l(fā) (1 N)求和,其中,1.1 雙周期邊界條件,其反變換為,10,1 通過(guò)快速傅立葉變換由 求 利用 求 通過(guò)快速傅立葉反變換由 求,計(jì)算量為,計(jì)算步驟,當(dāng),時(shí)，,11,周期邊界條件,以1D齊次邊界條件為例,第一類邊界條件,1.2 第一類邊界條件,源的反對(duì)稱延拓,12,周期邊界條件,第二類邊界條件,1.2 第二類邊界條件,源的對(duì)稱延拓,13,2 半均勻問(wèn)題,如x方向非均勻網(wǎng)格,對(duì)每一個(gè)分量 n ，上式給出一個(gè)沿 x 方向的三對(duì)角方程組， 采用追趕法即可將 解出，再通過(guò) l 方向的傅立葉反變換將 求出。,由于上式各系數(shù)與 l 無(wú)關(guān)，可在 y 方向進(jìn)

5、行傅立葉變換,此法也可用于均勻問(wèn)題，特別是對(duì)單周期邊界條件，可在具有周期邊條的方向進(jìn)行傅立葉變換，而另一方向采用追趕法。,14,12 . 4 循環(huán)約化方法的思想,對(duì)2D可分離變量橢圓型方程或非均勻網(wǎng)格下的常系數(shù)方程,它不可使用傅立葉方法，但可使用循環(huán)約化法，要求格點(diǎn)數(shù),15,其中,因此，我們將所有格點(diǎn)寫(xiě)成塊三角形式,循環(huán)約化方法的基本思想,（以一元三對(duì)角矩陣為例）,16,連續(xù)寫(xiě)出三個(gè)相鄰的方程,由第一、三式解出 后代入第二式,其中,這樣做后，方程數(shù)大致減至一半,17,對(duì)上式繼續(xù)約化，至第 r 步 （rk）,當(dāng)進(jìn)行至第k-1步，則僅剩一個(gè)未知數(shù), i.e., 解出 后上式逐步回代。,其中,可由遞推公式得出。,18,例子,對(duì)一非均勻N元三對(duì)角代數(shù)方程組，此法約需6N次除，8N次乘和6N次加，為通常追趕法的2倍，但對(duì)均勻情況，各系數(shù)與腳標(biāo)無(wú)關(guān)，卻比追趕法更有效，且節(jié)約內(nèi)存。,1 2 3 4 5 6 7,12 123 234 345 456 567 67,24 246 46,4,取n=3，則對(duì)應(yīng)7個(gè)點(diǎn),Swarztranfer, P. N. 1974, SIAM J. on N