傅里葉變換課件

3.5.2用正交多項式做最小二乘擬合

如果是關(guān)于點集帶權(quán)正交的（5.8）用最小二乘法得到的法方程組（5.6），其系數(shù)矩陣是病態(tài)的.函數(shù)族，即13.5.2用正交多項式做最小二乘擬合（5.9）則方程（5.6）的解為且平方誤差為2（5.9）則方程（5.6）的解為且平方誤差為2接下來根據(jù)給定節(jié)點及權(quán)函數(shù)構(gòu)造帶權(quán)正交的多項式.注意，用遞推公式表示，即（5.10）根據(jù)的這里是首項系數(shù)為1的次多項式，正交性，得3接下來根據(jù)給定節(jié)點及權(quán)函數(shù)（5.11）下面用歸納法證明這樣給出的是正交的.4（5.11）下面用歸納法證明這樣給出的假定對及要證對均成立.由（5.10）有由（5.10）第二式及（5.11）中的表達式，有均成立，（5.12）5假定對而，于是由（5.12），當時，另外，是首項系數(shù)為1的次多項式，它可由由歸納法假定，當時的線性組合表示.由歸納法假定又有6而，于是由（5.12），當由假定有再考慮（5.13）利用（5.11）中表達式及以上結(jié)果，得7由假定有再考慮（5.13）利用（5.11）中至此已證明了由（5.10）及（5.11）確定的多項式組成一個關(guān)于點集的正交系.用正交多項式的線性組合作最小二乘曲線擬合，只要根據(jù)公式（5.10）及（5.11）逐步求的同時，相應計算出系數(shù)最后，由和的表達式（5.11）有8至此已證明了由（5.10）及（5.11）確定的多項式并逐步把累加到中去，最后就可得到所求的用這種方法編程序不用解方程組，只用遞推公式，并且當逼近次數(shù)增加一次時，只要把程序中循環(huán)數(shù)加1，其余不用改變.這里可事先給定或在計算過程中根據(jù)誤差確定.擬合曲線9并逐步把累加到中去，最后就可得到所求3.6最佳平方三角逼近與快速傅里葉變換

當是周期函數(shù)時，顯然用三角多項式逼近比用代數(shù)多項式更合適，本節(jié)主要討論用三角多項式做最小平方逼近及快速傅里葉變換，簡稱FFT算法.103.6最佳平方三角逼近與快速傅里葉變換當3.6.1最佳平方三角逼近與三角插值設(shè)是以為周期的平方可積函數(shù)，用三角多項式（6.1）做最佳平方逼近函數(shù).由于三角函數(shù)族在上是正交函數(shù)族，于是在上的最小平方三角逼近多項式的系數(shù)是113.6.1最佳平方三角逼近與三角插值稱為傅里葉系數(shù).函數(shù)按傅里葉系數(shù)展開得到的級數(shù)（6.3）就稱為傅里葉級數(shù).（6.2）12稱為傅里葉系數(shù).函數(shù)按傅只要在上分段連續(xù)，則級數(shù)（6.3）一致收斂到.對于最佳平方逼近多項式（6.1）有由此可以得到相應于（4.11）的貝塞爾不等式因為右邊不依賴于，左邊單調(diào)有界，所以級數(shù)13只要在上分段連續(xù)，則級數(shù)（6當只在給定的離散點集上已知時，則可類似得到離散點集正交性與相應的離散傅里葉系數(shù).下面只給出奇數(shù)個點的情形.收斂，并有14當只在給定的離散點集可以證明對任何成立令15可以證明對任何成立令15這表明函數(shù)族在點集上正交.若令則的最小二其中乘三角逼近為16這表明函數(shù)族當時于是（6.4）就是三角插值多項式，系數(shù)仍由（6.4）表示.17當時于是（6.4）就是三角插值多項式，系數(shù)仍由于所以函數(shù)族在區(qū)間上是正交的.一般情形，假定是以為周期的復函數(shù)，給定在個等分點上的值函數(shù)在等距點集上的值組成的向量記作18由于所以函數(shù)族在區(qū)間當時，個復向量具有如下正交性：（6.5）19當時，個復向量事實上，令于是即若若則有則從而20事實上，令于是即若若則有則從而20于是若這就證明了（6.5）成立.即是正交的.則于是因此，在個點上的最小二乘傅里葉逼近為21于是若這就證明了（6.5）成立.即（6.6）其中（6.7）在（6.6）中，若，則為在點上的插值函數(shù)，于是由（6.6）得即（6.8）22（6.6）其中（6.7）在（6.6）中，若，則（6.7）是由求的過程，稱為的離散而（6.8）是由求的過程，稱為反變換.傅里葉變換.簡稱DFT，23（6.7）是由求的過程，稱為的

