10/25/2014

[數學分析] Compactness 與 Totally Boundedness

令 $X$ 為 metric space 且 metric 為 $d$;亦即 $(X,d)$ 為 metric space。

==========================
Definition: Compact Metric Space
(a) 由 open subsets 所形成的集合  $\{G_\alpha\}_{\alpha \in A} $ 被稱為 open cover 若 下列條件成立:
對任意 $x \in X$ 存在 $\alpha \in A$ 使得 $x \in G_\alpha$。

若 index set $A$ 為 finite 則 $\{G_\alpha\}$ 為 finite open cover。

(b) 我們說 metric space $(X,d)$ 為 compact 若下列條件成立:
對任意 open cover of $X$,存在 有限個 subcover of $X$。
==========================

Comment
注意到上述定義在 metric space $(X,d)$ 之上,若我們現在考慮其上的子集合:
\[
A \subset X
\]則 $A$ 仍為一個 metric space 且 metric 為 $d$;亦即 $(A,d)$ 仍為一個 metric space。


==========================
Definition: Compact Set
集合 $A \subset X$ 為 compact 若下列條件成立:
metric space $(A,d)$ 為 compact (亦即:對任意 open cover 存在 有限 subcover of $A$。)
==========================



==========================
Definition: Relatively Compact
集合 $A \subset X$ 稱為 relatively compact 若下列條件成立
\[
\bar A \subset X \text{ is compact}
\]上述 $\bar{A}$ 表示 closure of $A$
==========================

==========================
Theorem: Heine-Borel Theorem
若 $A \subset \mathbb{R}^n$ (或者 $\mathbb{C}^n$) 為 closed + bounded 則 $A$ 為 compact。
==========================

==========================
Definition: Sequentially Compact
我們說一個 metric space $(X,d)$ 為 sequentially compact 若下列條件成立
對任意 sequence in $X$ 存在 收斂 subsequence 。
==========================

==========================
Definition: Totally Bounded
一個 metric space $(X,d)$ 稱為 totally bounded 若下列條件成立:
對任意 $\varepsilon>0$,存在有限個 以半徑為 $\varepsilon$ 的 open Ball $\mathcal{B}_\varepsilon$ 所組成的集合 並且 covers $X$。
==========================


Example
考慮 $l^p$ space $:= \{\{a_n\}_n: \sum_{n}^\infty |a_n|^p < \infty, 0 <p <\infty\}$;且定義 metric 如下
\[d\left( {{a_n},{b_n}} \right): = {\left( {\sum\limits_{n = 1}^\infty  {|{a_n} - {b_n}{|^p}} } \right)^{\frac{1}{p}}}\]

