计算方法第四章(逼近法)课件

第四章函数最优逼近法

一、最优平方逼近

二、最优一致逼近一、最优平方逼近例1：距离0.511.522.533.54水深1.551.982.453.153.214.124.965.32例2：化学反应分子扩散时间0.10.511.52浓度2.821.61.31.2对于例2，设逼近函数形为：，该函数应该与已知点的某种差距最小。记：，可求如果取逼近函数形为：同样，对于例1，由于已知点几乎分布在一直线上，所以，设拟合函数为1.最小二乘拟合通常情况下，我们会遇到这样的问题：在研究某种客观现象的时候，需要建立所描述对象的量之间的函数关系式。此时，我们对要研究的函数进行一系列观测，得到若干组观测值，然后利用这些观测值构造函数表达式。显然，由于观测误差等原因，构造出的函数不可能严格过这些观测值的点。对此，我们要求构造出的函数在观测点上的值与观测值差的平方和达到最小。这称为最小二乘拟合。线性最小二乘问题的一般提法：已知函数列线性无关，对于一组已知点（观测值），求函数列的一个组合，使之在加权最小二乘的意义下最佳逼近这些点，即求系数，使下面的和取最小：这里，求和中加了数，代表求和的权重。称为基于函数列的对已知观测点的一个最小二乘逼近。注意到S实际上是关于的一个函数，欲取最小值，则如此得到一组方程，从中即可求出系数。引入记号：则得方程组：称为正规方程组，从中即可求出系数。类似，可以得到多元函数的线性最小二乘拟合：设多元函数列线性无关，一组测量数据为求拟合函数使最小。则拟合系数同样满足上页蓝色的方程。只不过例3：观测得到某函数一组数据，求其近似表达式：1234567891.782.242.743.744.455.316.928.8510.97设拟合函数为，引入变换，拟合函数为，数据变为：得正规方程组：1234567890.580.811.011.321.491.671.932.182.395最后结果如图最小二乘拟合多项式：设有变量x

和y

的一组数据：对多项式，选择适当系数后，使达到最小的多项式,称为数据的最小二乘(平方)拟合多项式，或称为变量x

和y之间的经验公式.显然，S达到最小值，则记：得正规方程组(法方程)：2.内积定义：设X为R上的线性空间，对于X中的任意两个向量u，v，定义(u,v)，如果满足下面条件：则称(u,v)为空间X上的一个内积。例：n维空间中的两个向量定义：证明：这是内积。例：设{i}

是一组正实数，定义：证明：这也是内积。例：区间[a,b]上的所有连续函数全体构成一个线性空间C[a,b],在这个空间上定义：证明：这是一个内积。定理：设(u,v)为空间X上的一个内积，对于空间中的一组向量，它们线性无关的充分必要条件是下面的所谓Gram（克拉姆）矩阵非奇异。定义：设(u,v)为空间X上的一个内积，对于X中的任意两个向量u，v，如果(u,v)＝0，则称u

与v

正交。记为：

u

v。例：3维空间中，证明下面向量两两正交例：区间[

-1,1]上的所有连续函数全体构成一个线性空间C[-1,1]，证明任意一个奇函数与偶函数正交。例：C[-,]中，证明下面函数两两正交：1,cosx,sinx,cos2x,sin2x正交多项式定义：满足的函数系称为正交函数系，如果该函数系是多项式，称为正交多项式系。1：[-,]中，1,cosx,sinx,cos2x,sin2x，cos3x,sin3x,…

