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

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

/*Chapter3

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

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

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

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

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

定義2

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

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

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

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

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

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

定義4設(shè)是有限或無限區(qū)間，在上的非負(fù)函數(shù)滿足條件：（1）存在且為有限值（2）對上的非負(fù)連續(xù)函數(shù)，如果則稱為上的一個權(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若是中的線性無關(guān)函數(shù)族，（1.17）根據(jù)定理3可知線性無關(guān)的充要條件是它的格拉姆矩陣為記§3.1Approximation3.2正交多項式/*OrthogonalPolynomials*/

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

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

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

性質(zhì)2奇偶性

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

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

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

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

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

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

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

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

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

<<

m。naaa10

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

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

的極值點應(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