計(jì)算方法課件第三章

1

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

數(shù)學(xué)上常把在各種集合中引入某一些不同的確定關(guān)系稱(chēng)為賦予集合以某種空間結(jié)構(gòu)，并將這樣的集合稱(chēng)為空間。5空間舉例例3

所有定義在[a,b]集合上的連續(xù)函數(shù)全體，按函數(shù)的加法和數(shù)乘構(gòu)成數(shù)域R上的連續(xù)函數(shù)線性空間–

C[a,b],稱(chēng)為連續(xù)函數(shù)空間.類(lèi)似地記Cp[a,b]為具有p階連續(xù)導(dǎo)數(shù)的函數(shù)空間.例1

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

對(duì)次數(shù)不超過(guò)n的（n為正整數(shù)）實(shí)系數(shù)多項(xiàng)式全體，按多項(xiàng)式加法和數(shù)乘構(gòu)成數(shù)域R上的多項(xiàng)式線性空間--Hn,稱(chēng)為多項(xiàng)式空間.6線性無(wú)關(guān)

定義1

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

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

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

(3.1)7線性空間

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

8多項(xiàng)式空間

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

線性無(wú)關(guān)，它是Hn的一組基，故集合

Hn=span{1,

x,…,xn}，且(a0,a1,…,an)是p(x)的坐標(biāo)向量，Hn是n+1維的.9連續(xù)函數(shù)逼近

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

定理1

設(shè)f(x)∈C[a,b]，則對(duì)任何ε>0，總存在一個(gè)代數(shù)多項(xiàng)式p(x)

，使在[a,b]上一致成立.（證明略，見(jiàn)書(shū)p52有說(shuō)明.）11伯恩斯坦多項(xiàng)式

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

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

來(lái)逼近f(x)∈C[a,b]，元素表示為

函數(shù)逼近問(wèn)題就是對(duì)任何f(x)∈C[a,b]，在子空間中找一個(gè)元素*(x)∈，使f(x)-*(x)在某種意義下最小.13范數(shù)與賦范線性空間

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

定義2

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

(1)

x0;當(dāng)且僅當(dāng)x＝0時(shí),x=0;(正定性) (2)x=||x,R;(齊次性) (3)x+yx+y,x,yS.(三角不等式)

則稱(chēng)·為線性空間S上的范數(shù)，S與·一起稱(chēng)為賦范線性空間，記為X.14向量的常用范數(shù)對(duì)Rn上的向量

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

三種常用范數(shù)為：15函數(shù)的常用范數(shù)

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

計(jì)算向量x的范數(shù)，其中解

18例題例5

計(jì)算函數(shù)x2關(guān)于C[0,1]的范數(shù).解

19例題例6

計(jì)算矩陣A的范數(shù)，其中解

20向量?jī)?nèi)積

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

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

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

若將它推廣到一般的線性空間X，則有下面的定義.21內(nèi)積與內(nèi)積空間

定義3

設(shè)X是數(shù)域K(R或C)上的線性空間，對(duì)任意u,v∈X，有K中一個(gè)數(shù)與之對(duì)應(yīng)，記為(u,v)，它滿(mǎn)足以下條件：則稱(chēng)(u,v)

為X上u與v的內(nèi)積，對(duì)應(yīng)了內(nèi)積的線性空間稱(chēng)為內(nèi)積空間.定義中(1)當(dāng)K為實(shí)數(shù)域R時(shí)為

(u,v)＝(v,u).22向量垂直

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

在C[a,b]上也可以類(lèi)似定義帶權(quán)內(nèi)積，為此先給出權(quán)函數(shù)定義.24權(quán)函數(shù)

定義4

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

例7

C[a,b]上的內(nèi)積，設(shè)f(x),g(x)∈C[a,b]，w(x)是上給定的權(quán)函數(shù)，則可內(nèi)積定義為容易驗(yàn)證它滿(mǎn)足內(nèi)積定義的4條，由此內(nèi)積導(dǎo)出的范數(shù)為帶權(quán)w(x)的范數(shù).26最佳逼近則稱(chēng)P*(x)是f(x)在[a,b]上的最佳逼近多項(xiàng)式.如果P(x)∈=span{0,1,…,n}，則稱(chēng)相應(yīng)的P*(x)為最佳逼近函數(shù).函數(shù)逼近主要討論給定f(x)∈C[a,b]，求它的最佳逼近多項(xiàng)式.若P*(x)∈Hn=span{1,x,…,xn}，使誤差27最佳一致逼近若范數(shù)·取為·∞,即則稱(chēng)P*(x)是f(x)在[a,b]上的最佳一致逼近多項(xiàng)式.這時(shí)求P*(x)就是求[a,b]上使得最大誤差最小的多項(xiàng)式.

