Ch3-函数逼近与快速傅里叶变换

第三章函数逼近与快速傅里叶变换

/*Chapter3

FunctionApproximationandFastFourierTransformation*/§3.1.1函数逼近与函数空间

1、数值计算中经常要计算函数值，如计算机中计算根本初等函数及其他特殊函数；2、当函数只在有限点集上给定函数值，要在包含该点集的区间上用公式给出函数的简单表达式.这些都涉及到在区间上用简单函数逼近已知复杂函数的问题，这就是函数逼近问题.§3.1函数逼近的根本概念插值法就是函数逼近问题的一种.记作，本章讨论的函数逼近，是指“对函数类中给定的函数中求函数，使与的误差在某种度量要在另一类简单的便于计算的函数类意义下最小”.函数类通常是区间上的连续函数，记作，称为连续函数空间.§3.1Approximation函数类通常为次多项式，有理函数或分段低次多项式等.

定义1设集合是数域上的线性空间，元素如果存在不全为零的数，（1.1）则称线性相关.否则，若等式(1.1)只对成立，那么称线性无关.使得§3.1Approximation如果中有无限个线性无关元素则称系数称为在基并称空间为维空间，若线性空间是由个线性无关元素生成的，即对都有则称为空间的一组基，记为下的坐标，记作为无限维线性空间.§3.1Approximation（1.2）它由个系数唯一确定.考察次数不超过次的多项式集合，它是的一组基，是线性无关的，且是的坐标向量，是维的.表示为其元素故§3.1Approximation使误差对连续函数，它不能用有限个线性无关的函数表示，故是无限维的，但它的任一元素均可用有限维的逼近，(为任给的小正数)，这就是著名的魏尔斯特拉斯定理.§3.1Approximation总存在一使

定理1设，则对任何，个代数多项式，在上一致成立.更一般地，可用一组在上线性无关的函数集合来逼近，可表示为（1.5）

函数逼近问题就是对任何，找一个元素，使在某种意义下最小.此时元素在子空间Φ中§3.1Approximation§3.1.2范数与赋范线性空间为了对线性空间中元素大小进行衡量，需要引进范数定义，它是空间中向量长度概念的直接推广.§3.1Approximation

定义2

设为线性空间，，（1）当且仅当时，（正定性）（2）(齐次性)（3）(三角不等式)则称‖·‖为线性空间上的范数，与‖·‖一起称为赋范线性空间，记为‖·‖，满足条件：假设存在唯一实数例如，在上的向量三种常用范数为称为范数或最大范数，称为1-范数，称为2-范数.§3.1Approximation而满足‖·‖1=1的向量则为对角线长度为1的菱形.实际上任何向量的实值函数，只要满足上述三个条件，就可以定义成一种向量范数.在中，满足‖·‖2=1，即的向量为单位圆，满足‖·‖∞=1，即的向量为单位正方形，§3.1Approximation所以说，范数是对向量长度的度量，度量方式不同，结果也不一样，但不同范数之间是存在等价关系的.类似地，对连续函数空间，若称为范数，称为1-范数，称为2-范数.可以验证这样定义的范数均满足定义2中的三个条件.可定义三种常用范数如下：§3.1Approximation在线性代数中，中两个向量及的内积定义为若将它推广到一般的线性空间，则有下面的定义.§3.1Approximation§3.1.3内积与内积空间

定义3有K中一个数与之对应，记为，它满足则称为X上与的内积.X是数域K(R或C)上的线性空间，对以下条件：§3.1Approximation定义中（1）的右端称为的共轭，当K为实数域R时.如果，则称与正交，这是向量相互垂直概念的推广.定义了内积的线性空间称为内积空间.§3.1Approximation

定理2对有（1.6）称为柯西-施瓦茨(Cauchy-Schwarz)不等式.设X为一个内积空间，

定理3（1.7）称为格拉姆(Gram)矩阵，则非奇异的充分必要条件是线性无关.设X为一个内积空间，矩阵§3.1Approximation

