1 最佳一致逼近
魏尔斯特拉斯定理表明, 多项式函数可以任意逼近一个函数
𝑓 (𝑥) ∈ 𝐶 [𝑎, 𝑏], ∀𝜖 > 0, ∃𝑝(𝑥)使得
max
𝑎≤𝑥 ≤𝑏
|
𝑓 (𝑥) − 𝑝(𝑥)
|
< 𝜖
可以由此定义最佳一致逼近: 设 𝑓 (𝑥) ∈ 𝐶[𝑎, 𝑏], 希望找到一个多项式 𝑝(𝑥), 使得最大误差最小
𝐸 = max
𝑎≤𝑥 ≤𝑏
|
𝑓 (𝑥) − 𝑝(𝑥)
|
最佳一致逼近多项式是存在的, 可以利用一致范数证明. 对于一个函数 𝑓 (𝑥), 可以其一致范数
|| 𝑓 || = max
𝑎≤𝑥 ≤𝑏
|
𝑓 (𝑥)
|
它应当是非负的实数. 实际上, 在连续函数空间, 一致范数是完备的度量
为了找到最佳一致逼近多项式, 有 Vallée-Poussin 定理
𝑓 (𝑥) ∈ 𝐶 [𝑎, 𝑏], 对于多项式 𝑝(𝑥), 若有
∃𝑥
0
, 𝑥
1
, . . . , 𝑥
𝑛+1
∈ [𝑎, 𝑏], 使得 𝑓 (𝑥
𝑖
) − 𝑝(𝑥
𝑖
)正负交替
则有
𝐸
𝑛
( 𝑓 ) ≥ min
0≤𝑘≤𝑛+1
|
𝑓 (𝑥
𝑘
) − 𝑝(𝑥
𝑘
)
|
这样的函数正是最佳一致逼近多项式
.
有
Chebyshev
定理
即 𝑃
𝑛
(𝑥) 是在区间 [𝑎, 𝑏] 上对函数 𝑓 (𝑥) 进行最佳一致逼近的多项式. 当且仅当存在 𝑛 + 2 个点
𝑎 ≤ 𝑥
0
< 𝑥
1
< ··· < 𝑥
𝑛+1
≤ 𝑏, 使得
𝑓 (𝑥
𝑖
) − 𝑃
𝑛
(𝑥
𝑖
) = (−1)
𝑖
𝐸,
其中 𝐸 = max
𝑥∈[𝑎,𝑏]
| 𝑓 (𝑥) − 𝑃
𝑛
(𝑥)|.
这样的点称为交错点组. 若 𝑓 (𝑥) 在 [𝑎, 𝑏] 上有 𝑛 +1 阶导数, 并且它们都保号, 则最佳一致逼近多项式 𝑝
∗
𝑛
满足
𝑓 − 𝑝
∗
𝑛
刚好有 𝑛 + 2 个交替点, 并且包含两个端点. 这是因为对其求一次导减少一个极值点
对于一次的最佳逼近多项式, 求解是简单的, 只需要找到 3 个交错点即可. 如对于 𝑒
𝑥
, 希望求其在 [−1, 1]
上的最佳一致逼近多项式, 可以设
𝑝
∗
1
(
𝑥
)
=
𝑎
0
+
𝑎
1
𝑥
由于 𝑒
𝑥
导数保号, 因而端点为交错点, 只需要再设一个交错点 𝑥
3
, 应当满足方程
𝑒
−1
− 𝑎
0
+ 𝑎
1
= −𝜇
𝑒
𝑥
3
− 𝑎
0
− 𝑎
1
𝑥
3
= 𝜇
𝑒
1
− 𝑎
0
− 𝑎
1
= −𝜇
求解即可得到最佳一致逼近多项式
可以利用迭代的方式找到交错点组 (Remez 算法). 给定误差 𝜖
0
, 按以下步骤迭代
1. 在 [𝑎, 𝑏] 上任取 𝑛 + 2 个点 𝑥
0
, 𝑥
1
, . . . , 𝑥
𝑛+1
, 可以给出多项式 𝑝
0
(𝑥) 以及误差 𝜇
0
2. 计算初始最佳一致逼近多项式 𝑝
∗
0
(𝑥), 它应当满足
𝑝
∗
0
(𝑥
𝑖
) − 𝑓 (𝑥
𝑖
) = (−1)
𝑖
𝜇 , 𝑖 = 0, 1, ··· , 𝑛 + 1
若认为
𝑝
∗
0
(𝑥) =
𝑛
Õ
𝑗=0
𝛼
0
𝑗
𝑥
𝑗
那么
𝑛
Õ
𝑗=0
𝛼
0
𝑗
𝑥
𝑗
𝑖
− 𝑓 (𝑥
𝑖
) = (−1)
𝑖
𝜇, 𝑖 = 0, 1, ··· , 𝑛 + 1
总共有 𝑛 + 2 个方程,𝑛 + 2 个未知数, 可以解出 𝛼
0
𝑗
与 𝜇
3. 计算多项式与函数的误差最大值点
𝑣
0
= max
𝑎≤𝑥 ≤𝑏
𝑓 (𝑥) − 𝑝
∗
0
(𝑥)
设最大误差点为
ˆ
𝑥, 则考虑
ˆ
𝑥 两侧的点, 将误差同号的点替换为
ˆ
𝑥. 若是
ˆ
𝑥 取到了端点并且与端点误
差异号, 则令
ˆ
𝑥 为新的端点, 并删除另一侧的端点
4. 回到步骤 2 进行迭代, 直到最大误差小于 𝜖
0
2 切比雪夫多项式
考虑函数 𝑓 (𝑥) = 𝑥
𝑛
, 希望找到其 𝑛 − 1 次的最佳一致逼近多项式 𝑃
∗
𝑛−1
(𝑥), 那么
𝑥
𝑛
− 𝑃
∗
𝑛−1
(𝑥)
是一个最高次项的系数为
1
的
𝑛
次多项式
,
即
𝑛
次首一多项式
.
找到最佳一致逼近多项式即寻找最小
0
偏差的 𝑛 次首一多项式
Chebyshev 多项式 𝑇
𝑛
(𝑥) 定义为
𝑇
𝑛
(𝑥) = cos(𝑛 arccos 𝑥), 𝑛 = 0, 1, 2, . . .
它虽然看着不像一个多项式, 但是令 𝑥 = cos 𝜃, 则
𝑇
𝑛
(𝑥) = cos(𝑛𝜃)
再利用
cos(𝑛𝜃) + cos((𝑛 − 2)𝜃) = 2 cos 𝜃 cos((𝑛 − 1)𝜃)
可以得到递推公式
𝑇
𝑛
(𝑥) = 2𝑥𝑇
𝑛−1
(𝑥) −𝑇
𝑛−2
(𝑥)
𝑇
0
(𝑥) = 1, 𝑇
1
(𝑥) = 𝑥
这确实是一个多项式, 它的最高次项系数是 2
𝑛−1
, 并且
𝑇
2𝑛
(𝑥)
只含有偶次项, 而
𝑇
2𝑛+1
(𝑥)
只含有奇次项. 切比雪夫多项式之间显然线性无关, 那么它显然可以作为多项式空间的一组基. 昨晚梦到
了一个权值, 在该权值下切比雪夫多项式满足正交性
∫
1
−1
𝑇
𝑚
(𝑥)𝑇
𝑛
(𝑥)
1
√
1 − 𝑥
2
d𝑥 =
0, 𝑚 ≠ 𝑛
𝜋, 𝑚 = 𝑛 ≠ 0
𝜋/2, 𝑚 = 𝑛 = 0
实际上这是傅里叶托梦得到的结果. 只需要令 𝑥 = cos 𝜃, 积分即化为了
∫
𝜋
0
cos(𝑚𝜃) cos(𝑛𝜃)d𝜃
昨晚还梦到了切比雪夫多项式的零点
𝑥
𝑘
= cos
2𝑘 − 1
2𝑛
𝜋
, 𝑘 = 1, 2, ··· , 𝑛
它们都在 [−1, 1] 上
注意到切比雪夫多项式满足当 𝑥 有
cos 𝑥 =
𝑘𝜋
𝑛
, 𝑘 = 0, 1, ··· , 𝑛
这些点为其极值点, 而它们正好是交错的. 因而寻找的最小 0 偏差的 𝑛 次首一多项式就是切比雪夫多项式
2
1−𝑛
𝑇
𝑛
(𝑥)
它对 0 的偏差满足
max
−1≤𝑥≤1
2
1−𝑛
𝑇
𝑛
(0)
= 2
1−𝑛
得到 𝑥
𝑛
的 𝑛 − 1 次最佳一致逼近多项式
𝑃
∗
𝑛−1
(𝑥) = 2
1−𝑛
𝑇
𝑛
(𝑥) − 𝑥
𝑛
2.1 代数插值多项式余项最小化
考虑定义在 [−1, 1] 上的函数 𝑓 (𝑥), 取插值点
𝑥
0
, 𝑥
1
, ··· , 𝑥
𝑛
则插值函数 𝑝
𝑛
(𝑥) 的插值余项为
𝑅
𝑛
(𝑥) = 𝑓 (𝑥) − 𝑝
𝑛
(𝑥) =
𝑓
(𝑛+1)
(𝜉)
(𝑛 + 1)!
𝑛
Ö
𝑖=0
(𝑥 − 𝑥
𝑖
)
前面的系数直接与函数相关, 考虑减小后面的项
max
−1≤𝑥≤1
𝑛
Ö
𝑖=0
(𝑥 − 𝑥
𝑖
)
注意到这是一个 𝑛 + 1 次首一多项式, 要令它最小, 自然应该取切比雪夫多项式
2
−𝑛
𝑇
𝑛+1
(𝑥)
即选择插值点为切比雪夫多项式的零点
𝑥
𝑘
= cos
2𝑘 − 1
2𝑛 + 2
𝜋
, 𝑘 = 1, 2, ··· , 𝑛 + 1
此时插值余项最大值应为
max
−1≤𝑥≤1
|
𝑅
𝑛
(𝑥)
|
≤
𝑓
(𝑛+1)
(𝜉)
(𝑛 + 1)!
2
−𝑛
2.2 降低近似多项式级数
考虑定义在 [−1, 1] 上的函数 𝑓 (𝑥), 希望用多项式级数逼近它, 有 Taylor 级数
𝑓 (𝑥) = 𝑓 (0) + 𝑓
′
(0)𝑥 +
𝑓
′′
(0)
2!
𝑥
2
+ ··· +
𝑓
(𝑛)
(0)
𝑛
!
𝑥
𝑛
+ ···
若是取前 𝑛 项, 则余项为
𝑅
𝑛
(𝑥) =
𝑓
(𝑛+1)
(0)
(𝑛 + 1)!
𝑥
𝑛+1
+ ···
若是考虑将 𝑥
𝑛
基换为切比雪夫多项式 𝑇
𝑛
(𝑥), 即考虑
𝑓 (𝑥) = 𝑡
0
𝑇
0
(𝑥) + 𝑡
1
𝑇
1
(𝑥) + ··· + 𝑡
𝑛
𝑇
𝑛
(𝑥) + ···
再取前 𝑛 项, 误差将会比较小
3 内积空间的最佳逼近
定义内积
( 𝑓 , 𝑔) =
∫
𝑏
𝑎
𝑓 (𝑥)𝑔(𝑥)𝜌(𝑥)d𝑥
由此定义范数 (即模)
|| 𝑓 || =
p
( 𝑓 , 𝑓 )
希望使用一个子空间 𝑉 中的函数来逼近一个函数 𝑓 (𝑥), 即找到一个 𝑔(𝑥) ∈ 𝑉, 使得
|| 𝑓 − 𝑔|| = min
ℎ(𝑥 )∈𝑉
|| 𝑓 − ℎ||
其中 𝑉 是一个有限维的子空间,ℎ(𝑥) 是 𝑉 中的任意函数. 存在性是显然的, 唯一性的证明可以利用反证法,
假设存在两个函数 𝑔
1
(𝑥), 𝑔
2
(𝑥) 满足
|| 𝑓 − 𝑔
1
|| = || 𝑓 −𝑔
2
|| = 𝜇
那么取
𝑔
0
=
𝑔
1
+ 𝑔
2
2
则
|| 𝑓 − 𝑔
0
|| =
|| 𝑓 − (𝑔
1
+ 𝑔
2
)/2||
2
≤
1
2
(
|| 𝑓 − 𝑔
1
|| + || 𝑓 − 𝑔
2
||
)
= 𝜇
等号成立当且仅当
||𝑔
1
− 𝑔
2
|| = 0
而
||𝑔
1
− 𝑔
2
|| =
∫
𝑏
𝑎
(𝑔
1
− 𝑔
2
)
2
𝜌(𝑥)d𝑥
若 𝑔
1
≠ 𝑔
2
, 则自然有 ||𝑔
1
− 𝑔
2
|| > 0, 矛盾, 因此唯一性得证
𝜙
∗
是 𝑓 的最佳逼近元素等价于
( 𝑓 − 𝜙
∗
, 𝜙) = 0
其中 𝜙 是 𝑉 中的任意函数. 必要性的证明采取反证法, 假设存在一个函数 𝜙 使得
( 𝑓 − 𝜙
∗
, 𝜙) ≠ 0
昨晚梦到
˜
𝜙 = 𝜙
∗
+ ( 𝑓 − 𝜙
∗
, 𝜙)
𝜙
||𝜙||
≡ 𝜙
∗
+ 𝛼𝜑
那么
|| 𝑓 −
˜
𝜙||
2
= || 𝑓 − 𝜙
∗
||
2
− 2𝛼( 𝑓 − 𝜙
∗
, 𝜑 ) + 𝛼
2
= || 𝑓 − 𝜙
∗
||
2
− 𝛼
2
< || 𝑓 − 𝜙
∗
||
2
这与 𝜙
∗
是最佳逼近元素矛盾, 因此必要性得证. 充分性的证明可以利用 Cauchy-Schwarz 不等式
|| 𝑓 − 𝜙||
2
− || 𝑓 − 𝜙
∗
||
2
= ||𝜙||
2
− 2||𝜙
∗
||
2
− 2(𝑓 , 𝜙) + 2(𝑓 , 𝜙
∗
)
= ||𝜙 − 𝜙
∗
||
2
+ 2(𝜙, 𝜙
∗
) − 2||𝜙
∗
||
2
+ 2(𝑓 , 𝜙
∗
− 𝜙)
= ||𝜙 − 𝜙
∗
||
2
+ 2(𝑓 − 𝜙
∗
, 𝜙
∗
− 𝜙)
由条件得到 ( 𝑓 − 𝜙
∗
, 𝜙
∗
− 𝜙), 而 ||𝜙 − 𝜙
∗
||
2
≥ 0, 因此
|| 𝑓 − 𝜙||
2
− || 𝑓 − 𝜙
∗
||
2
≥ 0
充分性得证
对于一组基张成的线性空间
𝑀 = 𝑆 𝑝𝑎𝑛{𝜙
1
, 𝜙
2
, ··· , 𝜙
𝑛
}
希望找到最佳逼近
𝜙
∗
=
𝑛
Õ
𝑖=1
𝑐
𝑖
𝜙
𝑖
即希望
𝑓 −
𝑛
Õ
𝑖=1
𝑐
𝑖
𝜙
𝑖
, 𝜙
𝑗
!
= 0, 𝑗 = 1, 2, ··· , 𝑛
等价于
( 𝑓 , 𝜙
𝑗
) =
𝑛
Õ
𝑖=1
𝑐
𝑖
(𝜙
𝑖
, 𝜙
𝑗
), 𝑗 = 1, 2, ·· · , 𝑛
可以将其写为矩阵的形式
𝐺c
∗
= b
其中
𝐺 =
©
«
(𝜙
1
, 𝜙
1
) (𝜙
1
, 𝜙
2
) ··· (𝜙
1
, 𝜙
𝑛
)
(𝜙
2
, 𝜙
1
) (𝜙
2
, 𝜙
2
) ··· (𝜙
2
, 𝜙
𝑛
)
.
.
.
.
.
.
.
.
.
.
.
.
(𝜙
𝑛
, 𝜙
1
) (𝜙
𝑛
, 𝜙
2
) ··· (𝜙
𝑛
, 𝜙
𝑛
)
ª
®
®
®
®
®
®
¬
, c
∗
=
©
«
𝑐
1
𝑐
2
.
.
.
𝑐
𝑛
ª
®
®
®
®
®
®
¬
, b =
©
«
( 𝑓 , 𝜙
1
)
( 𝑓 , 𝜙
2
)
.
.
.
( 𝑓 , 𝜙
𝑛
)
ª
®
®
®
®
®
®
¬
𝐺 是一个正定的对称矩阵, 因此方程的解是存在且唯一的. 若 𝜙
1
, 𝜙
2
, ··· , 𝜙
𝑛
是正交的, 则
(𝜙
𝑖
, 𝜙
𝑗
) = 𝛿
𝑖 𝑗
||𝜙
𝑖
||||𝜙
𝑗
||
此时 𝐺 是对角矩阵
𝐺 =
©
«
||𝜙
1
||
2
0 ··· 0
0 ||𝜙
2
||
2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· ||𝜙
𝑛
||
2
ª
®
®
®
®
®
®
¬
注意到解并不需要多少注意力
𝑐
∗
𝑗
=
( 𝑓 , 𝜙
𝑗
)
||𝜙
𝑗
||
2
最佳逼近多项式写为
𝜙
∗
=
𝑛
Õ
𝑖=1
( 𝑓 , 𝜙
𝑖
)
||𝜙
𝑖
||
2
𝜙
𝑖
这是一个类似于傅里叶级数的形式, 称为广义傅里叶级数. 它具有与傅里叶计数类似的性质
|| 𝑓 − 𝜙
∗
||
2
= || 𝑓 ||
2
−
𝑛
Õ
𝑖=1
𝑐
∗
𝑖
2
||𝜙
𝑖
||
2
逼近多项式的范数不会超过函数的范数, 因而它不是发散的
∞
Õ
𝑖=1
𝑐
∗
𝑖
2
||𝜙
𝑖
||
2
≤ || 𝑓 ||
2
这称为 Bessel 不等式. 正交基是一定存在的, 可以通过施密特正交化得到
可以定义一个离散的内积空间 𝑙
2
𝜔
, 其中有向量
x =
©
«
𝑥
1
𝑥
2
.
.
.
𝑥
𝑛
ª
®
®
®
®
®
®
¬
, y =
©
«
𝑦
1
𝑦
2
.
.
.
𝑦
𝑛
ª
®
®
®
®
®
®
¬
权系数为 𝜔
𝑖
> 0, 则有内积
(x, y) =
𝑛
Õ
𝑖=1
𝜔
𝑖
𝑥
𝑖
𝑦
𝑖
取其 𝑚 维子空间 𝑀, 取其一组基 x
1
, x
2
, ··· , x
𝑚
. 最佳逼近即对于空间中任意的向量 y, 找到一个 x
∗
∈ 𝑀,
使得
||y − x
∗
|| = min
x ∈𝑀
||y − x|| ⇔ ||𝑦 − x
∗
|| = 0
设
𝑥
∗
=
𝑚
Õ
𝑖=1
𝑐
𝑖
x
𝑖
那么
𝑚
Õ
𝑖=1
𝑐
𝑖
(𝑥
𝑖
, 𝑥
𝑗
) = (𝑦, 𝑥
𝑗
), 𝑗 = 1, 2, ·· · , 𝑚
写为向量形式即
𝐴c
∗
= d
其中
𝐴 =
©
«
(x
1
, x
1
) (x
1
, x
2
) ··· (x
1
, x
𝑚
)
(x
2
, x
1
) (x
2
, x
2
) ··· (x
2
, x
𝑚
)
.
.
.
.
.
.
.
.
.
.
.
.
(x
𝑚
, x
1
) (x
𝑚
, x
2
) ··· (x
𝑚
, x
𝑚
)
ª
®
®
®
®
®
®
¬
, c
∗
=
©
«
𝑐
1
𝑐
2
.
.
.
𝑐
𝑚
ª
®
®
®
®
®
®
¬
, d =
©
«
(y, x
1
)
(y, x
2
)
.
.
.
(y, x
𝑚
)
ª
®
®
®
®
®
®
¬
对于超定方程组, 可以利用最小二乘法求解
𝐴x = b
若
𝐴
的行数大于列数
,
则称为超定方程组
,
一般情况下无解
,
不过可以求解最佳逼近解
,
即
||𝐴x − b|| = min
x
||𝐴x − b||
即求解系数 𝑥
𝑖
使得
a
∗
=
𝑚
Õ
𝑖=1
𝑥
𝑖
a
𝑖
那么即求解方程组
©
«
(a
1
, a
1
) (a
1
, a
2
) ··· (a
1
, a
𝑚
)
(a
2
, a
1
) (a
2
, a
2
) ··· (a
2
, a
𝑚
)
.
.
.
.
.
.
.
.
.
.
.
.
(a
𝑚
, a
1
) (a
𝑚
, a
2
) ··· (a
𝑚
, a
𝑚
)
ª
®
®
®
®
®
®
¬
©
«
𝑥
1
𝑥
2
.
.
.
𝑥
𝑚
ª
®
®
®
®
®
®
¬
=
©
«
(a
1
, b)
(a
2
, b)
.
.
.
(a
𝑚
, b)
ª
®
®
®
®
®
®
¬
也就是
𝐴
𝑇
𝐴x = 𝐴
𝑇
b