28最佳平方逼近如果范數(shù)·取為·2，即則稱(chēng)P*(x)為f(x)在[a,b]上的最佳平方逼近多項(xiàng)式.

29最小二乘擬合若f(x)是[a,b]上的一個(gè)列表函數(shù)，在區(qū)間節(jié)點(diǎn)a≤x0<

x1<…<xm≤b上給出(xi)(i=0,1,…,m)，要求P*(x)∈使本章將著重討論實(shí)際應(yīng)用多便于計(jì)算的最佳平方逼近與最小二乘擬合.則稱(chēng)P*(x)為f(x)在[a,b]上的最小二乘擬合.

30§3.2正交多項(xiàng)式略31§3.3最佳平方逼近略32§3.4曲線擬合的最小二乘法問(wèn)題的提出某種合成纖維的強(qiáng)度與其拉伸倍數(shù)有直接關(guān)系，下表是實(shí)際測(cè)定的24個(gè)纖維樣品的強(qiáng)度與相應(yīng)拉伸倍數(shù)的記錄。提示：將拉伸倍數(shù)作為x,強(qiáng)度作為y,在座標(biāo)紙上標(biāo)出各點(diǎn)，可以發(fā)現(xiàn)什么?33數(shù)據(jù)表格34數(shù)據(jù)圖35曲線擬合

已知的離散數(shù)據(jù)yi=f(xi)(i=0,1,2,…,n)往往是通過(guò)觀測(cè)而得到的，經(jīng)常帶有觀測(cè)誤差。

曲線擬合：希望找到—條曲線，它既能反映結(jié)定數(shù)據(jù)的總體分布形式，又不致于出現(xiàn)局部較大的波動(dòng)。這種逼近方式．只要所構(gòu)造的逼近函數(shù)(x)與被逼近函數(shù)f(x)在區(qū)間[a,b]上的偏差滿(mǎn)足其種要求即可。36偏差

設(shè)給定數(shù)據(jù)點(diǎn)(xi,yi),(i=0,1,2,…,n),記并稱(chēng)ei為偏差。37最小二乘法曲線擬合的最小二乘法：以使得偏差的平方和最小為標(biāo)難38線性最小二乘擬合假設(shè)所給的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)的分布大致呈直線，故可選擇線性函數(shù)作擬合曲線?！締?wèn)題1】對(duì)于給定的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)，求作一次式y(tǒng)＝a+bx，使總誤差為最小。39線性最小二乘擬合（續(xù)）【解】由微積分的知識(shí)可知，這一問(wèn)題的求解，可歸結(jié)為求二元函數(shù)E(a,b)的極值，即40線性最小二乘擬合（續(xù)）這是關(guān)于a,b的線性方程組，稱(chēng)為法方程。4041多項(xiàng)式最小二乘擬合有時(shí)所給數(shù)據(jù)點(diǎn)的分布并不一定近似地呈一條直線，這時(shí)若仍用直線似合顯然是不合適的。對(duì)于這種情況，可以考慮用多項(xiàng)式擬合。【問(wèn)題2】對(duì)于給定的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)，求作多項(xiàng)式，使總誤差為最小。42多項(xiàng)式最小二乘擬合（續(xù)）【解】由微積分的知識(shí)可知，這一問(wèn)題的求解，可歸結(jié)為求二元函數(shù)E(a0,a1,…,am)的極值，即43多項(xiàng)式最小二乘擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性力程組，稱(chēng)為法方程。44例題例8