，cosnx,sinnx，…正交2：勒让德(Legendre)多项式：[-1,1]上权为1的正交多项式3.拉盖尔(Laguerre)多项式：的正交多项式区间[0,）上权函数为4.埃尔米特(Hermite)多项式：的正交多项式区间(-,)上权函数为5.切比雪夫(Chebyshev)多项式：区间[-1,1]上权函数为的正交多项式正交多项式的构造对给定的有限点集X和权{ωi}或区间[a,b]和权函数，定义了内积后，可与向量的Schmite正交化类似，通过函数组{1,x,…,xn,…}可构造由给定内积（离散型或连续型）定义的正交多项式，如下：设其中c10是待定常数。由设已构造，两两正交，令由

正交多项式的性质1.线性无关.证：假定存在常数,使得推论：次数低于n次的多项式必与n次正交多项式正交.2.

n次正交多项式在正交区间[a,b]上有n个不同零点.证：3.对于最高次项系数为1的正交多项式，有三项递推公式：[-1,1]与[a,b]上权函数为的正交多项式的关系。所以是[a,b]上权为1的正交多项式。如，[0,1]上的权为1的正交多项式系为☆利用三项递推关系,可逐步构造正交多项式,从而求出最优平方逼近多项式。函数的最优平方逼近

已知一组在区间[a,b]上线性无关的函数求f(x)在此区间上基于这一组函数的最佳近似。此问题实际是求已知函数的一个组合，使之与f(x)的距离最小,即例4：求在[0,1]上的一次最佳平方逼近多项式。解：直接计算,得方程：用正交函数组作最佳平方逼近已知区间[a,b]上的连续函数f(x),以及一组正交函数组，易知最佳平方逼近为：例5：求exp(x)在[-1,1]上的三次最佳逼近多项式。例6：求函数f(x)=xexp(-x)在区间[0,10]上的三次最佳平方逼近多项式二、最优一致逼近

已知区间[a,b]上的连续函数f(x)，如果有n次多项式，使得所有n次多项式中，该多项式与函数f(x)在区间上的距离达到最小，则称该多项式为函数f(x)在区间[a,b]上的n次最优一致逼近多项式。数学提法是：选取多项式使得偏差定理1(切比雪夫):

n次多项式P(x)为区间[a,b]上的连续函数f(x)的最优一致逼近多项式的充要条件是：f(x)-P(x)在该区间上以正负相间的符号依次取值为的点(称为交错点组)的个数不少于n+2个.证明:只证充分性,用反证法.设f(x)-pn*(x)在[a,b]上存在一个至少由n+2个点组成的交错点组，但pn*(x)不是最佳一致逼近元.不妨设Pn[a,b]中的元素qn(x)为最佳一致逼近元，即‖f(x)-qn(x)‖∞<‖f(x)-pn*(x)‖∞(1)令Q(x)=pn*(x)-qn(x)

=[f(x)-qn(x)]-[(f(x)-pn*(x)]记{x1*,x2*,…,xn+2*}为误差曲线函数f(x)-pn*(x)在[a,b]上的交错点组。由于

Q(xi*)=[f(xi*)-qn(xi*)]-[f(xi*)-pn*(xi*)]由(1)式可知,n次多项式Q(x)在点集{x1*,x2*,…,xn+2*}上的符号完全由f(x)-pn*(x)在这些点上的符号所决定。

又{x1*,x2*,…,xn+2*}为f(x)-pn*(x)的交错点组，即f(x)-pn*(x)

在这n+2个点上正负(或负正)相间至少n+1次，因此至少n+1次改变符号，故Q(x)也至少n+1次改变符号。这说明n次多项式Q(x)至少在[a,b]上有n+1个根，矛盾，所以

‖f(x)-pn*(x)‖∞≤‖f(x)-qn(x)‖∞.

证毕.必要性证明，见王德人著《数值逼近引论》，1990

定理2（最佳一致逼近元的惟一性）在Pn[a,b]中，若存在对函数f(x)∈C[a,b]的最佳一致逼近元，则唯一.证明:反证，设有2个最佳一致逼近元，分别是pn*和qn

则它们的平均函数也是一个最佳一致逼近元。

令

En=‖f(x)-pn*(x)‖∞=‖f(x)-qn(x)‖∞.

由于

En≤‖f(x)-（pn*(x)+qn(x))/2‖∞

≤1/2(‖f(x)-pn*(x)‖∞+‖f(x)-qn(x)‖∞)

≤1/2(En+En)=En,这说明也是对函数f(x)∈C[a,b]的最佳一致逼近元.现设误差曲线函数f(x)-pn(x)在区间[a,b]上的一个交错点组为{x1,x2,…,xn+2}，则

En=|f(xk)-pn(xk)|=1/2|(f(xk)-pn*(xk))+(f(xk)-qn(xk))|若对某一个k,1≤k≤n+2，f(xk)-pn*(xk)≠f(xk)-qn(xk)，那么上式两个差中至少有一个达不到En或-En，从而En＝|f(xk)-pn(xk)|≤1/2(|

f(xk)-pn*(xk)|)+|f(xk)-qn(xk)|)

