數(shù)值分析：第三章 函數(shù)基本逼近（二）-最佳逼近

1第三章函數(shù)基本逼近（二）

----最佳逼近

1湘潭大學數(shù)學與計算科學學院2§1引言

1.逼近空間：

主要為：代數(shù)多項式空間也將涉及：三角多項式空間2.逼近方式：最佳逼近2湘潭大學數(shù)學與計算科學學院3最佳逼近意義的刻劃:

它是一種整體意義下逼近它是誤差在某種度量下的最小值3湘潭大學數(shù)學與計算科學學院4

整體逼近（在整個區(qū)間上）第二章介紹的代數(shù)多項式插值逼近是一種整體逼近,但該整體逼近有明顯的缺點：

如Runge現(xiàn)象，數(shù)值不穩(wěn)定等.因此需要引入其它方式的逼近。(a)理論依據(jù):Weierstrass定理4湘潭大學數(shù)學與計算科學學院5定理３.1（Weierstrass）設函數(shù)在區(qū)間上連續(xù)，則，總存在一代數(shù)多項式,使得

定理說明：可以找到一個多項式去逼近一個函數(shù)到任意程度（整體逼近）.

表明,肯定存在比插值逼近更好的逼近。5湘潭大學數(shù)學與計算科學學院6例：考察在[-1，1]上的不同方式（意義）下的逼近效果。

解：方式1（插值）

于[-1，1]上通過2個端點的線性插值多項式及其誤差函數(shù)的圖象為：

的一次插值逼近

的一次插值逼近誤差

(b)通過例子來說明6湘潭大學數(shù)學與計算科學學院77湘潭大學數(shù)學與計算科學學院8方式2（最佳）

令，記考察：如何降低？

見下圖（a）,設與在[-1，1]上有2個點相交，通過適當?shù)匾苿又本€段，總能改善逼近.

8湘潭大學數(shù)學與計算科學學院9發(fā)現(xiàn)重要現(xiàn)象：

當使在[-1，1]均勻分布時，誤差的最大值達到最小，即：

誤差正好在以下三個點上正負相間地達到：

9湘潭大學數(shù)學與計算科學學院10的2個交點的坐標.而是的極值點，其中，和是與在結合（*3）和（*4）式

10湘潭大學數(shù)學與計算科學學院11計算得：

所求的最佳逼近多項式:

11湘潭大學數(shù)學與計算科學學院12本章討論兩種逼近：

1)最佳一致逼近：

求，使得：2)最佳平方逼近：

求，使得：12湘潭大學數(shù)學與計算科學學院13§2線性賦范空間的最佳逼近及存在性定理

13湘潭大學數(shù)學與計算科學學院14線性賦范空間設為實數(shù)域，抽象元素集合是一個實線性空間.若對中的每個元素都對應著一個實數(shù)，記作，并且它滿足下列條件：（1）的充要條件是；（2）；（3）.

上述對應關系可視為的映射，稱為線性空間的范數(shù)，并簡記為‖·‖.定義了范數(shù)的線性空間稱為線性賦范空間.14湘潭大學數(shù)學與計算科學學院15引入記號:

稱為一致范數(shù)或Chebyshev范數(shù)。

定義范數(shù)以后，就構成一個線性賦范空間.這時有：

——最佳一致逼近多項式.兩種常見度量：15湘潭大學數(shù)學與計算科學學院16引入記號：

這時有：

——最佳平方逼近多項式.16湘潭大學數(shù)學與計算科學學院1717湘潭大學數(shù)學與計算科學學院18線性賦范空間的最佳逼近

定義：設E為一線性賦范空間，為其m維子

空間，為任意給定元素，稱量

為子空間對元素的最佳逼近，而使上式成立的元素，即滿足，稱為的最佳逼近元素.

18湘潭大學數(shù)學與計算科學學院19給出了最佳逼近問題的提法，自然關心如下問題：（1）最佳逼近元素是否存在；（2）如果最佳逼近元素存在，是否唯一；（3）最佳逼近元素應具有什么特征；（4）最佳逼近元素的構造及其應用.19湘潭大學數(shù)學與計算科學學院20定理3.2（存在性定理）對任給的，總存在的最佳逼近元素.

