Ch3-函數(shù)逼近與快速傅里葉變換

第三章函數(shù)逼近與快速傅里葉變換

/*Chapter3

FunctionApproximationandFastFourierTransformation*/§3.1.1函數(shù)逼近與函數(shù)空間

1、數(shù)值計(jì)算中經(jīng)常要計(jì)算函數(shù)值，如計(jì)算機(jī)中計(jì)算根本初等函數(shù)及其他特殊函數(shù)；2、當(dāng)函數(shù)只在有限點(diǎn)集上給定函數(shù)值，要在包含該點(diǎn)集的區(qū)間上用公式給出函數(shù)的簡(jiǎn)單表達(dá)式.這些都涉及到在區(qū)間上用簡(jiǎn)單函數(shù)逼近已知復(fù)雜函數(shù)的問(wèn)題，這就是函數(shù)逼近問(wèn)題.§3.1函數(shù)逼近的根本概念插值法就是函數(shù)逼近問(wèn)題的一種.記作，本章討論的函數(shù)逼近，是指“對(duì)函數(shù)類中給定的函數(shù)中求函數(shù)，使與的誤差在某種度量要在另一類簡(jiǎn)單的便于計(jì)算的函數(shù)類意義下最小”.函數(shù)類通常是區(qū)間上的連續(xù)函數(shù)，記作，稱為連續(xù)函數(shù)空間.§3.1Approximation函數(shù)類通常為次多項(xiàng)式，有理函數(shù)或分段低次多項(xiàng)式等.

定義1設(shè)集合是數(shù)域上的線性空間，元素如果存在不全為零的數(shù)，（1.1）則稱線性相關(guān).否則，若等式(1.1)只對(duì)成立，那么稱線性無(wú)關(guān).使得§3.1Approximation如果中有無(wú)限個(gè)線性無(wú)關(guān)元素則稱系數(shù)稱為在基并稱空間為維空間，若線性空間是由個(gè)線性無(wú)關(guān)元素生成的，即對(duì)都有則稱為空間的一組基，記為下的坐標(biāo)，記作為無(wú)限維線性空間.§3.1Approximation（1.2）它由個(gè)系數(shù)唯一確定.考察次數(shù)不超過(guò)次的多項(xiàng)式集合，它是的一組基，是線性無(wú)關(guān)的，且是的坐標(biāo)向量，是維的.表示為其元素故§3.1Approximation使誤差對(duì)連續(xù)函數(shù)，它不能用有限個(gè)線性無(wú)關(guān)的函數(shù)表示，故是無(wú)限維的，但它的任一元素均可用有限維的逼近，(為任給的小正數(shù))，這就是著名的魏爾斯特拉斯定理.§3.1Approximation總存在一使

定理1設(shè)，則對(duì)任何，個(gè)代數(shù)多項(xiàng)式，在上一致成立.更一般地，可用一組在上線性無(wú)關(guān)的函數(shù)集合來(lái)逼近，可表示為（1.5）

函數(shù)逼近問(wèn)題就是對(duì)任何，找一個(gè)元素，使在某種意義下最小.此時(shí)元素在子空間Φ中§3.1Approximation§3.1.2范數(shù)與賦范線性空間為了對(duì)線性空間中元素大小進(jìn)行衡量，需要引進(jìn)范數(shù)定義，它是空間中向量長(zhǎng)度概念的直接推廣.§3.1Approximation

定義2

