概率论与数理统计 (Spring 2023)/Weierstrass Approximation Theorem: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(15 intermediate revisions by the same user not shown)
Line 1: Line 1:
[https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theorem '''魏尔施特拉斯逼近定理''']('''Weierstrass Approximation Theorem''')陈述了:闭区间上的连续函数总可以用多项式一致逼近。
[https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theorem '''魏尔施特拉斯逼近定理''']('''Weierstrass approximation theorem''')陈述了这样一个事实:闭区间上的连续函数总可以用多项式一致逼近。
{{Theorem|魏尔施特拉斯逼近定理|
{{Theorem|魏尔施特拉斯逼近定理|
:设<math>f:[a,b]\to\mathbb{R}</math>为定义在实数区间<math>[a,b]</math>上的连续实值函数。对每个<math>\epsilon>0</math>,存在一个多项式 <math>p</math> 使得对于 <math>[a,b]</math> 中所有 <math>x</math>,均有 <math>|p(x)-f(x)|\le \epsilon</math>,即
:设 <math>f:[a,b]\to\mathbb{R}</math> 为定义在实数区间 <math>[a,b]</math> 上的连续实值函数。对每个 <math>\epsilon>0</math>,存在一个多项式 <math>p</math> 使得对于 <math>[a,b]</math> 中所有 <math>x</math>,均有 <math>|p(x)-f(x)|\le \epsilon</math>,即
:::<math>\sup_{x\in[a,b]}\|f(x)-p(x)\|\le \epsilon</math>
:::<math>\sup_{x\in[a,b]}\|f(x)-p(x)\|\le \epsilon</math>
}}
}}
Line 13: Line 13:
将多项式 <math>p</math> 定义如下。对每个 <math>x\in[0,1]</math>,令:
将多项式 <math>p</math> 定义如下。对每个 <math>x\in[0,1]</math>,令:
:<math>p(x)=\mathbb{E}\left[f\left(\frac{Y_x}{n}\right)\right]=\sum_{k=0}^nf\left(\frac{k}{n}\right)\Pr(Y_x=k)=\sum_{k=0}^nf\left(\frac{k}{n}\right){n\choose k}x^k(1-x)^{n-k}</math>.
:<math>p(x)=\mathbb{E}\left[f\left(\frac{Y_x}{n}\right)\right]=\sum_{k=0}^nf\left(\frac{k}{n}\right)\Pr(Y_x=k)=\sum_{k=0}^nf\left(\frac{k}{n}\right){n\choose k}x^k(1-x)^{n-k}</math>.
容易看出,这是一个关于变量 <math>x\in[0,1]</math> 的(<math>n</math>次齐次)多项式。
容易看出,这是一个关于变量 <math>x\in[0,1]</math> 的(<math>n</math>次)多项式。


