第七章曲线拟合与函数逼近 /R Approximation Theory 仍然是已知…m:1…m求个简单易 算的近似函数P(x)≈八(x) 但是③m很大; y本身是测量值,不准确,即y≠f(x) 这时没必要取P(x)=,而要使P(x)-总体上尽可能小 纔常见做法: 不可导,求解困难⑧太复杂 >使 max P(xi)-y l≤isn r/*minimax problem * >使P(x)-到最小 >使∑P(x)-1最小 ast-squares method
第七章 曲线拟合与函数逼近 /* Approximation Theory */ 仍然是已知 x1 … xm ; y1 … ym, 求一个简单易 算的近似函数 P(x) f(x)。 但是 ① m 很大； ② yi 本身是测量值，不准确，即 yi f (xi ) 这时没必要取 P(xi ) = yi , 而要使 P(xi ) − yi 总体上尽可能小。 常见做法： ➢ 使 最小 /* minimax problem */ max | ( ) | 1 i i i m P x − y 太复杂 ➢ 使 最小 = − m i i i P x y 1 | ( ) | 不可导，求解困难 ➢ 使 最小 /* Least-Squares method */ = − m i i i P x y 1 2 | ( ) |
§1最小二乘拟合多项式 L-S approximating polynomials 确窍多项式P(x)=a0+a1x+…+anx",对于一组数 据(x,y)(=1,2,…,m使得φ=∑IP(x)-y达到极小, 这里n<<m 9实际上是ao2 Plao, a 回归系数 在的极值点 I regression coefficients * 0s0g=2∑IP(x)-y1l0k aP(i) a 2∑∑a i=1 21∑a∑ j+k ∑y 0+0 0+n 0 记=∑,=∑y4國 =1 0 1+n
§1 最小二乘拟合多项式 /* L-S approximating polynomials */ 确定多项式 ，对于一组数 据(xi , yi ) (i = 1, 2, …, n) 使得 达到极小， 这里 n << m。 n n P(x) = a + a x + ... + a x 0 1 = = − m i i i P x y 1 2 [ ( ) ] a0 a1 an 实际上是 a0 , a1 , …, an 的多元函数，即 [ ] = = + + + − m i i n a a an a a xi an xi y 1 2 0 1 0 1 ( , , ... , ) ... 在 的极值点应有 k n ak = 0 , = 0, ... , k i m i i i k a P x P x y a = − = = ( ) 0 2 [ ( ) ] 1 k i m i n j i j a j xi y x = = = − 1 0 2 [ ] = − = = = + n j m i k i i m i j k aj xi y x 0 1 1 2 记 = = = = m i k k i i m i k bk xi c y x 1 1 , = + + + + n n n n n n c c a a b b b b . . . . . . ... . . . . . . . . . ... 0 0 0 0 0 0 法方程组(或正规方程组) /* normal equations */ 回归系数 /* regression coefficients */
8 1 L-S Approximating Polynomials 定理Ls拟合多项式存在唯-(m<m 证明:记法方程组为B=c x2 B=φφ 则有 其中∮ 对任意山≠0∈R+,必有φ≠0。 则dB=山中φ山叫中2>0 →B为正定阵,则非奇异,所以法方程组存在唯一解。 Wait a second! You only gave me a criticalpoint, but it's not necessarily a minimum point
§1 L-S Approximating Polynomials 定理 L-S 拟合多项式存在唯一 (n < m)。 证明：记法方程组为 Ba = c . B Φ Φ T = 则有 其中 c Φ y T = = n m m m n x x ... x . . . . . . . . . . . . . . . x x ... x Φ 2 1 2 1 1 1 1 对任意 u 0 R n+1 ，必有 Φu 0 。 1 0 + n u R Φ u = 0 若不然，则 存在一个 使得 … 即 x u k m n j j j k 0 , 1, ... , 0 = = = x1 , ... , xm 是 n 阶多项式 n n P(x) = u + u x + ... + u x 0 1 的根 则 || || 0 2 u Bu = u Φ Φu = Φu 2 T T T B为正定阵，则非奇异，所以法方程组存在唯一解。 Wait a second! You only gave me a critical point, but it’s not necessarily a minimum point !
8 1 L-S Approximating Polynomials 定理Bm=c的解确是p的极小点。即:设为解,则任 意b=(b1…bn)对应的多项式F(x)=∑bx必有 P(=XIP(x:)-V2s2IF(x:)-y12=9(b) 证明:(b)-9(a)=ΣF(x)-y;2-2P(x1)-y i=1 ∑[F(x)-P(x1)+P(x)-y2-∑[P(x;)-y i=1 i=1 ∑F(x)-P(x)+2F(x)-P(x((x)-1 i=1 注: L-s method首先要求设定P(x)的形式。若设 n=m-1,则可取P(x)为过m个点的m1阶插值多 项式,这时p=0 矿P(x)不一定是多项式,通常根据经验确定
§1 L-S Approximating Polynomials 定理 Ba = c 的解确是 的极小点。即：设 a 为解，则任 意 b = (b0 b1 … bn ) T 对应的多项式 必有 = = n j j F x bj x 0 ( ) = = = − − = m i m i a P xi yi F xi yi b 1 1 2 2 ( ) [ ( ) ] [ ( ) ] ( ) 证明： = = − = − − − m i i i m i b a F xi yi P x y 1 2 1 2 ( ) ( ) [ ( ) ] [ ( ) ] = = = − + − − − m i i i m i F xi P xi P xi yi P x y 1 2 1 2 [ ( ) ( ) ( ) ] [ ( ) ] = = = − + − − m i i i i i m i F xi P xi F x P x P x y 1 1 2 [ ( ) ( )] 2 [ ( ) ( )][ ( ) ] 0 注： L-S method 首先要求设定 P(x) 的形式。若设 n=m−1，则可取 P(x) 为过 m 个点的m−1阶插值多 项式，这时 = 0。 P(x) 不一定是多项式，通常根据经验确定
8 1 L-S Approximating Polynomials 例 -- 方案一:设y≈P(x)= ax+b 求a和b使得叫a,b)=2(x+b-y)最小。 -1 线性化广neH吧1,x=1,则 have to linearize it Y≈a+bX就是个线性问题 将(x1,y1)化为(X,Y)后易解a和b
§1 L-S Approximating Polynomials 例： x y (xi , yi ) , i = 1, 2, …, m 方案一：设 ax b x y P x + ( ) = 求 a 和 b 使得 最小。 = − + = m i i i i y ax b x a b 1 2 ( , ) ( ) But hey, the system of equations for a and b is nonlinear ! Take it easy! We just have to linearize it … 线性化 /* linearization */：令 ，则 x X y Y 1 , 1 = = Y a + bX 就是个线性问题 将( xi , yi ) 化为(Xi ,Yi ) 后易解 a 和b