umm~傅立葉轉換＋小小Latex

這是為了專題所需，是很偏的東西

我覺得資訊的部分，還蠻簡單的，但在物理的部份就比較困難

但他實在是從物理開始的，所以從物理講起還是比較合理。

喔對了，在看下去前，希望先對複數平面，和些許微積分有初步體會

而你會在維基看到什麼『DFT』，『FFT』，『Fourier Series』，概念差不多，只是用處不同

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

首先！你要知道一個很重要的等號（原因的話，基本上是因為他們在微分的性質上是相同的且在相乘時也有相同性質，亦可以說他們其實是一體兩面的）

再來！你要對『正交』，也就是運用在非幾何地方的垂直，有一些了解：（我個人覺得這個東西很像向量的內積<只有兩個相同時才會有值，若兩個向量垂直則會得到零>所以故意用了dot，但應該是都可以的）

至於為什麼的話其實很簡單，看一下前面說的，轉換成圖形，一目了然

傅立葉級數（Fourier Series）：

你也可以叫他傅立葉展開，比較貼切他的本意。傅立葉在很久以前發現一個週期函數（舉個例就是9e^i2*(pi)）可以拆成唯一的sin, cos線性組合，寫成式子如下。這個東西很明顯就是已經知道 f 函數的週期才下去拆的，而在下式，我們是假設 f 函數為以2pi為週期的函數。

其實從第一式可以看出她的週期是2pi的蹤跡，第一式因為他是sigma，也就是說k為整數（就是角速度），你便可從中體會到 f 函數是由一群週期為2pi的倍數的基波（sin或cos函數）所組成（你可能會有疑問，為什麼是2pi的倍數勒？看本篇最上面的等式你就會了解了）

至於第二式，則有點套套邏輯的感覺（但他並沒有），他在裡頭又套回了第一式（想像他是由多個不同頻率的波所組成），並且用了剛剛所謂的正交的方式，將bk取了出來～實在是非常有趣的一件事情。

傅立葉轉換（Fourier Transform）：

最主要的用處，是將一個時間（t）對振幅（A）的圖（簡稱A-t圖）轉換成一個頻率（f）對振幅的圖（簡稱A-f圖）。說的更清楚一些，就是將一個看似週期函數的，做某種奇特的分解，將他變成無限多個基波的組合（有種泰勒的fu~）。（我們平常看的應該是第二式吧）

這個新的等式，看起來很不一樣，但其實改變的只有兩個地方：

1. 我剛剛有說在前一節用的是以2pi為週期，但這裡所要轉換的是不被認為是週期函數的函數（所以我才說很像泰勒，舉個例的話就像常態分布函數），因為你不知道他的週期，他有可能由很大週期的sinuoid所組成，所以必須要包含到所有的w（這裡用的就是平常物理上在用的角速度，他代表的也確實是角速度）

2. 就是第二式從-2pi~2pi變成-inf~inf，原因的話跟剛剛一樣，你想要包含這個某某函數的一切，但你不知道他的範圍，故必須要全部考慮進去才行。

剩下的，像是正交什麼的概念，皆由傅立葉級數一併帶過來。

離散傅立葉變換（Discrete Fourier Transform）:

這部份的公式其實就像是直接從前面的FT所轉過來，所以就不多討論了。從這裡我們要從另一個方向來看這個問題，從資訊的角度來看。

假設你現在碰到的問題是這樣的：

給你兩個多項式A(x)和B(x)，求C(x) = A(x)*B(x)。

最原始的方法就是將他們依照原本的公式，以O(n^2)的時間得到答案，但這實在是太慢了，我們不想要以這麼弱的時間求得，這裡我要給你們一個method使這個問題可以在O(nlgn)內求出來。

首先，我們要先對多項式有初步了解。

 n 項多項式A(x)的表示法：

1. 係數式：就是平常寫的a0+a1*x+a2*x^2...an-1*x^n-1
（乘法所需時間：O(n^2)）

2. 點值式：用n個(x,y)所表示，且y = A(x)且每個x皆相異
（乘法所需時間：O(n)）

而你可以證明出一個有n個點的點值式寫成n項係數式（說的精準一點應該是一個最多n項，因為有可能高次項的係數為零），只會有一種寫法。


（Hint：其實你就是要解一個n元一次式，而由克拉馬公式可以知道，要有唯一解的充要條件便是delta不等於零，接著，你可以用數學歸納法證明出delta = product of( xk-xj ) for{ 0<=j<k<=n-1 }，既然n個x皆不相同，則delta != 0，所以只有唯一解）


這時候，相信有認真看的人，腦中都會浮現一個想法，如果能很快的把係數式轉乘點值式，再以O(n)做乘法，最後再很快的轉回係數式，不就得到你想要的答案了嘛？苦苦思索，發現以平常的方法想要轉很快，還是得花上O(n^2)的時間，這不就跟原本一樣嘛？還要寫更長，所以在這裡我要給出一個演算法了！（是高斯發明的）


只要你選了好的x點，便可以在O(nlgn)的時間內，完成從係數式轉點值式的夢想。


在接下來的部分我們都把n當成是2^k，所以每次切半的n都會是偶數，至於在真實情況中，我們可以把n補乘2^k，最多變兩倍，並不會改變時間複雜度，就讓我們一起探究吧！


如果你有n項，那我們所選出的x值，便是使得 x^n = 1 的共n個解（我們分別叫他們w0~wn-1）而這裡用到的概念只有一個：

（n項）

（n/2項）

（n/2項）

這時，心機重的你可能已經發現了，如果我們定義了一個method叫做求A(w0~wn-1)（且w^n = 1），那你把他遞迴求A[0]和A[1]，他在method中的 w' 剛好會是原本的 w^2 ，跟我們想要的一樣，所以我們便可以D&C的作法求出答案（細節的話，就自己想一下囉～）

相信平常愛寫程式的人，一看就知道這就是O(nlgn)了～所以我們的夢想實現了。不知道你們有沒有往上拉，我們剛剛所使用的公式，就是DFT的轉換公式呢！至於逆運算（也就是點值式轉係數式）則可以用原本正交的概念，湊出一個逆公式（其實不過就是把integrate轉乘summation），相信你湊出的逆公式就是DFT的逆轉換公式哩。（喔～對了，剛剛講的演算法就是所謂的快速傅立葉轉換，FFT，也是平常用在電路，訊號的一個快速演算法，同時也是使DFT在生活中廣受運用的一大原因）

其實多項式的乘法就是圓周卷積，而將其做傅立葉轉換後，就會變成直接乘法，是我們把傅立葉運用到資訊上所得到的結果，但你也可以把傅立葉轉換想成就是係數式轉點值式，全然看你想從哪個層面去認識他罷了。

對了，這裡面的數學式都是我用Latex打的，所以偷偷講一下他：

包住一群東西：打 {}
一群字：打 \mbox(...)
特殊字：打 \XXXX
上標：打 ^
下標：打 _
討論：打 \left\{ \begin{array}{rcl}...&...&...\\...&...&... \end{array} \right.
（rcl代表要幾塊東西，也可以打rc或rl...，而&就是分塊用的，而如果你要換行，則是打\\）
矩陣：打 \left( \begin{array}{rcl} ...&...&... \end{array} \right)
積分：打 \int_{-\infty}^{\infty}
（從負無限大積到無限大）

各種字元：CLICK HERE