数值计算方法 第6章 函数逼近ppt课件.ppt

第6章 函数逼近,实际问题中, 通过测量或数值计算得到一批离散的数据, 希望通过某种函数(曲线)来描述它, 且使得它在某种意义下最“贴近”这批数据, 这就是数据拟合, 也称为函数逼近.,一组实验数据:,函数逼近的概念,函数逼近的例子,从图形上可看出, 数据分布接近于直线:,如何选取a,b, 使得直线“最好”地贴近于数据点?,记,评判残差大小的标准?,衡量残差大小的标准,使残差的绝对值之和最小, 即:,第6章 函数逼近,这一标准虽然简单, 但使用上不太方便.,使残差绝对值最大的分量达到最小, 即:,这一方法称为最佳一致逼近.,使残差的平方和达到最小, 即:,这一方法称为最佳平方逼近, 通常也称为曲线(数据)拟合的最小二乘法. 该方法较简单, 是应用中常用的一种方法.,一. 数据拟合的最小二乘法,多项式拟合,(xi, yi),第6章 函数逼近,最小二乘法的基本思想,选取近似函数类H, 寻求函数 使得,最小.,即,要求F(a0,am) 极小,H通常采用比较简单的函数类, 如低阶多项式, 指数函数等.,方法,数据点:,m次多项式:,残差平方和:,确定拟合多项式的系数,第6章 函数逼近,记为,可以证明, 该方程组有唯一解(a0,a1,am), 从而得Pm(x).,但要注意, 系数矩阵A通常是病态的, 其条件数cond(A)非常大.,多项式拟合的例子,第6章 函数逼近,用二次多项式拟合这批数据.,解. 二次拟合多项式:,正则方程 (n=6):,拟合曲线图,指数拟合,方法,取极小,称为非线性最小二乘问题.,即:,第6章 函数逼近,可用指数函数进行拟合:,改进的方法,拟合多项式:,正则方程:,分式线性拟合,当数据点分布接近于函数 时,第6章 函数逼近,作变换:,对数据点 进行线性最小二乘拟合.,参数a, b,拟合曲线,当数据点分布接近于函数 时,作变换:,对数据点 进行线性最小二乘拟合.,参数a, b,拟合曲线,上面两种拟合中, 参数a, b 满足以下正则方程:,最小二乘拟合的一般步骤,第6章 函数逼近,通过观测数据点的形态, 确定拟合函数的形式;对于一些简单的非线性问题, 通过合适的变换化成线性问题;由最小二乘的正则方程确定拟合函数中的参数;对于非线性问题, 将线性拟合函数再反变换成非线性函数.,观测数据点,取极小,几点说明,对于指数函数拟合问题:,非线性拟合结果,变换后的数据点,线性拟合参数,非线性拟合函数,反变换,实际问题中, 各个数据点的重要性可能不相等, 定义误差函数:,线性最小二乘法的一般形式,方法,要求F极小, 即,第6章 函数逼近,数据点,记:,取拟合函数:,线性无关函数组:,误差函数:,正则方程:,由于线性无关, 系数矩阵非奇异, 方程有唯一解.,下面证明 就是所求的最小二乘函数.,为权系数.,定理6.1 (最小二乘解),证明. 对,证毕 #,第6章 函数逼近,设(a0,a1,am) 是满足上述正则方程的解, 则 是数据点(xi,yi) (i=1,n) 的最小二乘函数.,证明,I,即,正交多项式方法的提出,第6章 函数逼近,正则方程一般是病态的, 尤其是m比较大的情况, 这样得到的系数 (a0,a1,.,am) 误差较大.,正则方程的系数矩阵为对角阵.,若选取的函数组 满足:,最小二乘函数:,若函数组 满足上述条件,定义 (正交函数族),则称为以 为权, 关于,点集 (x1,x2,xn) 的正交函数族.,正交多项式的构造,第6章 函数逼近,其中,证明过程类似于后面的定理6.4.,利用正交多项式求拟合多项式的过程,第6章 函数逼近,得拟合多项式:,构造正交函数系:,解正则方程, 得系数: a0,a1,am.,例. 利用正交函数求下列数据的最小二乘二次(m=2)拟合多项式,解. n=6, 取,构造正交多项式系:,例（续）,第6章 函数逼近,解正则方程, 得拟合函数的各个系数.,拟合多项式:,二. 正交多项式,基本概念,第6章 函数逼近,定义6.2 (正交函数系),特例:,正交函数系的例子,若函数系 满足:,则称函数系 在a,b上关于权函数 的正交函数系.,是区间 上关于权函数 的正交函数系.,三角函数系:,称为标准正交函数系.,正交函数系的性质由下面两个定理给出:,定理6.2 (线性无关性),证明 采用反证法 假设 线性相关, 即存在不全为0的系数ci,使,第6章 函数逼近,不妨设,由正交性,矛盾. 故 线性无关.,正交函数系必定是线性无关的.,定理6.3 (正交多项式的充要条件),设 是最高次系数非零的k次多项式, 则 是a,b上关于权函数 的正交多项式的充要条件是, 对任意次数不超过k-1次的多项式 , 都有:,定理6.3 (续),证毕 #,第6章 函数逼近,证明 充分性 若,对 成立.,取,即,故 为正交多项式系.,必要性 设 是a,b上关于权函数 的正交多项式,由定理6.2, 在a,b上线性无关.,格拉姆-施密特(Gram-Schmidt)方法,第6章 函数逼近,构造正交函数的一般方法:,其中,定理6.4 (正交函数的构造),证明 由递推式可看出, 是k次多项式, 且xk系数为1.,定理6.4 (续-1),第6章 函数逼近,下面用归纳法证明:,不妨设jk, k=1,2,n.,k=1:,命题成立.,假设结论对 k=m-1 (2mn) 成立, 即:,对k=m, 先考察,归纳法假设,其次考察,定理6.4 (续-2),由归纳法假设,第6章 函数逼近,结论对 k=m 也成立, 证毕 #,由,对0 j m-2,由,由于jm-2, 则 j+1m-1,对j=0,由归纳法假设,常用的正交多项式,第6章 函数逼近,也是下面微分方程的多项式解:,勒让德 (Legendre) 多项式,Pn(x) 的最高幂次系数为:,最早由Legendre在势论中引进, 是下面表达式的Talor展开系数:,前几阶的具体形式,一般形式罗巨格(Rodrigues)公式:,Legendre多项式的性质,证明. 不妨设nm, 利用Legendre多项式的一般形式,第6章 函数逼近,Pn(x) 是区间-1,1上关于权函数 的正交函数系, 且,若nm,(反复利用分部积分),I,即, nm 时,Legendre多项式的性质-1 证明 (续-1),第6章 函数逼近,若n=m,(分部积分),II,(反复使用分部积分),归纳:,证毕 #,Legendre多项式的性质 (续-2),证明. 由关系式,第6章 函数逼近,Legendre多项式满足递推公式:,上式对任意 t 成立, 故tn 密次的系数应为0, 即两边tn 的系数相等.,对 t 求导, 得,两边同乘 , 再利用(1), (1),证毕 #,Legendre多项式的性质 (续-3),证明. (略),第6章 函数逼近,Legendre多项式满足关系式:,说明: 这一关系式将在下一章证明Gauss-Legendre积分公式的系数时用到.,任意区间上的Legendre多项式,第6章 函数逼近,对任意a,b区间, 只要作线性变换:,则a,b上的正交多项式为:,如, 区间0,1上的正交多项式为:,第一类切比雪夫(Chebyshev)多项式,第6章 函数逼近,定义式:,Tn(x) 的最高次系数为:,Tn(x)的微分表示形式:,令,详细推导过程较为繁琐, 不再详述. 具体表达式如下:,它满足微分方程:,第一类Chebyshev多项式的性质,第6章 函数逼近,Tn(x) 是区间-1,1上关于权函数 的正交函数系, 且,m=n=0,证明. 作变换 则,m=n0,mn,证毕 #,第一类Chebyshev多项式的性质（续）,第6章 函数逼近,Tn(x) 满足递推关系式:,即,证明. 作变换 则,即,证毕 #,Tn(x) 在-1,1上有n个互异的零点:,证明. 由,证毕 #,Tn(x)在-1,1上有n+1个极值点:,且 (k是偶数),证明. 作变换 则,而,即,(k是奇数),证毕 #,拉盖尔(Laguerre)多项式,第6章 函数逼近,定义式:,Ln(x) 的最高次系数为:,它满足微分方程:,具体表达式:,Laguerre多项式的性质,第6章 函数逼近,Ln(x) 是区间0,+上关于权函数 的正交函数系, 且,证明. (略),满足递推关系式,证明. (略),三. 函数的最佳平方逼近,第6章 函数逼近,定义6.3 (最佳平方逼近函数),设f(x)在区间a,b上连续, 为a,b上的一组线性无关的连续函数, H是其张成的线性空间. 如果,主要研究用最小二乘法求连续函数的近似函数.,特例. 如果,使得误差:,其中 为权函数, 则称 为函数f(x)在H中关于权函数 的最佳平方逼近函数.,则称 为函数f(x)在H中关于权函数 的m次最佳平方逼近多项式 或 最小二乘平方逼近多项式.,最佳平方逼近函数中的系数,第6章 函数逼近,由极值的必要条件:,得正则方程:,矩阵形式:,其中,由 线性无关, 可证明Gram矩阵非奇异, 正则方程有唯一解 .,下面证明这样的解一定是最佳平方逼近.,故正则方程也可写为:,定理6.5 (最佳平方逼近函数的充要条件),第6章 函数逼近,可构造函数,设f(x)在区间a,b上连续, 是f(x)在线性空间H中关于权函数 的最佳平方逼近函数的充要条件是,与 是最佳平方逼近函数矛盾. 必要性得证.,证明. 必要性 设 是最佳平方逼近函数, 须证明,采用反证法. 假若存在 0im, 使得,定理6.5 (续),第6章 函数逼近,证明. 充分性 设,即,另外,则对任意,故 是f(x) 关于权函数 的最佳平方逼近. 必要性得证.,证毕 #,这样, 由正则方程得到的一定是唯一的最佳平方逼近.,最佳平方逼近函数的例子,第6章 函数逼近,正则方程:,其中,最佳平方逼近函数:,解. 利用Legendre多项式构造0,1上正交多项式:,求 在0,1区间上的二次最佳平方逼近多项式,整理得:,最佳平方逼近函数的例子（续）,第6章 函数逼近,在0,1区间上的二次最佳平方逼近的图形.,四. 最佳一致逼近多项式（补充）,第6章 函数逼近,定理6.6 (Weierstrass定理),关于最佳一致逼近, 早在1885年, Weierstrass就给出以下定理:,1912年伯恩斯坦(Bernstein)给出了一个构造性的证明.,称,为关于f(x)的n次Bernstein多项式, 当 时, 在0,1上一致收敛到f(x).,问题是, 当精度要求比较高时, n比较大, 不太实用. 希望能对固定的n, 构造不超过n次的多项式, 使其最佳逼近f(x).,最佳一致逼近多项式,第6章 函数逼近,即H为n次多项式空间,则最佳一致逼近函数:,定义6.4 (最佳一致逼近函数),则称 为f(x)在H中的最佳一致逼近函数.,设f(x)在a,b上连续, H为给定的函数类, 若函数 满足:,特例. 若,称为最佳一致逼近多项式Pn(x).,若,若,若,可以证明, 若f(x)在a,b上连续, 其最佳一致逼近多项式必定存在且唯一.,定理6.7 (Chebyshev定理),第6章 函数逼近,f(x)在a,b上的零次最佳一致逼近多项式.,若f(x)在区间a,b上连续, 则 是f(x)在a,b上的n次最佳一致逼近多项式的充要条件是, Pn(x)在a,b上至少有n+2个依次轮流为正负的偏差点(也称为等幅振动点).,由于P0(x)=const,证明. (略),推论:,则 是,记,证明. 由闭区间上连续函数的性质, 存在 使得,x1,x2分别为正负偏差点. 由定理6.6, P0(x)为最佳零次逼近多项式.,一般情况下, 较难求得最佳一致逼近多项式. 下面举例说明.,最佳一致逼近多项式的例子,第6章 函数逼近,解. 设一次最佳一致逼近多项式为,求 在0,1区间上的一次最佳一致逼近多项式.,根据Chebyshev定理, P1(x)在0,1上至少有三个等幅振动点.,记,偏差点使g(x)取极值, 或最大(小)值, 即,要使,另外两个偏差点只能是0,1的端点.,于是,记,最佳一致逼近多项式的例子(续),第6章 函数逼近,在0,1区间上的一次最佳一致逼近多项式的图形.,Chebyshev插值法,第6章 函数逼近,Chebyshev多项式 Tn+1(x)在-1,1上n+1个互异的零点作为节点:,由于a,b上函数, 总可通过线性变换, 化为-1,1区间的函数. 故下面的讨论适用于任意区间.,如果f(x)在-1,1上n+1可微, 由第5章的余项公式:,Chebyshev插值的基本思想,作为n次最佳一致逼近多项式的近似.,其中,与Tn+1(x) 有相同的零点.,定理6.8 (Chebyshev插值余项最小),第6章 函数逼近,设 为最高次项系数为1的n次多项式的集合, 则有:,证明. (略),即, 在所有n次多项式中, Chebyshev插值多项式产生的最大误差是最小的. 因此, n次Chebyshev插值多项式可作为最佳一致逼近多项式的近似.,