根据[https://en.wikipedia.org/wiki/Heine%E2%80%93Cantor_theorem '''一致连续性定理''']('''海涅-康托尔定理'''),紧空间 <math>[0,1]</math> 上的连续函数 <math>f</math> 必然也是'''一致连续'''的。即,对任意 <math>\epsilon>0</math>,总存在 <math>\delta_\epsilon>0</math>,使得对于 <math>[0,1]</math> 中任意满足 <math>|x-y|\le\delta_\epsilon</math> 的 <math>x,y</math>,都有 <math>|f(x)-f(y)|\le\frac{\epsilon}{2}</math>。
根据[https://en.wikipedia.org/wiki/Heine%E2%80%93Cantor_theorem '''一致连续性定理''']('''海涅-康托尔定理'''),紧空间 <math>[0,1]</math> 上的连续函数 <math>f</math> 必然也是'''一致连续'''的。即,对任意 <math>\epsilon>0</math>,总存在 <math>\delta_\epsilon>0</math>,使得对于 <math>[0,1]</math> 中任意满足 <math>|x-y|\le\delta_\epsilon</math> 的 <math>x,y</math>,都有 <math>|f(x)-f(y)|\le\frac{\epsilon}{2}</math>。


不妨定下任意的<math>\epsilon>0</math>,以及一致连续性定理因此保证的 <math>\delta_\epsilon>0</math>。
不妨定下任意的<math>\epsilon>0</math>,以及一致连续性定理因此保证的 <math>\delta_\epsilon>0</math>。
定下任意的 <math>x\in[0,1]</math>。我们希望验证 <math>|p(x)-f(x)|\le\epsilon</math>。
并且定下任意的 <math>x\in[0,1]</math>。我们希望验证 <math>|p(x)-f(x)|\le\epsilon</math>。


根据 <math>p</math> 的定义,有:
根据 <math>p</math> 的定义,有:
Line 45: Line 45:
上述最后一个不等式 <math>(\star)</math> 成立是因为根据一致连续性,条件 <math>\left|\frac{Y_x}{n}-x\right|\le \delta_\epsilon</math> 保证了 <math>\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\le\frac{\epsilon}{2}</math>,因此
上述最后一个不等式 <math>(\star)</math> 成立是因为根据一致连续性,条件 <math>\left|\frac{Y_x}{n}-x\right|\le \delta_\epsilon</math> 保证了 <math>\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\le\frac{\epsilon}{2}</math>,因此
:<math>\mathbb{E}\left[\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\,\,\bigg{|}\,\, \left|\frac{Y_x}{n}-x\right|\le \delta_\epsilon\right]\le\frac{\epsilon}{2}</math>
:<math>\mathbb{E}\left[\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\,\,\bigg{|}\,\, \left|\frac{Y_x}{n}-x\right|\le \delta_\epsilon\right]\le\frac{\epsilon}{2}</math>
另一方面,<math>\left|f\left({Y_x}/{n}\right)-f(x)\right|\le \sup_{y\in[0,1]}|f(y)-f(x)|\le \sup_{y\in[0,1]}|f(y)| = 2\|f\|_{\infty}</math> 无条件成立,因此
另一方面,有 <math>\left|f\left({Y_x}/{n}\right)-f(x)\right|\le \sup_{y\in[0,1]}|f(y)-f(x)|\le 2\sup_{y\in[0,1]}|f(y)| = 2\|f\|_{\infty}</math> 无条件成立,因此
:<math>\mathbb{E}\left[\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\,\,\bigg{|}\,\, \left|\frac{Y_x}{n}-x\right|\le \delta_\epsilon\right]\le 2\|f\|_{\infty}</math>.
:<math>\mathbb{E}\left[\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\,\,\bigg{|}\,\, \left|\frac{Y_x}{n}-x\right|> \delta_\epsilon\right]\le 2\|f\|_{\infty}</math>.


由切比雪夫不等式可得:
公式 <math>(\star)</math> 中的概率可由切比雪夫不等式得出如下上界:
:<math>
:<math>
\begin{align}
\begin{align}
Line 56: Line 56:
&\le
&\le
\frac{\mathbf{Var}[Y_x]}{n^2\delta_\epsilon^2} && \text{(切比雪夫不等式)}\\
\frac{\mathbf{Var}[Y_x]}{n^2\delta_\epsilon^2} && \text{(切比雪夫不等式)}\\
&\le
&=
\frac{nx(1-x)}{n^2\delta_\epsilon^2} && (\mathbf{Var}[Y_x]=nx(1-x))\\
\frac{nx(1-x)}{n^2\delta_\epsilon^2} && (\mathbf{Var}[Y_x]=nx(1-x))\\
&\le  
&\le  
Line 62: Line 62:
\end{align}
\end{align}
</math>
</math>
因此可以选择正整数 <math>n\ge\frac{\|f\|_{\infty}}{\epsilon\delta_\epsilon^2}</math>。如此选取的 <math>n</math> 可保证
因此可以选择 <math>n</math> 为任意满足 <math>n\ge\frac{\|f\|_{\infty}}{\epsilon\delta_\epsilon^2}</math> 的正整数(注意到这一 <math>n</math> 的选取是与  <math>x</math> 无关的,因此可对所有  <math>x</math> 选取一致的  <math>n</math>)。如此可保证以上的概率上界为 <math>\frac{1}{4n\delta_\epsilon^2}\le\frac{\epsilon}{4\|f\|_{\infty}}</math>
:<math>\Pr\left[\left|\frac{Y_x}{n}-x\right|> \delta_\epsilon\right]\le\frac{1}{4n\delta_\epsilon^2}\le\frac{\epsilon}{4\|f\|_{\infty}}</math>
将其代回至 <math>(\star)</math>式,得到如下结论:
于是 <math>(\star)</math>式总有如下的上界
:<math>|p(x)-f(x)|\le \frac{\epsilon}{2}+2\|f\|_{\infty}\cdot \frac{\epsilon}{4\|f\|_{\infty}}\le\epsilon</math>
:<math>|p(x)-f(x)|\le \frac{\epsilon}{2}+2\|f\|_{\infty}\cdot \frac{\epsilon}{4\|f\|_{\infty}}\le\epsilon</math>
}}
}}