注：一般情況下,最佳逼近元素的唯一性并不能夠得到保證,它依賴于引入的范數(shù)和子空間Hm的性質。

20湘潭大學數(shù)學與計算科學學院21§3最佳一致逼近多項式

21湘潭大學數(shù)學與計算科學學院22設在中求多項式使其誤差這就是最佳一致逼近或切比雪夫逼近問題.問題的引入：

22湘潭大學數(shù)學與計算科學學院23如果它滿足并稱xi為交錯點，簡稱(e)點.23湘潭大學數(shù)學與計算科學學院24例若則構成了f(x)在[0,1]上的交錯點組.24湘潭大學數(shù)學與計算科學學院25證用反證法.注意25湘潭大學數(shù)學與計算科學學院26于是，由介值定理知，即在這些點處交錯地取正負值.這樣就證明了定理.因此，必有從而與假設矛盾.26湘潭大學數(shù)學與計算科學學院27定理3.4(Chebyshev)對任意函數(shù)，，

是的次最佳一致逼近多項式的充要條件是在上存在至少有個點組成的交錯點組.

即：——

為交錯點，.27湘潭大學數(shù)學與計算科學學院2828湘潭大學數(shù)學與計算科學學院29注：雖然Chebyshev定理從理論上給出了最佳一致逼近的特征性質，但在一般情況下，求最佳一致逼近多項式是很困難的，通常只能近似計算。29湘潭大學數(shù)學與計算科學學院30里米茲算法(Remes算法):

求解近似最佳一致逼近多項式的算法,它是尋找交錯點組近似值的一種方法..

30湘潭大學數(shù)學與計算科學學院31我們下面將對它作深入的探討.由于Remes算法的計算量較大，實際計算中，常使用其它近似方法.其中一類重要的近似方法將用到所謂的Chebyshev多項式.鑒于Chebyshev多項式在理論和實際應用中的重要性31湘潭大學數(shù)學與計算科學學院作業(yè):P915題,6題,8題,9題32湘潭大學數(shù)學與計算科學學院33§4最小偏差于零的多項式——Chebyshev多項式33湘潭大學數(shù)學與計算科學學院34求的n-1次最佳一致逼近多項式([a,b]=[-1,1]).可描述為：求，使得：

34湘潭大學數(shù)學與計算科學學院35換一種說法：記表首項系數(shù)為1的n次代數(shù)多項式的全體，則上述最佳逼近問題等價于問題：求，使得：

上述最佳逼近問題也稱為與零偏差最小問題．35湘潭大學數(shù)學與計算科學學院36引入Chebyshev多項式：

令：，即：.于是：

由于：

36湘潭大學數(shù)學與計算科學學院37Chebyshev多項式的如下性質：性質1：

性質2：

是最高次數(shù)項系數(shù)為的n次代數(shù)多項

的奇次冪.

式，且只含的偶次冪，只含37湘潭大學數(shù)學與計算科學學院38湘潭大學數(shù)學與計算科學學院39湘潭大學數(shù)學與計算科學學院40湘潭大學數(shù)學與計算科學學院

41湘潭大學數(shù)學與計算科學學院性質4:

在[-1，1]上恰有個不同的實根：

42湘潭大學數(shù)學與計算科學學院定理3.5

在首項系數(shù)為1的所有n次多項式中，

對零的偏差最小.

推論：設是最高次項系數(shù)為1的n次多項式，則Chebyshev多項式具有廣泛的應用價值，下面介紹它的兩個重要應用.43湘潭大學數(shù)學與計算科學學院44現(xiàn)取使得盡可能的小.應選取Tn+1(x)的n+1個零點：

這里{x0,…,xn}為Tn+1(x)的n+1個零點，做f

的插值多項式Pn(x)，則插值余項的上界可達極小。Chebyshev多項式的其它應用