3.6.2快速傅氏變換（FFT）

不論是按（6.7）式由求，由求，（6.9）其中(正變換)或(反變換)，還是由（6.4）計算傅里葉逼近系數(shù)都可歸結(jié)為計算是已知復數(shù)序列.或是按（6.8）243.6.2快速傅氏變換（FFT）不當較大且處理數(shù)據(jù)很多時，就是用高速的電子計算機，很多實際問題仍然無法計算，如直接用（6.9）計算，需要次復數(shù)乘法和次復數(shù)加法，稱為個操作，計算全部共要個操作.直到20世紀60年代中期產(chǎn)生了FFT算法，大大提高了運算速度，從而使傅氏變換得以廣泛應用.FFT算法的基本思想就是盡量減少乘法次數(shù).25當較大且處理數(shù)據(jù)很多時，就是用高速的電子計算用（6.9）計算全部，表面看要做個乘法，實際上所有中，只有個不同的值特別當時，只有個不同的值.因此可把同一個對應的相加后再乘，這就能大量減少乘法次數(shù).26用（6.9）計算全部，表面看要做個乘設(shè)正整數(shù)除以后得商及余數(shù)，則，稱為的同余數(shù)，以表示.由于因此計算時可用的同余數(shù)代替，從而推出FFT算法.以為例.說明FFT的計算方法.由于則（6.9）的和是（6.10）故有27設(shè)正整數(shù)除以后得商及余數(shù)，則將用二進制表示為其中只能取0或1，例如根據(jù)表示法，有公式（6.10）可表示為28將用二進制表示為其中（6.11）若引入記號（6.12）29（6.11）若引入記號（6.12）29則（6.11）變成它說明利用同余數(shù)可把計算分為步，用公式（6.12）計算.每計算一個只用2次復數(shù)乘法，計算一個用次復數(shù)乘法，計算全部共用次復數(shù)乘法.若注意公式（6.12）還可進一步簡化為30則（6.11）變成它說明利用同余數(shù)可把計算將這表達式中二進制表示還原為十進制表示：31將這表達式中二進制表示還原為十進制表示：31（6.13）同樣（6.12）中的也可簡化為即即得32（6.13）同樣（6.12）中的也可簡化為即即把二進制表示還原為十進制表示，得（6.14）同理（6.12）中可簡化為即33把二進制表示還原為十進制表示，得（6.14）同理（6.12表示為十進制，有（6.15）34表示為十進制，有（6.15）34根據(jù)公式(6.13)，(6.14)，(6.15)，由逐次計算到見表3-2(略）.上面推導的的計算公式可類似地推廣到的情形.根據(jù)公式(6.13)，(6.14)，(6.15)，一般情況的FFT計算公式如下：35根據(jù)公式(6.13)，(6.14)，(6.15)，由（6.16）其中從出發(fā)，由到算到一組占用個復數(shù)單元，計算時需給出兩組單元，括號內(nèi)的數(shù)代表它的位置，在計算機中代表存放數(shù)的地址.即為所求.36（6.16）其中從這個計算公式除了具有不倒地址的優(yōu)點外，計算只有兩重循環(huán)，計算過程中只要按地址號存放則最后得到的就是所求離散頻譜的次序.外循環(huán)由計算到，內(nèi)循環(huán)由計算到由計算到更重要的是整個計算過程省計算量.由公式看到算一個共做次復數(shù)乘法，而最后一步計算時，由于37這個計算公式除了具有不倒地址的優(yōu)點外，計算只有兩（注意時故），因此，總共要算次復數(shù)乘法，它比直接用（6.9）需次乘法當時比值是它比一般FFT的計算量（次乘法）也快一倍.快得多，計算量比值是我們稱（6.16）的計算公式為改進的FFT算法.38（注意時故）3.7有理逼近

3.7.1有理逼近與連分式

有理函數(shù)逼近是指用形如的函數(shù)逼近與前面討論一樣，如果最小就可得到最佳有理一致逼近.

（7.1）393.7有理逼近3.7.1有理如果最小則可得到最佳有理平方逼近函數(shù).本節(jié)主要討論利用函數(shù)的泰勒展開獲得有理逼近函數(shù)的方法.對函數(shù)用泰勒展開得（7.2）取部分和40如果最小則可得到最佳另一方面若對（7.2）式用輾轉(zhuǎn)相除可得到的一種連分式展開（7.3）41另一方面若對（7.2）式用輾轉(zhuǎn)相除可得到（7.4）（7.3）右端為的無窮連分式的前5項，最后式子若?。?.3）的前2，4，6，8項，則可分別得到的以下有理逼近是它的緊湊形式.42（7.4）（7.3）右端為的無窮連分式的前5若用同樣多項的泰勒展開部分和逼近并計算處的值及，計算結(jié)果見表3-3.的準確值為從表3-1可以看出，43若用同樣多項的泰勒展開部分和逼近但它們的計算量是相當?shù)?，這說明用有理逼近比多項式逼近好得多.由此看出的精度比高出近10萬倍，

