曲线拟合与函数逼近省公共课一等奖全国赛课获奖课件.pptx

依然是已知依然是已知 x1 xm;y1 ym,求一个简单求一个简单易算近似函数易算近似函数 P(x)f(x)。不过不过 m 很大；很大；yi 本身是测量值，不准确，即本身是测量值，不准确，即 yi f(xi)这时没必要取这时没必要取 P(xi)=yi,而要使而要使 P(xi)yi 总体上总体上尽可能小。尽可能小。拟合标准：拟合标准：使使 最小最小太复杂太复杂 使使 最小最小不可导，求解困难不可导，求解困难 使使 最小最小按均方误差到达极小结构拟合曲按均方误差到达极小结构拟合曲线方法称为最小二乘法线方法称为最小二乘法第第7章章 曲线拟合与函数迫近曲线拟合与函数迫近第1页设有直线设有直线p(x)=a+bx，拟合点坐标为，拟合点坐标为(xi,yi),i=1,2,m；均方误差为；均方误差为确定直线方程确定直线方程 计算计算min Q(a,b)最小值最小值由多元函数极值原理，由多元函数极值原理，min Q(a,b)极小值需满足：极小值需满足：得到满足最小均方差法方程组（正规方程）：得到满足最小均方差法方程组（正规方程）：线性拟合：线性拟合：第2页整理得到满足最小均方差法方程组（正规方程）：整理得到满足最小均方差法方程组（正规方程）：写成矩阵形式：写成矩阵形式：第3页用消元法或克莱姆方法解出方程组用消元法或克莱姆方法解出方程组第4页法方程组法方程组给定一组数据给定一组数据(xi,yi),i=1,2,m；xi互不相同，互不相同，拟合直线拟合直线p(x)=a+bx均方误差均方误差定义定义第5页做出法方程组得元素表：做出法方程组得元素表：给出以下离散数据，试对数据做出给出以下离散数据，试对数据做出线性拟合线性拟合并计算并计算均方误差均方误差例：例：形成法方程组形成法方程组解解:设拟合直线设拟合直线p(x)=a+bx，法方程组，法方程组计算得计算得:a=1.7729018 b=1.6219643 所以，拟合直线：所以，拟合直线：p(x)=1.7729018+1.6219643x第6页给定数据序列给定数据序列(xi,yi),i=1,2,m，设设p(x)=a0+a1x+a2x2，做出拟合函数与数据序列均方误差为做出拟合函数与数据序列均方误差为由多元函数极值原理，由多元函数极值原理，min Q(a0,a1,a2)极小值需满足：极小值需满足：二次拟合函数：二次拟合函数：第7页整理得到满足最小均方差法方程组（正规方程）：整理得到满足最小均方差法方程组（正规方程）：注：注：法方程系数矩阵是对称法方程系数矩阵是对称 当当N5时时，法方程系数矩阵是病态，在计算中法方程系数矩阵是病态，在计算中要用双精度或一些特殊算法以保护解准确性要用双精度或一些特殊算法以保护解准确性第8页给出以下离散数据，试对数据做出形如给出以下离散数据，试对数据做出形如a+bx2拟合曲线拟合曲线解：解：设拟合函数设拟合函数p(x)=a+bx2，法方程组，法方程组整理得：整理得：例：例：第9页计算得计算得a=-3.0，b=1.0所以，拟合直线所以，拟合直线f(x)=-3.0+1.0 x2第10页确定多项式确定多项式 ，对于一组，对于一组数据数据(xi,yi)(i=1,2,m)使得使得 到到达达极小极小，这里，这里 n m。naaa10 实际上是实际上是 a0,a1,an 多元函数，即多元函数，即 =+=miinininyxaxaaaaa121010.),.,(在在 极值点应有极值点应有kiminjijijxyxa =102=+njmikiimikjijxyxa0112记记 =mikiikmikikxycxb11,法方程组法方程组(或或正规方程组正规方程组)回归系数回归系数第11页L-S 拟合多项式拟合多项式存在唯一存在唯一(n 0,b 0)线性化：线性化：由由 可做变换可做变换xbay lnlnbBaAxXyY=,ln,1,lnBXAY+就是个就是个线性问题线性问题将将 化为化为 后易解后易解 A 和和B),(iiYX),(iiyx见见P147例例7-2第16页/*Orthogonal Polynomials&Least-Squares Approximation */已知已知 x1 xm;y1 ym,求一个简单易算近求一个简单易算近似函数似函数 P(x)f(x)使得使得 最小。最小。已知已知 a,b上定义上定义 f(x)，求一个简单易算近，求一个简单易算近似函数似函数 P(x)使得使得 最小。最小。线线性性无无关关/*linearly independent*/函函数数族族 0(x),1(x),n(x),满足条件：其中任意函数线性组合满足条件：其中任意函数线性组合 a0 0(x)+a1 1(x)+an n(x)=0 对任意对任意 x a,b成立成立当且仅当当且仅当 a0=a1=an=0。2 正交多项式与最小二乘拟合正交多项式与最小二乘拟合第17页2 Orthogonal Polynomials&L-S Approximation考考虑虑普普通通线线性性无无关关函函数数族族=0(x),1(x),n(x),，其其有有限限项项线线性性组组合合 称称为为广广义义多项式多项式/*generalized polynomial*/.常见多项式：常见多项式：j(x)=x j 对应对应代数代数多项式多项式/*algebraic polynomial*/j(x)=cos jx、j(x)=sin jx j(x),j(x)对对应应三角三角多项式多项式/*trigonometric polynomial*/j(x)=e kj x,ki kj 对应对应指数指数多项式多项式/*exponential polynomial*/第18页2 Orthogonal Polynomials&L-S Approximation权函数：权函数：离散型离散型/*discrete type*/依据一系列离散点依据一系列离散点 拟合时，在每一拟合时，在每一误差前乘一正数误差前乘一正数wi，即，即 误差函数误差函数 ，这个，这个wi 就称作就称作权权/*weight*/，反应该点主要程度。，反应该点主要程度。=niiiiyxPw12)(连续型连续型/*continuous type*/在在a,b上用广义多项式上用广义多项式 P(x)拟合连续函数拟合连续函数 y(x)时时,定义定义权权函数函数 (x)Ca,b，即误差函数，即误差函数 =。权函数必须权函数必须(x)满足：非负、可积，且在满足：非负、可积，且在a,b任何子区任何子区间上间上(x)0。第19页2 Orthogonal Polynomials&L-S Approximation广义广义 L-S 拟合：拟合：离散型离散型/*discrete type*/在点集在点集 x1 xm 上测得上测得 y1 ym，在一组权系数，在一组权系数 w1 wm 下求广义多项式下求广义多项式 P(x)使得使得误差函数误差函数 最小。最小。=niiiiyxPw12)(连续型连续型/*continuous type*/已知已知 y(x)Ca,b 以及权函数以及权函数 (x)，求广义多项式求广义多项式 P(x)使使得误差函数得误差函数 =最小最小。dxxyxPxba2)()()(内积内积与与范数范数离散型离散型连续型连续型则易证则易证(f,g)是是内积内积，而而 是是范数范数。(f,g)=0 表示表示 f 与与 g 带权正交带权正交。广义广义 L-S 问题可叙述为：求广义多项式问题可叙述为：求广义多项式P(x)使得使得 最小。最小。第20页2 Orthogonal Polynomials&L-S Approximationnkyaknjjjk,.,0,),(),(0=设设则完全类似地有：则完全类似地有：)(.)()()(1100 xaxaxaxPnn +=法方程组法方程组/*normal equations*/定理定理 Ba=c 存在唯一解存在唯一解 0(x),1(x),n(x)线性无线性无关。关。即：即：),(),(),(00yyaabnnjiij =c证实：证实：若存在一组系数若存在一组系数 i 使得使得0.1100=+nn 则等式两边分别与则等式两边分别与 0,1,n作内积，得到：作内积，得到：即：即：B =0 第21页2 Orthogonal Polynomials&L-S Approximation例：例：用用 来拟合来拟合 ，w 1解：解：0(x)=1，1(x)=x，2(x)=x2It is soooo simple!What can possibly go wrong?7623)(463|484,|1=BcondBB第22页2 Orthogonal Polynomials&L-S Approximation 连续型拟合中，取连续型拟合中，取则则 Hilbert阵！阵！改进：改进：若能取函数族若能取函数族=0(x),1(x),n(x),，使得任意一对，使得任意一对 i(x)和和 j(x)两两两两（带权）正（带权）正交交，则，则 B 就化为就化为对角阵对角阵！这时直接可算出这时直接可算出ak=Well,no free lunch anyway 正交正交多项式多项式结构：结构：将正交函数族中将正交函数族中 k 取为取为k 阶阶多项式多项式，为简单起见，可取，为简单起见，可取 k 首项系数为首项系数为 1。有递推有递推关系式：关系式：其中其中证实略证实略p.148-149例：例：第23页2 Orthogonal Polynomials&L-S Approximation例：例：用用 来拟合来拟合 ，w 1解：解：经过正交多项式经过正交多项式 0(x),1(x),2(x)求解求解设设)()()(221100 xaxaxay +=1)(0=x 229),(),(0000=ya25),(),(00001=x25)()()(011=xxxx 537),(),(1111=ya25),(),(11112=x45),(),(00111=b b55)(45)()25()(2012+=xxxxxx 21),(),(2222=ya与前例结果一致。与前例结果一致。注：注：手算时也可手算时也可用待定系数法确用待定系数法确定函数族。定函数族。第24页/*Optimal Approximation*/最正确最正确平方平方迫近：即连续型迫近：即连续型L-S迫近，在迫近，在 意义下，使得意义下，使得 最小。最小。最正确最正确一致一致迫近迫近/*uniform approximation*/在在 意义下，使得意义下，使得 最小。也最小。也称为称为minimax problem。偏差偏差/*deviation*/若若 ，则称，则称 x0 为为 偏差点偏差点。Didnt you say its a very difficult problem?Take it easy.Its not so difficult if we consider polynomials only.3 函数最正确迫近函数最正确迫近第25页3 Optimal Approximationv 1.0 最正确一致迫近多项式最正确一致迫近多项式/*optimal uniform approximating polynomial*/结构：求结构：求 n 阶多项式阶多项式 Pn(x)使得使得|Pn y|最小。最小。直接结构直接结构 OUAP 确实比较困难，不妨换个角度，先确实比较困难，不妨换个角度，先考查它应该具备考查它应该具备性质性质。有以下结论：。有以下结论：OUAP 存在，且必同时有存在，且必同时有 偏差点。偏差点。证实：证实：存在性证实略。后者用反证法，设只有正偏差点。存在性证实略。后者用反证法，设只有正偏差点。设设而对于全部而对于全部 x a,b 都有都有是是n阶多项式阶多项式是误差更小多项式是误差更小多项式第26页3 Optimal Approximation（Chebyshev定理）定理）Pn 是是 y OUAP Pn 关于关于 y 在定义域上在定义域上最少有最少有n+2个个交织交织 偏差点。偏差点。即存在点集即存在点集 a t1 tn+2 b 使得使得 tk 称为称为切比雪夫交织组切比雪夫交织组/*Chebyshev alternating sequence*/若若 且且 y 不是不是 n 次多项式，则次多项式，则 n 次次OUAP 唯一唯一。证实：证实：反证，设有反证，设有2个个OUAPs，分别是，分别是Pn 和和 Qn 。则它们平均函数则它们平均函数 也是一个也是一个OUAP。2)()()(xQxPxRnnn+=对于对于Rn 有有Chebyshev交织组交织组 t1,tn+2 使得使得nkknkknkknnEtytQtytPtytRE +=|)()(|21|)()(|21|)()(|nkknkknEtytQtytP=|)()(|)()(|则最少在一个点上必须有则最少在一个点上必须有)()()()(knkkkntQtytytP=0)()(=kkntytR0=nE第27页3 Optimal Approximation 由由Chebyshev定理可推出：定理可推出：Pn(x)y(x)在定义域上最少变号在定义域上最少变号 次，故最少有次，故最少有 个个根根。xy0yy x=()yy xEn=+()yy xEn=()yP xn=()n+1n+1可见可见Pn(x)是是 y(x)某一个某一个插值多项式插值多项式 怎样确定怎样确定插值节点插值节点 x0,xn 位置，使得位置，使得Pn(x)刚好是刚好是 y OUAP？即，使插？即，使插值余项值余项v 2.0到达极小？到达极小？第28页3 Optimal Approximationv 2.1 在在 1,1上求上求 x1,xn 使得使得|wn|最小。最小。=niinxxxw1)()(注意到注意到 ，要使，要使|wn|最小就意味着最小就意味着)()(1xPxxwnnn =v 3.0 在在 1,1上求函数上求函数 xn n 1阶阶 OUAP。由由Chebyshev定理可推出：定理可推出：Pn 1(x)关于关于xn 有有n+1个个偏差点，即偏差点，即wn(x)在在 n+1个点上交织取极大、极小值。个点上交织取极大、极小值。v 3.1 在在 1,1上求上求切比雪夫交织组切比雪夫交织组 t1,tn+1 。第29页/*Chebyshev polynomials*/3 Optimal Approximation考虑三角函数考虑三角函数 cos(n )在在 0,上上 个极值点。个极值点。n+1当当 时，时，cos(n )交织到达极大值交织到达极大值 1 和和极小值极小值 1，且存在系数，且存在系数 a0,an 使得使得 令令 x=cos()，则，则 x 1,1。)cos arccos()cos()(xnnxTn=称为称为Chebyshev多项式多项式 Tn 主要性质：主要性质：当当 时，时，交织取到极大值交织取到极大值 1 和极小值和极小值 1，即，即1 当当 时时 ，即，即 x1,xn 为为Tn(x)n个零点。个零点。切比雪夫多项式切比雪夫多项式第30页3 Optimal Approximation Tn(x)满足递推关系：满足递推关系：T0(x)=1，T1(x)=x，Tn(x)为为 n 次多项式，首项系数为次多项式，首项系数为 。且。且T2n(x)只含只含 x 次幂，次幂，T2n+1(x)只含只含x 次幂。次幂。2n 1偶偶奇奇 T0(x),T1(x),是是 1,1 上关于权上关于权 正交函数族。即在内积正交函数族。即在内积 意义下意义下有有 OKOK,I think its enough for us Whats our target again?v 3.1 在在 1,1上求上求切比雪夫交织组切比雪夫交织组 t1,tn+1 。v 3.0 在在 1,1上求函数上求函数 xn n 1阶阶 OUAP。第31页Tn(x)n个个零点零点。3 Optimal Approximation 可见：若取可见：若取 ，则，则wn在在 1,1 上有上有 n+1 个个极极值点值点 tk，也即，也即Pn 1(x)=xn wn(x)关于关于xn在在 1,1 上有上有n+1个交织个交织偏差点偏差点 tk 。v3.0 OKv 2.1 在在 1,1上求上求 x1,xn 使得使得|wn|最小。最小。=niinxxxw1)()(取最小值取最小值 n=首项系数为首项系数为1 n 阶多项式阶多项式/*monic polynomials of degree n*/x1,xn 即即为为 怎样确定插值节点怎样确定插值节点 x0,xn 位置，使得位置，使得Pn(x)刚刚好是好是 y OUAP？即，使插值余项？即，使插值余项到达极小？到达极小？v 2.0 取取 x0,xn 为为Tn+1(x)n+1个个零点零点，做，做 y 插值多项式插值多项式Pn(x)，则插值余项上界可达极小，则插值余项上界可达极小 。第32页3 Optimal Approximation注：注：上界上界最小不表示最小不表示|Rn(x)|最小，故最小，故Pn(x)严格意义上只是严格意义上只是y(x)近似近似最正确迫近多项式；最正确迫近多项式；对于普通区间对于普通区间 x a,b，可作变量替换，可作变量替换 ，则则 t 1,1 ，这时，这时即以即以 为插值节点为插值节点(k=0,n)，得，得Pn(x)，余项，余项 有最小上有最小上界。界。第33页3 Optimal Approximation例：例：求求 f(x)=ex 在在0,1上近似最正确迫近多项式，使其误上近似最正确迫近多项式，使其误差不超出差不超出 0.5 10 4。解：解：依据误差上界确定依据误差上界确定 n:n=4 计算计算 T5(t)根：根：以以 x0,x4 为节点作为节点作L4(x)第34页3 Optimal Approximation 多项式降次多项式降次/*reduce the degree of polynomial with a minimal loss of accuracy*/设设 f(x)Pn(x)。在降低在降低 Pn(x)次数同时次数同时,使所以增加误差尽可能小使所以增加误差尽可能小,也叫也叫 economiza-tion of power series。从从 Pn中去掉一个含有其最高次项中去掉一个含有其最高次项 ,结果降次结果降次为为 ,则：则：PnPn 1|)(|max|)()(|max|)()(|max1,11,111,1xPxPxfxPxfnnn +因降次而增误差因降次而增误差设设 Pn 首项系数为首项系数为an，则取，则取 可使可使精度尽可能少损失。精度尽可能少损失。12)()(=nnnnxTaxP Chebyshev 多项式其它应用多项式其它应用第35页3 Optimal Approximation例：例：f(x)=ex 在在 1,1上上4 阶阶 Taylor 展开为展开为，此时误差，此时误差请将其请将其降为降为2阶多项式阶多项式。解：解：取取（查表知（查表知 ）取取（查表知（查表知 ）若简单取若简单取 ，则误差，则误差另类解法可查另类解法可查p.163表表7-2，将将x3 和和x4 中中T3 和和T4 删除。删除。注：注：对普通区间对普通区间a,b，先将，先将 x 换为换为 t，考虑，考虑 f(t)在在 1,1上迫近上迫近Pn(t)，再将，再将 t 换回换回x，最终得到，最终得到Pn(x)。HW:p.164#3第36页