数值分析与4-1-0 .pptVIP

* －DFT －逆DFT (N次乘法＋N次加法)N=NN次操作 §1.DFT §2.FFT 小结 * 本章上机练习 试分别对N=64和N=128两种情形 （1）计算 的FFT （2）计算 的FFT逆变换 并与 的N个抽样值相比较。 (3) 比较并讨论N=64和N=128两种情形下的结果 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 第四章 傅里叶变换 计算物理 Fourier Transform * 法国数学家及物理学家Fourier。 主要贡献是在研究热的传播時創立了一套数学理论。1807年向巴黎科学院呈交《热的传播》论文，推导出著名的热传导方程 ，並在求解該方程時發現其解函数可以由三角函数构成的級数形式表示，從而提出任一函数都可以展成三角函数的无穷級数。 　 问题的提出： “ 对自然界的深刻研究是数学最富饶的源泉。” * 恩格斯(Engels) 把傅里叶的数学成就与他所推崇的哲学家黑格尔(Hegel) 的辩证法相提并论. 恩格斯写道：傅里叶是一首数学的诗，黑格尔是一首辩证法的诗. 1822 年在代表作《热的分析理论》中解决了热在非均匀加热的 固体中分布传播问题，成为分析学在物理中应用的最早例证之一，对19 世紀数学和理论物理学的发展产生深远影响。傅里叶級数（即三角級数）、傅里叶分析等理论均由此创立。 问题的提出： * 对于一个物理现象和客观实体的描述，可以从不同角度进行。以往人们常常习惯于在时间域或空间域中作分析，固然可以得出有用的结论，而傅氏变换用到物理问题中来，则提供了从另一角度观察，描述问题的方法，有时更能揭示问题的实质，因而具有特别的价值。因此，在许多科研领域，如线性系统、信息处理、量子物理、固体物流、表面物理或实验数据处理中，傅理叶变换往往是一个重要分析工具。 问题的提出： 近年来，信息光学已成为物理光学中越来越受人们重视的研究课题。信息光学与信息理论之间有着惊人的相似，同样可用傅氏变换进行频谱分析。 * 问题的提出： 傅氏变换最先曾在通讯系统中普遍使用。无线电通讯中所研究的无线电信号是一个带有信息的时间序列，通过傅氏变换，可以把这种信号大小按时间分布的波形 转换 成按不同的谐波频率的分布，从而获得其谐波特性。 在物理实验的数据处理中傅氏变换更是经常应用的数据分析技术。 * 总之傅理叶理论不仅是现代分析中最绝妙的理论之一，而且广泛应用于现代物理中每一个深奥问题。把一个时域的问题通过傅氏变换转换为频域的问题来研究，往往会使问题大为简化. 问题的提出： * 1965年，Cooley, Tukey（库利——图基）在DFT:Discrete Fourier Transform 的基础上发表的一种使计算量降到(N/2)log2N。快速算法 《机器计算傅里叶级数的一种算法》 FFT: Fast Fourier Transform 问题的提出： * §1.DFT(离散傅理叶变换） 一、思想 函数的拉格朗尔插值： －以n次多项式为插值基。 DFT： 以傅氏变换核－ 为插值基。 * 二、问题 已知 已知 * 三、方法 －DFT －逆DFT * 四、计算量 一个 ： N次乘法＋N次加法 共N个 ： (N次乘法＋N次加法)N=NN次操作 1965年,库利(J.W.Cooley)和图基(J.W.Tukey)在Mathematics of Computation杂志发表论文《机器计算傅立叶级数的一种算法》，首先提出FFT算法,这就是库利——图基算法（时间抽取基2FFT算法）。对于N点DFT,仅需(N/2)log2N 次复数乘法运算.例如N=1024=210 时，需要(1024/2)log2 210 =512*10=5120次。5120/1048576=4.88% ,速度提高20倍 * §2.FFT方法 一、思想：引入二进制，减少计算量 二、构造： 三、方法： 1、 的二进制表示： 以m=3为例： （最多是二进制三位数） * 二进制数 三、方法： * 三、方法： 1、 的二进制表示： * 2、 的具体计算过程： 三、方法： * 四、计算量： 四乘四加 四加 * 四、计算量： 记 * 四、计算量： 四乘四加 四加 * 四、计算量： * 四、计算量： * 四、计算量： ∧ ∧ ∧ * 复乘次数 N N 2 四、计算量： DFT FFT * 五、FFT的特点 0 0 0 0 ④ ④ ④ ④ 0 0 0 ④ ④ ② ② ② ④ ⑥ ⑥ ⑥