<1/2(‖f(x)-pn*(x)‖∞+‖f(x)-qn(x)‖∞)＝1/2(En+En)=En.矛盾！所以f(xk)-pn*(xk)=f(xk)-qn(xk),

即

pn*(xk)=qn(xk),

k=1,2,…，n+2.而pn*(x),qn(x)∈Pn[a,b]，故必有Pn*(x)=qn(x).

证毕.切比雪夫多项式的性质性质1：切比雪夫多项式为区间[-1,1]上关于权的正交多项式。性质2：三项递推关系性质3：是最高次项系数为的n次多项式。为偶函数，为奇函数。证：由性质2，用归纳法即知结论成立。性质4：在[-1,1]上有n个零点证：性质5：在[-1,1]上,且在交错的取得最大值1和最小值–1。这些点称为偏差点。证:

性质6：设Pn(x)为最高次项系数为1的n次多项式，则这个性质称为Chebyshev多项式的最小模性质.证:取f(x)=0,由Chebyshev定理可知结论成立.利用性质2可以得到关于最佳一致逼近多项式的求解问题（1）当f(x)为[-１,１]上的n+1次多项式时，求f(x)在Pn[-１,１]中的最佳一致逼近多项式。不妨记f(x)=b0+b1x+…+bn+1xn+1,|x|≤1,设pn(x)为最佳一致逼近元，由于首项系数为1的n+1次Chebyshev多项式T*n+1(x)的无穷模最小（性质6），所以考虑两种特殊情形:例7

设f(x)=4x4+2x３-５x２+8x-5/2，|x|≤1.

求f(x)在P3[-1,1]中的最佳一致逼近元p3(x).

解:由f(x)的表达式可知b４＝４,首项系数为1的4次Chebyshev多项式T4(x)＝x４－x２＋1/8.由(1)得p3(x)=f(x)-4T4(x)=2x３-x２+8x-3.

●对区间为[a,b]的情形，作变换x=(b-a)t/2+(b+a)/2(*)后,对变量为t的多项式用(1)求得Pn(t)，然后再作(*)式的反变换得到[a,b]上的最佳一致逼近多项式。（2）逼近多项式为低次多项式时关于交错点组的定理定理3

设pn*(x)∈Pn[a,b]为对f(x)∈C[a,b]的最佳一致逼近元.若f(n+1)(x)在区间[a,b]上不变号，则x=a和b为误差曲线函数f(x)-pn(x)在区间[a,b]上交错点组中的点。证明：（用反证法）若点a(点b类似)不属于交错点组，那么在区间(a,b)内至少存在n+1个点属于交错点组.若f(x)足够光滑，由交错点组的定义，可以证得(a,b)内的交错点必为误差曲线函数f(x)-Pn*(x)的驻点，即区间(a,b)内n+1个交错点上,f(x)-Pn*(x)的一阶导数等于零.这样，由Rolle定理便可推得，在(a,b)内至少存在一点,使得这与在[a,b]上不变号，即无零点矛盾，故点x=a属于交错点组。证毕。推论1设pn*(x)∈Pn[a,b]为对f(x)∈C[a,b]的最佳一致逼近元.若f(n+1)(x)在区间(a,b)上不变号，但在x=a(或b)处不存在(但为无穷)而符号与(a,b)内f(n+1)(x)的符号相同，则x=a(或b)属于f(x)-pn*(x)的交错点组.例8.设f(x)=x,求在P1[0,1]中对f(x)的最佳一致逼近元.

解:由定理3和推论1可知,x=0,1为f(x)-p1*(x)交错点组的点.由定理3，交错点还差一个，记这个点为x1∈(０,１),x０＝０,x２＝１.x１为区间(0，1)内的交错点，所以x１就是误差曲线函数f(x)-p1*(x)的驻点.Chebyshev多项式应用1--