§ 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 )()()( xQxPxR nnn
对于 Rn 有 Chebyshev交错组 { t1,…,tn+2 }使得
nkknkknkknn EtytQtytPtytRE |)()(|2
1|)()(|
2
1|)()(|
nkknkkn EtytQtytP |)()(||)()(|
则至少在一个点上必须有 )()()()( knkkkn tQtytytP
0)()( kkn tytR 0?nE?
§ 3 Optimal Approximation
由 Chebyshev定理可推出,Pn(x)? y(x) 在定义域上至少变号次，故至少有 个 根 。
x
y
0
y y x? ( )
y y x En( )
y y x En( )
y P xn? ( )
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
in xxxw
1
)()(
注意到,要使 ||wn||?最小就意味着)()( 1 xPxxw nnn
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 ]。
)cosarccos()cos()( xn·nxTn 称为 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
in xxxw
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[
xPxPxfxPxf nnn
~
因降次而增的误差设 Pn 的首项系数为 an，则取 可使精度尽可能少损失。
12
)()(
n
n
nn
xTaxP
§ 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||)(
~|| 2xPe 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 )()()( xQxPxR nnn
对于 Rn 有 Chebyshev交错组 { t1,…,tn+2 }使得
nkknkknkknn EtytQtytPtytRE |)()(|2
1|)()(|
2
1|)()(|
nkknkkn EtytQtytP |)()(||)()(|
则至少在一个点上必须有 )()()()( knkkkn tQtytytP
0)()( kkn tytR 0?nE?
§ 3 Optimal Approximation
由 Chebyshev定理可推出,Pn(x)? y(x) 在定义域上至少变号次，故至少有 个 根 。
x
y
0
y y x? ( )
y y x En( )
y y x En( )
y P xn? ( )
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
in xxxw
1
)()(
注意到,要使 ||wn||?最小就意味着)()( 1 xPxxw nnn
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 ]。
)cosarccos()cos()( xn·nxTn 称为 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
in xxxw
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[
xPxPxfxPxf nnn
~
因降次而增的误差设 Pn 的首项系数为 an，则取 可使精度尽可能少损失。
12
)()(
n
n
nn
xTaxP
§ 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||)(
~|| 2xPe 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
