数值分析复习：最佳逼近、最佳一致逼近

文章目录

• 最佳逼近
• • 1. 度量空间中的逼近
  • 2. 赋范线性空间中的逼近
  • 3. 连续函数空间上的最佳逼近
  • • 3.1 多项式逼近
    • 3.2 存在性和唯一性
    • 3.3 最小零偏差多项式

本篇文章适合个人复习翻阅，不建议新手入门使用

最佳逼近

1. 度量空间中的逼近

给定度量空间 ( X , d ) (X,d) (X,d) 及其子集 S S S，若对 X X X中任意一点 a a a， S S S 中可以找到一个点 s s s 使得
d ( a , s ) = d i s t ( a , S ) d(a,s)=dist(a,S) d(a,s)=dist(a,S)则称 s s s 是 a a a 在 S S S 中的最佳逼近元

存在性
对度量空间中的点，紧子空间中一定有其最佳逼近元

证明

• 由dist的定义， ∃ s n ∈ S , d ( a , s n ) → d i s t ( a , s ) \exists s_n\in S,d(a,s_n)\to dist(a,s) ∃sn​∈S,d(a,sn​)→dist(a,s)
• 由紧性得 S S S 闭， ∃ s ∈ S , s . t . d ( s n , s ) → 0 \exists s\in S,s.t.d(s_n,s)\to 0 ∃s∈S,s.t.d(sn​,s)→0
• 由三角不等式， d ( a , s ) ≤ d ( a , s n ) + d ( s n , s ) → d i s t d(a,s)\leq d(a,s_n)+d(s_n,s)\to dist d(a,s)≤d(a,sn​)+d(sn​,s)→dist

2. 赋范线性空间中的逼近

给定赋范线性空间 ( X , ∣ ∣ ⋅ ∣ ∣ ) (X,||\cdot||) (X,∣∣⋅∣∣) 及其子集 S S S，若对 X X X中任意一点 a a a， S S S 中可以找到一个点 s s s 使得
∣ ∣ a − s ∣ ∣ = d i s t ( a , S ) ||a-s||=dist(a,S) ∣∣a−s∣∣=dist(a,S)则称 s s s 是 a a a 在 S S S 中的最佳逼近元

存在性和唯一性

1. 对赋范线性空间中的点，有限维子空间中一定有最佳逼近元
2. 对严格凸赋范线性空间中的点，子空间中最多有一个最佳逼近元
3. 对严格凸赋范线性空间中的点，有限维子空间内存在唯一的最佳逼近元

证明

1. 由度量空间的相关结论立得
2. 同一法：设有两个最佳逼近元 s 1 , s 2 s_1,s_2 s1​,s2​，导出矛盾

3. 连续函数空间上的最佳逼近

3.1 多项式逼近

对给定的 f ( x ) ∈ C [ a , b ] f(x)\in C[a,b] f(x)∈C[a,b] ，在某种范数下，在多项式函数空间 P n \mathbb{P}_n Pn​ 中 P ( x ) P(x) P(x)，使得
∣ ∣ P ( x ) − f ( x ) ∣ ∣ = inf ⁡ g ∈ P n ∣ ∣ g ( x ) − f ( x ) ∣ ∣ ||P(x)-f(x)||=\inf\limits_{g\in \mathbb{P}_n} ||g(x)-f(x)|| ∣∣P(x)−f(x)∣∣=g∈Pn​inf​∣∣g(x)−f(x)∣∣注：

• 在 L ∞ L^{\infty} L∞ 范数意义下， P ( x ) P(x) P(x) 称为最佳一致逼近多项式（BUAP）
• 在 L 2 L^2 L2 范数意义下， P ( x ) P(x) P(x) 称为最佳平方逼近多项式

定义

偏差：称 Δ ( P ) = max ⁡ x ∣ f ( x ) − P ( x ) ∣ \Delta (P)=\max\limits_x|f(x)-P(x)| Δ(P)=xmax​∣f(x)−P(x)∣ 为 P ( x ) P(x) P(x) 与 f ( x ) f(x) f(x) 的偏差

最小偏差：称 E n = inf ⁡ P ∈ P n Δ ( P ) E_n=\inf\limits_{P\in\mathbb{P}_n}\Delta (P) En​=P∈Pn​inf​Δ(P) 为 P ( x ) P(x) P(x) 对 f ( x ) f(x) f(x) 的最小偏差；

偏离点：使 P ( x ) P(x) P(x) 达到最小偏差的 x x x 称为偏离点，根据其相对 f ( x ) f(x) f(x) 的位置分别称为正、负偏离点

