函数逼近与FFT曲线拟合的最小二乘法.ppt

1,曲线拟合的最小二乘法,2,本节内容,曲线拟合,曲线拟合基本概念 最小二乘算法 最小二乘拟合多项式,3,给出一组离散点，确定一个简单函数近似原函数，多项式插值提供了一种处理手段。,然而，在实际问题中，给出的结点处的离散数据或多或少的都带有误差，插值要求多项式严格通过这些插值结点，无形之中就将这些点处的误差保留下来；,尤其是当结点数目较多时，误差可能累积起来，从而对最终近似效果产生较大影响（这正是高次插值产生Runge现象的一个主要原因）；,此外，即便给出的结点处的离散数据较为精确，但由于插值条件的限制，也导致多项式插值仅仅在处理结点附近的函数值近似问题时较为有效，即插值的局部近似效果好，整体逼近效果差。,这些都促使我们考虑一种函数逼近的新方法曲线拟合。,4,曲线拟合,能否找到一个简单易算的 p(x)，使得 f(x)p(x),已知 f(x)在某些点的函数值：,5,使 最小,使 最小,曲线拟合,p(xi)yi 总体上尽可能小,使 最小,常见做法,6,最小二乘,曲线拟合的最小二乘问题,这个问题实质上是最佳平方逼近问题的离散形式。可以将求连续函数的最佳平方逼近函数的方法直接用于求解该问题。,已知函数值表(xi,yi)，在函数空间 中求 S*(x)，使得,其中 i 是点 xi 处的权。,7,最小二乘求解,对任意 S(x)=span0,1,n，可设,S(x)=a00+a11+ann(x),则求 S*(x)等价于求下面的多元函数的最小值点,8,最小二乘求解,(k=0,1,n),这里的内积是离散带权内积，即,，,法方程,G,9,要使法方程有唯一解a0,a1,an,就要求矩阵G非奇异.,必须指出,0(x),1(x),n(x)在a,b上线性无关不能推出矩阵G非奇异.例如,令0(x)=sinx,1(x)=sin2x,x0,2,显然0(x),1(x)在0,2上线性无关,但若取点xk=k,k=0,1,2(n=1,m=2),那么有0(xk)=1(xk)=0,k=0,1,2,由此得出,为保证系数矩阵G非奇异，必须加上另外的条件.,定义 设0(x),1(x),n(x)Ca,b的任意线性组合在点集xi,i=0,l,.,m(mn)上至多只有n个不同的零点,则称0(x),1(x),n(x)在点集xi,i=0,l,.,m上满足哈尔(Haar)条件.,可以证明,如果0(x),1(x),n(x)Ca,b在xi0m上满足哈尔(Haar)条件,则法方程的系数矩阵G非奇异.,10,最小二乘求解,11,举例,最小二乘问题中，如何选择数学模型很重要，即如何选取函数空间=span0,1,n，通常需要根据物理意义，或所给数据的分布情况来选取合适的数学模型。,12,多项式拟合,Hn=span1,x,.,xn,即 i=xi,则相应的法方程为,此时 为 f(x)的 n 次最小二乘拟合多项式,多项式最小二乘曲线拟合,13,解,将所给数据在坐标纸上标出，见图3-5.,图3-5,选线性函数作拟合曲线,令,这里,故,14,解得,法方程,所求拟合曲线为,多项式拟合的Matlab现程序,其中输入参数 为要拟合的数据，为拟合多项式的次数，,输出参数 为拟合多项式的系数.,上例的Matlab多项式拟合,x=1 1 2 3 3 3 4 5;f=4 4 4.5 6 6 6 8 8.5;aa=poly(x,f,1);y=polyval(aa,x);plot(x,f,r+,x,y,k)xlabel(x);ylabel(y);gtext(y=s1(x)）,15,例：用 来拟合，w 1,解：0(x)=1，1(x)=x，2(x)=x2,正交多项式与最小二乘拟合,16,例：连续型拟合中，取,则,Hilbert阵！,若能取函数族=0(x),1(x),n(x),，使得任意一对i(x)和j(x)两两（带权）正交，则 B 就化为对角阵！,这时直接可算出ak=,17,正交多项式拟合,带权正交（离散情形）,给定点集 以及各点的权系数，如果函数族 满足,则称 关于点集 带权 正交,若 0,1,n 是多项式，则可得正交多项式族,18,正交多项式拟合,用正交多项式做最小二乘,设多项式 p0,p1,pn 关于点集 x0,x1,xm 带权 0,1,m 正交，则 f(x)在 Hn 中的最小二乘拟合多项式为,其中,k=0,1,n,19,正交多项式的构造,给定 和权系数，如何构造正交多项式族,可以证明：关于点集 带权 正交,20,几点注记,可以将构造正交多项式族、解法方程、形成拟合多项式穿插进行；n 可以事先给定，或在计算过程中根据误差来决定；该方法非常适合编程实现，只用递推公式，并且当逼近次数增加时，只要将相应地增加程序中的循环次数即可。该方法是目前多项式拟合最好的计算方法，有通用程序。,21,例：用 来拟合，w 1,解：通过正交多项式 0(x),1(x),2(x)求解,注：手算时也可用待定系数法确定函数族。,22,三、可线性化的非线性最小二乘拟合,曲线拟合问题的关键在于四点，其一是确定恰当拟合函数类型（这是最重要也是最困难的一点）；其二是确定最佳拟合的标准（例如最小二乘原理）；其三是确定拟合函数中的待定参数（利用函数极值理论建立并求解方程组）；其四是对拟合效果进行评价（如：利用偏差平方和、均方差等）。,在前两目的学习中，我们看到最终确定拟合函数中的系数是利用线性方程组的求解来实现，因此我们将其称作是线性最小二乘拟合。若待定系数的确定需要用到非线性方程组，则称为是非线性最小二乘拟合。这类问题由于牵涉到非线性方程组的求解，因此变得有些困难。然而不少非线性拟合问题都可以利用某些手段（如变量代换）将其转化为线性拟合问题。,23,例3：在某化学反应里,测得生成物浓度y%与时间t的数据如下，试建立y关于t的经验公式,解：,第一步：画出生成物浓度与反应时间的散点图,第二步：确定拟合函数类型。作为例题我们直接给出下面两种函数：,（1）指数函数形式,（2）双曲函数形式,其中，a，b是待定系数,24,第三步：确定最佳拟合原则。这里我们依然采用最小二乘原理。我们以第一种函数类型为例：即确定一组系数a，b使得,最小。,第四步：利用多元函数极值理论，建立关于待定系数a，b的方程组。,令,25,即，,显然，上面的方程组整理之后，是关于a，b的非线性方程组（这就是非线性拟合的含义），这直接导致了a，b求解的困难。,我们考虑用下面的变量代换手段将此问题线性化。,26,对于指数函数形式,在方程两端取对数，,作变量代换：,由此我们将y与t的关系转化为Y与T的关系，利用最小二乘原理可以得到A、b的最优解。,A=2.4270，b=-1.0567，由此a=11.3252，即,27,思考：该如何评判两种不同曲线的拟合效果？,28,29,可化为线性拟合问题的常见函数类型,