設(shè)為線性空間，，（1）當(dāng)且僅當(dāng)時(shí)，（正定性）（2）(齊次性)（3）(三角不等式)則稱‖·‖為線性空間上的范數(shù)，與‖·‖一起稱為賦范線性空間，記為‖·‖，滿足條件：假設(shè)存在唯一實(shí)數(shù)例如，在上的向量三種常用范數(shù)為稱為范數(shù)或最大范數(shù)，稱為1-范數(shù)，稱為2-范數(shù).§3.1Approximation而滿足‖·‖1=1的向量則為對(duì)角線長(zhǎng)度為1的菱形.實(shí)際上任何向量的實(shí)值函數(shù)，只要滿足上述三個(gè)條件，就可以定義成一種向量范數(shù).在中，滿足‖·‖2=1，即的向量為單位圓，滿足‖·‖∞=1，即的向量為單位正方形，§3.1Approximation所以說(shuō)，范數(shù)是對(duì)向量長(zhǎng)度的度量，度量方式不同，結(jié)果也不一樣，但不同范數(shù)之間是存在等價(jià)關(guān)系的.類似地，對(duì)連續(xù)函數(shù)空間，若稱為范數(shù)，稱為1-范數(shù)，稱為2-范數(shù).可以驗(yàn)證這樣定義的范數(shù)均滿足定義2中的三個(gè)條件.可定義三種常用范數(shù)如下：§3.1Approximation在線性代數(shù)中，中兩個(gè)向量及的內(nèi)積定義為若將它推廣到一般的線性空間，則有下面的定義.§3.1Approximation§3.1.3內(nèi)積與內(nèi)積空間

定義3有K中一個(gè)數(shù)與之對(duì)應(yīng)，記為，它滿足則稱為X上與的內(nèi)積.X是數(shù)域K(R或C)上的線性空間，對(duì)以下條件：§3.1Approximation定義中（1）的右端稱為的共軛，當(dāng)K為實(shí)數(shù)域R時(shí).如果，則稱與正交，這是向量相互垂直概念的推廣.定義了內(nèi)積的線性空間稱為內(nèi)積空間.§3.1Approximation

定理2對(duì)有（1.6）稱為柯西-施瓦茨(Cauchy-Schwarz)不等式.設(shè)X為一個(gè)內(nèi)積空間，

定理3（1.7）稱為格拉姆(Gram)矩陣，則非奇異的充分必要條件是線性無(wú)關(guān).設(shè)X為一個(gè)內(nèi)積空間，矩陣§3.1Approximation

證明G非奇異等價(jià)于，其充要條件是齊次只有零解；（1.9）方程組（1.8）而§3.1Approximation從以上等價(jià)關(guān)系知，而后者等價(jià)于從（1.9）推出即線性無(wú)關(guān).在內(nèi)積空間X上，可以由內(nèi)積導(dǎo)出一種范數(shù)，即對(duì)于（1.10）等價(jià)于從（1.8）推出記§3.1Approximation兩端開方即得三角不等式（1.11）利用§3.1Approximation

例1與的內(nèi)積.設(shè)（1.12）向量2-范數(shù)為§3.1Approximation相應(yīng)的范數(shù)為（1.13）若給定實(shí)數(shù)稱為權(quán)系數(shù)，當(dāng)時(shí)，上的加權(quán)內(nèi)積為〔1.13〕就是前面定義的內(nèi)積.§3.1Approximation如果，（1.14）這里仍為正實(shí)數(shù)序列，為的共軛.在上也可以類似定義帶權(quán)內(nèi)積.帶權(quán)內(nèi)積定義為§3.1Approximation

定義4設(shè)是有限或無(wú)限區(qū)間，在上的非負(fù)函數(shù)滿足條件：（1）存在且為有限值（2）對(duì)上的非負(fù)連續(xù)函數(shù)，如果則稱為上的一個(gè)權(quán)函數(shù).則§3.1Approximation

例2設(shè)是上給定的權(quán)函數(shù)（1.15）由此內(nèi)積導(dǎo)出的范數(shù)為稱（1.15）和（1.16）為帶權(quán)的內(nèi)積和范數(shù).上的內(nèi)積.那么可定義內(nèi)積（1.16）§3.1Approximation常用的是的情形，即§3.1Approximation若是中的線性無(wú)關(guān)函數(shù)族，（1.17）根據(jù)定理3可知線性無(wú)關(guān)的充要條件是它的格拉姆矩陣為記§3.1Approximation3.2正交多項(xiàng)式/*OrthogonalPolynomials*/

3.2.1正交函數(shù)族與正交多項(xiàng)式