Latest revision as of 12:53, 18 April 2023

魏尔施特拉斯逼近定理Weierstrass approximation theorem)陈述了这样一个事实:闭区间上的连续函数总可以用多项式一致逼近。

魏尔施特拉斯逼近定理
[math]\displaystyle{ f:[a,b]\to\mathbb{R} }[/math] 为定义在实数区间 [math]\displaystyle{ [a,b] }[/math] 上的连续实值函数。对每个 [math]\displaystyle{ \epsilon\gt 0 }[/math],存在一个多项式 [math]\displaystyle{ p }[/math] 使得对于 [math]\displaystyle{ [a,b] }[/math] 中所有 [math]\displaystyle{ x }[/math],均有 [math]\displaystyle{ |p(x)-f(x)|\le \epsilon }[/math],即
[math]\displaystyle{ \sup_{x\in[a,b]}\|f(x)-p(x)\|\le \epsilon }[/math]
Proof.

不失一般性地,可以仅考虑区间[math]\displaystyle{ [a,b]=[0,1] }[/math]。因为对于定义在一般的实数区间[math]\displaystyle{ [a,b] }[/math]上的任意函数[math]\displaystyle{ f }[/math],可通过变量变换[math]\displaystyle{ t\mapsto a+(b-a)t }[/math]将其转化为定义在[math]\displaystyle{ [0,1] }[/math]上的新函数[math]\displaystyle{ g(t)=f(a+(b-a)t) }[/math],这并不会改变函数的连续性以及是否为多项式。

因此,可假设连续函数[math]\displaystyle{ f:[0,1]\to\mathbb{R} }[/math]。令[math]\displaystyle{ n }[/math]为足够大的正整数,取值待定。

对于任意 [math]\displaystyle{ x\in [0,1] }[/math],令 [math]\displaystyle{ Y_x\sim\text{Bin}\left(n,x\right) }[/math] 为以[math]\displaystyle{ n,x }[/math]为参数的二项分布随机变量。

将多项式 [math]\displaystyle{ p }[/math] 定义如下。对每个 [math]\displaystyle{ x\in[0,1] }[/math],令:

[math]\displaystyle{ p(x)=\mathbb{E}\left[f\left(\frac{Y_x}{n}\right)\right]=\sum_{k=0}^nf\left(\frac{k}{n}\right)\Pr(Y_x=k)=\sum_{k=0}^nf\left(\frac{k}{n}\right){n\choose k}x^k(1-x)^{n-k} }[/math].

容易看出,这是一个关于变量 [math]\displaystyle{ x\in[0,1] }[/math] 的([math]\displaystyle{ n }[/math]次)多项式。

根据一致连续性定理(海涅-康托尔定理),紧空间 [math]\displaystyle{ [0,1] }[/math] 上的连续函数 [math]\displaystyle{ f }[/math] 必然也是一致连续的。即,对任意 [math]\displaystyle{ \epsilon\gt 0 }[/math],总存在 [math]\displaystyle{ \delta_\epsilon\gt 0 }[/math],使得对于 [math]\displaystyle{ [0,1] }[/math] 中任意满足 [math]\displaystyle{ |x-y|\le\delta_\epsilon }[/math][math]\displaystyle{ x,y }[/math],都有 [math]\displaystyle{ |f(x)-f(y)|\le\frac{\epsilon}{2} }[/math]

不妨定下任意的[math]\displaystyle{ \epsilon\gt 0 }[/math],以及一致连续性定理因此保证的 [math]\displaystyle{ \delta_\epsilon\gt 0 }[/math]。 并且定下任意的 [math]\displaystyle{ x\in[0,1] }[/math]。我们希望验证 [math]\displaystyle{ |p(x)-f(x)|\le\epsilon }[/math]

根据 [math]\displaystyle{ p }[/math] 的定义,有:

