§ 3 函数的最佳逼近 /* Optimal Approximation */
? 最佳 平方 逼近：即连续型 L-S逼近，在 意义
下，使得 最小。
),(|||| 2 fff ?
2|||| yP ?
? 最佳 一致 逼近 /* uniform approximation */
|)(|m a x|||| ],[ xff bax ???
在 意义下，使得 最小。也称
为 minimax problem。
?? |||| yP
偏差
/* deviation*/
若,则称 x0 为 ? 偏差点 。
????? ||||)()( 00 yPxyxP
Didn’t you say it’s a very
difficult problem?
Take it easy,It’s not so
difficult if we consider
polynomials only,
§ 3 Optimal Approximation
v 1.0 最佳一致逼近多项式 /* optimal uniform approximating
polynomial */ 的构造：求 n 阶多项式 Pn(x) 使得 || Pn ? y ||? 最
小。
直接构造 OUAP 的确比较困难，不妨换个角度，先
考察它应该具备的 性质 。有如下结论,
? OUAP 存在，且必同时有 ? 偏差点。
证明,存在性证明略。后者用反证法，设只有正偏差点。
设
nnbaxn ExyxPyP ???? ?? |)()(|m a x|||| ],[
而对于所有的 x?[a,b] 都有
nn ExyxP ??? )()(
nnn ExyxPE ????? )()(?
2/|)(]2/)([| ?? ???? nn ExyxP
是 n阶多项式 是误差更小的多项式
§ 3 Optimal Approximation
? （ Chebyshev定理） Pn 是 y 的 OUAP ? Pn 关于 y 在定义域
上至少有 n+2个 交错 的 ? 偏差点。
即存在点集 a ? t1 <…< tn+2 ? b 使得
{ tk }称为 切比雪夫交错组 /* Chebyshev alternating sequence */
?????? ||||)1()()( yPtytP nkkkn
? 若 且 y 不是 n 次多项式，则 n 次 OUAP 唯一 。 ],[ baCy ?
证明,反证，设有 2个 OUAP’s，分别是 Pn 和 Qn 。
则它们的平均函数 也是一个 OUAP。 2 ) ( ) ( ) ( x Q x P x R n n n ? ? ?
对于 Rn 有 Chebyshev交错组 { t1,…,tn+2 }使得
n k k n k k n k k n n E t y t Q t y t P t y t R E ? ? ? ? ? ? ? | ) ( ) ( | 2
1 | ) ( ) ( |
2
1 | ) ( ) ( |
n k k n k k n E t y t Q t y t P ? ? ? ? | ) ( ) ( | | ) ( ) ( |
则至少在一个点上必须有 ) ( ) ( ) ( ) ( k n k k k n t Q t y t y t P ? ? ?
?
?
0 ) ( ) ( ? ? k k n t y t R 0 ? n E ?
§ 3 Optimal Approximation
? 由 Chebyshev定理可推出,Pn(x) ? y(x) 在定义域上至少变号
次，故至少有 个 根 。
x
y
0
y y x ? ( )
y y x E n ? ? ( )
y y x E n ? ? ( )
y P x n ? ( )
n+1 n+1
可见 Pn(x) 是 y(x)的
某一个 插值多项式
如何确定
插值节点 { x0,…,xn }
的位臵，使得 Pn(x)
刚好是 y 的 OUAP？
即，使插值余项
v 2.0
达到极小？ ?
?
?
???
n
i
i
n
n xxn
yxR
0
)1(
)()!1( )(|)(| ?
§ 3 Optimal Approximation
v 2.1 在 [ ?1,1]上求 { x1,…,xn } 使得
的 ||wn||? 最小。
?
?
? ?
n
i
i n xx xw
1
) ( )(
注意到,要使 ||wn||? 最小就意味着 ) ( ) ( 1 x P x x w n n n ? ? ?
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 } 。
? 切比雪夫多项式 /* Chebyshev polynomials */
§ 3 Optimal Approximation
考虑三角函数 cos(n? ) 在 [ 0,? ] 上的 个极值点。 n + 1
当 时,cos(n? )交错达到极大值 1 和极
小值 ?1,且存在系数 a0,…,an 使得
),...,1,0( nknkk ?? ??
?
?
? n
k
k
kan
0
)( c o s)c o s ( ??
? 令 x = cos(? ),则 x ?[ ?1,1 ]。
) cos arccos( ) cos( ) ( x n· n x T n ? ? ? 称为 Chebyshev多项式
? Tn 的重要性质,
? 当 时,交错取到极大值 1
和极小值 ?1，即
),...,1,0(c o s nknkt k ???????? ? )( kn tT
??? ||)(||)1()( xTtT nkkn
1
? 当 时,即 {x1,…,
xn } 为 Tn(x)的 n个零点。
),...,1(2 12c o s nknkx k ??????? ?? ? 0)( ?kn xT
§ 3 Optimal Approximation
? Tn(x)满足递推关系,
T0(x) = 1,T1(x) = x,)()(2)(
11 xTxTxxT nnn ?? ??
Tn(x)为 n 次多项式，首项系数为 。且 T2n(x)只含
x 的 次幂,T2n+1(x)只含 x 的 次幂。
2n?1
偶 奇
? { T0(x),T1(x),… } 是 [ ?1,1 ]上关于权 正交
的函数族。即在内积 的意义下有
21
1)(
xx ???
??? 1 1 )()()(),( dxxTxTxTT lklk ?
?
?
?
??
?
?
??
??
?
?
0
2
0
0
),(
lk
lk
lk
TT lk
?
?
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]上求函数 xn 的 n?1阶 OUAP。
Tn(x)的 n个 零点 。
§ 3 Optimal Approximation
? 可见：若取,则 wn在 [ ?1,1 ]上有 n+1 个 极
值点 { tk }，也即 Pn?1(x) = xn ? wn(x)关于 xn在 [ ?1,1 ]上有
n+1个交错 偏差点 { tk } 。
12
)()(
?? n
nn xTxw
v3.0 OK
v 2.1 在 [ ?1,1]上求 { x1,…,xn } 使得 的
||wn||? 最小。
?
?
? ?
n
i
i n x x x w
1
) ( ) (
取最小值
?? ? ||)(|| 1 nn xxP
?
?? ??? )(2
1||||min
1 xTw nnnw
nn
12
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 xxn
yxR
0
)1(
)()!1( )(|)(| ?
? 取 { x0,…,xn } 为 Tn+1(x)的 n+1个 零点,做 y 的插值多项式
Pn(x)，则插值余项的上界可达极小 。
)!1(2 ?n
M
n
§ 3 Optimal Approximation
注,
? 上界 最小不表示 | Rn(x)|最小，故 Pn(x)严格意义上只是 y(x)
的 近似 最佳逼近多项式；
? 对于一般区间 x ?[a,b],可作变量替换,则
t ?[ ?1,1 ],这时
tabbax 22 ????
)),,, (()()( 220222211 nabbaabbaabbann xtxttwxw ??????? ????????
? ? )),,, (( 012 nnab tttt ??? ??
? ? )()( 12 )(12 112 12 1 tTtT nabnnab n nn ????? ? ???
即以 为插值节点 (k=0,…,n)，
得 Pn(x)，余项 有最小上界。
?????? ?????? ?22 12c o s22 nkabbax k
)(2 )()!1( )()( 112
1)1(
tTabnyxR nn
nn
n ??
?? ?
??
?
§ 3 Optimal Approximation
例,求 f (x) = ex 在 [0,1]上的近似最佳逼近多项式，使其误差
不超过 0.5?10?4。
解,? 根据误差上界确定 n,
410
2
1
2
1
)!1(|| 12
????
?? ?nn n
eR n = 4
? 计算 T5(t)的根,
10
9c o s,
10
7c o s,
10
5c o s,
10
3c o s,
10c o s 43210
????? ????? ttttt
)1(2122 ?????? ttabbax
02.0)1
10
9
( c o s
2
1
21.0)1
10
7
( c o s
2
1
,50.0)1
10
5
( c o s
2
1
79.0)1
10
3
( c o s
2
1
,98.0)1
10
( c o s
2
1
4
32
10
???
??????
??????
?
??
??
x
xx
xx
? 以 x0,…,x4 为节点作 L4(x)
§ 3 Optimal Approximation
? Chebyshev 多项式的其它应用
—— 多项式降次 /* reduce the degree of
polynomial with a minimal loss of accuracy */
设 f (x) ? Pn(x)。 在降低 Pn(x) 次数的同时,使
因此增加的误差尽可能小,也叫 economiza-
tion of power series。
从 Pn中去掉一个含有其最高次项的,结果降
次为,则,
Pn
~ P
n?1
| ) ( | max | ) ( ) ( | max | ) ( ) ( | max
] 1,1 [ ] 1,1 [ 1 ] 1,1 [
x P x P x f x P x f n n n
? ? ? ?
? ? ? ? ~
因降次而增的误差
设 Pn 的首项系数为 an，则取 可使
精度尽可能少损失。
1 2
) ( )(
? ? ? n
n
n n
x T ax P
§ 3 Optimal Approximation
例,f (x) = ex 在 [?1,1]上的 4 阶 Taylor 展开为
24621
432
4
xxxxP ?????,此时误差 023.0||
!5|)(|
5
4 ?? x
exR
请将其 降为 2阶多项式 。
解,取 )
8
1(
24
1)(
2
1
24
1 24
434 ????? xxxTP
188 244 ??? xxT（查表知 ）
)81(241621 23244 ???????? xxxxPP 32 6124131 91 9 1 xxx ????
取
)43(61)(2161 3323 xxxTP ???? xxT 4 33 ??
（查表知 ）
1 9 2
1 9 1
8
9
24
13~ 2
33 ???? xxPP 0 5 7.0||)(
~|| 2 ?? ?xPe x
若简单取,则误差
21)(
2
2
xxxP ??? 45.0
!3 ??
e
另类解法可查 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
? 最佳 平方 逼近：即连续型 L-S逼近，在 意义
下，使得 最小。
),(|||| 2 fff ?
2|||| yP ?
? 最佳 一致 逼近 /* uniform approximation */
|)(|m a x|||| ],[ xff bax ???
在 意义下，使得 最小。也称
为 minimax problem。
?? |||| yP
偏差
/* deviation*/
若,则称 x0 为 ? 偏差点 。
????? ||||)()( 00 yPxyxP
Didn’t you say it’s a very
difficult problem?
Take it easy,It’s not so
difficult if we consider
polynomials only,
§ 3 Optimal Approximation
v 1.0 最佳一致逼近多项式 /* optimal uniform approximating
polynomial */ 的构造：求 n 阶多项式 Pn(x) 使得 || Pn ? y ||? 最
小。
直接构造 OUAP 的确比较困难，不妨换个角度，先
考察它应该具备的 性质 。有如下结论,
? OUAP 存在，且必同时有 ? 偏差点。
证明,存在性证明略。后者用反证法，设只有正偏差点。
设
nnbaxn ExyxPyP ???? ?? |)()(|m a x|||| ],[
而对于所有的 x?[a,b] 都有
nn ExyxP ??? )()(
nnn ExyxPE ????? )()(?
2/|)(]2/)([| ?? ???? nn ExyxP
是 n阶多项式 是误差更小的多项式
§ 3 Optimal Approximation
? （ Chebyshev定理） Pn 是 y 的 OUAP ? Pn 关于 y 在定义域
上至少有 n+2个 交错 的 ? 偏差点。
即存在点集 a ? t1 <…< tn+2 ? b 使得
{ tk }称为 切比雪夫交错组 /* Chebyshev alternating sequence */
?????? ||||)1()()( yPtytP nkkkn
? 若 且 y 不是 n 次多项式，则 n 次 OUAP 唯一 。 ],[ baCy ?
证明,反证，设有 2个 OUAP’s，分别是 Pn 和 Qn 。
则它们的平均函数 也是一个 OUAP。 2 ) ( ) ( ) ( x Q x P x R n n n ? ? ?
对于 Rn 有 Chebyshev交错组 { t1,…,tn+2 }使得
n k k n k k n k k n n E t y t Q t y t P t y t R E ? ? ? ? ? ? ? | ) ( ) ( | 2
1 | ) ( ) ( |
2
1 | ) ( ) ( |
n k k n k k n E t y t Q t y t P ? ? ? ? | ) ( ) ( | | ) ( ) ( |
则至少在一个点上必须有 ) ( ) ( ) ( ) ( k n k k k n t Q t y t y t P ? ? ?
?
?
0 ) ( ) ( ? ? k k n t y t R 0 ? n E ?
§ 3 Optimal Approximation
? 由 Chebyshev定理可推出,Pn(x) ? y(x) 在定义域上至少变号
次，故至少有 个 根 。
x
y
0
y y x ? ( )
y y x E n ? ? ( )
y y x E n ? ? ( )
y P x n ? ( )
n+1 n+1
可见 Pn(x) 是 y(x)的
某一个 插值多项式
如何确定
插值节点 { x0,…,xn }
的位臵，使得 Pn(x)
刚好是 y 的 OUAP？
即，使插值余项
v 2.0
达到极小？ ?
?
?
???
n
i
i
n
n xxn
yxR
0
)1(
)()!1( )(|)(| ?
§ 3 Optimal Approximation
v 2.1 在 [ ?1,1]上求 { x1,…,xn } 使得
的 ||wn||? 最小。
?
?
? ?
n
i
i n xx xw
1
) ( )(
注意到,要使 ||wn||? 最小就意味着 ) ( ) ( 1 x P x x w n n n ? ? ?
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 } 。
? 切比雪夫多项式 /* Chebyshev polynomials */
§ 3 Optimal Approximation
考虑三角函数 cos(n? ) 在 [ 0,? ] 上的 个极值点。 n + 1
当 时,cos(n? )交错达到极大值 1 和极
小值 ?1,且存在系数 a0,…,an 使得
),...,1,0( nknkk ?? ??
?
?
? n
k
k
kan
0
)( c o s)c o s ( ??
? 令 x = cos(? ),则 x ?[ ?1,1 ]。
) cos arccos( ) cos( ) ( x n· n x T n ? ? ? 称为 Chebyshev多项式
? Tn 的重要性质,
? 当 时,交错取到极大值 1
和极小值 ?1，即
),...,1,0(c o s nknkt k ???????? ? )( kn tT
??? ||)(||)1()( xTtT nkkn
1
? 当 时,即 {x1,…,
xn } 为 Tn(x)的 n个零点。
),...,1(2 12c o s nknkx k ??????? ?? ? 0)( ?kn xT
§ 3 Optimal Approximation
? Tn(x)满足递推关系,
T0(x) = 1,T1(x) = x,)()(2)(
11 xTxTxxT nnn ?? ??
Tn(x)为 n 次多项式，首项系数为 。且 T2n(x)只含
x 的 次幂,T2n+1(x)只含 x 的 次幂。
2n?1
偶 奇
? { T0(x),T1(x),… } 是 [ ?1,1 ]上关于权 正交
的函数族。即在内积 的意义下有
21
1)(
xx ???
??? 1 1 )()()(),( dxxTxTxTT lklk ?
?
?
?
??
?
?
??
??
?
?
0
2
0
0
),(
lk
lk
lk
TT lk
?
?
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]上求函数 xn 的 n?1阶 OUAP。
Tn(x)的 n个 零点 。
§ 3 Optimal Approximation
? 可见：若取,则 wn在 [ ?1,1 ]上有 n+1 个 极
值点 { tk }，也即 Pn?1(x) = xn ? wn(x)关于 xn在 [ ?1,1 ]上有
n+1个交错 偏差点 { tk } 。
12
)()(
?? n
nn xTxw
v3.0 OK
v 2.1 在 [ ?1,1]上求 { x1,…,xn } 使得 的
||wn||? 最小。
?
?
? ?
n
i
i n x x x w
1
) ( ) (
取最小值
?? ? ||)(|| 1 nn xxP
?
?? ??? )(2
1||||min
1 xTw nnnw
nn
12
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 xxn
yxR
0
)1(
)()!1( )(|)(| ?
? 取 { x0,…,xn } 为 Tn+1(x)的 n+1个 零点,做 y 的插值多项式
Pn(x)，则插值余项的上界可达极小 。
)!1(2 ?n
M
n
§ 3 Optimal Approximation
注,
? 上界 最小不表示 | Rn(x)|最小，故 Pn(x)严格意义上只是 y(x)
的 近似 最佳逼近多项式；
? 对于一般区间 x ?[a,b],可作变量替换,则
t ?[ ?1,1 ],这时
tabbax 22 ????
)),,, (()()( 220222211 nabbaabbaabbann xtxttwxw ??????? ????????
? ? )),,, (( 012 nnab tttt ??? ??
? ? )()( 12 )(12 112 12 1 tTtT nabnnab n nn ????? ? ???
即以 为插值节点 (k=0,…,n)，
得 Pn(x)，余项 有最小上界。
?????? ?????? ?22 12c o s22 nkabbax k
)(2 )()!1( )()( 112
1)1(
tTabnyxR nn
nn
n ??
?? ?
??
?
§ 3 Optimal Approximation
例,求 f (x) = ex 在 [0,1]上的近似最佳逼近多项式，使其误差
不超过 0.5?10?4。
解,? 根据误差上界确定 n,
410
2
1
2
1
)!1(|| 12
????
?? ?nn n
eR n = 4
? 计算 T5(t)的根,
10
9c o s,
10
7c o s,
10
5c o s,
10
3c o s,
10c o s 43210
????? ????? ttttt
)1(2122 ?????? ttabbax
02.0)1
10
9
( c o s
2
1
21.0)1
10
7
( c o s
2
1
,50.0)1
10
5
( c o s
2
1
79.0)1
10
3
( c o s
2
1
,98.0)1
10
( c o s
2
1
4
32
10
???
??????
??????
?
??
??
x
xx
xx
? 以 x0,…,x4 为节点作 L4(x)
§ 3 Optimal Approximation
? Chebyshev 多项式的其它应用
—— 多项式降次 /* reduce the degree of
polynomial with a minimal loss of accuracy */
设 f (x) ? Pn(x)。 在降低 Pn(x) 次数的同时,使
因此增加的误差尽可能小,也叫 economiza-
tion of power series。
从 Pn中去掉一个含有其最高次项的,结果降
次为,则,
Pn
~ P
n?1
| ) ( | max | ) ( ) ( | max | ) ( ) ( | max
] 1,1 [ ] 1,1 [ 1 ] 1,1 [
x P x P x f x P x f n n n
? ? ? ?
? ? ? ? ~
因降次而增的误差
设 Pn 的首项系数为 an，则取 可使
精度尽可能少损失。
1 2
) ( )(
? ? ? n
n
n n
x T ax P
§ 3 Optimal Approximation
例,f (x) = ex 在 [?1,1]上的 4 阶 Taylor 展开为
24621
432
4
xxxxP ?????,此时误差 023.0||
!5|)(|
5
4 ?? x
exR
请将其 降为 2阶多项式 。
解,取 )
8
1(
24
1)(
2
1
24
1 24
434 ????? xxxTP
188 244 ??? xxT（查表知 ）
)81(241621 23244 ???????? xxxxPP 32 6124131 91 9 1 xxx ????
取
)43(61)(2161 3323 xxxTP ???? xxT 4 33 ??
（查表知 ）
1 9 2
1 9 1
8
9
24
13~ 2
33 ???? xxPP 0 5 7.0||)(
~|| 2 ?? ?xPe x
若简单取,则误差
21)(
2
2
xxxP ??? 45.0
!3 ??
e
另类解法可查 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