某合金成分x與膨脹系數(shù)y之間的關(guān)系有如下實(shí)驗(yàn)數(shù)據(jù)，求膨脹系數(shù)y與成分x的擬合曲線y=P(x)。i0123456x37383940414243y3.403.002.101.531.801.902.9045例題解將數(shù)據(jù)標(biāo)在坐標(biāo)紙上，由散點(diǎn)圖可以推斷他們大致分布在一條拋物線上。為此取46例題法方程47例題代入數(shù)據(jù)后得解得于是所求擬合曲線為48其他函數(shù)曲線擬合最小二乘法并不只限于多項(xiàng)式，也可以用任何具體給出的函數(shù)形式。即可取【問(wèn)題3】對(duì)于給定的數(shù)據(jù)點(diǎn)(xi，yi),(i=0,1,2,…,n)，求作曲線，使總誤差為最小。49其他函數(shù)曲線擬合（續(xù)）【解】由微積分的知識(shí)可知，這一問(wèn)題的求解，可歸結(jié)為求二元函數(shù)E(a0,a1,…,am)的極值，即50其他函數(shù)曲線擬合（續(xù)）引進(jìn)內(nèi)積記號(hào)51其他函數(shù)曲線擬合（續(xù)）這是關(guān)于a0,a1,…,am的線性方程組，稱(chēng)為法方程。52例題例9

對(duì)例8中的數(shù)據(jù)，試求形如的擬合函數(shù)。解取擬合函數(shù)系53例題53得法方程解出因此所求的擬合函數(shù)為54正交多項(xiàng)式最小二乘擬合

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

55正交多項(xiàng)式

正交多項(xiàng)式：對(duì)給定點(diǎn)集

及權(quán)函數(shù)如果函數(shù)系滿(mǎn)足則稱(chēng)函數(shù)系帶權(quán)函數(shù)關(guān)于點(diǎn)集正交。56法方程56代替現(xiàn)在以，并利用的正交性，則法方程（3.4）成為對(duì)角型方程組（3.5）57廣義多項(xiàng)式其解為于是所求的擬合函數(shù)（稱(chēng)為廣義多項(xiàng)式）為誤差為58正交多項(xiàng)式遞推公式推導(dǎo)

設(shè)式（3.7）中的正交函數(shù)系系數(shù)為1的正交多項(xiàng)式系。正交多項(xiàng)式的一個(gè)基本性質(zhì)是能夠通過(guò)遞推關(guān)系逐個(gè)生成。事實(shí)上，任何一個(gè)k次多項(xiàng)式能表示成正交多項(xiàng)式的線性組合，于是成立，其中是特定參數(shù)。以為最高次項(xiàng)對(duì)式（3.9）兩邊作內(nèi)積59正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）即由于次數(shù)小于k，可寫(xiě)成代入上式，并利用正交性，得60正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對(duì)式（3.9）兩邊內(nèi)積即可寫(xiě)成代入上式，并利用正交性，得61正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）以對(duì)式（3.9）兩邊作內(nèi)積，得將的表達(dá)式，代入式（3.9），得62正交多項(xiàng)式遞推公式推導(dǎo)（續(xù)）若記63正交多項(xiàng)式遞推公式則得遞推公式64誤差遞推關(guān)系另外，誤差的遞推關(guān)系也不難得到。由式（3.8）可得由式（3.7）和（3.8）可得65例題例10

利用正交多項(xiàng)式對(duì)例8中的數(shù)據(jù)作二次擬合。解按遞推公式（3.10）計(jì)算權(quán)函數(shù)為1的正交多項(xiàng)式按公式（3.6）計(jì)算廣義多項(xiàng)式系數(shù)66例題代入式（3.7）中，得到所求的二次函數(shù)67非線性最小二乘擬合兩邊取對(duì)數(shù)，得則得令兩邊取自然對(duì)數(shù)，得令則得（1）（2）68非線性最小二乘擬合（續(xù)）（3）兩邊取對(duì)數(shù)，得則得令令則得（4）69非線性最小二乘擬合（續(xù)）令則得（6）令則得（5）70例題例11

給定實(shí)驗(yàn)數(shù)據(jù)x1.001.251.501.752.00y5.105.796.537.458.46試求形如的擬合函數(shù)。解對(duì)擬合函數(shù)的兩邊取自然對(duì)數(shù)，即令則上式成為關(guān)于A，b的線性函數(shù)71例題根據(jù)數(shù)據(jù)(x,y)算出對(duì)應(yīng)的(z,w),得下表z1.001.251.501.752.00w1.62921.75611.87642.00822.1353建立法方程解得因此，所求的擬合函數(shù)為72線性矛盾方程組方程個(gè)數(shù)大于未知量個(gè)數(shù)的方程組稱(chēng)為矛盾方程組，一般形式為即73線性矛盾方程組（續(xù)）

Ax＝