计算方法CH.5.doc

第五章 函数的最优逼近与拟合1 线性赋范空间中的逼近问题1.1 函数逼近与函数空间逼近的思想和方法渗透于几乎所有的学科，其中包括自然科学和人文科学中的学科。逼近论既是一门研究函数的各类逼近性质的学科，属于函数论的范畴，同时又是计算数学和科学工程计算诸多数值方法的理论基础和方法的依据。本章讨论科学计算中基于逼近论的一些函数逼近方法。函数逼近方法与函数插值方法相类似，它也是在某一函数类中求函数，使它与被逼近函数之间满足一定的近似条件。在插值方法中，这个近似条件是在插值结点上使插值函数与被插值函数的函数值对应相等（包括各阶导数值对应相等）；在逼近方法中，这个近似条件用逼近函数与被逼近函数之间的某种距离来表达。数学上常在各种集合中引入某些确定关系，称为赋予集合以某种空间结构，并将这样的集合称为空间。例如，在线性代数中将所有实n维向量组成的集合，按向量加法及向量与数的乘法构成实数域上的线性空间，记作，称为n维向量空间。类似地，对次数不超过n（n为正整数）的实系数多项式全体，按通常多项式加法及数与函数乘法构成数域R上的线性空间，用表示，称为多项式空间，又如所有定义在区间上的连续函数集合，按函数加法和数与函数乘法构成R上的线性空间，记作，称为连续函数空间。定义1.1 设集合S是数域P上的线性空间，如果存在不全为零的数使得 （1.1）则称是线性相关的；若（1.1）式只对成立，则称是线性无关的。如果S包含一个由n个元素组成的极大线性无关组，则称S是n维的，如果对任意自然数N，S中存在N个线性无关的元素，则称S是无穷维的。显然是无穷维的，但对于和0，可以用有限维空间中的元素逼近，使误差，这就是著名的Weierstrass逼近定理。定理1.1 设，则0，使得在上一致成立。此定理可在数学分析书中找到证明。1912年Bernstein构造了一个多项式 （1.2）并证明在上一致成立，若在上m阶可导，则还有。这也就从理论上给出定理1.1的构造性证明。称为f的n次Bernstein多项式。但由于收敛于很慢，因此实际计算的近似值时，很少用这种方法。连续函数还可用其他函数集合逼近。一般地，可用一组在上线性无关的函数集合的线性组合来逼近，即用 （1.3）逼近。于是函数逼近问题就是对，在线性子空间中找某一元素,使在某种意义下最小。换句话说，也就是找一组系数，使（1.3）式中的成为在中的最佳逼近元。1.2 赋范线性空间中的最佳逼近既然是在线性子空间中寻找某一函数的逼近，必须引入一个度量的概念来衡量逼近的好坏，即衡量误差的大小。这对于不仅要计算函数在个别点上的值，而且要考虑函数在区间上的整体性质时，特别有意义。定义1.2 设为线性空间，如果对每一向量，都有一实数与之对应，把这一实数记为，并且这一对应具有下列性质1），等号成立当且仅当，（的零向量）正性2），正齐性3）.三角不等式则称为x的范数，一个线性空间，如果其中定义了满足上述三条公理的范数，我们称之为赋范线性空间，记为X；.注：范数的概念是很广泛的，只要满足上述3条，都可作为范数。以前我们引入的向量和矩阵的范数都是相应空间的范数。同一线性空间可以赋予不同的范数。定义1.3 设为赋范线性空间，其范数为，若序列，使则称序列依范数收敛于f，记作. 现在运用赋范线性空间的概念来讲解函数的逼近问题。逼近论的两个基本问题1给定赋范线性空间，以及的一个真子空间。对于如果在中存在这样的元素使得对所有的有成立，则称为f在范数意义下在中的最佳逼近元。立即就会出现这样的问题：（1）最佳逼近元是否存在？是否唯一？（2）当最佳逼近元唯一存在时，如何构造最佳逼近元。2设有的一系列子空间，若对每一个子空间，问题1中的最佳逼近元存在，是否有，以及收敛的速度。我将对于不同的范数定义，逐一研究这些问题。2 最佳一致逼近给出线性空间，取其范数和子空间为， （2.1）根据定理1.1，问题2的回答是肯定的。考虑问题1对中任一元素f的最佳逼近问题称为最佳一致逼近（通常又称为Chebyshev意义下的逼近）。定理2.1 如果f在上连续，则在集合中存在一个元素，是f的最佳一致逼近元。证略。4 最佳平方逼近大家已经学过三维欧氏空间，知道在欧氏空间里一个向量的长度，两个向量的夹角，向量到子空间的投影等是什么意思，在这一节里，我们要把函数逼近问题与欧氏空间联系起来，研究欧氏范数下的最佳逼近。4.1 线性内积空间定义4.1 设为实线性空间，如果对每一对向量，都有一实数与之对应，把这一实数记为，并且这一对应具有下列性质1），2），3），4），等号成立当且仅当，（的零向量）。则称为x和y的内积，一个线性空间，如果其中定义了满足上述四条公理的内积，我们称之为内积空间。例4.1 设，对，定义内积，易验证它满足公理1)-4）。例4.2 令（n维实向量空间），对其中向量，定义内积易知它满足公理1)-4）。令，可以证明满足第二章中关于范数的公理，即是一种范数，称为由内积导出的范数，通常记作，在不发生混淆的情况下也可简记为。定义4.2 设为内积空间，若，则称x与y正交，记作4.2 线性内积空间的最佳逼近设，是线性内积空间的n+1个线性无关的元素，子集，在中寻求对的某一元素f的最佳逼近，即对有定理4.1 是集合中对f的最佳逼近元素，其充要条件是与所有正交。证明 先证充分性，设S是中任一元素，考虑由于与所有正交，从而也与正交，因此从而就是最佳逼近元素，充分性得证。再证必要性，假设是中元素，与，中某一元素不正交，记，则且 记易知，现估计的范数从而推得即不是最佳逼近元，必要性得证。推论 最佳逼近元素如果存在，必定是唯一的。事实上，如果在子集中有两元素都是f的最佳逼近，则由定理4.1必有，j=0，1，n于是和都与正交，于是有 =0这就表示。下面，我们证明最佳逼近元素是存在的并将其构造出来，由定理4.1最佳逼近元，必须满足：，k=0，1，n （4.1）式（4.1）即，k=0，1，n （4.2）从而由下列方程组所决定 （4.3）方程组（4.3）通常称为法方程组。现在我们研究方程组的系数行列式 （4.4）称为关于的Gram行列式。定理4.2 子集的元素，线性相关的充要条件是它们的Gram行列式等于零。证明 先证必要性。由于，线性相关，因此有一组不全为零的数，使得上式分别对，作内积有这是关于，的齐次线性方程组，由于，不全为零，故推出其系数行列式必为零，从而再证充分性，假设研究下列方程组容易明白它必有非零解，设为。令易知，另一方面，对上式分别用作内积可得，从而有由于不全为零，故线性相关。定理的充分性得证。现在我们回到方程组（4.3）的讨论，由于是的线性无关元素，故从而（4.3）的解存在且唯一。也就是说，最佳逼近元素是存在的并可由（4.3）构造出来。下面再给出误差估计式，记为最佳逼近误差，则有 （4.5）至此，关于内积空间的最佳逼近元素的特征，存在唯一性，构造及误差估计已全部论述清楚了。4.3 函数的最佳平方逼近设a,b为有限或无限的区间，定义在它上面的函数，如果具有下列性质：1） ,2）0, 3）积分存在，n=0，1，。则称其为a,b上的权函数。对于在a,b上给定的函数，引入内积这里为权函数，总假设积分 （4.6）是存在的。我们研究满足（4.6）存在的函数全体组成的内积空间，并选子集。在子集上寻找一函数为中某一函数f(x)的最佳逼近，是指对于，都有 （4.7）（4.7）式的意义就是误差的平方在积分意义下达到极小，因此对于这种逼近就称为函数的最佳平方逼近，或称为最小二乘逼近，由于它是一个特殊的线性内积空间，因此最佳逼近的存在性，唯一性，解的构造，误差估计等等已由4.2节全部回答了。我们在这里指出，（4.7）也可从另外的观点来得解，我们知道，上任一函数可写成，而积分是关于的二次多元函数，记 （4.8）在子集寻找对f的最佳平方逼近函数，就是寻找函数的极小值。其必要条件是，k=0，1，n从而有写成内积符号就是，k=0，1，n上式恰巧就是（4.3）式。当然，从函数极小值的讨论去构造最佳逼近函数，其存在性，唯一性等都要建立一套理论来回答这些问题，但是由于我们已建立了一套最佳逼近理论，所以在解决具体问题时运用求极小值的办法，常常会带来演算的方便。例4.3 在空间给定元素，子集由1，x的线性组合构成（线性多项式空间），试求在中的最佳平方逼近（取）。解 由于，故，另外又有设最佳逼近元为，据（4.3）列出法方程式解得即线性函数为在子集中的最佳平方逼近函数。从例4.3可以看出，平方逼近算法简单。例4.4 取，k=0，1，n，在中求的n次最佳平方逼近多项式此时 ， j,k=0，1，n则法方程组（4.3）的系数矩阵为 （4.9）这是一个Hilbert矩阵，前面我们已经知道当n较大时，系数矩阵（4.9）是高度病态的，求解时舍入误差很大，这是很不利于计算的，为避免这种情况，需要引入正交基的概念。4.4 正交基如果是两两互相正交的（称为的一组正交基），法方程组的系数矩阵为对角阵，（4.3）成为从而直接可得，i=0，1，n （4.10）这样就不存在方程组病态的问题了。如果假设的范数均为1（称为的一组标准正交基），那么进一步有，i=0，1，n （4.11）在这种情况下，而（4.5）式的误差估计式有 （4.12）上式左端恒正，故又有Bessel不等式 （4.13）如果对所有的i，都存在， 称为f的广义Fourier展开，称为广义Fourier系数。下面用正交化过程来证明正交基的存在性。定理4.3 任何n维空间都存在正交基证明 按照n维空间的定义，存在一组基，由这组基，通过正交化过程，可以构造出两两正交的基。令，在所在“平面”上找，也就是找具有下列形式的选择数，使，即使由此得设两两正交而异于零的向量已经构造出来，向量要求具有形式选择系数使与向量正交，即满足 由于两两正交，故上述等式简化为：， 。由此得 最后我们利用线性无关的条件来证明，注意到是和的线性组合，又可表示为和的线性组合，依此类推最后可将表示为的系数为1，而线性无关，所以，证毕以上的正交化方法通常称为Schmidt正交化过程。5 正交多项式若首项系数的n次多项式，满足 （j,k=0，1，）则称多项式序列在a,b上带权正交，并称是a,b上带权的n次正交多项式。一般来说，当权及区间a,b给定后，从序列就可用4.4节所述的Schmidt正交化过程构造出正交多项式。用上述方法只能一个接一个地构造出正交多项式，在使用上有所不便，利用多项式的某些性质，我们可以得到一些更直接，更方便的方法来构造正交多项式，较重要的有下列几类：5.1 勒让德（Legendre）多项式当区间为-1,1，权函数时，由正交化所得的多项式就作为Legendre多项式并用表示，这一类正交多项式有如下的简单表达式，n=0，1， （5.1）由于是2n次多项式，求n阶导数后得于是得到首项的系数，显然最高系数为1的Legendre多项式为 （5.2）Legendre多项式有下述几个重要性质性质1 正交性 （5.3）证明 令，则（k=0，1，n-1）。设是在区间-1,1上有n阶连续可微的函数，由分部积分知 下面分两种情况讨论（1）若是次数小于n的多项式，则，故得，当（2）若，于是由于，故于是（5.3）得证。性质2 奇偶性 （5.4）由于是偶次多项式，经过偶次求导仍为偶次多项式，经过奇次求导则为奇次多项式，故n为偶数时为偶函数，n为奇数时为奇函数，于是（5.4）式成立。性质3 递推关系 考虑n+1次多项式它可表示为两边乘以，并从-1到1积分，得当时，次数小于等于n-1，上式左端积分为0，故得，当k=n时为奇函数，左端积分仍为0。故，于是其中从而得到以下的递推公式 （n=1，2，） （5.5）由，利用（5.5）式就可推出，性质4 在所有最高次项系数为1的n次多项式中，Legendre多项式在-1,1上与零的平方误差最小。设是任意一个最高次项系数为1的n次多项式，它可表示为于是当且仅当时等号才成立，即当时平方误差最小。性质5 在区间（-1，1）内有n个不同的实零点。前几个Legendre多项式的图形如下：5.2 切比雪夫（Chebyshev）多项式 （3.1）如此定义的是x的多项式吗？试看n=0和n=1的情形：注意到如下的三角恒等式：令，则有， n=1，2， （3.2）不难看出确实是n次多项式且与n的奇偶性相同，即随n为奇数或偶数而成为上的奇函数或偶函数。显然的最高次项的系数为，即 （3.3）称为n次Chebyshev多项式。前9个Chebyshev多项式如下表表3-1显然 （3.4）并且在点列 （3.5）1=1上，以正负交错的符号取到它的绝对值的最大值1。 （3.6）根据定理2.2，首项系数为1的多项式 为所有系数为1的n次多项式类中唯一的，在-1,1上与零偏差最小的多项式。的n个零点全位于（1，1）内，且都是单重的，它们是：。， （3.7）从几何上看，如果将以原点为圆心，以1为半径的上半圆周分成2n等分，再把圆周上所有奇分点位往x轴上投影，则恰好得到点列（3.7）。此外，实际计算中时常要求用，的线性组合表示，其公式为这里规定，n=18的结果见表3-2。表3-2它还是一类重要的正交多项式。Chebyshev多项式有很多重要性质：性质1 正交性Chebyshev 多项式在区间-1,1上带权正交，且 （5.7）事实上，令，则，于是性质2 递推关系，n=1，2，这只要由三角恒等式 令即得。性质3 只含x的偶次幂，只含x的奇次幂，这性质由递推关系直接得到。性质4 在区间（-1,1）上有n个零点，k=1，2，n。前几个Tchebyshev 多项式的图形如下： 5.3 无穷区间上的正交多项式正交多项式的正交区间a,b也可以是无界区域，当然此时权函数必须保证，n=1，2，。1拉盖尔（Laguerre）多项式 在区间上带权的正交多项式称为Laguerre多项式，其表达式为它也具有正交性质和递推关系，n=1，2，。2埃尔米特（Hermite）多项式 在区间上带权的正交多项式称为Hermite多项式，其表达式为它满足正交关系并有递推关系， n=1，2，。5.4 正交多项式的两个重要性质定理5.1 是a,b上带权的n次正交多项式的充分必要条件是：是n次多项式并且 k=0,1,n-1证明是容易的，从略。定理5.2 设是a,b上带权的n次正交多项式，则的零点全位于(a,b)内，并且都是单重的。证明：设，如果，不妨设，令，据定理5.1，但是上式中的被积函数为，积分应当大于0，矛盾。同理可证所有的零点不可能大于b，出现一对共轭复数或为二重的。6 离散情况的最佳平方逼近在4论述了内积空间的最佳逼近理论。现在我们讨论离散情况的最佳平方逼近。对于n维欧氏空间中任二向量，其内积定义为，相应的范数为.给定欧氏空间的一个子集，其中为线性无关组。子集对某一向量Y的最佳逼近，是指在中寻找一向量使它对的任意向量X都满足不等式如果，也即子集是一个n维欧氏空间，那么由线性代数的知识，恒有唯一的一组常数使此时，因此就是Y的最佳平方逼近，下面我们讨论ln的情况。由4定理4.1，与所有正交，即， k=1，2，l记，那么有从而由下列方程组所决定： （6.1）其中（6.1）可写成，j=1，2，l.容易看出，上式又可写成引入阶矩阵 （6.2）于是上式可写成 （6.3）其中为l阶方阵，分别为l，n维向量， .容易看出，（6.3）式的系数矩阵是对称的。由于为线性无关组，我们可进一步推出矩阵是正定的。事实上，对于l维欧氏空间的任一向量g，考虑的二次型有：其中等号仅当时才成立：即有，或即由是线性无关组推得，即。从而，当时有0，也就是说矩阵是正定矩阵。由于矩阵是正定的，所以可建立求解（6.3）的特殊方法，例如平方根法，乔列斯基（Cholesky）法。若两两正交，则矩阵成为对角形，即从而（6.3）的解变为：，i=1,l7 数据拟合的最小二乘法7.1 问题的引入在工程实践和科学实验中，量与量之间的关系表现为：1）确定性关系：如电学中著名的欧姆定律就是确定性的关系。用V表示电压，R表示电阻，I表示电流，欧姆定律指出有的确定性关系是由微分方程或积分方程来描述的。例如，阻尼振动中，位移x与时间的确定性关系由微分方程所决定，其中为固有频率，为阻尼系数。2）非确定性关系：由于因素的复杂性或其它原因，变量之间找不到完全确定的关系。例如纱的回潮率与原棉含水量之间；钢水含碳量与冶炼时间；鱼的活动与海水温度；台风登陆路径与沿海各地的风向、气温、湿度之间等等，这些量之间，既存在密切关系，又不能由一个（或几个）变量的数值精确地求出另一个变量的值。但是通过人的实践，通过仪器，我们获得了大量的实验数据，这些大量的偶然现象，始终是服从内部隐藏着的规律的。现在我们又回到数值逼近范围内来谈这个问题，为了叙述方便，先讨论两个变量x，y的情况。也就是说，通过观测变量x，y积累了一组资料，i=1，2，n，一般地说n都比较大。我们的任务是从积累得到的实验数据，i=1，2，n，寻求一近似函数去逼近y。由于观测数据都带有观测误差，数组数目又较大，对于这类问题运用插值函数去描述y往往是不适当的。我们以下面的例子来说明建立近似函数的一种办法，即最小二乘法。+例7.1 合成纤维抽丝工段，第一导丝盘的速度对丝的质量是很重要的参数，现发现它和电流周波有重要关系，由生产记录得到的数据如下表：周波x49.250.049.349.049.049.549.849.950.250.2第一导丝盘速度（y）16.717.016.816.616.716.816.917.017.017.1表4今要研究y与x的关系，通常的步骤如下：1）先用一坐标纸，将描于图上（图8）。图7.12）凭视觉约略知道在一条直线的两侧附近，于是猜想y与x近似地成直线关系，上面直线关系式称为数学模型。在第i次观测数据中，与实测值有误差，i=1，2，n，将它们平方后加起来得到总误差：我们当然希望，数学模型（主观猜想）应尽量接近客观实际，即总误差越小越好，也就是选取a,b使I(a,b)最小。问题又回到了内积空间的最佳逼近。定义向量Y、X、E分别为，n维欧氏空间的一个子集SpanX，E对Y的最佳平方逼近就是选取a,b使向量的范数达到极小，即 （7.2）（7.2）与（7.1）的提法完全一致。从问题的来源看，确定使误差平方和达到最小的方法称为最小二乘法，高斯对于天文观测数据的处理就运用了这个方法。依照我们建立的理论，a,b由下列方程组所决定：解之有运用表4的数据求得a=0.04，b=0.339,即必须指出，这里所说的欧氏空间最佳逼近，并不是说是y的最佳数学模型。因此就存在着另一个问题，上述数学模型是否符合客观实际呢？也就是说，如何检查数学模型的质量呢？当然，最根本的办法是拿到生产中去考验，但当观测数据积累多了以后，就能够建立一套数学理论去检验数学模型的准确性，偶然的现象，隐藏着必然的规律，概率统计的课程里将介绍这个问题。例7.2某航空售票点（PVG-IAD）机票销售加价和预期销售量之间的关系加价额度x（元）销售量P（张/周）加价额度x（元）销售量P（张/周）505822554755325052100592755012555300471506232535175623502720055对P和x的关系用三次多项式进行拟合，用最小二乘法可解得最小二乘法模型中的非线性函数例7.4 出钢时所用盛钢水的钢包，由于钢水对耐火材料的浸蚀，容积不断增大，我们希望找出使用次数与增大的容积之间的关系。试验数据如下表：使用次数增大容积使用次数增大容积使用次数增大容积26.42710.001210.6038.2089.931310.8049.5899.991410.6059.501010.491510.9069.701110.591610.76解 将数据标在坐标纸上（参见图7.2），我们看到，开始时浸蚀速度快，然后逐渐减弱，显然钢包容积不会无穷增加，于是可以想象它有一条平行于x轴的渐近线，根据这些特点我们选取数据拟合的曲线为双曲线。图7.2假设选择的数学模型为：,令于是上式变为.利用例7.1来决定计算结果如下：a=0.0823, b=0.1312.从而即若将曲线拟合的双曲线模型改成指数形式将上式两边取对数则有于是又可运用例7.1来求解，求得从而最后求得怎样比较数学模型的好坏呢？双曲线模型的误差为指数形式模式模型的误差为针对建立的模型比较实测值与拟合值的误差如下表：实测值拟合值拟合值误差误差实测值拟合值拟合值误差误差双曲模型指数模型双曲模型指数模型6.426.7616.702-0.341-0.28210.4910.47910.4510.0110.0398.207.9348.0650.2660.13510.5910.61210.557-0.0220.0339.588.6878.8470.8930.73310.6010.72510.646-0.125-0.0469.509.2129.3530.2880.14710.8010.82310.723-0.0230.0779.709.5999.7050.101-0.00510.6010.90810.788-0.308-0.18810.009.8969.9650.104-0.03510.9010.98310.845-0.0830.0559.9310.13110.165-0.201-0.23510.7611.04910.896-0.289-0.1369.9910.32210.322-0.332-0.333由于较小，所以我们选择指数模型作为钢包使用次数与增大容积之间的近似关系。选择合适的曲线模型是一件不容易做到的事情，主要靠人们对问题所属的专业知识的了解来定，如专业上也不清楚时，可用坐标纸描出点来从数学上加以选择。9 问题与探索：最小二乘法模型中的非线性函数和约束条件 最小二乘问题中所包含的条件方程一般可能是非线性的。可是，通常是用线性函数进行最小二乘处理，因为寻求非线性方程的最小二乘解是相当困难的，所以，每当模型中的方程原来是非线性时，必须采用某种线性化方法获得线性方程。为此目的，常常应用级数展开式，特别是泰勒