第3章函數(shù)逼近與快速傅里葉變換§3.1函數(shù)逼近的基本概念§3.2正交多項(xiàng)式§3.3最佳平方逼近§3.4曲線擬合的最小二乘法§3.5有理逼近§3.6三角逼近與快速傅里葉變換1第3章函數(shù)逼近與快速傅里葉變換§3.1函數(shù)逼近的§3.1函數(shù)逼近的基本概念問題的提出在數(shù)值計(jì)算中經(jīng)常要計(jì)算函數(shù)值，如計(jì)算機(jī)中計(jì)算基本初等函數(shù)及其它特殊函數(shù)；當(dāng)函數(shù)只在有限點(diǎn)集上給定函數(shù)值，要在包含該點(diǎn)集的區(qū)間上用公式給出函數(shù)的簡單表達(dá)式，這些都涉及在區(qū)間[a,b]上用簡單函數(shù)逼近已知復(fù)雜函數(shù)的問題，這就是函數(shù)逼近問題.第二章討論的插值法就是函數(shù)逼近的一種.2§3.1函數(shù)逼近的基本概念問題的提出2本章討論的函數(shù)逼近，是指“對函數(shù)類A中給定的函數(shù)f(x)，記作f(x)∈A，要求在另一類簡單的便于計(jì)算的函數(shù)類B中求函數(shù)p(x)∈B，使p(x)與f(x)的誤差在某種度量意義下最小”.函數(shù)類A通常是區(qū)間[a,b]上的連續(xù)函數(shù)，記作C[a,b]，稱為函數(shù)逼近空間；而函數(shù)B通常為n次多項(xiàng)式,有理函數(shù)或分段低次多項(xiàng)式等.為了在數(shù)學(xué)上描述更精確，先要介紹代數(shù)和分析中一些基本概念及預(yù)備知識。問題的提出3本章討論的函數(shù)逼近，是指“對函數(shù)類A中給定的函數(shù)f(x)，記空間定義

數(shù)學(xué)上常把在各種集合中引入某一些不同的確定關(guān)系稱為賦予集合以某種空間結(jié)構(gòu)，并將這樣的集合稱為空間。4空間定義數(shù)學(xué)上常把在各種集合中引入某一些不同空間舉例例3所有定義在[a,b]集合上的連續(xù)函數(shù)全體，按函數(shù)的加法和數(shù)乘構(gòu)成數(shù)域R上的連續(xù)函數(shù)線性空間–C[a,b],稱為連續(xù)函數(shù)空間.類似地記Cp[a,b]為具有p階連續(xù)導(dǎo)數(shù)的函數(shù)空間.例1

所有實(shí)n維向量集合，按向量的加法和數(shù)乘構(gòu)成實(shí)數(shù)域R上的線性空間---Rn,稱為n維向量空間.例2

對次數(shù)不超過n的（n為正整數(shù)）實(shí)系數(shù)多項(xiàng)式全體，按多項(xiàng)式加法和數(shù)乘構(gòu)成數(shù)域R上的多項(xiàng)式線性空間--Hn,稱為多項(xiàng)式空間.5空間舉例例3所有定義在[a,b]集合上的連續(xù)函數(shù)全體線性無關(guān)

定義1設(shè)集合S是數(shù)域P上的線性空間，元素x1,x2,…,xn∈S，如果存在不全為零的數(shù)a1,a2,…,an∈P，使得則稱x1,x2,…,xn

線性相關(guān)，否則稱x1,x2,…,xn

線性無關(guān)，即只有當(dāng)a1=a2=…=an=0時等式(3.1)才成立.

(3.1)6線性無關(guān)定義1設(shè)集合S是數(shù)域P上的線性線性空間

若線性空間S是由n個線性無關(guān)元素x1,…,xn生成的，即對任意x∈S，都有則x1,…,xn稱為空間S的一組基,記為S=span{x1,…,xn},并稱空間S為n維空間，系數(shù)a1,…,an為x在基x1,…,xn下的坐標(biāo)，記作(a1,…,an)，如果S中有無限多個線性無關(guān)元素x1,…,xn,…，則稱S為無限維線性空間.

7線性空間若線性空間S是由n個線性無關(guān)元素x1多項(xiàng)式空間

下面考慮次數(shù)不超過n實(shí)系數(shù)多項(xiàng)式集合Hn，其元素p(x)∈Hn表示為它由n+1個系數(shù)(a0,a1,…,an)唯一確定.1,x,…,xn

線性無關(guān)，它是Hn的一組基，故集合Hn=span{1,

x,…,xn}，且(a0,a1,…,an)是p(x)的坐標(biāo)向量，Hn是n+1維的.8多項(xiàng)式空間下面考慮次數(shù)不超過n實(shí)系數(shù)多項(xiàng)式集連續(xù)函數(shù)逼近