命题
若存在 P ∗ ( x ) ∈ P n P^*(x)\in\mathbb{P}_n P∗(x)∈Pn​ ，使得 Δ ( P ∗ ) = E n \Delta(P^*)= E_n Δ(P∗)=En​，则 P ∗ ( x ) P^*(x) P∗(x) 即为 f ( x ) f(x) f(x) 在 P n \mathbb{P}_n Pn​ 中的最佳一致逼近多项式（BUAP）

3.2 存在性和唯一性

Borel存在定理： P n \mathbb{P}_n Pn​ 中最佳逼近多项式存在

证明

• 对任意最小偏差 E n E_n En​，可找到一列多项式 P m ( x ) P_m(x) Pm​(x)，使得 Δ ( P m ) → E n \Delta(P_{m})\to E_n Δ(Pm​)→En​ （Weierstrass 逼近定理可证）
• 一列有界多项式 P m ( x ) P_m(x) Pm​(x) 必有一致收敛的子列 P ∗ ( x ) P^*(x) P∗(x)

设 P m ( x ) = a 0 , m + a 1 , m x + a 2 , m x 2 + ⋯ + a n , m x n P_m(x)=a_{0,m}+a_{1,m} x+a_{2,m}x^2+\cdots+a_{n,m} x^n Pm​(x)=a0,m​+a1,m​x+a2,m​x2+⋯+an,m​xn
为寻找 P ∗ ( x ) P^*(x) P∗(x) 的各项系数，取 n + 1 n+1 n+1 个点 x 0 , x 1 … , x n x_0,x_1\dots,x_n x0​,x1​…,xn​，有
( 1 x 0 ⋯ x 0 n 1 x 1 ⋯ x 1 n ⋮ ⋮ ⋮ 1 x n ⋯ x n n ) ⋅ ( a 0 , m a 1 , m ⋮ a n , m ) = ( P m ( x 0 ) P m ( x 1 ) ⋮ P m ( x n ) ) \begin{pmatrix} 1&x_0&\cdots&x_0^n\\ 1&x_1&\cdots&x_1^n\\ \vdots&\vdots&&\vdots\\ 1&x_n&\cdots&x_n^n\\ \end{pmatrix}\cdot \begin{pmatrix} a_{0,m}\\a_{1,m}\\\vdots\\a_{n,m}\\ \end{pmatrix}= \begin{pmatrix} P_m(x_0)\\P_m(x_1)\\\vdots\\P_m(x_n)\\ \end{pmatrix} ​11⋮1​x0​x1​⋮xn​​⋯⋯⋯​x0n​x1n​⋮xnn​​ ​⋅ ​a0,m​a1,m​⋮an,m​​ ​= ​Pm​(x0​)Pm​(x1​)⋮Pm​(xn​)​ ​
由Vandermonde行列式的性质， a 0 , m , a 1 , m , … , a n , m a_{0,m},a_{1,m},\dots,a_{n,m} a0,m​,a1,m​,…,an,m​ 可被唯一表示，由 P m ( x ) P_m(x) Pm​(x) 的有界性得到 a 0 , m , a 1 , m , … , a n , m a_{0,m},a_{1,m},\dots,a_{n,m} a0,m​,a1,m​,…,an,m​ 的有界性
故由对角线方法，可选到共同的子列使得 a 0 , m i → a 0 ∗ , … , a n , m i → a n ∗ a_{0,m_i}\to a_0^*,\dots,a_{n,m_i}\to a_n^* a0,mi​​→a0∗​,…,an,mi​​→an∗​
令 P ∗ ( x ) = a 0 ∗ + a 1 ∗ x + a 2 ∗ x 2 + ⋯ + a n ∗ x n P^*(x)=a_0^*+a_1^* x+a_2^*x^2+\cdots+a_n^* x^n P∗(x)=a0∗​+a1∗​x+a2∗​x2+⋯+an∗​xn

• 得到的 P ∗ ( x ) P^*(x) P∗(x) 即为所求
  E n ≤ Δ ( P ∗ ) ≤ Δ ( P ) + max ⁡ x ∣ P − P ∗ ∣ ≤ E n + ε → E n \begin{split} E_n&\leq \Delta (P^*)\\ &\leq \Delta (P) + \max\limits_x {|P-P^*|}\\ &\leq E_n + \varepsilon\to E_n \end{split} En​​≤Δ(P∗)≤Δ(P)+xmax​∣P−P∗∣≤En​+ε→En​​