——代數(shù)插值多項式余數(shù)的極小化44湘潭大學數(shù)學與計算科學學院45

注：上界最小不表示|Rn(x)|最小，故Pn(x)嚴格意義上只是y(x)的近似最佳逼近多項式；對于一般區(qū)間x[a,b]，可作變量替換，則t[1,1

]，這時即以為插值節(jié)點(k=0,…,n)，得Pn(x)，余項有最小上界。45湘潭大學數(shù)學與計算科學學院46

例：求f(x)=ex

在[0,1]上的近似最佳逼近多項式，使其誤差不超過0.5104。解：根據(jù)誤差上界確定n:n=4計算T5(t)的根：以x0,…,x4為節(jié)點作L4(x)46湘潭大學數(shù)學與計算科學學院47

Chebyshev多項式的其它應用

——多項式降次

設f(x)Pn(x)。在降低Pn(x)次數(shù)的同時,使因此增加的誤差盡可能小。從Pn中去掉一個含有其最高次項的,結果降次為,則：Pn~Pn1|)(|max|)()(|max|)()(|max]1,1[]1,1[1]1,1[xPxPxfxPxfnnn----+--~因降次而增的誤差設Pn的首項系數(shù)為an，則取可使精度盡可能少損失。12)()(-=nnnnxTaxP47湘潭大學數(shù)學與計算科學學院48

例：

f(x)=ex

在[1,1]上的4階Taylor展開為，此時誤差請將其降為2階多項式。解：?。ú楸碇┤。ú楸碇┤艉唵稳。瑒t誤差另一解法可查p.70表3-2，將x3

和x4

中的T3和T4刪除。注：對一般區(qū)間[a,b]，先將x

換為

t，考慮f(t)在[1,1]上的逼近Pn(t)，再將t

換回x，最后得到Pn(x)。48湘潭大學數(shù)學與計算科學學院可提高計算效率和改善其整體逼近效果.Taylor逼近是一種局部逼近，利用Chebyshev多項式對它進行改造49湘潭大學數(shù)學與計算科學學院上式可由Chebyshev多項式表成可見k越大的系數(shù)就越小，50湘潭大學數(shù)學與計算科學學院可見k越大的系數(shù)就越小，由于因此可略去含次數(shù)高的的項.降低逼近多項式的次數(shù)，從而大大節(jié)省了計算工作量.51湘潭大學數(shù)學與計算科學學院則有而若按Taylor展式截斷到x5這一項則有52湘潭大學數(shù)學與計算科學學院則約為前者絕對誤差的33倍.兩種近似的誤差曲線如下圖所示53湘潭大學數(shù)學與計算科學學院而運用Chebyshev多項式調整后，誤差分布顯得均勻，由圖可知：當x在原點附近時，Taylor逼近誤差非常小，但越偏離原點，其誤差就越大.54湘潭大學數(shù)學與計算科學學院§5內積空間的最佳逼近55湘潭大學數(shù)學與計算科學學院定義5.1

設X是實線性空間，在X上定義了一個二元若它滿足實函數(shù)則稱為內積，X為內積空間.56湘潭大學數(shù)學與計算科學學院1、n維歐氏空間Rn是內積空間，其中的內積定義為為Rn中的任意向量.

這里兩種重要的內積空間57湘潭大學數(shù)學與計算科學學院2、空間是區(qū)間[a,b]上滿足(x)f2(x)可積的函數(shù)f(x)的全體，定義內積其中(x)為權函數(shù)。58湘潭大學數(shù)學與計算科學學院權函數(shù)的概念稱區(qū)間[a,b]上的非負函數(shù)(x)為權函數(shù)，若它滿足（1）

對一切非負整數(shù)n可積且有限；

（2）假設對某個非負的連續(xù)函數(shù)g(x)，則在[a,b]上函數(shù)g(x)≡0.59湘潭大學數(shù)學與計算科學學院內積空間的性質性質1（Cauchy-Schwarz不等式）設X是內積空間，則有在內積空間X中引入如下范數(shù)：則內積空間X就構成一類賦范線性空間.60湘潭大學數(shù)學與計算科學學院性質2（平行四邊形等式）對內積空間X，有幾何解釋：xy

x+y

x-y

61湘潭大學數(shù)學與計算科學學院稱內積空間X中的兩個元素x,y是正交的，類似于歐氏空間中向量正交的定義，(x,y)=0.則有如果xy

x+y

幾何解釋：62湘潭大學數(shù)學與計算科學學院定義5.2

設X為一內積空間，為有限維子空間,稱量對為子空間M對元素f的最佳逼近，并簡記為E(f).使上式成立的元素即滿足稱為f的最佳逼近元素.63湘潭大學數(shù)學與計算科學學院對定理5.1在M中存在著f的唯一最佳逼近元素.證

用反證法.令并記則有設在M中有兩個不同的最佳逼近元素64湘潭大學數(shù)學與計算科學學院這樣由性質2可推得這與假設矛盾，證畢.

因此,65湘潭大學數(shù)學與計算科學學院定義5.1

設X是實線性空間，在X上定義了一個二元若它滿足實函數(shù)則稱為內積，X為內積空間.內容回顧66湘潭大學數(shù)學與計算科學學院1、n維歐氏空間Rn是內積空間，其中的內積定義為為Rn中的任意向量.

這里兩種重要的內積空間內容回顧67湘潭大學數(shù)學與計算科學學院2、空間是區(qū)間[a,b]上滿足(x)f2(x)可積的函數(shù)f(x)的全體，定義內積其中(x)為權函數(shù)。內容回顧68湘潭大學數(shù)學與計算科學學院內積空間的性質性質1（Cauchy-Schwarz不等式）設X是內積空間，則有內容回顧性質2（平行四邊形等式）對內積空間X，有69湘潭大學數(shù)學與計算科學學院在內積空間X中引入如下范數(shù)：則內積空間X就構成一類賦范線性空間.內容回顧70湘潭大學數(shù)學與計算科學學院定義5.2

設X為一內積空間，為有限維子空間,稱量對為子空間M對元素f的最佳逼近，并簡記為E(f).使上式成立的元素即滿足稱為f的最佳逼近元素.內容回顧71湘潭大學數(shù)學與計算科學學院對定理5.1在M中存在著f的唯一最佳逼近元素.內容回顧72湘潭大學數(shù)學與計算科學學院證必要性.令則73湘潭大學數(shù)學與計算科學學院從而必要性得證.充分性.則74湘潭大學數(shù)學與計算科學學院充分性得證.幾何意義:75湘潭大學數(shù)學與計算科學學院注：利用可得最佳逼近值的如下表達式設X的n維子空間76湘潭大學數(shù)學與計算科學學院由于則有即77湘潭大學數(shù)學與計算科學學院稱為最佳逼近元素的法方程組(或正規(guī)方程組).記n×n階對稱矩陣容易證明矩陣G是正定的.因此，法方程組的解存在且唯一.78湘潭大學數(shù)學與計算科學學院則矩陣G成為對角矩陣，即此時法方程組為故最佳逼近元素為79湘潭大學數(shù)學與計算科學學院稱為f的廣義富氏展開，相應的系數(shù)稱為廣義富氏系數(shù)又因則有80湘潭大學數(shù)學與計算科學學院由此可得——Bessel不等式特別，若最佳逼近元素序列收斂于f，則上述不等式成為等式，稱之為廣義Paseval等式.81湘潭大學數(shù)學與計算科學學院有限維空間正交基的存在性定理定理5.3

任何n維內積空間M都存在正交基.具體作法如下令求元素使82湘潭大學數(shù)學與計算科學學院設已構造了k-1個兩兩正交且異于零的向量83湘潭大學數(shù)學與計算科學學院聯(lián)立上面兩式可得將上述正交化過程進行下去,最后可得正交元素系它構成了M的一組正交基,從而定理得證.84湘潭大學數(shù)學與計算科學學院作業(yè):P91-922題,10題,12題,14題85湘潭大學數(shù)學與計算科學學院§6

最佳平方逼近與正交多項式

86湘潭大學數(shù)學與計算科學學院6.1連續(xù)情形的最佳平方逼近87湘潭大學數(shù)學與計算科學學院這里88湘潭大學數(shù)學與計算科學學院解設所求的最佳一次逼近多項式為計算可得89湘潭大學數(shù)學與計算科學學院將上述式子代入故一次最佳平方逼近多項式為90湘潭大學數(shù)學與計算科學學院內容回顧91湘潭大學數(shù)學與計算科學學院注：利用設X的n維子空間內容回顧92湘潭大學數(shù)學與計算科學學院由于則有即內容回顧93湘潭大學數(shù)學與計算科學學院稱為最佳逼近元素的法方程組(或正規(guī)方程組).法方程組的解存在且唯一.內容回顧94湘潭大學數(shù)學與計算科學學院內容回顧95湘潭大學數(shù)學與計算科學學院這里內容回顧96湘潭大學數(shù)學與計算科學學院則矩陣G成為對角矩陣，即此時法方程組為故最佳逼近元素為內容回顧97湘潭大學數(shù)學與計算科學學院6.2正交多項式（2）98湘潭大學數(shù)學與計算科學學院特別，若記99湘潭大學數(shù)學與計算科學學院定理6.1

上述帶權正交基有遞推公式其中常數(shù)證明略。100湘潭大學數(shù)學與計算科學學院由定理6.1及數(shù)學歸納法可證.略即若101湘潭大學數(shù)學與計算科學學院幾類特殊而又重要的帶權正交多項式（1）勒讓德（Legendre）多項式102湘潭大學數(shù)學與計算科學學院遞推公式103湘潭大學數(shù)學與計算科學學院（2）Chebyshev多項式又稱為第一類Chebyshev多項式.104湘潭大學數(shù)學與計算科學學院（3）第二類Chebyshev多項式105湘潭大學數(shù)學與計算科學學院（4）拉蓋爾（Laguerre）多項式106湘潭大學數(shù)學與計算科學學院（5）埃爾米特（Hermite）多項式107湘潭大學數(shù)學與計算科學學院6.3近似Chebyshev逼近

由于

是Chebyshev多項式是關于權的正交基.則有

考慮，，給出其次最佳平方逼近多項式。108湘潭大學數(shù)學與計算科學學院

稱為按Chebyshev多項式展開的部分和.

可以證明：

1）一致收斂于；

2）.

故當充分大時：

為的交錯點.

可作為的近似Chebyshev逼近多項式.

109湘潭大學數(shù)學與計算科學學院解由可知其中110湘潭大學數(shù)學與計算科學學院利用數(shù)值積分可得111湘潭大學數(shù)學與計算科學學院可見它與最佳一致逼近具有非常相似的特征，即誤差函數(shù)是均勻分布的.112湘潭大學數(shù)學與計算科學學院§7

數(shù)據(jù)擬合的最小二乘法113湘潭大學數(shù)學與計算科學學院一、離散情況的最佳平方逼近任給向量及一組權系數(shù)相應的內積和范數(shù)分別定義為114湘潭大學數(shù)學與計算科學學院設為Rn中的一組線性無關向量，為Rn的l維子空間。這時Hl中的任意元素115湘潭大學數(shù)學與計算科學學院考慮最佳逼近問題：求使得現(xiàn)對Rn中的任意向量116湘潭大學數(shù)學與計算科學學院由記則(*)式的等價矩陣形式為(*)117湘潭大學數(shù)學與計算科學學院這里向量l階方陣而矩陣元素稱方程組(*)為離散情況最佳平方逼近問題的(*)法方程組118湘潭大學數(shù)學與計算科學學院由向量系容易證明系數(shù)矩陣A是l階對稱正定陣.(*)的線性無關性，Y的最佳平方逼近向量就是它自己，即119湘潭大學數(shù)學與計算科學學院應用：求解如下超定方程組其中，向量長方陣應用離散情況的最佳平方逼近來求解！120湘潭大學數(shù)學與計算科學學院則：記：121湘潭大學數(shù)學與計算科學學院設矩陣A列滿秩，則超定方程組的求解轉化為：或者：求，使得：求，使得：

122湘潭大學數(shù)學與計算科學學院解超定方程組的法方程組：

即法方程為123湘潭大學數(shù)學與計算科學學院例：

則：記：124湘潭大學數(shù)學與計算科學學院法方程為解：（上例）

即：125湘潭大學數(shù)學與計算科學學院二、數(shù)據(jù)擬合的最小二乘法在生產實踐中，人們常常需要根據(jù)已知觀測數(shù)據(jù)確定不同量之間的關系，為進一步判斷、預測等提供理論依據(jù)，數(shù)據(jù)擬合的最小二乘法正是解決這個問題的重要方法.126湘潭大學數(shù)學與計算科學學院1、兩個變量的數(shù)據(jù)擬合考察變量x和y，通過實驗得到它們之間滿足一組數(shù)據(jù)我們希望建立變量y和x的近似函數(shù)關系式，并稱為相應的數(shù)據(jù)擬合曲線.為了建立y與x的關系，首先需猜想的形式，或稱給出問題的數(shù)學模型.127湘潭大學數(shù)學與計算科學學院例1

某物質的溶解度y和溫度x的關系經測定滿足下面數(shù)據(jù)表，試建立該問題的數(shù)學模型.將(x,y)的數(shù)據(jù)點描在一坐標紙上，則如下圖所示.128湘潭大學數(shù)學與計算科學學院y與x近似成拋物線關系，數(shù)據(jù)點分布在一拋物線的兩側.從圖中可見，因此，可以猜測即有其中是待定常數(shù)，這就是本問題的數(shù)學模型.129湘潭大學數(shù)學與計算科學學院確定了問題的數(shù)學模型，如何來確定中的待定常數(shù)？

假設與待定常數(shù)呈線性關系，即這里是線性無關函數(shù)系，為待定常數(shù).130湘潭大學數(shù)學與計算科學學院最小二乘逼近問題求使得稱為關于數(shù)據(jù)的最小二乘逼近函數(shù).131湘潭大學數(shù)學與計算科學學院記n維向量則l維子空間132湘潭大學數(shù)學與計算科學學院則極小問題等價于離散情況的最佳平方逼近問題可通過求解相應的法方程組得到待定系數(shù).133湘潭大學數(shù)學與計算科學學院現(xiàn)在我們對下表中的離散數(shù)據(jù)求其最小二乘逼近取權系數(shù)為1，基函數(shù)134湘潭大學數(shù)學與計算科學學院待定常數(shù)由法方程組確定.經計算可得因此，溶解度y和溫度x近似滿足關系135湘潭大學數(shù)學與計算科學學院注：這里是將最小二乘逼近問題化為離散情況的最佳平方逼近問題進行求解的.實用中，也可將誤差帶權平方和通過對該多元函數(shù)求極小值點，同樣可得極小解視為待定參數(shù)的多元函數(shù)，136湘潭大學數(shù)學與計算科學學院上述變量y依賴于單個變量x的數(shù)據(jù)擬合問題可推廣到依賴于多個變量的情形.相應的數(shù)據(jù)擬合問題可描述為：已知一組測量數(shù)據(jù)以及一組權系數(shù)2、兩個以上變量的數(shù)據(jù)擬合137湘潭大學數(shù)學與計算科學學院用數(shù)據(jù)擬合的最小二乘法確定變量y與變量的關系式，即求多元函數(shù)分二步可實現(xiàn)多個變量的最小二乘數(shù)據(jù)擬合.類似于兩個變量的數(shù)據(jù)擬合的最小二乘法,138湘潭大學數(shù)學與計算科學學院步1

建立多個變量數(shù)據(jù)擬合問題的數(shù)學模型，即確定多元函數(shù)所屬的有限維函數(shù)空間不妨記這里多元函數(shù)系是線性無關函數(shù)組.139湘潭大學數(shù)學與計算科學學院步2求使得這里稱為關于測量數(shù)據(jù)的最小二乘逼近（擬合）函數(shù).

140湘潭大學數(shù)學與計算科學學院同兩個變量的情形完全類似，多個變量最小二乘問題等價于離散情況的最佳平方逼近問題只是法方程組中內積的定義為141湘潭大學數(shù)學與計算科學學院§8快速傅立葉變換

問題的背景

傅立葉變換——函數(shù)展開為三角級數(shù)設f(x)周期為2，在[0,2]上展開為三角級數(shù)，其中Cj

為復系數(shù)，，則實際計算時要取級數(shù)的前N

項，并要求在區(qū)間的N

個等分點上與f(x)重合。即：給定[0,2]上N個等分點上的函數(shù)值，令滿足插值條件。N個未知數(shù)N個方程DiscreteFourierTransformInverseofDFT總之要進行形如的計算，其中已知，142湘潭大學數(shù)學與計算科學學院

FastFourierTransform快速計算(j=0,1,…,N1)，其中直接計算需復數(shù)乘法次N2

降到N·logN由于W的周期性WqN+s=Ws,Wkj實際上只有這

個不同的值。若N

為偶數(shù)，則Wkj只有個不同值。10...-NWWNN/2先合并同類項，再做乘法。143湘潭大學數(shù)學與計算科學學院

例：N=23=8,計算，j=0,1,2,3,4,5,6,7技巧：將k,j

先記為二進制數(shù)

/*binarynumbers*/=++==++=)(222)(222012001122012001122jjjjjjjkkkkkkkkjW)222()222(001122001122++++=kkkjjjW)()222()222(012010213212031422kkkjkkkjkkkjW++++++=)()0()00(012001102kkkjkkjkjW++=23次乘法全部計算需要238次乘法一般地：取N=2p

，每個Cj

用2p

次乘法，共用2Nlog2N

次乘法。利用，還可以進一步化簡到N(p1)/2

次乘法。144湘潭大學數(shù)學與計算科學學院

最佳逼近小結最佳一致逼近最佳平方逼近（分連續(xù)和離散兩種情形）。

（注意問題的提法，最佳逼近多項式的構造方法）正交多項式。最小二乘法。145湘潭大學數(shù)學與計算科學學院§8周期函數(shù)的最佳逼近與

快速富氏變換

146湘潭大學數(shù)學與計算科學學院一、最佳平方逼近三角多項式1、連續(xù)情形設f(x),g(x)是以2π為周期的實的平方可積函數(shù)，分別定義相應的內積和范數(shù)為147湘潭大學數(shù)學與計算科學學院這里唯一存在，且可表示成則空間X關于f(x)的最佳平方逼近元素148湘潭大學數(shù)學與計算科學學院其中最佳平方逼近三角多項式函數(shù)fn(x)恰好是f(x)的Fourier級數(shù)的部分和，而ak,bk為富氏系數(shù).由數(shù)學分析中的富氏級數(shù)理論知：149湘潭大學數(shù)學與計算科學學院由Fourier級數(shù)的收斂性定理知：即2、離散情形（數(shù)據(jù)擬合的三角多項式最小二乘逼近）記Cn是n維復向量空間，內積和范數(shù)分別定義如下：150湘潭大學數(shù)學與計算科學學院這里令Tm是所有次數(shù)不超過m-1的復三角多項式全體所構成函數(shù)空間，且構成Tm的一個基底.151湘潭大學數(shù)學與計算科學學院設f(x)是以2π為周期的復函數(shù)，是f(x)在n個等分點上的值?？紤]數(shù)據(jù)擬合的三角多項式最小二乘逼近問題:152湘潭大學數(shù)學與計算科學學院求m-1次復三角多項式(m≤

n)使得這里是任意m-1次復三角多項式,是虛數(shù)單位.153湘潭大學數(shù)學與計算科學學院154湘潭大學數(shù)學與計算科學學院和它們對應的復三角多項