[math]\displaystyle{ \begin{align} |p(x)-f(x)| =& \left|\mathbb{E}\left[f\left(\frac{Y_x}{n}\right)\right]-f(x)\right|\\ =& \left|\mathbb{E}\left[f\left(\frac{Y_x}{n}\right)-f(x)\right]\right| && \text{(期望的线性)}\\ \le& \mathbb{E}\left[\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\right] && \text{(琴生不等式)}\\ =& \mathbb{E}\left[\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\,\,\bigg{|}\,\, \left|\frac{Y_x}{n}-x\right|\le \delta_\epsilon\right] \cdot \Pr\left[\left|\frac{Y_x}{n}-x\right|\le \delta_\epsilon\right] \\ &+ \mathbb{E}\left[\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\,\,\bigg{|}\,\, \left|\frac{Y_x}{n}-x\right|\gt \delta_\epsilon\right] \cdot \Pr\left[\left|\frac{Y_x}{n}-x\right|\gt \delta_\epsilon\right] && \text{(全期望法则)}\\ \le& \frac{\epsilon}{2} +2\|f\|_{\infty}\cdot \Pr\left[\left|\frac{Y_x}{n}-x\right|\gt \delta_\epsilon\right] && (\star) \end{align} }[/math]

上述最后一个不等式 [math]\displaystyle{ (\star) }[/math] 成立是因为根据一致连续性,条件 [math]\displaystyle{ \left|\frac{Y_x}{n}-x\right|\le \delta_\epsilon }[/math] 保证了 [math]\displaystyle{ \left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\le\frac{\epsilon}{2} }[/math],因此

[math]\displaystyle{ \mathbb{E}\left[\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\,\,\bigg{|}\,\, \left|\frac{Y_x}{n}-x\right|\le \delta_\epsilon\right]\le\frac{\epsilon}{2} }[/math]

另一方面,有 [math]\displaystyle{ \left|f\left({Y_x}/{n}\right)-f(x)\right|\le \sup_{y\in[0,1]}|f(y)-f(x)|\le 2\sup_{y\in[0,1]}|f(y)| = 2\|f\|_{\infty} }[/math] 无条件成立,因此

[math]\displaystyle{ \mathbb{E}\left[\left|f\left(\frac{Y_x}{n}\right)-f(x)\right|\,\,\bigg{|}\,\, \left|\frac{Y_x}{n}-x\right|\gt \delta_\epsilon\right]\le 2\|f\|_{\infty} }[/math].

公式 [math]\displaystyle{ (\star) }[/math] 中的概率可由切比雪夫不等式得出如下上界:

[math]\displaystyle{ \begin{align} \Pr\left[\left|\frac{Y_x}{n}-x\right|\gt \delta_\epsilon\right] &= \Pr\left[\left|{Y_x}-\mathbb{E}[Y_x]\right|\gt n\delta_\epsilon\right] && (\mathbb{E}[Y_x]=nx)\\ &\le \frac{\mathbf{Var}[Y_x]}{n^2\delta_\epsilon^2} && \text{(切比雪夫不等式)}\\ &= \frac{nx(1-x)}{n^2\delta_\epsilon^2} && (\mathbf{Var}[Y_x]=nx(1-x))\\ &\le \frac{1}{4n\delta_\epsilon^2}. \end{align} }[/math]

因此可以选择 [math]\displaystyle{ n }[/math] 为任意满足 [math]\displaystyle{ n\ge\frac{\|f\|_{\infty}}{\epsilon\delta_\epsilon^2} }[/math] 的正整数(注意到这一 [math]\displaystyle{ n }[/math] 的选取是与 [math]\displaystyle{ x }[/math] 无关的,因此可对所有 [math]\displaystyle{ x }[/math] 选取一致的 [math]\displaystyle{ n }[/math])。如此可保证以上的概率上界为 [math]\displaystyle{ \frac{1}{4n\delta_\epsilon^2}\le\frac{\epsilon}{4\|f\|_{\infty}} }[/math]。 将其代回至 [math]\displaystyle{ (\star) }[/math]式,得到如下结论:

[math]\displaystyle{ |p(x)-f(x)|\le \frac{\epsilon}{2}+2\|f\|_{\infty}\cdot \frac{\epsilon}{4\|f\|_{\infty}}\le\epsilon }[/math]
[math]\displaystyle{ \square }[/math]