《数值分析》中有这么一节内容，简单了解一下基本原理，会用matlab调用fft()，多数同学也能学会。但如何学好学清楚这节内容呢，我看如下几条很关键。
(1、要认识到算法的重要性，应用的广泛性，这个不用多讲，学的时候一定要认识到学好它的必要性，不然学的时候模糊，将来用的时候就不顺手。
(2、得亲自找几个数手工算一算，亲自编写一下算法，这是最好的学习方法，也是验证是否真正掌握算法、编写的算法是否有效的方法。
引用一句话­——“人们常常说，除非一个人能将某事教给其他人，他才算是真正地了解了这件事。实际上，直到一个人可以将某事教授给计算机，他才算真正地了解了这件事。---Donald Knuth 1974”；所以，照着算法自己编一下程序，是最好的学习方法。
(3、把学习这个算法当作一件有趣好玩的事来做。曾看过一段国外视频公开课，那个老外说：“它真的如此美妙，所以我说这好比一个人生命中，并不一定要有傅里叶算法，但我非常欣赏它，以及它背后的所有思想。”
以下我摘录整理一下我的讲稿和程序，希望对初学者有所借鉴。
====================================================
1. 首先要理解傅立叶级数、傅立叶变换的数学表达式。多看相关数学书，虽然不同的书不同作者可能用不同的符号和形式表示，初学时容易引起混淆，但多看、多做比较,可以更清楚地掌握数学语言所表达的意义。（多到图书馆翻翻书）

2. 对傅立叶变换的应用要搞清楚，学任何算法，知道问题的本质，就算解决了一半。傅立叶变换在信号处理中实现时间域<=>频率域 的转换，是实现滤波的基础算法；在函数逼近中，可把函数展开成傅里叶级数，实现用简单的三角函数替代复杂或难表示的函数，也是进行近似计算的基础算法。傅立叶变换的应用很广泛，网上也有很多直观有趣的图示(如下面两张图)。

3. 在此阐述一下，函数f(x)的傅立叶级数系数的表示和计算。
  我看可以从三个方面来理解，这样便于记忆。（当然先要知道正交函数的妙处，正交函数内积为0可简化很多事。）
  (1) 高数教材中一般都先入为主地告诉你，函数可展成三角级数，系数an怎么定呢？用cosnx乘两端，再从-π到π逐项积分，根据三角函数系的正交性，其余各项为0,得系数an。单从这外角度来看，多数同学虽然可理解，但总感觉太“数学”了，学了《数值分析》还可从以下函数逼近角度理解。
  (2) 最佳平方逼近
       用正交函数族作最佳平方逼近：求系数a组成的多元函数极值，得法方程，因所选的基函数为正交函数，所以解可直接写为:
       ak=( f(x), φk(x) ) / ( φk(x), φk(x) ), k=0,1…n.
根据内积的定义直接写了傅立叶系数的表达式。这样更好地理解傅立叶级数。
  (3) 函数向量投影到基向量
       有时从几何的角度来理解这一问题更直观。把函数作为一个向量，投影到基函数(基向量)上，傅立叶系数就是在各基函数向量上的长度坐标(射影)，也就是坐标值。形式如：prjba=|a|cos∠(a,b)=a.b/|b|。函数向量f(x),投射到函数向量cos(nx)上,an=(f(x),cos(nx))/(cos(nx),cos(nx)),够直观吧。(?

4. 离散傅立叶变换(DFT)
  学习快速傅立叶变换，当然先要明白普通的离散傅立叶变换程序的编写。
  (1) 复数域表示
复数的有限离散形式

  (2) C语言程序
先定义数据结构
typedef struct{
  double R;
  double I;
}COMPLEX;
COMPLEX add(COMPLEX a,COMPLEX b)
{    COMPLEX c;
    c.R=a.R+b.R;     c.I=a.I+b.I;  return c;
}
COMPLEX sub(COMPLEX a,COMPLEX b)
{    COMPLEX c;
    c.R=a.R-b.R;     c.I=a.I-b.I;  return c;
}
COMPLEX mul(COMPLEX a,COMPLEX b)
{    COMPLEX c;
    c.R=a.R*b.R-a.I*b.I;     c.I=a.R*b.I+b.R*a.I;
 return c;
}
// 定义变量及数组,分配内存,参数传递见下文程序

(文件太大，转下一篇)