Question: 試定義 半徑為1 且球心為 $\{0,0,0,...\}$ 的 open ball $\mathcal{B} \in l^p$:
ANS:\[
\mathcal{B}: = \left\{ {{{\left\{ {{a_n}} \right\}}_{n \in \mathbb{N}}}:\sum\limits_{n = 0}^\infty  {{{\left| {{a_n}} \right|}^p} < 1} } \right\}
\]
現在定義 example element in $l^p$
\[\left\{ {{e_n}^{\left( k \right)}} \right\}: = \left\{ \begin{array}{l}
0,\begin{array}{*{20}{c}}
{}
\end{array}n \ne k\\
1,\begin{array}{*{20}{c}}
{}
\end{array}n = k
\end{array} \right.
\]舉例而言,若 $k=1$ 則 上述定義表示 $e_n^{(1)} = \{1, 0, 0, 0,...\}$ 若 $k=2$ 則上述定義表示 $e_n^{(2)} = \{0, 1, 0, 0,...\}$

注意到
1. $\{e_n^{(k)}\} \in  \mathcal{\bar{B}}$
2. 且 example element 的 距離 (metric, $d$) 為 \[d({e^{(k)}},{e^{(m)}}) = {\left( {\sum\limits_{n = 0}^\infty  {{{\left| {e_n^{(k)} - e_n^{\left( m \right)}} \right|}^p}} } \right)^{\frac{1}{p}}} = {2^{\frac{1}{p}}}\]

Question: 試問 $ \mathcal{\bar{B}}$ 是否為 totally bounded?
NO! 亦即 存在 $\varepsilon>0$,使得 沒有 有限的 collection of open balls covers $X$

取 $\varepsilon < 1/2^p$ 則可證明 沒有有限的 collection of open balls covers $X$。


以下我們看個 totally bounded 的結果

=============
FACT: 若 $X$ 為 totally bounded metric space,則 $X$ 具有 countable 且 dense 的子集合 (亦即 $X$ 中存在 separable 的子集合)。
=============
Proof:
此為存在性的定理,我們要找出 一個 $X$ 的子集合 滿足 countable 與 dense。

首先由於 $X$ 為 totally bounded metric space,由定義可知 對任意 $\varepsilon >0$, 存在有限個 由半徑為 $\varepsilon>0$ 的 open ball $\mathcal{B}$ 所組成 的  cover of $X$。故對任意 $n \in \mathbb{N}$ 我們選 $\varepsilon_n:=1/n$,並且令有限個點 $x_1,...x_n \in X$,則由 toally boundedness of $X$ 我們可建構集合
\[
A_n := \{x_1, x_2,...,x_n\}
\] 使得 $X \subset \cup_i^n \mathcal{B}(x_i) $。那麼若我們現在令
\[
A:= \cup_n A_n
\] 則此集合 $A \subset X$ 且為 countable。

接著我們證集合 $A$ 為 dense。亦即要證明 :
對任意 $z \in X$,存在一組 sequence $\{z_n\} \in A$ 使得 $z_n \rightarrow z$。

現在給定任意 $z \in X$ ,則由 totally boundedness 我們可知必定存在 一個 點 $z_n \in A$ 使得 $d(z_n, z) < 1/n$ ,故對任意 $n \in \mathbb{N}$ 我們可建構一組 sequence $\{z_n\}$ 滿足
\[
\lim_{n \rightarrow \infty} d(z_n,z) =0
\]亦即 $z_n \rightarrow z$。

===================
Lemma 1: 任意 closed subset $F$ of compact metric space $X$ 必為 compact。
Proof: omitted.
===================

===================
Lemma 2: 任意 在 $X$ 中的無窮集合 必有 accumulation point 若且為若 $X$ 為 sequentially compact。
===================

Proof: $(\Rightarrow)$ 假設 在 $X$ 中的無窮集合 必有 accumulation point,我們要證明  $X$ 為 sequentially compact;亦即給定任意 sequence in $X$ ,要證明 存在 有收斂 subsequence 。

現在取 $\{p_n\}$ 為 $X$ 中任意 sequence。 將此 $\{p_n\} $ 中的元素形成集合 $A \subset X$ 且考慮以下兩種情況:
1.若 集合 $A$ 中元素為有限個,則 $\{p_n\}$ sequence 中 必定存在一點為重複出現無限次,則我們可取此點為形成 constant subsequence。
2. 若 集合 $A$ 中元素為無限個,亦即 $\{p_n\}$ 為無限個相異元素;由 假設可知
"任意 在 $X$ 中的無窮集合 必有 accumulation point "
$A$ 為 $X$ 中的無窮集合,必有  accumulation point ,此等價為 $\{p_n\}$ 具有收斂子數列。

$(\Leftarrow)$ 假設 $X$ 為 sequentially compact,要證明 任意 在 $X$ 中的無窮集合 必有 accumulation point。

令 $A \subset X$ 為無窮集合,我們要證 $A$ 必有 accumulation point。
我們取 $\{a_n\} \subset A$ 為 sequence,則由於  $X$ 為 sequentially compact,故可知給定任意sequence in $X$,必有收斂子數列。此等價為 $A$ 必有 accumulation point。

===================
Lemma 3: 若 $X$ 為 compact,則 $X$ 為 sequentially compact。
===================
Proof:
要證 $X$ 為 sequentially compact;可由 Lemma 2 我們證 任意 在 $X$ 中的無窮集合 必有 accumulation point 。

利用歸謬法(Proof by contradiction):假設 $X$ 為 compact,且存在一個 $X$ 中的無窮集合,但此集合並沒有 accumulation point 。我們要證矛盾。

故現在令 $Y \subset X$ 為此 無窮集合 (沒有 accumulation point)。則由於 $Y$ 並沒有 accumulation point ,我們可推知 對任意 $y \in Y$,存在適當的半徑 $r>0$ 使得開球 $B_r(y)$ 與 $Y$ 的交集
 \[B_r(y) \cap Y = \{y\}
\] 且由於  $Y$ 無 accumulation point,我們亦另外推知 $Y$ 為 closed。 ($Y$ is closed iff its contains all its accumulation point,但由於 $Y$ 並無 accumulation point,故 $Y$ 為 closed。)

由於 $X$ 為 compact,且 $Y \subset X$ 為 closed,由 Lemma 1 可知 $Y$ 亦為 compact。

對任意 $y$,我們確實可透過 $B_r(y)$ 來 cover $Y$ (透過 $ B_r(y) \cap Y = \{y\}$ ) 故由 compactness of $Y$ 可知必定存在有限個 subcover 來蓋住 $Y$。但此與 $Y$ 為無窮集合 矛盾。 $\square$

現在我們回憶 totally bounded
==========================
Definition: Totally Bounded
一個 metric space $(X,d)$ 稱為 totally bounded 若下列條件成立:
對任意 $\varepsilon>0$,存在有限個 以半徑為 $\varepsilon$ 的 open Ball $\mathcal{B}_\varepsilon$ 所組成的集合 並且 covers $X$。
==========================

Definition: 一個集合 $A$ 為 $\varepsilon$-net for space $X$ 若下列條件成立:
$A$ 為 finite set 且對 $x \in A$,開球 $B_\varepsilon(x)$ 建構一個 open cover of $X$。

現在我們給出等價定義: 我們說 $A$ is totally bounded 若 對任意 $\varepsilon>0$ 而言,我們有 $\varepsilon$-net。

Claim: 若 $X$ 為 sequentially compact,則 集合 $A \subset X$ 滿足 $p,q \in A, p \neq q$ 且 $d(p,q) \ge \varepsilon$ 為 有限集。
proof:


Lemma 4: 一個 sequentially compact 的 metric space $X$ 為 totally bounded + complete。

Proof:
先證 totally bounded。給定 $\varepsilon$,要建構 一個 $\varepsilon$-net。

現在令 $A \subset X$ 為一集合 滿足其中的元素之間互相之距離大於 $\varepsilon$,由 Claim 可知此集合 $A$ 為 有限集合,故對任意點 $p_i \in A$ 則我們可對每一個 $i$,建構一開球 $B_\varepsilon(p_i)$ 且此開球確實 蓋住 $X$。
亦即我們確實建構出 $\varepsilon$-net for $X$ 故  $X$ 為 totally bounded。$\square$

接著我們證  $X$ 為  complete:亦即給定任意 Cauchy sequence $\{x_n\} \subset X$ 要證明 此 $\{x_n\}$ 收斂在 $X$ 上。

由於 $X$ 為 sequentially compact ,故此 $\{x_n\}$ 具有收斂子數列 $\{x_{n_k}\}$在 $X$ 上。稱其極限為 $l$ 現在觀察 對足夠大的 $N$ 使得當 $n,n_k \ge N$ 我們有
\[\begin{array}{l}
\left| {{x_n} - l} \right| = \left| {{x_n} - {x_{{n_k}}} + {x_{{n_k}}} - l} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} \le \left| {{x_n} - {x_{{n_k}}}} \right| + \left| {{x_{{n_k}}} - l} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} < \varepsilon /2 + \varepsilon /2 < \varepsilon
\end{array}\]故$X$ 為  complete。 $\square$