對連續(xù)函數(shù)f(x)∈C[a,b]，它不能用有限個線性無關(guān)的函數(shù)表示，故C[a,b]是無限維的，但它的任一元素f(x)∈C[a,b]均可用有限維的p(x)∈Hn逼近，使誤差其中ε為任意給的小正數(shù)，即精度要求.這就是下面著名的魏爾斯特拉斯（Weierstrass）定理.9連續(xù)函數(shù)逼近對連續(xù)函數(shù)f(x)∈C[a,b魏爾斯特拉斯定理

定理1設(shè)f(x)∈C[a,b]，則對任何ε>0，總存在一個代數(shù)多項(xiàng)式p(x)，使在[a,b]上一致成立.（證明略，見書p52有說明.）10魏爾斯特拉斯定理定理1設(shè)f(x)∈C[a伯恩斯坦多項(xiàng)式

由(3.3)式給出的Bn(f,x)也是f(x)在[0,1]上的一個逼近多項(xiàng)式，但它收斂太慢，實(shí)際中很少使用.11伯恩斯坦多項(xiàng)式由(3.3)式給出的Bn(f,x)也是f一般提法

更一般地，可用一組在C[a,b]上線性無關(guān)的函數(shù)集合

來逼近f(x)∈C[a,b]，元素表示為函數(shù)逼近問題就是對任何f(x)∈C[a,b]，在子空間中找一個元素*(x)∈，使f(x)-*(x)在某種意義下最小.12一般提法更一般地，可用一組在C[a,b]上范數(shù)與賦范線性空間

為了對線性空間中元素大小進(jìn)行衡量，需要引進(jìn)范數(shù)定義，它是Rn空間中向量長度概念的直接推廣.

定義2設(shè)S為線性空間，xS，若存在唯一實(shí)數(shù)·，滿足條件： (1)

x0;當(dāng)且僅當(dāng)x＝0時,x=0;(正定性) (2)x=||x,R;(齊次性) (3)x+yx+y,x,yS.(三角不等式) 則稱·為線性空間S上的范數(shù)，S與·一起稱為賦范線性空間，記為X.13范數(shù)與賦范線性空間為了對線性空間中元素大小進(jìn)行衡量，向量的常用范數(shù)對Rn上的向量

x＝(x1,x2,…,xn)T,

三種常用范數(shù)為：14向量的常用范數(shù)對Rn上的向量x＝(x1,x2,…,xn)T函數(shù)的常用范數(shù)

類似的對連續(xù)函數(shù)空間C[a,b],若f∈C[a,b]可定義以下三種常用函數(shù)的范數(shù)15函數(shù)的常用范數(shù)類似的對連續(xù)函數(shù)空間C[a,b],矩陣的常用范數(shù)max11=?=￡￡￥aAnjijni)=aAnij（()0)(max=-=AAEfAAAATTTmax111=?=￡￡aAniijnjlll)(max2=AAATl即的最大特征值表示其中稱為A的行范數(shù)對n階方陣稱為A的列范數(shù)稱為A的2-范數(shù)16矩陣的常用范數(shù)max11=?=￡￡￥aAnjijni)=aA例題例4計(jì)算向量x的范數(shù)，其中解

17例題例4計(jì)算向量x的范數(shù)，其中解17例題例5計(jì)算函數(shù)x2關(guān)于C[0,1]的范數(shù).解

18例題例5計(jì)算函數(shù)x2關(guān)于C[0,1]的范數(shù).解18例題例6計(jì)算矩陣A的范數(shù)，其中解

19例題例6計(jì)算矩陣A的范數(shù)，其中解19向量內(nèi)積

在線性代數(shù)中，Rn上的兩個向量

x＝(x1,x2,…,xn)T與y＝(y1,y2,…,yn)T的內(nèi)積定義為

(x,y)=x1y1+x2y2+…+xnyn.

若將它推廣到一般的線性空間X，則有下面的定義.20向量內(nèi)積在線性代數(shù)中，Rn上的兩個向量x＝內(nèi)積與內(nèi)積空間

定義3設(shè)X是數(shù)域K(R或C)上的線性空間，對任意u,v∈X，有K中一個數(shù)與之對應(yīng)，記為(u,v)，它滿足以下條件：則稱(u,v)為X上u與v的內(nèi)積，對應(yīng)了內(nèi)積的線性空間稱為內(nèi)積空間.定義中(1)當(dāng)K為實(shí)數(shù)域R時為