例9用輾轉(zhuǎn)相除法將它化為連分式并寫成緊湊形式.

解給出有理函數(shù)用輾轉(zhuǎn)相除可逐步得到44但它們的計算量是相當?shù)?，這說明用有理逼近比多項式逼近本例中用連分式計算的值只需3次除法，1次乘法和7次加法.45本例中用連分式計算的值只需3次除法，1次若直接用多項式計算的秦九韶算法則需6次乘法和1次除法及7次加法.可見將化成連分式可節(jié)省計算乘除法次數(shù).對一般的有理函數(shù)（7.1）可轉(zhuǎn)化為一個連分式它的乘除法運算只需次.而直接用有理函數(shù)（7.1）計算乘除法次數(shù)為次.46若直接用多項式計算的秦九韶算法則需6次乘法和1次可見3.7.2帕德逼近

利用函數(shù)的泰勒展開可以得到它的有理逼近.設(shè)在的泰勒展開為（7.5）它的部分和記作（7.6）473.7.2帕德逼近利用函數(shù)

定義11設(shè)其中無公因式，且滿足條件（7.8）則稱為函數(shù)在處的階帕德逼近，記作,簡稱的帕德逼近.如果有理函數(shù)（7.7）48定義11設(shè)其中無公因式，且滿根據(jù)定義，若令則滿足條件（7.8）等價于即由于應用萊布尼茲求導公式得49根據(jù)定義，若令則滿足條件（7.8）等價于即由于這里是由（7.6）得到的，上式兩端除，并由可得（7.9）及（7.10）注意當時故（7.10）可寫成50這里是由（7.6）得到的，上式兩端（7.11）其中時，若記（7.12）51（7.11）其中時，若記（7.12）5則方程組（7.11）的矩陣形式為

定理10（7.7）的有理函數(shù)是的階帕德逼近的充分必要條件是多項式的系數(shù)及滿足方程組（7.9）及（7.11）.設(shè)則形如52則方程組（7.11）的矩陣形式為定理10（7.7）根據(jù)定理10,求的帕德逼近時，首先要由（7.11）解出的系數(shù)，的系數(shù).的各階帕德逼近可列成再由（7.9）直接算出一張表，稱為帕德表（見表3-4）.53根據(jù)定理10,求的帕德逼近時，首先要由（

例10求的帕德逼近及.

解由的泰勒展開得當時，由（7.11）得求得再由（7.9）得54例10求的帕德逼近于是得當時，由（7.11）得55于是得當時，由（7.11）得55代入（7.9）得解得于是得56代入（7.9）得解得于是得56可以看到這里得到的及與的前面為了求帕德逼近的誤差估計，由(7.9)及(7.11)求得的系數(shù)及，直接代入則得將除上式兩端，即得連分式展開得到的有理逼近（7.4）結(jié)果一樣.57可以看到這里得到的及與（7.13）其中當時可得誤差近似表達式58（7.13）其中當時可得誤差近似表達式3.5.2用正交多項式做最小二乘擬合

如果是關(guān)于點集帶權(quán)正交的（5.8）用最小二乘法得到的法方程組（5.6），其系數(shù)矩陣是病態(tài)的.函數(shù)族，即593.5.2用正交多項式做最小二乘擬合（5.9）則方程（5.6）的解為且平方誤差為60（5.9）則方程（5.6）的解為且平方誤差為2接下來根據(jù)給定節(jié)點及權(quán)函數(shù)構(gòu)造帶權(quán)正交的多項式.注意，用遞推公式表示，即（5.10）根據(jù)的這里是首項系數(shù)為1的次多項式，正交性，得61接下來根據(jù)給定節(jié)點及權(quán)函數(shù)（5.11）下面用歸納法證明這樣給出的是正交的.62（5.11）下面用歸納法證明這樣給出的假定對及要證對均成立.由（5.10）有由（5.10）第二式及（5.11）中的表達式，有均成立，（5.12）63假定對而，于是由（5.12），當時，另外，是首項系數(shù)為1的次多項式，它可由由歸納法假定，當時的線性組合表示.由歸納法假定又有64而，于是由（5.12），當由假定有再考慮（5.13）利用（5.11）中表達式及以上結(jié)果，得65由假定有再考慮（5.13）利用（5.11）中至此已證明了由（5.10）及（5.11）確定的多項式組成一個關(guān)于點集的正交系.用正交多項式的線性組合作最小二乘曲線擬合，只要根據(jù)公式（5.10）及（5.11）逐步求的同時，相應計算出系數(shù)最后，由和的表達式（5.11）有66至此已證明了由（5.10）及（5.11）確定的多項式并逐步把累加到中去，最后就可得到所求的用這種方法編程序不用解方程組，只用遞推公式，并且當逼近次數(shù)增加一次時，只要把程序中循環(huán)數(shù)加1，其余不用改變.這里可事先給定或在計算過程中根據(jù)誤差確定.擬合曲線67并逐步把累加到中去，最后就可得到所求3.6最佳平方三角逼近與快速傅里葉變換

