数值分析NA07c.ppt

§3 函数的最佳逼近/* Optimal Approximation */
最佳平方逼近:即连续型L-S逼近,在意义下,使得最小。
最佳一致逼近/* uniform approximation */
在意义下,使得最小。也称为minimax problem。
偏差
/* deviation*/
若,则称 x0 为偏差点。
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
最佳一致逼近多项式/* optimal uniform approximating polynomial */ 的构造:求 n 阶多项式 Pn(x) 使得|| Pn  y ||最小。
直接构造 OUAP 的确比较困难,不妨换个角度,先考察它应该具备的性质。有如下结论:
 OUAP 存在,且必同时有偏差点。
证明:存在性证明略。后者用反证法,设只有正偏差点。
设
而对于所有的 x[a, b] 都有
是n阶多项式
是误差更小的多项式
§3 Optimal Approximation
(Chebyshev定理)Pn 是 y 的OUAP  Pn 关于 y 在定义域上至少有n+2个交错的偏差点。
即存在点集 a  t1 <…< tn+2  b 使得
{ tk }称为切比雪夫交错组/* Chebyshev alternating sequence */
若且 y 不是 n 次多项式,则 n 次OUAP 唯一。
证明:反证,设有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
达到极小?
§3 Optimal Approximation
v
在[ 1, 1]上求{ x1, …, xn } 使得的||wn||最小。

=
-
=
n
i
i
n
x
x
x
w
1
)
(
)
(
注意到,要使||wn||最小就意味着
)
(
)
(
1
x
P
x
x
w
n
n
n
-
-
=
v
在[ 1, 1]上求函数 xn 的n1阶 OUAP。
由Chebyshev定理可推出:Pn1(x) 关于xn 有n+1个偏差点,即wn(x)在 n+1个点上交错取极大、极小值。
v
在[ 1, 1]上求切比雪夫交错组{ t1, …, tn+1 } 。
切比雪夫多项式/* Chebyshev polynomials */
§3 Optimal Approximation
考虑三角函数 cos(