定理：若最佳逼近多项式存在，那么正、负偏离点必同时存在

证明：容易想象，如果多项式无法同时达到正、负偏离点，那么总可以通过上下平移的方式减小偏差

Chebyshev定理： P n \mathbb{P}_n Pn​ 中最佳逼近多项式存在且唯一，且 P n ( x ) P_n(x) Pn​(x) 为最佳逼近多项式当且仅当不少于 n + 2 n+2 n+2 个点为正负偏离点，且交错取到

证明
充分性：（Vallee-Poussin 定理）

设 P ( x ) ∈ P n P(x)\in\mathbb{P}_n P(x)∈Pn​， ε ( x ) = P ( x ) − f ( x ) \varepsilon (x)=P(x)-f(x) ε(x)=P(x)−f(x) 在 x 1 < ⋯ < x N x_1<\cdots<x_N x1​<⋯<xN​ 上取值为非零的正负相间值 λ 1 , − λ 2 , … , ( − 1 ) N − 1 λ N , ( λ i > 0 ) \lambda_1,-\lambda_2,\dots,(-1)^{N-1}\lambda_N,(\lambda_i>0) λ1​,−λ2​,…,(−1)N−1λN​,(λi​>0) 且 N ≥ n + 2 N\geq n+2 N≥n+2 ，则有
∀ Q ( x ) ∈ P n , Δ ( Q ) ≥ min ⁡ λ i \forall Q(x)\in\mathbb{P}_n,\Delta (Q)\geq \min \lambda_i ∀Q(x)∈Pn​,Δ(Q)≥minλi​

证：反证法+零点存在性定理可导出 P ( x ) = Q ( x ) P(x)=Q(x) P(x)=Q(x) ，得矛盾

必要性：只需证不少于 n + 2 n+2 n+2 个正负偏离点，用反证法
若只有 n + 1 n+1 n+1 个正负偏离点 x i x_i xi​，则构造
Q ( x ) = P ( x ) + ω ∏ ( x − x i ) Q(x)=P(x)+\omega \prod\limits(x-x_i) Q(x)=P(x)+ω∏(x−xi​)适当选择 ω \omega ω 的符号，即可得到 Δ ( Q ) < Δ ( P ) \Delta (Q)<\Delta(P) Δ(Q)<Δ(P)

唯一性：同一法 + 零点存在性定理

定理
若 f ( n + 1 ) ( x ) f^{(n+1)}(x) f(n+1)(x) 在 ( a , b ) (a,b) (a,b) 上存在且保号，则 f ( x ) f(x) f(x) 在 P n \mathbb{P}_n Pn​中的最佳逼近多项式满足：恰有 n + 2 n+2 n+2 个正负偏离点，且 a , b a,b a,b 均为正负偏离点

证明：反证法+Rolle定理

3.3 最小零偏差多项式

定义：（最小零偏差多项式）
0 0 0 在 P n \mathbb{P}_n Pn​ 中的最佳逼近多项式称为最小零偏差多项式，或称 Chebshev最佳逼近多项式

注：等价于 x n x^n xn 在 P n − 1 \mathbb{P}_{n-1} Pn−1​ 中的最佳逼近多项式

定理：（Chebshev最佳逼近多项式的结构）
最小零偏差多项式为 2 1 − n T n ( x ) 2^{1-n}T_n(x) 21−nTn​(x) ，其中 T n ( x ) T_n(x) Tn​(x) 为 Chebshev多项式
T n ( x ) = cos ⁡ ( n arccos ⁡ x ) T_n(x)=\cos{(n\arccos{x})} Tn​(x)=cos(narccosx)

证明：
找 x n x^n xn 在 P n − 1 \mathbb{P}_{n-1} Pn−1​ 中的最佳逼近多项式的 n + 1 n+1 n+1 个交错点列，对于 Chebshev多项式即 cos ⁡ k π n , k = 0 , 1 , … , n \cos{\frac{k\pi}{n}},k=0,1,\dots,n cosnkπ​,k=0,1,…,n

推论：
对所有首项系数为 1的 n n n 次多项式，有
max ⁡ ∣ x ∣ ≤ 1 ∣ P n ( x ) ∣ ≥ 2 1 − n \max\limits_{|x|\leq 1}|P_n(x)|\geq 2^{1-n} ∣x∣≤1max​∣Pn​(x)∣≥21−n

参考书籍：《数值分析》李庆扬 王能超 易大义 编