傅里葉變換課件

3.5.2用正交多項(xiàng)式做最小二乘擬合

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

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

3.6.2快速傅氏變換（FFT）

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

3.7.1有理逼近與連分式

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

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

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

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

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

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

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

例10求的帕德逼近及.

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

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

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

3.6.2快速傅氏變換（FFT）

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

3.7.1有理逼近與連分式

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

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

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

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