當是周期函數(shù)時，顯然用三角多項式逼近比用代數(shù)多項式更合適，本節(jié)主要討論用三角多項式做最小平方逼近及快速傅里葉變換，簡稱FFT算法.683.6最佳平方三角逼近與快速傅里葉變換當3.6.1最佳平方三角逼近與三角插值設(shè)是以為周期的平方可積函數(shù)，用三角多項式（6.1）做最佳平方逼近函數(shù).由于三角函數(shù)族在上是正交函數(shù)族，于是在上的最小平方三角逼近多項式的系數(shù)是693.6.1最佳平方三角逼近與三角插值稱為傅里葉系數(shù).函數(shù)按傅里葉系數(shù)展開得到的級數(shù)（6.3）就稱為傅里葉級數(shù).（6.2）70稱為傅里葉系數(shù).函數(shù)按傅只要在上分段連續(xù)，則級數(shù)（6.3）一致收斂到.對于最佳平方逼近多項式（6.1）有由此可以得到相應于（4.11）的貝塞爾不等式因為右邊不依賴于，左邊單調(diào)有界，所以級數(shù)71只要在上分段連續(xù)，則級數(shù)（6當只在給定的離散點集上已知時，則可類似得到離散點集正交性與相應的離散傅里葉系數(shù).下面只給出奇數(shù)個點的情形.收斂，并有72當只在給定的離散點集可以證明對任何成立令73可以證明對任何成立令15這表明函數(shù)族在點集上正交.若令則的最小二其中乘三角逼近為74這表明函數(shù)族當時于是（6.4）就是三角插值多項式，系數(shù)仍由（6.4）表示.75當時于是（6.4）就是三角插值多項式，系數(shù)仍由于所以函數(shù)族在區(qū)間上是正交的.一般情形，假定是以為周期的復函數(shù)，給定在個等分點上的值函數(shù)在等距點集上的值組成的向量記作76由于所以函數(shù)族在區(qū)間當時，個復向量具有如下正交性：（6.5）77當時，個復向量事實上，令于是即若若則有則從而78事實上，令于是即若若則有則從而20于是若這就證明了（6.5）成立.即是正交的.則于是因此，在個點上的最小二乘傅里葉逼近為79于是若這就證明了（6.5）成立.即（6.6）其中（6.7）在（6.6）中，若，則為在點上的插值函數(shù)，于是由（6.6）得即（6.8）80（6.6）其中（6.7）在（6.6）中，若，則（6.7）是由求的過程，稱為的離散而（6.8）是由求的過程，稱為反變換.傅里葉變換.簡稱DFT，81（6.7）是由求的過程，稱為的

3.6.2快速傅氏變換（FFT）