(u,v)＝(v,u).21內(nèi)積與內(nèi)積空間定義3設(shè)X是數(shù)域K(R向量垂直

如果(u,v)=0，則稱u與v正交(記為u⊥v)，這是向量相互垂直概念的推廣.22向量垂直如果(u,v)=0，則稱u與v正交加權(quán)內(nèi)積若給定實(shí)數(shù)wi>0(i=1,…,n)，{wi}稱為權(quán)函數(shù)，則在Rn上可定義加權(quán)內(nèi)積為

在C[a,b]上也可以類似定義帶權(quán)內(nèi)積，為此先給出權(quán)函數(shù)定義.23加權(quán)內(nèi)積若給定實(shí)數(shù)wi>0(i=1,…,n)，{wi}稱為權(quán)權(quán)函數(shù)

定義4設(shè)[a,b]是有限或無限區(qū)間，在[a,b]上的非負(fù)函數(shù)w(x)滿足條件：則稱w(x)為[a,b]上的一個權(quán)函數(shù).它的物理意義可以解釋為密度函數(shù)..0)(0)()(],[)2(o=òxgdxxxgbaba則，如果上的非負(fù)連續(xù)函數(shù)g(x)對w24權(quán)函數(shù)定義4設(shè)[a,b]是有限或無例題

例7

C[a,b]上的內(nèi)積，設(shè)f(x),g(x)∈C[a,b]，w(x)是上給定的權(quán)函數(shù)，則可內(nèi)積定義為容易驗(yàn)證它滿足內(nèi)積定義的4條，由此內(nèi)積導(dǎo)出的范數(shù)為帶權(quán)w(x)的范數(shù).25例題例7C[a,b]上的內(nèi)積，設(shè)f(x),g(最佳逼近則稱P*(x)是f(x)在[a,b]上的最佳逼近多項(xiàng)式.如果P(x)∈=span{0,1,…,n}，則稱相應(yīng)的P*(x)為最佳逼近函數(shù).函數(shù)逼近主要討論給定f(x)∈C[a,b]，求它的最佳逼近多項(xiàng)式.若P*(x)∈Hn=span{1,x,…,xn}，使誤差26最佳逼近則稱P*(x)是f(x)在[a,b]上的最佳逼近多最佳一致逼近若范數(shù)·取為·∞,即則稱P*(x)是f(x)在[a,b]上的最佳一致逼近多項(xiàng)式.這時求P*(x)就是求[a,b]上使得最大誤差最小的多項(xiàng)式.27最佳一致逼近若范數(shù)·取為·∞,即則稱P*最佳平方逼近如果范數(shù)·取為·2，即則稱P*(x)為f(x)在[a,b]上的最佳平方逼近多項(xiàng)式.28最佳平方逼近如果范數(shù)·取為·2，即則稱P最小二乘擬合若f(x)是[a,b]上的一個列表函數(shù)，在區(qū)間節(jié)點(diǎn)a≤x0<

x1<…<xm≤b上給出(xi)(i=0,1,…,m)，要求P*(x)∈使本章將著重討論實(shí)際應(yīng)用多便于計(jì)算的最佳平方逼近與最小二乘擬合.則稱P*(x)為f(x)在[a,b]上的最小二乘擬合.29最小二乘擬合若f(x)是[a,b]上的一個列表函數(shù)，在§3.2正交多項(xiàng)式略30§3.2正交多項(xiàng)式略30§3.3最佳平方逼近略31§3.3最佳平方逼近略31§3.4曲線擬合的最小二乘法問題的提出某種合成纖維的強(qiáng)度與其拉伸倍數(shù)有直接關(guān)系，下表是實(shí)際測定的24個纖維樣品的強(qiáng)度與相應(yīng)拉伸倍數(shù)的記錄。提示：將拉伸倍數(shù)作為x,強(qiáng)度作為y,在座標(biāo)紙上標(biāo)出各點(diǎn)，可以發(fā)現(xiàn)什么?32§3.4曲線擬合的最小二乘法問題的提出32數(shù)據(jù)表格33數(shù)據(jù)表格33數(shù)據(jù)圖34數(shù)據(jù)圖34曲線擬合

已知的離散數(shù)據(jù)yi=f(xi)(i=0,1,2,…,n)往往是通過觀測而得到的，經(jīng)常帶有觀測誤差。曲線擬合：希望找到—條曲線，它既能反映結(jié)定數(shù)據(jù)的總體分布形式，又不致于出現(xiàn)局部較大的波動。這種逼近方式．只要所構(gòu)造的逼近函數(shù)(x)與被逼近函數(shù)f(x)在區(qū)間[a,b]上的偏差滿足其種要求即可。35曲線擬合已知的離散數(shù)據(jù)yi=f(xi)(i=偏差

設(shè)給定數(shù)據(jù)點(diǎn)(xi,yi),(i=0,1,2,…,n),記并稱ei為偏差。36偏差設(shè)給定數(shù)據(jù)點(diǎn)(xi,yi),(i=0,最小二乘法曲線擬合的最小二乘法：以使得偏差的平方和最小為標(biāo)難37最小二乘法曲線擬合的最小二乘法：以使得偏差的平方和37線性最小二乘擬合假設(shè)所給的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)的分布大致呈直線，故可選擇線性函數(shù)作擬合曲線。【問題1】對于給定的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)，求作一次式y(tǒng)＝a+bx，使總誤差為最小。38線性最小二乘擬合假設(shè)所給的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,線性最小二乘擬合（續(xù)）【解】由微積分的知識可知，這一問題的求解，可歸結(jié)為求二元函數(shù)E(a,b)的極值，即39線性最小二乘擬合（續(xù)）【解】由微積分的知識可知，這一問題的求線性最小二乘擬合（續(xù)）這是關(guān)于a,b的線性方程組，稱為法方程。4040線性最小二乘擬合（續(xù)）這是關(guān)于a,b的線性方程組，稱為法方程多項(xiàng)式最小二乘擬合有時所給數(shù)據(jù)點(diǎn)的分布并不一定近似地呈一條直線，這時若仍用直線似合顯然是不合適的。對于這種情況，可以考慮用多項(xiàng)式擬合。【問題2】對于給定的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)，求作多項(xiàng)式，使總誤差為最小。41多項(xiàng)式最小二乘擬合有時所給數(shù)據(jù)點(diǎn)的分布并不一定近似地呈一條直多項(xiàng)式最小二乘擬合（續(xù)）【解】由微積分的知識可知，這一問題的求解，可歸結(jié)為求二元函數(shù)E(a0,a1,…,am)的極值，即42多項(xiàng)式最小二乘擬合（續(xù)）【解】由微積分的知識可知，這一問題的多項(xiàng)式最小二乘擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性力程組，稱為法方程。43多項(xiàng)式最小二乘擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性例題例8某合金成分x與膨脹系數(shù)y之間的關(guān)系有如下實(shí)驗(yàn)數(shù)據(jù)，求膨脹系數(shù)y與成分x的擬合曲線y=P(x)。i0123456x37383940414243y3.403.002.101.531.801.902.9044例題例8某合金成分x與膨脹系數(shù)y之間的關(guān)系有如下實(shí)驗(yàn)數(shù)例題解將數(shù)據(jù)標(biāo)在坐標(biāo)紙上，由散點(diǎn)圖可以推斷他們大致分布在一條拋物線上。為此取45例題解將數(shù)據(jù)標(biāo)在坐標(biāo)紙上，由散點(diǎn)圖可以45例題法方程46例題法方程46例題代入數(shù)據(jù)后得解得于是所求擬合曲線為47例題代入數(shù)據(jù)后得解得于是所求擬合曲線為47其他函數(shù)曲線擬合最小二乘法并不只限于多項(xiàng)式，也可以用任何具體給出的函數(shù)形式。即可取【問題3】對于給定的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)，求作曲線，使總誤差為最小。48其他函數(shù)曲線擬合最小二乘法并不只限于多項(xiàng)式，也可以用任何具【其他函數(shù)曲線擬合（續(xù)）【解】由微積分的知識可知，這一問題的求解，可歸結(jié)為求二元函數(shù)E(a0,a1,…,am)的極值，即49其他函數(shù)曲線擬合（續(xù)）【解】由微積分的知識可知，這一問題的求其他函數(shù)曲線擬合（續(xù)）引進(jìn)內(nèi)積記號50其他函數(shù)曲線擬合（續(xù)）引進(jìn)內(nèi)積記號50其他函數(shù)曲線擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性方程組，稱為法方程。51其他函數(shù)曲線擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性方例題例9對例8中的數(shù)據(jù)，試求形如的擬合函數(shù)。解取擬合函數(shù)系52例題例9對例8中的數(shù)據(jù)，試求形如的擬合函數(shù)。解取例題53得法方程解出因此所求的擬合函數(shù)為53例題53得法方程解出因此所求的擬合函數(shù)為53正交多項(xiàng)式最小二乘擬合