定義5若（2.1）則稱與在上帶權(quán)正交.上的權(quán)函數(shù)且滿足為三角函數(shù)族就是在區(qū)間上的正交函數(shù)族.若函數(shù)族滿足關(guān)系則稱是上帶權(quán)的正交函數(shù)族.

若，則稱之為標(biāo)準(zhǔn)正交函數(shù)族.（2.2）滿足關(guān)系式(2.2)，

定義6設(shè)是上首項(xiàng)系數(shù)的次多項(xiàng)式，為上權(quán)函數(shù)，則稱多項(xiàng)式序列為在上帶權(quán)正交，稱為上帶權(quán)的次正交多項(xiàng)式.如果多項(xiàng)式序列（2.3）只要給定區(qū)間及權(quán)函數(shù)，均可由一族線性無(wú)關(guān)的冪函數(shù)利用逐個(gè)正交化手續(xù)構(gòu)造出正交多項(xiàng)式序列：3.2.2勒讓德多項(xiàng)式當(dāng)區(qū)間為，權(quán)函數(shù)時(shí)，并用表示.羅德利克(Rodrigul〕給出了簡(jiǎn)單的表達(dá)式（2.5）正交化得到的多項(xiàng)式就稱為勒讓德(Legendre)多項(xiàng)式，由勒讓德多項(xiàng)式重要性質(zhì)：（2.7）

性質(zhì)1正交性（2.8）由于是偶次多項(xiàng)式，經(jīng)過(guò)偶次求導(dǎo)仍為偶次多項(xiàng)式，經(jīng)過(guò)奇次求導(dǎo)則為奇次多項(xiàng)式.

性質(zhì)2奇偶性

性質(zhì)3遞推關(guān)系在區(qū)間內(nèi)有個(gè)不同的實(shí)零點(diǎn).性質(zhì)4

性質(zhì)2（2.8）由于是偶次多項(xiàng)式，經(jīng)過(guò)偶次求導(dǎo)仍為偶次多項(xiàng)式，經(jīng)過(guò)奇次求導(dǎo)則為奇次多項(xiàng)式，故為偶數(shù)時(shí)為偶函數(shù)，為奇數(shù)時(shí)為奇函數(shù)，于是（2.8）成立.奇偶性

性質(zhì)3遞推關(guān)系在區(qū)間內(nèi)有個(gè)不同的實(shí)零點(diǎn).性質(zhì)43.2.3切比雪夫多項(xiàng)式

當(dāng)權(quán)函數(shù)，區(qū)間為時(shí)，由序列正交化得到的正交多項(xiàng)式就是切比雪夫(Chebyshev)多項(xiàng)式.它可表示為（2.10）若令，則切比雪夫多項(xiàng)式有很多重要性質(zhì)：

性質(zhì)5遞推關(guān)系（2.11）

性質(zhì)6切比雪夫多項(xiàng)式在區(qū)間上帶權(quán)（2.12）正交，且

性質(zhì)7只含的偶次冪，只含的奇次冪.這個(gè)性質(zhì)由遞推關(guān)系直接得到.可以用的線性組合表示，

性質(zhì)8在區(qū)間上有個(gè)零點(diǎn)其公式為（2.13）3.3最正確平方逼近法方程組

/*normalequations*/Hilbert陣！確定多項(xiàng)式，對(duì)于一組數(shù)據(jù)(xi,yi)(i=1,2,…,n)使得達(dá)到極小，這里n

<<

m。naaa10

實(shí)際上是a0,a1,…,an的多元函數(shù)，即[]

=-+++=miinininyxaxaaaaa121010...),...,,(j在

的極值點(diǎn)應(yīng)有kiminjijijxyxa

==-=10][2-=

===+njmikiimikjijxyxa0112記

====mikiikmikikxycxb11,法方程組(或正規(guī)方程組)/*normalequations*/回歸系數(shù)/*regressioncoefficients*/3.4曲線擬合的最小二乘法§3.4L-SApproximatingPolynomials例：xy(xi,yi),i=1,2,…,m方案一：設(shè)ba