不論是按（6.7）式由求，由求，（6.9）其中(正變換)或(反變換)，還是由（6.4）計算傅里葉逼近系數(shù)都可歸結(jié)為計算是已知復數(shù)序列.或是按（6.8）823.6.2快速傅氏變換（FFT）不當較大且處理數(shù)據(jù)很多時，就是用高速的電子計算機，很多實際問題仍然無法計算，如直接用（6.9）計算，需要次復數(shù)乘法和次復數(shù)加法，稱為個操作，計算全部共要個操作.直到20世紀60年代中期產(chǎn)生了FFT算法，大大提高了運算速度，從而使傅氏變換得以廣泛應用.FFT算法的基本思想就是盡量減少乘法次數(shù).83當較大且處理數(shù)據(jù)很多時，就是用高速的電子計算用（6.9）計算全部，表面看要做個乘法，實際上所有中，只有個不同的值特別當時，只有個不同的值.因此可把同一個對應的相加后再乘，這就能大量減少乘法次數(shù).84用（6.9）計算全部，表面看要做個乘設(shè)正整數(shù)除以后得商及余數(shù)，則，稱為的同余數(shù)，以表示.由于因此計算時可用的同余數(shù)代替，從而推出FFT算法.以為例.說明FFT的計算方法.由于則（6.9）的和是（6.10）故有85設(shè)正整數(shù)除以后得商及余數(shù)，則將用二進制表示為其中只能取0或1，例如根據(jù)表示法，有公式（6.10）可表示為86將用二進制表示為其中（6.11）若引入記號（6.12）87（6.11）若引入記號（6.12）29則（6.11）變成它說明利用同余數(shù)可把計算分為步，用公式（6.12）計算.每計算一個只用2次復數(shù)乘法，計算一個用次復數(shù)乘法，計算全部共用次復數(shù)乘法.若注意公式（6.12）還可進一步簡化為88則（6.11）變成它說明利用同余數(shù)可把計算將這表達式中二進制表示還原為十進制表示：89將這表達式中二進制表示還原為十進制表示：31（6.13）同樣（6.12）中的也可簡化為即即得90（6.13）同樣（6.12）中的也可簡化為即即把二進制表示還原為十進制表示，得（6.14）同理（6.12）中可簡化為即91把二進制表示還原為十進制表示，得（6.14）同理（6.12表示為十進制，有（6.15）92表示為十進制，有（6.15）34根據(jù)公式(6.13)，(6.14)，(6.15)，由逐次計算到見表3-2(略）.上面推導的的計算公式可類似地推廣到的情形.根據(jù)公式(6.13)，(6.14)，(6.15)，一般情況的FFT計算公式如下：93根據(jù)公式(6.13)，(6.14)，(6.15)，由（6.16）其中從出發(fā)，由到算到一組占用個復數(shù)單元，計算時需給出兩組單元，括號內(nèi)的數(shù)代表它的位置，在計算機中代表存放數(shù)的地址.即為所求.94（6.16）其中從這個計算公式除了具有不倒地址的優(yōu)點外，計算只有兩重循環(huán)，計算過程中只要按地址號存放則最后得到的就是所求離散頻譜的次序.外循環(huán)由計算到，內(nèi)循環(huán)由計算到由計算到更重要的是整個計算過程省計算量.由公式看到算一個共做次復數(shù)乘法，而最后一步計算時，由于95這個計算公式除了具有不倒地址的優(yōu)點外，計算只有兩（注意時故），因此，總共要算次復數(shù)乘法，它比直接用（6.9）需次乘法當時比值是它比一般FFT的計算量（次乘法）也快一倍.快得多，計算量比值是我們稱（6.16）的計算公式為改進的FFT算法.96（注意時故）3.7有理逼近

3.7.1有理逼近與連分式

有理函數(shù)逼近是指用形如的函數(shù)逼近與前面討論一樣，如果最小就可得到最佳有理一致逼近.

（7.1）973.7有理逼近3.7.1有理如果最小則可得到最佳有理平方逼近函數(shù).本節(jié)主要討論利用函數(shù)的泰勒展開獲得有理逼近函數(shù)的方法.對函數(shù)用泰勒展開得（7.2）取部分和98如果最小則可得到最佳另一方面若對（7.2）式用輾轉(zhuǎn)相除可得到的一種連分式展開（7.3）99另一方面若對（7.2）式用輾轉(zhuǎn)相除可得到（7.4）（7.3）右端為的無窮連分式的前5項，最后式子若?。?.3）的前2，4，6，8項，則可分別得到的以下有理逼近是它的緊湊形式.100（7.4）（7.3）右端為的無窮連分式的前5若用同樣多項的泰勒展開部分和逼近并計算處的值及，計算結(jié)果見表3-3.的準確值為從表3-1可以看出，101若用同樣多項的泰勒展開部分和逼近但它們的計算量是相當?shù)?，這說明用有理逼近比多項式逼近好得多.由此看出的精度比高出近10萬倍，

例9用輾轉(zhuǎn)相除法將它化為連分式并寫成緊湊形式.

解給出有理函數(shù)用輾轉(zhuǎn)相除可逐步得到102但它們的計算量是相當?shù)?，這說明用有理逼近比多項式逼近本例中用連分式計算的值只需3次除法，1次乘法和7次加法.103本例中用連分式計算的值只需3次除法，1次若直接用多項式計算的秦九韶算法則需6次乘法和1次除法及7次加法.可見將化成連分式可節(jié)省計算乘除法次數(shù).對一般的有理函數(shù)（7.1）可轉(zhuǎn)化為一個連分式它的乘除法運算只需