§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 }
8 3 Optimal approximation >切比雪夫多项式/ Chebyshev polynomials 考虑三角函数cos(nO)在[0,x]上的n+1个极值点。 当θ4=-丌(k=0,…,n)时,cos(n)交错达到极大值1和极 n 小值-1,且存在系数ay…,an使得cos(n)=∑a(cos) 令x=c0s(0),则x∈[-1,1l Tn(x)=cos(n6)=cos(m; arc cosr)称为 Chebyshev多项式 今T的重要性质: a当4=cosz(k=0,,m)时,T()交错取到极大值1 和极小值-1,即T(t)=(-1)4T(x) 2k-1 a当x=c0s z(k=1,…,n)时T(xk)=0,即{x1…, 2 xn}为T(x)的n个零点
➢ 切比雪夫多项式 /* Chebyshev polynomials */ §3 Optimal Approximation 考虑三角函数 cos(n ) 在[ 0, ] 上的 n + 1 个极值点。 当 时， cos(n )交错达到极大值 1 和极 小值 −1 ，且存在系数 a0 , …, an 使得 (k 0, 1, ... , n) n k k = = = = n k k n ak 0 cos( ) (cos ) 令 x = cos( ) ，则 x [ −1 , 1 ]。 T (x) cos(n ) cos(n·arc cos x) n = = 称为Chebyshev多项式 ❖ Tn 的重要性质： 当 时， 交错取到极大值 1 和极小值−1，即 cos (k 0, 1, ... ,n) n k t k = = ( ) n k T t = − T (t ) ( 1) ||T (x)|| n k n k 1 当 时 ，即 {x1 , …, xn } 为Tn (x)的n个零点。( 1, ... , ) 2 2 1 cos k n n k xk = − = Tn (xk ) = 0
83 Optimal approximation aTn(x)满足递推关系: To()=1, T()=x, Tu(x)=2x T,(x)-T-(x) Tn(x)为n次多项式,首项系数为2n且Tn(x)只含 x的偶次幂,Tn+1(x)只含x的奇次幂。 a{T(x),T1(x),…}是[-1,1|上关于权p(x)= 正交的 函数族。即在内积(x,)=,m(x(xm(x)的意义下有 0k≠l OKOK,I think it's enough for us. (T,T)={zk=l=0 What's our target again? k=l≠0 v3在[-1,1上求切比雪夫交错组{4,…,tn+}。 9v30在-1,1上求函数x的n-阶OUAP
§3 Optimal Approximation Tn (x)满足递推关系： T0 (x) = 1， T1 (x) = x， ( ) 2 ( ) ( ) 1 1 T x x T x T x n+ = n − n− Tn (x)为 n 次多项式，首项系数为 。且T2n (x)只含 x 的 次幂， T2n+1(x)只含x 的 次幂。 2 n−1 偶 奇 { T0 (x), T1 (x), … } 是[ −1 , 1 ]上关于权 正交的 函数族。即在内积 的意义下有 2 1 1 ( ) x x − = − = 1 1 (T ,T ) (x)T (x)T (x)dx k l k l = = = = 0 2 0 0 ( , ) k l k l k l Tk Tl OKOK, I think it’s enough for us… What’s our target again? v 3.1 在[ −1, 1]上求切比雪夫交错组{ t1 , …, tn+1 } 。 v 3.0 在[ −1, 1]上求函数 x n 的n−1阶 OUAP
8 3 Optimal approximation 令可见:若取v(x)=T(x ,则wn在[-1,1上有m+1个极 值点{k},也即Pn1(x)=xn-wn(x)关于x在-1,1上有 n+1个交错偏差点{4}。30k 在(-1,上求{x,…,x}使得m()-i(x=x)的 n最小 ‖Pn1(x)-x”取最小值→ minn,l=Tn(x) M,∈I 2′ 2 令{x1…xn}即为T(2 、如季阶多项式的位置,使得P()刚 monic polynomials of degree n 好是y的OUAP?即,使插值余项|Rx X-x 达到极小? (n+1) 令取{x0,…,xn}为Tn+1(x)的n+1个零点,做y的插值多项式 Pn(x),则插值余项的上界可达极小 2"(m1)!
Tn (x)的n个零点。 §3 Optimal Approximation ❖ 可见：若取 ，则wn在[ −1 , 1 ]上有 n+1 个极 值点{ tk }，也即Pn−1 (x) = x n − wn (x)关于x n在[ −1 , 1 ]上有 n+1个交错偏差点{ tk } 。 1 2 ( ) ( ) − = n n n T x w x v3.0 OK v 2.1 在[ −1, 1]上求{ x1 , …, xn } 使得 的 ||wn || 最小。 = = − n i wn x x xi 1 ( ) ( ) || −1 ( ) − || 取最小值 n n P x x − = ( ) 2 1 min || || 1 w Tn x n n wn n 1 2 1 − = n n = {首项系数为1的 n 阶多项式 /*monic polynomials of degree n */ } ❖ { x1 , …, xn } 即为 如何确定插值节点{ x0 , …, xn }的位置，使得Pn (x) 刚 好是 y 的OUAP ？即，使插值余项 达到极小？ v 2.0 = + − + = n i i n n x x n y R x 0 ( 1) ( ) ( 1)! ( ) | ( )| ❖ 取{ x0 , …, xn } 为Tn+1(x)的n+1个零点，做 y 的插值多项式 Pn (x)，则插值余项的上界可达极小 。 2 (n +1)! M n
8 3 Optimal approximation 注: G上界最小不表示Rn(x)l最小,故Px)严格意义上只是yx) 的近似最佳逼近多项式; 对于一般区间x∈a,b,可作变量替换x=a+b+t,则 t∈-1,1],这时 m(x)=wn1(+221)=(叶2+2t一为”2 +b t=x (e2)y(t-t1).(t-t) n+1 (b-a)+ 2 22m+1 MMI(t) 即以x=2+2m2k+x)为插值节点…,n), a+bb一 2n+2 得P(x),余项Rx)=y(5(b-Tm)有最小上界 +1 (n+1)!2
§3 Optimal Approximation 注： 上界最小不表示| Rn (x)|最小，故Pn (x)严格意义上只是y(x) 的近似最佳逼近多项式； 对于一般区间 x [a, b] ，可作变量替换 ，则 t [ −1 , 1 ] ，这时 t a b b a x 2 2 − + + = ( ) ( ) ( )...( ) 1 1 2 2 2 2 0 2 2 n a b b a a b b a a b b a n n w x = w + t = + t − x + t − x + − + − + − + + ( ) ( )...( ) 0 1 2 n n b a = t − t t − t + − ( ) ( ) ( ) 1 2 ( ) 1 2 1 1 2 2 1 1 T t T t n b a n n b a n n n + − + + − + + = = 即以 为插值节点 (k=0,…, n)， 得Pn (x)，余项 有最小上界。 + − + + + = 2 2 2 1 cos 2 2 n a b b a k xk ( ) 2 ( ) ( 1)! ( ) ( ) 2 1 1 ( 1) 1 T t b a n y R x n n n n n + + + + − + =
83 Optimal approximation 例:求f(x)=e在0,1上的近似最佳逼近多项式,使其误差 不超过05×10-4。 解:①根据误差上界确定n: e Rn|≤ <-×10-4 (n+1)!2 ②计算T5(的根: 3兀 5兀 to=cos,t, 9丌 cos cos 10 lo,t,=cos 102=c0s a+b b-a t=:(t+1) 2 2 1.3兀 x0=(c0+1)≈0.98,x=(c0+1)≈0.79 5丌 7丌 x2=(C0+1)≈0.50,x3=(c0s+1)≈0.21 1.9兀 x=2(c010+)02③以x,…,x为节点作L(x)
§3 Optimal Approximation 例：求 f (x) = e x 在[0, 1]上的近似最佳逼近多项式，使其误差 不超过 0.510−4 。 解： 根据误差上界确定 n : 4 10 2 1 2 1 ( 1)! | | 2 1 − + n n+ n e R n = 4 计算 T5 (t)的根： 10 9 , cos 10 7 , cos 10 5 , cos 10 3 , cos 10 cos 0 1 2 3 4 t = t = t = t = t = ( 1) 2 1 2 2 = + − + + = t t a b b a x 1) 0.02 10 9 (cos 2 1 1) 0.21 10 7 (cos 2 1 1) 0.50 , 10 5 (cos 2 1 1) 0.79 10 3 (cos 2 1 1) 0.98 , 10 (cos 2 1 4 2 3 0 1 = + = + = + = + = + x x x x x 以 x0 , …, x4 为节点作L4 (x)