中国科学技术大学：《计算方法》课程教学资源（课件讲义）第二章 最小二乘拟合

第二章最小二乘拟合 2

2 第二章 最小二乘拟合

拟合函数 ■在实际问题中，数据不可避免的会有误差，插值函数 会将这些误差也包括在内 ■若误差较大时，用插值方法构造函数的效果不好 ■用通近的方法构造函数 ●不要求过所有的点（可以减少误差影响） ●尽可能表现数据的趋势，靠近这些点 16 14 12 10 8 ￥=1.538x-0.360 64 2468i0 3

拟合函数  在实际问题中，数据不可避免的会有误差，插值函数 会将这些误差也包括在内  若误差较大时，用插值方法构造函数的效果不好  用逼近的方法构造函数  不要求过所有的点（可以减少误差影响）  尽可能表现数据的趋势，靠近这些点 3

拟合函数 1958 ■如何刻画数据点和通近函数之间的靠近程度？ ·给定一组观察或测量得到的一组离散数据序列{(x,y,) ，选定函数空间Φ，构造函数p(x)∈Φ，使得函数p(x)最 优的靠近高散数据序列{(x,y)%,即向量 =(p(x),p(x),p(xm)与Y=(y,2,ym)Y的误差或距离 最小 ■如何定义向量之间的距离：向量范数 R=0-Y=∑p(x)- 最小平均逼近 RQ-Y6=②x)-f 最小平方逼近 R =le-Y ll=max ((x)-y,D 最小一致逼近 1si≤m

拟合函数  如何刻画数据点和逼近函数之间的靠近程度？  给定一组观察或测量得到的一组离散数据序列 ，选定函数空间 ，构造函数 ，使得函数 最 优的靠近离散数据序列 ，即向量 与 的误差或距离 最小  如何定义向量之间的距离：向量范数 4 { } 1 (, ) m i i i x y = Φ ϕ( ) x ∈Φ ϕ( ) x { } 1 (, ) m i i i x y = ( ) 1 2 ( ), ( ), , ( ) T Q xx x = ϕϕ ϕ  m 1 2 (, , , )T Y yy y =  m 1 1 1 || || ( ) m i i i R QY x y ϕ = =− = − ∑ 1/2 2 2 2 1 || || ( ) m i i i R QY x y ϕ =   =− = −     ∑ { } 1 || || max | ( ) | i i i m R QY x y ∞ ∞ ϕ ≤ ≤ =− = − 最小平均逼近 最小平方逼近 最小一致逼近

拟合函数 Gauss:和Legendre分别发明 最小二乘法：R==o(x)- ●均方误差 ●按均方误差达到最小 ·优点：易于求解 ■最小二乘法是最基本的函数逼近方法，被广泛应用于 运筹学、统计学、通近论等各个领城 ■问题：如何选定函数空间Φ？ ●专业知识或工作经验 ●观察数据 5

拟合函数  Gauss和Legendre分别发明  最小二乘法：  均方误差  按均方误差达到最小  优点：易于求解  最小二乘法是最基本的函数逼近方法，被广泛应用于 运筹学、统计学、逼近论等各个领域  问题：如何选定函数空间 ？  专业知识或工作经验  观察数据 5 2 2 2 1 ( ) m i i i RR x y ϕ =   = = −     ∑ Φ

线性拟合和二次拟合函数 ■最小二乘问题：给定数据序列{(x,)和函数空间 D=spani (x)(x).(x) 求函数p(x)∈Φ，使得 m∑(ox)-y)月 其中p(x)=a1p,(x)+a2p2(x)+.+anpn(x),a,∈R,i=1,2,.n ■ 若定义 0(a,4.,a,)=2(o(x)-y)'=2(a(x)+a9,(x)++a,0.(x)-y 则最小二乘问题可写成 min_Q(a1,a2,.,an） aa,.aneR 6

线性拟合和二次拟合函数  最小二乘问题：给定数据序列 和函数空间 求函数 ，使得 其中  若定义 则最小二乘问题 可写成 6 { } 1 (, ) m i i i x y = 1 2 span{ ( ), ( ), , ( )}, n Φ = ϕϕ ϕ xx x  ϕ( ) x ∈Φ ( ) 2 1 min ( ) m i i i x y ϕ ϕ ∈Φ = ∑ − 11 2 2 ( ) ( ) ( ) ( ), , 1,2, nn i ϕϕ ϕ ϕ x a x a x a xa i n = + ++ ∈ =   ( ) ( ) 2 2 1 2 11 2 2 1 1 (, , , ) () () () () m n n ii i i nn i i i i Qa a a x y a x a x a x y ϕ ϕϕ ϕ = =   = − = + ++ − ∑ ∑ 1 2 1 2 , , min ( , , , ) n n aa a Qa a a  ∈ 

线性拟合和二次拟合函数 将Q(a,a)=∑(a,0,(x)+ap,(x)+.+a,p(x)-y)2写成矩阵的 表示形式：记 e(x) p2(x1) . .(x) p(x2) p2(x2) . (x2) a y2 A= ,X . ,b= 0(xm）p2(xm) . Pn(Xm)Jmn dn)nx ym)mxl 则有 (x)=Ax-b=xATAx-2x7ATb+bTb 二次型取最小值的条件 =0→2A'Ax-2A'b=0→A'Ax=A'b Ox 7

线性拟合和二次拟合函数  将 写成矩阵的 表示形式：记 则有  二次型取最小值的条件 7 ( ) 2 1 2 11 2 2 1 (, , , ) () () () m n i i nn i i i Qa a a a x a x a x y ϕϕ ϕ =   = + ++ − ∑ 11 21 1 1 1 12 22 2 2 2 1 2 1 1 () () () () () () , , , () () () n n m m nm m n n n m m xx x a y xx x a y xx x a y ϕϕ ϕ ϕϕ ϕ ϕϕ ϕ ×× ×           =  = =        A x b        2 2 ( ) || || 2 TT TT T Q x Ax b x A Ax x A b b b = −= − + ( ) 02 2 0 ∂Q T T TT =⇒ − =⇒ = ∂ x A Ax A b A Ax A b x

线性拟合和二次拟合函数 线性拟合：取函数空间Φ=span{L,x,p(x)=a+bx,则 m AAx=Ab 8

线性拟合和二次拟合函数  线性拟合：取函数空间 ， ，则 8 Φ = span{1, }x ϕ( ) x a bx = + T T A Ax A b = 1 1 2 11 1 m m i i i i mm m i i i i ii i mx y a b x x x y = = = = =         =        ∑ ∑ ∑∑ ∑

线性拟合和二次拟合函数 ■ 二次松合：取函数空间Φ=span{L,x,x2},p(x)=a+bx+cx2, 则 a ATAx=ATb b x 9

线性拟合和二次拟合函数  二次拟合：取函数空间 ， ， 则 9 2 Φ = span{1, , } x x 2 ϕ( ) x a bx cx =+ + T T A Ax A b = 2 1 1 1 2 3 11 1 1 234 2 111 1 m m m i i i i i i mm m m i i i i i ii i i mmm m i i i i i iii i m xx y a x x x b xy c x x x xy = = = = = = = = = = =                 =                      ∑∑ ∑ ∑∑∑ ∑ ∑∑∑ ∑

线性拟合和二次拟合函数 1958 ■形如aer曲线拟合：取函数空间Φ={aem|a,b∈R} ●非线性空间 ·线性化：作变换z=lny,有 z;=Iny, Ino(x)=In(ae )Ina+bx=A+Bx ●利用线性拟合求A,B ·类似地，可求形如a+曲线拟合 ■ 注意：变换后的所得拟合曲线，已经不在是平方误差 极小意义下的拟合曲线 10

线性拟合和二次拟合函数  形如 曲线拟合：取函数空间  非线性空间  线性化：作变换 ，有  利用线性拟合求  类似地，可求形如 曲线拟合  注意：变换后的所得拟合曲线，已经不在是平方误差 极小意义下的拟合曲线 10 bx ae { |, } bx Φ= ∈ ae a b  z y = ln ln ( ) ln( ) ln bx ϕ x ae a bx A Bx = = + =+ ln i i z y = A B, 1 a bx +

解矛盾方程组 ■矛盾方程组： an 412 an b a12 a22 a2n A= ,X= b= : amn mxn mxl ■ 当m>n时，方程组Ax=b通常无解，故称为矛盾方程 组 ■修改：要求均方误差最小 min‖Ax-bl ●最小二乘意义下的解 11

解矛盾方程组  矛盾方程组：  当 时，方程组 通常无解，故称为矛盾方程 组  修改：要求均方误差最小  最小二乘意义下的解 11 11 12 1 1 1 12 22 2 2 2 1 2 1 1 , , n n m m mn m n n n m m aa a x b aa a x b aa a x b ×× ×         =  = =       A x b        m n  Ax b = 2 min || || n 2 ∈ − x Ax b 