10/01/2014

[數學分析] Weierstrass Theorem (1) - 先備概念

回憶在數學分析的內容中,我們試圖利用 $\mathbb{Q}$ 在 $\mathbb{R}$ 中 dense的想法,指出 任意在 $\mathbb{R}$ 上的實數 $r$,皆可透過 一組 sequence $\{q_n\} \in \mathbb{Q}$ 逼近 。也就是說 $q_n \rightarrow r$ 當 $n \rightarrow \infty$。那麼我們想問在函數上是否也有類似的概念? Weierstrass Approximation Theorem 便是試圖回答這個問題。

Weierstrass  Approximation Theorem 主要想法: 利用多項式 均勻收斂 連續函數!!

不過在介紹之前,我們需要一些先備知識。
首先看個 算子 (operator) 的概念:
定義 $A: \text{one function} \rightarrow \text{different function}$ 為一個算子(operator)

我們看個例子:

------------
Example
Fourier transform of 函數 $f$ 為一個算子 (將函數 $f$ 映射到另一個函數 $F$)
\[F(j\omega ) = \int_{ - \infty }^\infty  f (t){e^{ - j\omega }}dt
\]-----------

那麼算子何其多? 哪一種算子適合我們?? 以下我們介紹一個即為有用的特殊算子:摺積(Convolution)