证明G非奇异等价于，其充要条件是齐次只有零解；（1.9）方程组（1.8）而§3.1Approximation从以上等价关系知，而后者等价于从（1.9）推出即线性无关.在内积空间X上，可以由内积导出一种范数，即对于（1.10）等价于从（1.8）推出记§3.1Approximation两端开方即得三角不等式（1.11）利用§3.1Approximation

例1与的内积.设（1.12）向量2-范数为§3.1Approximation相应的范数为（1.13）若给定实数称为权系数，当时，上的加权内积为〔1.13〕就是前面定义的内积.§3.1Approximation如果，（1.14）这里仍为正实数序列，为的共轭.在上也可以类似定义带权内积.带权内积定义为§3.1Approximation

定义4设是有限或无限区间，在上的非负函数满足条件：（1）存在且为有限值（2）对上的非负连续函数，如果则称为上的一个权函数.则§3.1Approximation

例2设是上给定的权函数（1.15）由此内积导出的范数为称（1.15）和（1.16）为带权的内积和范数.上的内积.那么可定义内积（1.16）§3.1Approximation常用的是的情形，即§3.1Approximation若是中的线性无关函数族，（1.17）根据定理3可知线性无关的充要条件是它的格拉姆矩阵为记§3.1Approximation3.2正交多项式/*OrthogonalPolynomials*/

3.2.1正交函数族与正交多项式

定义5若（2.1）则称与在上带权正交.上的权函数且满足为三角函数族就是在区间上的正交函数族.若函数族满足关系则称是上带权的正交函数族.

若，则称之为标准正交函数族.（2.2）满足关系式(2.2)，

定义6设是上首项系数的次多项式，为上权函数，则称多项式序列为在上带权正交，称为上带权的次正交多项式.如果多项式序列（2.3）只要给定区间及权函数，均可由一族线性无关的幂函数利用逐个正交化手续构造出正交多项式序列：3.2.2勒让德多项式当区间为，权函数时，并用表示.罗德利克(Rodrigul〕给出了简单的表达式（2.5）正交化得到的多项式就称为勒让德(Legendre)多项式，由勒让德多项式重要性质：（2.7）

性质1正交性（2.8）由于是偶次多项式，经过偶次求导仍为偶次多项式，经过奇次求导则为奇次多项式.

性质2奇偶性

性质3递推关系在区间内有个不同的实零点.性质4

性质2（2.8）由于是偶次多项式，经过偶次求导仍为偶次多项式，经过奇次求导则为奇次多项式，故为偶数时为偶函数，为奇数时为奇函数，于是（2.8）成立.奇偶性

性质3递推关系在区间内有个不同的实零点.性质43.2.3切比雪夫多项式

当权函数，区间为时，由序列正交化得到的正交多项式就是切比雪夫(Chebyshev)多项式.它可表示为（2.10）若令，则切比雪夫多项式有很多重要性质：

性质5递推关系（2.11）

性质6切比雪夫多项式在区间上带权（2.12）正交，且

性质7只含的偶次幂，只含的奇次幂.这个性质由递推关系直接得到.可以用的线性组合表示，

性质8在区间上有个零点其公式为（2.13）3.3最正确平方逼近法方程组

/*normalequations*/Hilbert阵！确定多项式，对于一组数据(xi,yi)(i=1,2,…,n)使得达到极小，这里n

<<

m。naaa10

实际上是a0,a1,…,an的多元函数，即[]

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

的极值点应有kiminjijijxyxa

==-=10][2-=

===+njmikiimikjijxyxa0112记

====mikiikmikikxycxb11,法方程组(或正规方程组)/*normalequations*/回归系数/*regressioncoefficients*/3.4曲线拟合的最小二乘法§3.4L-SApproximatingPolynomials例：xy(xi,yi),i=1,2,…,m方案一：设ba