普通多項(xiàng)式作最小二乘擬合時，其法方程是病態(tài)的。為了避免解病態(tài)方程組，通常用正交多項(xiàng)式作最小二乘擬合。

54正交多項(xiàng)式最小二乘擬合普通多項(xiàng)式作最小二乘擬合時正交多項(xiàng)式正交多項(xiàng)式：對給定點(diǎn)集

及權(quán)函數(shù)如果函數(shù)系滿足則稱函數(shù)系帶權(quán)函數(shù)關(guān)于點(diǎn)集正交。55正交多項(xiàng)式正交多項(xiàng)式：對給定點(diǎn)集及權(quán)函數(shù)如果函數(shù)系滿足則法方程56代替現(xiàn)在以，并利用的正交性，則法方程（3.4）成為對角型方程組（3.5）56法方程56代替現(xiàn)在以，并利用的正交性，則法方程（3.4）成為廣義多項(xiàng)式其解為于是所求的擬合函數(shù)（稱為廣義多項(xiàng)式）為誤差為57廣義多項(xiàng)式其解為于是所求的擬合函數(shù)（稱為廣義多項(xiàng)式）為誤差為正交多項(xiàng)式遞推公式推導(dǎo)設(shè)式（3.7）中的正交函數(shù)系系數(shù)為1的正交多項(xiàng)式系。正交多項(xiàng)式的一個基本性質(zhì)是能夠通過遞推關(guān)系逐個生成。事實(shí)上，任何一個k次多項(xiàng)式能表示成正交多項(xiàng)式的線性組合，于是成立，其中是特定參數(shù)。以為最高次項(xiàng)對式（3.9）兩邊作內(nèi)積58正交多項(xiàng)式遞推公式推導(dǎo)設(shè)式（3.7）中的正交函正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）即由于次數(shù)小于k，可寫成代入上式，并利用正交性，得59正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）即由于次數(shù)小于k，可寫成代入上式正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對式（3.9）兩邊內(nèi)積即可寫成代入上式，并利用正交性，得60正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對式（3.9）兩邊內(nèi)積即可寫成正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對式（3.9）兩邊作內(nèi)積，得將的表達(dá)式，代入式（3.9），得61正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對式（3.9）兩邊作內(nèi)積，得將正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）若記62正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）若記62正交多項(xiàng)式遞推公式則得遞推公式63正交多項(xiàng)式遞推公式則得遞推公式63誤差遞推關(guān)系另外，誤差的遞推關(guān)系也不難得到。由式（3.8）可得由式（3.7）和（3.8）可得64誤差遞推關(guān)系另外，誤差的遞推關(guān)系也不難得到。由式（3.8）可例題例10利用正交多項(xiàng)式對例8中的數(shù)據(jù)作二次擬合。解按遞推公式（3.10）計(jì)算權(quán)函數(shù)為1的正交多項(xiàng)式按公式（3.6）計(jì)算廣義多項(xiàng)式系數(shù)65例題例10利用正交多項(xiàng)式對例8中的數(shù)據(jù)作二次擬合。按公例題代入式（3.7）中，得到所求的二次函數(shù)66例題代入式（3.7）中，得到所求的二次函數(shù)66非線性最小二乘擬合兩邊取對數(shù)，得則得令兩邊取自然對數(shù)，得令則得（1）（2）67非線性最小二乘擬合兩邊取對數(shù)，得則得令兩邊取自然對數(shù)，得令則非線性最小二乘擬合（續(xù)）（3）兩邊取對數(shù)，得則得令令則得（4）68非線性最小二乘擬合（續(xù)）（3）兩邊取對數(shù)，得則得令令則得（4非線性最小二乘擬合（續(xù)）令則得（6）令則得（5）69非線性最小二乘擬合（續(xù)）令則得（6）令則得（5）69例題例11給定實(shí)驗(yàn)數(shù)據(jù)x1.001.251.501.752.00y5.105.796.537.458.46試求形如的擬合函數(shù)。解對擬合函數(shù)的兩邊取自然對數(shù)，即令則上式成為關(guān)于A，b的線性函數(shù)70例題例11給定實(shí)驗(yàn)數(shù)據(jù)x1.001.251.50例題根據(jù)數(shù)據(jù)(x,y)算出對應(yīng)的(z,w),得下表z1.001.251.501.752.00w1.62921.75611.87642.00822.1353建立法方程解得因此，所求的擬合函數(shù)為71例題根據(jù)數(shù)據(jù)(x,y)算出對應(yīng)的(z,w),得線性矛盾方程組方程個數(shù)大于未知量個數(shù)的方程組稱為矛盾方程組，一般形式為即72線性矛盾方程組方程個數(shù)大于未知量個數(shù)的方程組稱為矛盾方程組，線性矛盾方程組（續(xù)）

Ax＝b

