§3函数的最佳逼近/ Optimal Approximation >最佳平方逼近:即连续型LS逼近,在‖∫l2=√,f意义 下,使得‖P-y|2最小 偏差 >最佳一致逼近/ uniform approximation* I deviation*/ 在‖∫|=mx|f(x)|意义下,使得‖Py|最小。也称 xEla, b 为 minimax problem。 若P(x)-y(x)=±‖P-y,则称x0为±偏差点。 Take it easv. It's not so difficultif we consider polynomials only
§3 函数的最佳逼近 /* Optimal Approximation */ ➢ 最佳平方逼近：即连续型L-S逼近，在 意义 下，使得 最小。 || || ( , ) 2 f = f f 2 || P − y || ➢ 最佳一致逼近 /* uniform approximation */ || || max | ( )| [ , ] f f x x a b 在 = 意义下，使得 最小。也称 为minimax problem。 − || P y || 偏差 /* deviation*/ 若 P(x0 )− y(x0 ) = || P − y || ，则称 x0 为 偏差点。 Didn’t you say it’s a very difficult problem? Take it easy. It’s not so difficult if we consider polynomials only
83 Optimal approximation 、10最佳一致逼近多项式 /*optimal uniform approximating polynomia的构造:求n阶多项式Px)使得Pn-y|最 直接构造OUAP的确比较困难,不妨换个角度,先 考察它应该具备的性质。有如下结论: ①OUAP存在,且必同时有±偏差点。 证明:存在性证明略。后者用反证法,设只有正偏差点。 设‖P-y|=max|P(x)-y(x)|=En tEla, b 而对于所有的x∈a,b都有P(x)yx)>-En →-En+E≤P(x)-y(x)≤En |(x)-6/2|-y(x)≤En-E/2 是n阶多项式 是误差更小的多项式
§3 Optimal Approximation v 1.0 最佳一致逼近多项式 /* optimal uniform approximating polynomial */ 的构造：求 n 阶多项式 Pn (x) 使得 || Pn − y || 最 小。 直接构造 OUAP 的确比较困难，不妨换个角度，先 考察它应该具备的性质。有如下结论： OUAP 存在，且必同时有 偏差点。 证明：存在性证明略。后者用反证法，设只有正偏差点。 设 n n x a b Pn − y = P x − y x = E || || max | ( ) ( )| [ , ] 而对于所有的 x[a, b] 都有 n x En P (x) − y( ) − n n x En − E + P (x) − y( ) |[ ( )− / 2]− ( )| − / 2 n En P x y x 是n阶多项式 是误差更小的多项式
8 3 Optimal approximation ②( Chebyshev定理)Pn是y的OUAP台Pn关于y在定义域 上至少有n+2个交错的±偏差点。 即存在点集a≤t1<…<tn+2≤b使得Pk)-y(tk)=±(-1)‖Pn-yl {}称为切比雪夫交错组/ Chebyshev alternating sequence ③若y∈Cla,b且y不是n次多项式则n次OUAP唯 证明:反证,设有2个 OUAP,s八分别是P和Qn 则它们的平均函数R(=2)+也是一个OUAP。? 2 对于Rn有 hebyshev交错组4…,2}使得 En=R()-(4)≤1P(G)-)+(Q(4)-(4)sEn →→|P(t)-y()=1Q,(x)-()=En? 则至少在一个点上必须有P())=()-a()? R, (tk)-y(t =0 ?
§3 Optimal Approximation （Chebyshev定理）Pn 是 y 的OUAP Pn 关于 y 在定义域 上至少有n+2个交错的 偏差点。 即存在点集 a t1 <…< tn+2 b 使得 { tk }称为切比雪夫交错组 /* Chebyshev alternating sequence */ − = − − P (t ) y(t ) ( 1) || P y || n k n k k 若 y C[a,b] 且 y 不是 n 次多项式，则 n 次OUAP 唯一。 证明：反证，设有2个OUAP’s，分别是Pn 和 Qn 。 则它们的平均函数 也是一个OUAP。 2 ( ) ( ) ( ) P x Q x R x n n n + = 对于Rn 有Chebyshev交错组{ t1 ,…, tn+2 }使得 n n k k n k k n k k En E = R t − y t P t − y t + |Q (t ) −y(t )| 2 1 | ( ) ( )| 2 1 | ( ) ( )| n k k n k k En | P (t ) − y(t )| = | Q (t ) − y(t )| = 则至少在一个点上必须有 ( ) ( ) ( ) ( ) n k k k n k P t − y t = y t −Q t Rn (t k )− y(t k ) = 0 En = 0
8 3 Optimal approximation ④由 Chebyshev定理可推出:Pn(x)-y(x)在定义域上至少变号 n+1次,故至少有n+1个根。 可见Px)是y(x)的 某一个插值多项式 y=y(c)+E y=y y=y()-En@、20如何确定插 值节点{x0,…,xn}的 位置,使得P(x)刚 好是p的OUAP?即, 0 使插值余项 ()-2-151(x-x)达到极小?
§3 Optimal Approximation 由Chebyshev定理可推出：Pn (x) − y(x) 在定义域上至少变号 次，故至少有 个根。 x y 0 y = y(x) y y x En = ( ) + y y x En = ( ) − y = Pn (x) n+1 n+1 可见Pn (x) 是 y(x)的 某一个插值多项式 如何确定插 值节点{ x0 , …, xn }的 位置，使得Pn (x) 刚 好是 y 的OUAP ？即， 使插值余项 v 2.0 达到极小？ = + − + = n i i n n x x n y R x 0 ( 1) ( ) ( 1)! ( ) | ( )|
8 3 Optimal approximation 1在-1,1上求(xn…,xn}使得n(-(x-x) 的vl最小 注意到w(x)=x"-P1(x),要使wl最小就意味着 ⑨、30在-1,1上求函数x的n-1阶OUAP 由 Chebyshev定理可推出:Pn-1(x)关于x有n+1个偏 差点,即wnx)在n+1个点上交错取极大、极小值。 回在-,1止上求切比雪夫交错组{n…,.}
§3 Optimal Approximation v 2.1 在[ −1, 1]上求{ x1 , …, xn } 使得 的||wn || 最小。 = = − n i wn x x xi 1 ( ) ( ) 注意到 ，要使||wn w (x) x Pn 1 (x) || 最小就意味着 n n = − − v 3.0 在[ −1, 1]上求函数 x n 的n−1阶 OUAP。 由Chebyshev定理可推出：Pn−1 (x) 关于x n 有n+1个偏 差点，即wn (x)在 n+1个点上交错取极大、极小值。 v 3.1 在[ −1, 1]上求切比雪夫交错组{ t1 , …, tn+1 }