===================
Definition: Convolution (Integral)
給定兩可積函數 $f,g$ on $\mathbb{R}$,則其折積(convolution) 定義為
\[(f*g)\left( x \right): = \int f (x - y)g(y)dy = \int g (x - y)f(y)dy
\]===================

Example
$f,g$ 為在 $[-1,1]$ 上的週期函數,且 $|\delta| <1$ \[f\left( x \right): = \left\{ \begin{array}{l} 1/2\delta ,\begin{array}{*{20}{c}} {}&{} \end{array}x \in \left[ { - \delta ,\delta } \right]\\ 0,\begin{array}{*{20}{c}} {}&{}&{} \end{array}o.w \end{array} \right.
\]試求其 convolution $(f * g)(x)=?$
Proof:
\[\begin{array}{l}
f*g: = \int_{ - 1}^1 {f\left( y \right)g\left( {x - y} \right)dy}  = \int_{ - \delta }^\delta  {\frac{\delta }{2}g\left( {x - y} \right)dy} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \frac{\delta }{2}\int_{ - \delta }^\delta  {g\left( {x - y} \right)dy}. \ \ \ \ \square
\end{array}
\]

Convolution 的好處:可以保留原函數的本身的優點!!

===================
FACT: 令 $K$ 為 compact interval,若 $f \in \mathcal{C}^{\infty}(\mathbb{R})$ (smooth function) 且 $g$ 為 可積函數,則
\[
(f * g)(x) = \int_K f(y)g(x-y)dy
\]亦為在 $K$ 上 smooth function
==================
Proof: omitted.

現在我們看個函數
===================
Definition: A Specific Smooth Function
令 $\phi(x)$ 為 $\mathbb{R}$ 上的 smooth function 且滿足下列條件
在 $(-1,1)$, $\phi>0$ ;且在 $(-1,1)^c$, $\phi=0$ ;另外我們限定此函數  $\phi$ 必須滿足下列積分
\[
\int_{-1}^{1} \phi(t) dt =1
\]===================

有了上述函數,我們可以定義算子 Operator $A$ 如下:
對 $s>0$,定義 $\phi_s$ 為\[{\phi _s}(t): = \frac{1}{s}\phi (\frac{t}{s});\;\;\;\int_{-1}^1 \phi  dt = 1\]且
\[
A_s f(t) :=( \phi_s * f)(t) = \int \phi_s(t) f(x-t) dt
\]其中 $\phi \ge 0$ on $[-1,1]$ 且 $\phi =0$ on $[-1,1]^c$ 。
============
Theorem: Preliminary Lemma for Weierstrass Approximation Theorem
令 $f$ 為 有界 連續 函數 on $\mathbb{R}$ ($f \in \mathcal{C}(\mathbb{R})$) 且 令 $J$ 為任意 compact interval in $\mathbb{R}$。則 當 $s \rightarrow 0$,我們有 $A_s f \rightarrow f$ 均勻收斂 on $J$。
============

Proof:
令 $\varepsilon>0$ ,我們要證明 $A_s f \rightarrow f$ 均勻收斂;(注意到上述定理陳述是當 $s \rightarrow 0$,故令 $n := 1/s$) 故要證 存在 $N>0$ 使得 $n > N$ 我們有
\[
|A_sf(x) - f(x) | < \varepsilon
\]對任意 $x \in J$ 。

觀察
\[\small
\begin{array}{l}
|{A_s}f(x) - f(x)| = \left| {\int_{ - \infty }^\infty  {{\phi _s}\left( t \right)f\left( {x - t} \right)dt}  - f\left( x \right)} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \left| {\int_{ - \infty }^\infty  {{\phi _s}\left( t \right)f\left( {x - t} \right)dt}  - f\left( x \right)\underbrace {\int_{ - \infty }^\infty  {{\phi _s}\left( t \right)dt} }_{ = 1}} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \left| {\int_{ - \infty }^\infty  {\left[ {f\left( {x - t} \right) - f\left( x \right)} \right]{\phi _s}\left( t \right)dt} } \right| \le \int_{ - \infty }^\infty  {\left| {f\left( {x - t} \right) - f\left( x \right)} \right|{\phi _s}\left( t \right)dt}  < \varepsilon
\end{array}\]注意到上式中當 $|t| >s$時, $\phi_s =0$故上式積分範圍為
\[|{A_s}f(x) - f(x)| \le \int_{ - s}^s {\left| {f\left( {x - t} \right) - f\left( x \right)} \right|{\phi _s}\left( t \right)dt}  < \varepsilon \]
故如果可以讓上式 $|f(x-t) - f(x)|$ 對任意 $x \in J$ 都可使其任意小便完成證明。故現在透過 $J$ 為任意 compact interval on $\mathbb{R}$,我們可推知 $f$ 在 $J$ 上為 uniform continuous。亦即我們可選 $\delta >0$ 使得對任意 $u,v \in J$,
\[
|u-v| < \delta \Rightarrow |f(u) - f(v)| < \varepsilon
\]取 $u :=x, v := x+t \in J$ 則我們可知
\[
|u-v| = |x - (x+t)| < \delta \Rightarrow  |f(x) - f(x-t)| < \varepsilon
\]也就是說只要能找到 $N$ 使得 $n >N$ 且滿足 $|t| < \delta$ 則 我們便會有
\[|{A_s}f(x) - f(x)| \le \int_{ - s}^s {\left| {f\left( {x - t} \right) - f\left( x \right)} \right|{\phi _s}\left( t \right)dt}  < \varepsilon \]由於 $n =1/s; \; n >N \Rightarrow s < 1/N$ 且又由 $\phi_s(t)$ 定義可知 $t \in [-s,s]$故取 $N = 1/\delta$ 則上述自動滿足。$\square$

[最佳化] C^2 函數一階逼近的餘項積分表示

令 $f: \mathbb{R}^m \to \mathbb{R}$ 為 $C^2$-函數。對 $f$ 在 $y$ 附近使用一階泰勒展開: \[ T_y(x) := f(y) + \nabla f(y)^\top (x - y) \] 則其餘項 $R(x,y)$ 訂為 $$R(...