A是n×m階的列滿秩矩陣,x是m維的列向量,b是n維的列向量,剩余向量（3.11）（3.12）73線性矛盾方程組（續(xù)）線性矛盾方程組（續(xù)）由于A的m個列向量線性無關(guān)，易知是m×m階對稱正定矩陣，而且上式右端最后一項(xiàng)是正定二次型，同時其它兩項(xiàng)與x無關(guān)。因此，欲使式（3.12）成立，必須有74線性矛盾方程組（續(xù)）由于A的m個列向量線性無關(guān)，易知是m×m線性矛盾方程組（續(xù)）該式稱為方程組Ax＝b的法方程。因此，求解n階矛盾方程組的問題轉(zhuǎn)化求解m階線性方程組的問題。75線性矛盾方程組（續(xù)）該式稱為方程組Ax＝b的法方程。因此，例題例12利用解線性矛盾方程組對例8中的數(shù)據(jù)作二次擬合，。解：按題意，得矛盾方程組，i0123456x37383940414243y3.403.002.101.531.801.902.9076例題例12利用解線性矛盾方程組對例8中的數(shù)據(jù)作二次擬合例題寫成矩陣形式，為其中

77例題寫成矩陣形式，為其中77例題其法方程為即78例題其法方程為78例題解得于是所求擬合曲線為79例題解得于是所求擬合曲線為79例題例13已知觀測數(shù)據(jù)(1，-5)，(2，0)，(4，5)，(5，6)，試用最小二乘法求形如上的經(jīng)驗(yàn)公式。80例題例13已知觀測數(shù)據(jù)(1，-5)，(2，0)，(4，5例題81解：記按題意，得矛盾方程組，寫成矩陣形式，為81例題81解：記81例題寫成矩陣形式，為其中

82例題寫成矩陣形式，為其中82例題其法方程為即83其法方程為即解得

于是所求擬合曲線為83例題其法方程為83其法方程為83§3.5有理逼近略84§3.5有理逼近略84§3.6三角逼近與快速傅里葉變換略85§3.6三角逼近與快速傅里葉變換略85本章小結(jié)最小二乘法曲線擬和是實(shí)驗(yàn)數(shù)據(jù)處理的常用方法。但當(dāng)正規(guī)方程階數(shù)較高時，往往出現(xiàn)病態(tài)。因此必須謹(jǐn)慎對待和加以巧妙處理。有效方法之一是引入正交多項(xiàng)式以改善其病態(tài)性。86本章小結(jié)最小二乘法曲線擬和是實(shí)驗(yàn)數(shù)據(jù)處理的常用方法。但當(dāng)正本章習(xí)題作業(yè)P94-953,16,17,1887本章習(xí)題87本章結(jié)束88本章結(jié)束88

第3章函數(shù)逼近與快速傅里葉變換§3.1函數(shù)逼近的基本概念§3.2正交多項(xiàng)式§3.3最佳平方逼近§3.4曲線擬合的最小二乘法§3.5有理逼近§3.6三角逼近與快速傅里葉變換89第3章函數(shù)逼近與快速傅里葉變換§3.1函數(shù)逼近的§3.1函數(shù)逼近的基本概念問題的提出在數(shù)值計(jì)算中經(jīng)常要計(jì)算函數(shù)值，如計(jì)算機(jī)中計(jì)算基本初等函數(shù)及其它特殊函數(shù)；當(dāng)函數(shù)只在有限點(diǎn)集上給定函數(shù)值，要在包含該點(diǎn)集的區(qū)間上用公式給出函數(shù)的簡單表達(dá)式，這些都涉及在區(qū)間[a,b]上用簡單函數(shù)逼近已知復(fù)雜函數(shù)的問題，這就是函數(shù)逼近問題.第二章討論的插值法就是函數(shù)逼近的一種.90§3.1函數(shù)逼近的基本概念問題的提出2本章討論的函數(shù)逼近，是指“對函數(shù)類A中給定的函數(shù)f(x)，記作f(x)∈A，要求在另一類簡單的便于計(jì)算的函數(shù)類B中求函數(shù)p(x)∈B，使p(x)與f(x)的誤差在某種度量意義下最小”.函數(shù)類A通常是區(qū)間[a,b]上的連續(xù)函數(shù)，記作C[a,b]，稱為函數(shù)逼近空間；而函數(shù)B通常為n次多項(xiàng)式,有理函數(shù)或分段低次多項(xiàng)式等.為了在數(shù)學(xué)上描述更精確，先要介紹代數(shù)和分析中一些基本概念及預(yù)備知識。問題的提出91本章討論的函數(shù)逼近，是指“對函數(shù)類A中給定的函數(shù)f(x)，記空間定義

數(shù)學(xué)上常把在各種集合中引入某一些不同的確定關(guān)系稱為賦予集合以某種空間結(jié)構(gòu)，并將這樣的集合稱為空間。92空間定義數(shù)學(xué)上常把在各種集合中引入某一些不同空間舉例例3所有定義在[a,b]集合上的連續(xù)函數(shù)全體，按函數(shù)的加法和數(shù)乘構(gòu)成數(shù)域R上的連續(xù)函數(shù)線性空間–C[a,b],稱為連續(xù)函數(shù)空間.類似地記Cp[a,b]為具有p階連續(xù)導(dǎo)數(shù)的函數(shù)空間.例1

所有實(shí)n維向量集合，按向量的加法和數(shù)乘構(gòu)成實(shí)數(shù)域R上的線性空間---Rn,稱為n維向量空間.例2

對次數(shù)不超過n的（n為正整數(shù)）實(shí)系數(shù)多項(xiàng)式全體，按多項(xiàng)式加法和數(shù)乘構(gòu)成數(shù)域R上的多項(xiàng)式線性空間--Hn,稱為多項(xiàng)式空間.93空間舉例例3所有定義在[a,b]集合上的連續(xù)函數(shù)全體線性無關(guān)

定義1設(shè)集合S是數(shù)域P上的線性空間，元素x1,x2,…,xn∈S，如果存在不全為零的數(shù)a1,a2,…,an∈P，使得則稱x1,x2,…,xn

線性相關(guān)，否則稱x1,x2,…,xn

線性無關(guān)，即只有當(dāng)a1=a2=…=an=0時等式(3.1)才成立.

(3.1)94線性無關(guān)定義1設(shè)集合S是數(shù)域P上的線性線性空間

若線性空間S是由n個線性無關(guān)元素x1,…,xn生成的，即對任意x∈S，都有則x1,…,xn稱為空間S的一組基,記為S=span{x1,…,xn},并稱空間S為n維空間，系數(shù)a1,…,an為x在基x1,…,xn下的坐標(biāo)，記作(a1,…,an)，如果S中有無限多個線性無關(guān)元素x1,…,xn,…，則稱S為無限維線性空間.

95線性空間若線性空間S是由n個線性無關(guān)元素x1多項(xiàng)式空間

下面考慮次數(shù)不超過n實(shí)系數(shù)多項(xiàng)式集合Hn，其元素p(x)∈Hn表示為它由n+1個系數(shù)(a0,a1,…,an)唯一確定.1,x,…,xn

線性無關(guān)，它是Hn的一組基，故集合Hn=span{1,

x,…,xn}，且(a0,a1,…,an)是p(x)的坐標(biāo)向量，Hn是n+1維的.96多項(xiàng)式空間下面考慮次數(shù)不超過n實(shí)系數(shù)多項(xiàng)式集連續(xù)函數(shù)逼近

對連續(xù)函數(shù)f(x)∈C[a,b]，它不能用有限個線性無關(guān)的函數(shù)表示，故C[a,b]是無限維的，但它的任一元素f(x)∈C[a,b]均可用有限維的p(x)∈Hn逼近，使誤差其中ε為任意給的小正數(shù)，即精度要求.這就是下面著名的魏爾斯特拉斯（Weierstrass）定理.97連續(xù)函數(shù)逼近對連續(xù)函數(shù)f(x)∈C[a,b魏爾斯特拉斯定理

定理1設(shè)f(x)∈C[a,b]，則對任何ε>0，總存在一個代數(shù)多項(xiàng)式p(x)，使在[a,b]上一致成立.（證明略，見書p52有說明.）98魏爾斯特拉斯定理定理1設(shè)f(x)∈C[a伯恩斯坦多項(xiàng)式

由(3.3)式給出的Bn(f,x)也是f(x)在[0,1]上的一個逼近多項(xiàng)式，但它收斂太慢，實(shí)際中很少使用.99伯恩斯坦多項(xiàng)式由(3.3)式給出的Bn(f,x)也是f一般提法

更一般地，可用一組在C[a,b]上線性無關(guān)的函數(shù)集合

來逼近f(x)∈C[a,b]，元素表示為函數(shù)逼近問題就是對任何f(x)∈C[a,b]，在子空間中找一個元素*(x)∈，使f(x)-*(x)在某種意義下最小.100一般提法更一般地，可用一組在C[a,b]上范數(shù)與賦范線性空間

為了對線性空間中元素大小進(jìn)行衡量，需要引進(jìn)范數(shù)定義，它是Rn空間中向量長度概念的直接推廣.

定義2設(shè)S為線性空間，xS，若存在唯一實(shí)數(shù)·，滿足條件： (1)

x0;當(dāng)且僅當(dāng)x＝0時,x=0;(正定性) (2)x=||x,R;(齊次性) (3)x+yx+y,x,yS.(三角不等式) 則稱·為線性空間S上的范數(shù)，S與·一起稱為賦范線性空間，記為X.101范數(shù)與賦范線性空間為了對線性空間中元素大小進(jìn)行衡量，向量的常用范數(shù)對Rn上的向量

x＝(x1,x2,…,xn)T,

三種常用范數(shù)為：102向量的常用范數(shù)對Rn上的向量x＝(x1,x2,…,xn)T函數(shù)的常用范數(shù)

類似的對連續(xù)函數(shù)空間C[a,b],若f∈C[a,b]可定義以下三種常用函數(shù)的范數(shù)103函數(shù)的常用范數(shù)類似的對連續(xù)函數(shù)空間C[a,b],矩陣的常用范數(shù)max11=?=￡￡￥aAnjijni)=aAnij（()0)(max=-=AAEfAAAATTTmax111=?=￡￡aAniijnjlll)(max2=AAATl即的最大特征值表示其中稱為A的行范數(shù)對n階方陣稱為A的列范數(shù)稱為A的2-范數(shù)104矩陣的常用范數(shù)max11=?=￡￡￥aAnjijni)=aA例題例4計(jì)算向量x的范數(shù)，其中解

105例題例4計(jì)算向量x的范數(shù)，其中解17例題例5計(jì)算函數(shù)x2關(guān)于C[0,1]的范數(shù).解

106例題例5計(jì)算函數(shù)x2關(guān)于C[0,1]的范數(shù).解18例題例6計(jì)算矩陣A的范數(shù)，其中解

107例題例6計(jì)算矩陣A的范數(shù)，其中解19向量內(nèi)積

在線性代數(shù)中，Rn上的兩個向量

x＝(x1,x2,…,xn)T與y＝(y1,y2,…,yn)T的內(nèi)積定義為

(x,y)=x1y1+x2y2+…+xnyn.

若將它推廣到一般的線性空間X，則有下面的定義.108向量內(nèi)積在線性代數(shù)中，Rn上的兩個向量x＝內(nèi)積與內(nèi)積空間

定義3設(shè)X是數(shù)域K(R或C)上的線性空間，對任意u,v∈X，有K中一個數(shù)與之對應(yīng)，記為(u,v)，它滿足以下條件：則稱(u,v)為X上u與v的內(nèi)積，對應(yīng)了內(nèi)積的線性空間稱為內(nèi)積空間.定義中(1)當(dāng)K為實(shí)數(shù)域R時為

(u,v)＝(v,u).109內(nèi)積與內(nèi)積空間定義3設(shè)X是數(shù)域K(R向量垂直

如果(u,v)=0，則稱u與v正交(記為u⊥v)，這是向量相互垂直概念的推廣.110向量垂直如果(u,v)=0，則稱u與v正交加權(quán)內(nèi)積若給定實(shí)數(shù)wi>0(i=1,…,n)，{wi}稱為權(quán)函數(shù)，則在Rn上可定義加權(quán)內(nèi)積為

在C[a,b]上也可以類似定義帶權(quán)內(nèi)積，為此先給出權(quán)函數(shù)定義.111加權(quán)內(nèi)積若給定實(shí)數(shù)wi>0(i=1,…,n)，{wi}稱為權(quán)權(quán)函數(shù)

定義4設(shè)[a,b]是有限或無限區(qū)間，在[a,b]上的非負(fù)函數(shù)w(x)滿足條件：則稱w(x)為[a,b]上的一個權(quán)函數(shù).它的物理意義可以解釋為密度函數(shù)..0)(0)()(],[)2(o=òxgdxxxgbaba則，如果上的非負(fù)連續(xù)函數(shù)g(x)對w112權(quán)函數(shù)定義4設(shè)[a,b]是有限或無例題

例7

C[a,b]上的內(nèi)積，設(shè)f(x),g(x)∈C[a,b]，w(x)是上給定的權(quán)函數(shù)，則可內(nèi)積定義為容易驗(yàn)證它滿足內(nèi)積定義的4條，由此內(nèi)積導(dǎo)出的范數(shù)為帶權(quán)w(x)的范數(shù).113例題例7C[a,b]上的內(nèi)積，設(shè)f(x),g(最佳逼近則稱P*(x)是f(x)在[a,b]上的最佳逼近多項(xiàng)式.如果P(x)∈=span{0,1,…,n}，則稱相應(yīng)的P*(x)為最佳逼近函數(shù).函數(shù)逼近主要討論給定f(x)∈C[a,b]，求它的最佳逼近多項(xiàng)式.若P*(x)∈Hn=span{1,x,…,xn}，使誤差114最佳逼近則稱P*(x)是f(x)在[a,b]上的最佳逼近多最佳一致逼近若范數(shù)·取為·∞,即則稱P*(x)是f(x)在[a,b]上的最佳一致逼近多項(xiàng)式.這時求P*(x)就是求[a,b]上使得最大誤差最小的多項(xiàng)式.115最佳一致逼近若范數(shù)·取為·∞,即則稱P*最佳平方逼近如果范數(shù)·取為·2，即則稱P*(x)為f(x)在[a,b]上的最佳平方逼近多項(xiàng)式.116最佳平方逼近如果范數(shù)·取為·2，即則稱P最小二乘擬合若f(x)是[a,b]上的一個列表函數(shù)，在區(qū)間節(jié)點(diǎn)a≤x0<

x1<…<xm≤b上給出(xi)(i=0,1,…,m)，要求P*(x)∈使本章將著重討論實(shí)際應(yīng)用多便于計(jì)算的最佳平方逼近與最小二乘擬合.則稱P*(x)為f(x)在[a,b]上的最小二乘擬合.117最小二乘擬合若f(x)是[a,b]上的一個列表函數(shù)，在§3.2正交多項(xiàng)式略118§3.2正交多項(xiàng)式略30§3.3最佳平方逼近略119§3.3最佳平方逼近略31§3.4曲線擬合的最小二乘法問題的提出某種合成纖維的強(qiáng)度與其拉伸倍數(shù)有直接關(guān)系，下表是實(shí)際測定的24個纖維樣品的強(qiáng)度與相應(yīng)拉伸倍數(shù)的記錄。提示：將拉伸倍數(shù)作為x,強(qiáng)度作為y,在座標(biāo)紙上標(biāo)出各點(diǎn)，可以發(fā)現(xiàn)什么?120§3.4曲線擬合的最小二乘法問題的提出32數(shù)據(jù)表格121數(shù)據(jù)表格33數(shù)據(jù)圖122數(shù)據(jù)圖34曲線擬合

已知的離散數(shù)據(jù)yi=f(xi)(i=0,1,2,…,n)往往是通過觀測而得到的，經(jīng)常帶有觀測誤差。曲線擬合：希望找到—條曲線，它既能反映結(jié)定數(shù)據(jù)的總體分布形式，又不致于出現(xiàn)局部較大的波動。這種逼近方式．只要所構(gòu)造的逼近函數(shù)(x)與被逼近函數(shù)f(x)在區(qū)間[a,b]上的偏差滿足其種要求即可。123曲線擬合已知的離散數(shù)據(jù)yi=f(xi)(i=偏差

設(shè)給定數(shù)據(jù)點(diǎn)(xi,yi),(i=0,1,2,…,n),記并稱ei為偏差。124偏差設(shè)給定數(shù)據(jù)點(diǎn)(xi,yi),(i=0,最小二乘法曲線擬合的最小二乘法：以使得偏差的平方和最小為標(biāo)難125最小二乘法曲線擬合的最小二乘法：以使得偏差的平方和37線性最小二乘擬合假設(shè)所給的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)的分布大致呈直線，故可選擇線性函數(shù)作擬合曲線。【問題1】對于給定的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)，求作一次式y(tǒng)＝a+bx，使總誤差為最小。126線性最小二乘擬合假設(shè)所給的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,線性最小二乘擬合（續(xù)）【解】由微積分的知識可知，這一問題的求解，可歸結(jié)為求二元函數(shù)E(a,b)的極值，即127線性最小二乘擬合（續(xù)）【解】由微積分的知識可知，這一問題的求線性最小二乘擬合（續(xù)）這是關(guān)于a,b的線性方程組，稱為法方程。128128線性最小二乘擬合（續(xù)）這是關(guān)于a,b的線性方程組，稱為法方程多項(xiàng)式最小二乘擬合有時所給數(shù)據(jù)點(diǎn)的分布并不一定近似地呈一條直線，這時若仍用直線似合顯然是不合適的。對于這種情況，可以考慮用多項(xiàng)式擬合。【問題2】對于給定的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)，求作多項(xiàng)式，使總誤差為最小。129多項(xiàng)式最小二乘擬合有時所給數(shù)據(jù)點(diǎn)的分布并不一定近似地呈一條直多項(xiàng)式最小二乘擬合（續(xù)）【解】由微積分的知識可知，這一問題的求解，可歸結(jié)為求二元函數(shù)E(a0,a1,…,am)的極值，即130多項(xiàng)式最小二乘擬合（續(xù)）【解】由微積分的知識可知，這一問題的多項(xiàng)式最小二乘擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性力程組，稱為法方程。131多項(xiàng)式最小二乘擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性例題例8某合金成分x與膨脹系數(shù)y之間的關(guān)系有如下實(shí)驗(yàn)數(shù)據(jù)，求膨脹系數(shù)y與成分x的擬合曲線y=P(x)。i0123456x37383940414243y3.403.002.101.531.801.902.90132例題例8某合金成分x與膨脹系數(shù)y之間的關(guān)系有如下實(shí)驗(yàn)數(shù)例題解將數(shù)據(jù)標(biāo)在坐標(biāo)紙上，由散點(diǎn)圖可以推斷他們大致分布在一條拋物線上。為此取133例題解將數(shù)據(jù)標(biāo)在坐標(biāo)紙上，由散點(diǎn)圖可以45例題法方程134例題法方程46例題代入數(shù)據(jù)后得解得于是所求擬合曲線為135例題代入數(shù)據(jù)后得解得于是所求擬合曲線為47其他函數(shù)曲線擬合最小二乘法并不只限于多項(xiàng)式，也可以用任何具體給出的函數(shù)形式。即可取【問題3】對于給定的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)，求作曲線，使總誤差為最小。136其他函數(shù)曲線擬合最小二乘法并不只限于多項(xiàng)式，也可以用任何具【其他函數(shù)曲線擬合（續(xù)）【解】由微積分的知識可知，這一問題的求解，可歸結(jié)為求二元函數(shù)E(a0,a1,…,am)的極值，即137其他函數(shù)曲線擬合（續(xù)）【解】由微積分的知識可知，這一問題的求其他函數(shù)曲線擬合（續(xù)）引進(jìn)內(nèi)積記號138其他函數(shù)曲線擬合（續(xù)）引進(jìn)內(nèi)積記號50其他函數(shù)曲線擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性方程組，稱為法方程。139其他函數(shù)曲線擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性方例題例9對例8中的數(shù)據(jù)，試求形如的擬合函數(shù)。解取擬合函數(shù)系140例題例9對例8中的數(shù)據(jù)，試求形如的擬合函數(shù)。解取例題141得法方程解出因此所求的擬合函數(shù)為141例題53得法方程解出因此所求的擬合函數(shù)為53正交多項(xiàng)式最小二乘擬合

普通多項(xiàng)式作最小二乘擬合時，其法方程是病態(tài)的。為了避免解病態(tài)方程組，通常用正交多項(xiàng)式作最小二乘擬合。

142正交多項(xiàng)式最小二乘擬合普通多項(xiàng)式作最小二乘擬合時正交多項(xiàng)式正交多項(xiàng)式：對給定點(diǎn)集

及權(quán)函數(shù)如果函數(shù)系滿足則稱函數(shù)系帶權(quán)函數(shù)關(guān)于點(diǎn)集正交。143正交多項(xiàng)式正交多項(xiàng)式：對給定點(diǎn)集及權(quán)函數(shù)如果函數(shù)系滿足則法方程144代替現(xiàn)在以，并利用的正交性，則法方程（3.4）成為對角型方程組（3.5）144法方程56代替現(xiàn)在以，并利用的正交性，則法方程（3.4）成為廣義多項(xiàng)式其解為于是所求的擬合函數(shù)（稱為廣義多項(xiàng)式）為誤差為145廣義多項(xiàng)式其解為于是所求的擬合函數(shù)（稱為廣義多項(xiàng)式）為誤差為正交多項(xiàng)式遞推公式推導(dǎo)設(shè)式（3.7）中的正交函數(shù)系系數(shù)為1的正交多項(xiàng)式系。正交多項(xiàng)式的一個基本性質(zhì)是能夠通過遞推關(guān)系逐個生成。事實(shí)上，任何一個k次多項(xiàng)式能表示成正交多項(xiàng)式的線性組合，于是成立，其中是特定參數(shù)。以為最高次項(xiàng)對式（3.9）兩邊作內(nèi)積146正交多項(xiàng)式遞推公式推導(dǎo)設(shè)式（3.7）中的正交函正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）即由于次數(shù)小于k，可寫成代入上式，并利用正交性，得147正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）即由于次數(shù)小于k，可寫成代入上式正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對式（3.9）兩邊內(nèi)積即可寫成代入上式，并利用正交性，得148正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對式（3.9）兩邊內(nèi)積即可寫成正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對式（3.9）兩邊作內(nèi)積，得將的表達(dá)式，代入式（3.9），得149正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對式（3.9）兩邊作內(nèi)積，得將正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）若記