Linear Algebra (D. Cherney et al.) 二日目

CC BY-NC-SA 3.0

3.4 Pablo Meets Dantzig

線形関数$f(x_1, ..., x_n)$を最大化する$x_i \geq 0$を
$$Mx = v, x := (x_1, ... ,x_n)^T$$
を満たすように探すのがDantzig’s algorithmだが,これをこのまま適用できない場合もある

Examle 42

Pabloの場合, $x \geq 5, y \geq 7$だから, $x_1 = x-5, x_2 = y-7$と置き換える.
$15 \leq x + y \leq 25$は3$\leq x_1 + x_2 \leq 13$となるが, $Mx=v$という形ではない.そこで, $x_3 \geq 0, x_4 \geq 4$なる変数をさらに導入して,$c_1 := x_1 + x_2 - x_3 = 3, c_2 := x_1 + x_2 + x_4 = 13$を束縛条件とする.このように,不等式の条件を等式の条件に変換するために加えられる変数をslack variablesという.こうして
$$\left( \begin{array}{} 1 & 1 & -1 & 0 \\ 1 & 1 & 0 & 1 \end{array}\right) \left(\begin{array}{} x_1 \\x_2 \\ x_3 \\ x_4 \end{array} \right) = \left( \begin{array}{} 3 \\ 13\end{array} \right)$$
が拘束条件$Mx=v$となった.$s = 5x + 10y$を最小化するため, 最大化する関数$f$を $$f = -5x - 10y +95 = -s + 95= -5x_1 -10x_2$$
最大化する$x_1, x_2$を求める.
拡大係数行列は
$$\left( \begin{array}{} 1 & 1 & -1& 0 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 13 \\ 5 & 10 & 0& 0 & 1 & 0 \end{array}\right)$$
となる.
第三行の係数がすべて非負だから$x_1, x_2=0$としてしまいたいが,slack valuableの係数が負であると(この場合,第一行の$x_3$)slack valuableが非負であるという条件のもとで解けなくなってしまうので,さらにartificial variables を導入する.大きな$\alpha>0$によって,$f$を$f -\alpha x_5 -\alpha x_6$とすれば,$f$が最大となるのに$x_5, x_6=0$が必要.
拡大係数行列は
$$\left( \begin{array}{} 1 & 1 & -1 & 0 & 1 & 0 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 13 \\ 5 & 10 & 0 & 0 & 10 & 10 & 1 & 0 \end{array}\right) \\ \downarrow \mbox{(artificial variablesの消去)} \\ \left( \begin{array}{} 1 & 1 & -1 & 0 & 1 & 0 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 13 \\ -15 & -10 & 10 & -10 & 0 & 0& 1 & -160& \end{array}\right) \\ \downarrow \ \ \mbox{(3.3と同じアルゴリズム)} \\ \left( \begin{array}{} 1 & 1 & 1 & 0 & 1 & 0 & 0 & 3 \\ 0 & 0 & 1 & 1 & -1 & 1 & 0 & 10 \\ 0 & 5 & 5 & 0 & 5 & 10 & 1 & -15 \end{array}\right)$$
$x_1 = 3, x_4 = 10$, 他の係数を$0$とすると$f=-15$となって,$\min s = -f+95=110$が解けて,さらに$x=8, y=7$となる.
(正直なんで解けてるのかわからん)

Basic Analysis (Jiri Lebl) 七日目 べき級数と収束半径

CC BY-NC-SA 3.0

2.6.4 Multiplication of series

級数どうしの掛け算は,少なくとも一方が絶対収束すると議論ができる.

Theorem 2.6.5 (Merten’s theorem)

$\sum_{n\geq 0} a_n, \sum_{n\geq 0} b_n$がそれぞれ$A, B$に収束するとする.少なくとも一方が絶対収束するとき,
$$c_n = a_0 b_n + a_1 b_{n-1} + \cdots + a_n b_0 = \sum_{j=0}^n a_j b_{n-j}$$
とすると, $\sum_{n\geq 0} c_n$は$AB$に収束する.この級数$\sum_{n\geq 0} c_n$を$\sum a_n, \sum b_n$のコーシー積(Cauchy product)という.

proof.
略

2.6.5 Power series (べき級数)

$x_0 \in \mathbb{R}$におけるべき級数とは,
$$\sum_{n\geq 0} a_n (x-x_0)^n$$
の形をした$x$の関数で,$x \neq x_0$の少なくともひとつの(実際には収束するなら無限個の)点で収束するとき,べき級数は収束するという.$x \neq x_0$のすべての点で発散するとき,べき級数は発散するという.

Example 2.6.7 (Exponential)

$$\sum_{n \geq 0} \frac{1}{n!} x^n$$
は, $[x^n / n!]/[x^{n+1}/(n+1)!] = x/(n+1) \rightarrow 0$より,ダランベルの収束判定を使って,このべき級数はすべての$x$で収束する.これは$e^x$に等しい.

Proposition 2.6.10 (収束半径)

べき級数$\sum a_n(x-x_0)^n$には,$|x| < \rho$ならば収束, $|x| > \rho$なら発散するような$\rho > 0$がある.この$\rho$を収束半径という.べき級数が発散するときには$\rho=0$, 常に収束するときには$\rho = \infty$とする.
proof. (本の証明がややこしいので”Understanding Analysis”, Abbottを参考にした)

ある$p$で$\sum a_b(x-x_0)^n$が収束するとき,$|x-x_0|<|p-x_0|$なるすべての$x$でべき級数が絶対収束($\Rightarrow$収束)することを示す.$\sum a_n(p-x_0)^n$が収束するから,$|a_n (p-x_0)^n| \leq M$がすべての$n$になりたつ$M$がある.$|x-x_0|<|p-x_0|$とすると,
$$|a_n (x-x_0)^n| = |a_n| |p-x_0|^n \left| \frac{x-x_0}{p-x_0} \right| ^n \leq M \left| \frac{x-x_0}{p-x_0} \right| ^n \rightarrow 0$$
$\sum M |(x-x_0)/(p-x_0)|$ は$r=|(x-x_0)/(p-x_0)| <1$の幾何級数で,収束する.よってこの$x$に$\sum a_n(x-x_0)^n$が絶対収束すことが示せた.
さらに,
$$R = \limsup |a_n|^{1/n}, L=\limsup |a_n(x-x_0)^n|^{1/n} = |x-x_0|\limsup|a_n|^{1/n} = |x-x_0|R$$
とする. $R=0$なら$L=0$で,級数はすべての$x$で収束し,$R=\infty$なら$L=\infty$ですべての$x\neq x_0$に発散する. $0 < R < \infty$とすると, $1 > L = R|x-x_0| \Leftrightarrow |x-x_0| < 1/R$で級数は絶対収束し, また$|x-x_0|>1/R$なら級数は発散する.$\rho = 1/R$とすると,命題が示せた.

Basic Analysis (Jiri Lebl) 六日目 コーシー列と級数の収束

CC BY-NC-SA 3.0

2.4 Cauchy sequences

Definition 2.4.1

$\{x_n\}$がコーシー列$\Leftrightarrow$
$$\forall \epsilon > 0 \ \ \exists N \ \ s.t. \ \ m,n > N \Rightarrow |x_m-x_n| < \epsilon$$

Proposition 2.4.4

コーシー列は有界
proof. 略

Theorem 2.4.5

$\{x_n\}$がコーシー列$\Leftrightarrow\{x_n\}$は収束する$
proof.

($\Rightarrow$)
$\{x_n\}$は有界だから,$\liminf x_n = \limsup x_n$を示せば良い.$a=\limsup x_n, b=\liminf x_n$とすと,$x_{n_k} \rightarrow a, x_{m_k} \rightarrow b$なる部分列$\{x_{n_k}\}, \{x_{m_k}\}$がある.したがって
$$\forall \epsilon \ \ \exists M \ \ s.t. k \geq M \Rightarrow |x_{n_k}-a| < \epsilon \ \&\ |x_{m_k}-b|<\epsilon$$
このとき, $|a - b| = |a - x_{n_k} + x_{n_k} - x_{m_k} + x_{m_k} - b|\leq |a-x_{n_k}| +|x_{n_k}-x_{m_k}|+|x_{m_k}-b|$
コーシー列と部分列の定義から, $k \geq N \Rightarrow |x_{n_k}-x_{m_k}|<\epsilon$なる$N$があって,$L=\max(M,N)$とすると, $$[\forall \epsilon \exists L s.t. k \geq L \Rightarrow |a-b| < \epsilon] \Leftrightarrow a=b$$
以上により示せた
($\Leftarrow$) 略

他の教科書でよく見る証明とは違うが,上下極限が一致するなら極限が存在するという性質を知っていればこっちのほうが単純に書ける.

2.4.1 Exercise

Exercise 2.4.7

問: $\{x_n\}$がコーシー列で, 無限に多くの$n$に$x_n=c$が成立するとき,コーシー列の定義だけを使って$\lim x_n = c$を示せ.

$$\forall \epsilon \exists N \mbox{s.t}. l,m \geq N \Rightarrow |x_l - x_m| < \epsilon$$
無限に多くの$n$に$x_n=c$が成立するから,$x_n= c, n \geq N$を満たす$n$が必ず存在する.このような$l$を$N$を選ぶたびに一つ選んで$\nu$とすると,
$$\forall \epsilon \exists N \mbox{s.t}. l \geq N \Rightarrow |x_l - c| < \epsilon$$
よって$\lim x_n = c$が示せた.

Exercise 2.4.8

問: $\{x_n\}$がコーシー列ならある,$n \geq M \Rightarrow |x_{n+1}-x_n| \leq |x_n - x_{n-1}|$を満たす$M$が存在するか.

$$x_n = \begin{cases} 0 \ \ \ &(mod(n, 3) = 0) \\ 1/n \ \ \ &(mod(n,3)=1) \\ 1/3n \ \ \ &(mod(n, 3) = 2) \end{cases}$$
とすると,$\{x_n\}$が0に収束するのは明らかだが,$mod(n, 3)=0$なる任意の$n$に,
$$|x_{n+1}-x_n|=1/n, |x_{n}-x_{n-1}|=1/3(n-1) \Rightarrow |x_{n+1}-x_n| > |x_n - x_{n-1}|$$
よって反例を示せた.

2.5 Series

2.5.1 Definition

Definition 2.5.1

$$\sum_{n\geq 1} x_n$$
の値を, $s_n = \sum_{i=1}^n$ として部分和の列$\{s_n\}$の極限と定義する.

Proposition 2.5.5

任意の$k$nに
$\sum_{n \geq 1} x_n$が収束する$\Leftrightarrow$ $\sum_{n \geq k} x_n$が収束する

proof.略

2.5.2 Cauchy Series

Definition 2.5.6

$\sum x_n$がコーシー(級数)である$\Leftrightarrow$部分和列がコーシー列である

2.5.3 Basic properties

Proposition 2.5.8

$\sum x_n$が収束するとき, $\{x_n\}$は収束し$\lim x_n=0$.
proof.

級数の収束の定義から, $\sum x_n$が収束する$\Leftrightarrow$ $\sum x_n$はコーシー級数である $\Leftrightarrow$ 部分和列がコーシー列である
部分和列を$\{ s_n\}$とする.これがコーシー列だから$m,n \geq N \Rightarrow |s_m -s_n| < \epsilon$
$m=n-1$と限定すると$|s_n-s_{n-1}| = |x_n| < \epsilon \ \ \ (n \geq n)$
したがって確かに$\{x_n\}$は$0$に収束する.(逆は一般には成り立たない)

Proposition 2.5.10

$\alpha \in \mathbb{R}$があって, $\sum x_n, \sum y_n$が収束級数とすると,
(i) $\sum \alpha x_n$は収束し,$\sum \alpha x_n = \alpha \sum x_n$
(ii)$\sum (x_n + y_n)$は収束し$\sum(x_n+y_n) = \sum x_n + \sum y_n$
proof. 略

2.5.4 Absolute convergence

$\sum x_n$の各$x_n$が非負であれば,部分和列は単調増加列となって,議論しやすい.一般の級数も項に絶対値を施して扱いやすくして,性質を論じることができる.

Definition 2.5.12

$\sum x_n$が絶対収束する(converges absolutely) $\Leftrightarrow$ $\sum |x_n|$が収束する

Proposition 2.5.13

絶対収束する級数は収束する.
proof.

$\sum |x_n|$の部分和$s_n^{abs} = \sum_{k=1}^n |x_n|$はコーシー列だから,
$$\forall \epsilon \ \ \exists N \ \ \mbox{s.t.} m, n \geq N \Rightarrow \left| \sum_{k=n}^m |x_k| \right|<\epsilon$$
ここで, $|\sum_{k=n}^m x_k| \leq \sum_{k=n}^m |x_k|$から, $\sum_{k=1}^n x_k$もコーシー列.
よってもとの級数も収束する.

一方, 絶対収束しなくても収束する(条件収束する)級数の例として$\sum \frac{(-1)^n}{n}$がある.

2.5.5 Comparison test and the p-series

Proposition 2.5.14 (Comparison test)

$0 \leq x_n \leq y_n$であるとき,
(i) $\sum y_n$が収束する $\Rightarrow$ $\sum x_n$も収束
(ii) $\sum x_n$が発散する $\Rightarrow$ $\sum y_n$も発散

proof.

(i)
$x_n, y_n$の部分列をそれぞれ$s_n^{(x)}, s_n^{(y)}$とすると, 仮定より$0 \leq s_n^{(x)} \leq s_n^{(y)}$.
$s_n^{(y)}$の極限を$Y$とすると$0 \leq s_n^{(x)} \leq Y$が常に成立し,$s_n^{(x)}$は収束してLemma 2.2.3よりその極限は$Y$以下.以上により示せた.
(ii) 略

Proposition 2.5.15 (p-series of p-test)

$$\sum_{n=1} ^\infty \frac{1}{n^p}$$
が発散する$\Leftrightarrow p >1$

proof.

$p \leq 1$とする.$n\geq 1 \Rightarrow \frac{1}{n^p} \geq \frac{1}{n}$.
$\sum 1/n$は発散するから,$\sum 1/n^p$も発散する.
$p > 1$とする. 部分和$s_n$は,
$s_1 = 1$
$s_3 = (1) + \left( 2^{-p} + 3^{-p} \right)$
$s_7 = (1) + \left( 2^{-p} + 3^{-p} \right) + \left( 4^{-p} + ... + 7^{-p} \right)$
$\vdots$
$s_{2^k -1} = 1 + \sum_{j=1}^{k-1} \left( \sum_{m=2^j} ^{2^{j+1}-1} m^{-p} \right)$
$p> 0$から, $2^{-p}+3^{-p} < 2^{-p} + 2^{-p}$, $4^{-p}+...+7^{-p} < 4^{-p} + ... +4^{-p}, ...$より,
$$\begin{aligned} s_{2^k -1} &=& 1 + \sum_{j=1}^k \left( \sum_{m=2^j} ^{2^{j+1}-1} m^{-p} \right) \\ &<& 1 + \sum_{j=1}^k 2^{-(p-1)j} \end{aligned}$$
$p>1$から$2^{-(p-1)}<1$. Exercise 2.5.2から, $\sum 2^{-(p-1)}$は収束し,prop2.5.14より$\sum n^{-p}$も収束する.

Example 2.5.16

$\sum \frac{1}{n^2+1}$は収束する.
proof.

$\frac{1}{n^2+1} < \frac{1}{n^2}$であり,Prop2.5.14, 2.5.15から成立.

2.5.6 Ratio test

Proposition 2.5.17 (Ratio test, ダランベルの収束半径)

$L = \lim \frac{|x_{n+1}|}{|x_n|}$が存在するとき,
(i) $L < 1$なら, $\sum x_n$は絶対収束する
(ii) $L>1$なら, $\sum x_n$は発散する

proof.

(i) 略
(ii)Lemma 2.2.12より, $L>1$なら$x_n$は発散する. Prop2.5.8の対偶を考えれば,$\sum x_n$は発散すると示せる.

2.5.7 Exercises

2.5.12

$x_n = \sum_{j=1}^n 1/j$とする. 任意の$k$に$\lim |x_{n+k}-x_n| =0だが,${x_n}$はコーシー列でないと示せ.

1. $\{x_n\}$がコーシー列でないことを示す.
   $m > n$とすると, $|x_m - x_n| = \sum_{j=n+1}^m 1/j$.これは発散する級数の(n+1)-tailであって,$n$を決めれば$m$とともに発散する.よってこれはコーシー列でない.
2. $\lim |x_{n+k}-x_n| = 0$を示す.
   $|x_{n+k} - x_n| = \sum_{j=n+1}^{n+k} 1/j \leq \sum_{j=n+1}^{n+k} 1/(n+1) = k/(n+1) \rightarrow 0 \ \ (n\rightarrow \infty)$

2.5.13

$\sum x_n$の部分和を$s_n$とする.
(a) $\lim s_{mk}$が存在するような$m$があって$\lim x_n=0$なら,$\sum x_n$は収束することを示せ
(b) $\lim s_{2k}$が存在して, $\lim x_n \neq 0$(このとき \sum x_n は発散する)ような$\{x_n\}$を考えよ
(c) $\lim x_n = 0$かつ $\lim s_{k_j}$が収束するような部分列$\{s_{k_j}\}$が存在するが,$\sum x_n$は発散するような$\{x_n\}$を考えよ.

(a) コーシー級数であることを示せば良い.
$p>q$として,$m(k+1) > p\geq mk \geq mk' > q+1 \geq m(k'-1)$なる$k , k'$があるから,
$$\begin{aligned} |s_p -s_q| &\leq |x_{p} |+ |x_{p-1}| + \cdots |s_{mk} - s_{mk'}| + \cdots |x_{q+1}| \\ &\leq |s_{mk} - s_{mk'}| + 2m\max\{|x_i|\}_{i\geq q+1}^p\end{aligned}$$
ここで, $\lim_ks_{mk}$が存在するから$\{s_{mk}\}_k$はコーシー列で,
$\forall \epsilon \ \ \exists N \ \ \mbox{s.t.} \ \ k, k' \geq N_1 \Rightarrow |s_{mk}-s_{mk'}|<\epsilon$
また, $\lim x_n=0$から, $\forall \epsilon \ \ \exists N_2 \ \ \mbox{s.t.} n \geq N_2 \Rightarrow |x_n| < \epsilon$
これらから, $p,q \geq \max(N_1, N_2) \Rightarrow |s_p - s_q| \leq 2\epsilon$.以上により示せた.
(b)$x_n = (-1)^n$とする. $s_{2k} = ((-1) + 1) + ((-1) + 1) + \cdots ((-1)+1) = 0 \times k = 0$
一方,$x_n$は発散(振動)する.
(c)$x_n = \begin{cases} 1/2^m \ \ \ &(2^m \leq n < 2^{m+1}, m:\mbox{odd})\\ -1/2^{(m-1)} \ &(2^m \leq n < 2^{m+1}, m:\mbox{even})\end{cases}$
とする. $\lim x_n = 0$は明らか.
$k_j = 2^{2j+1}$とすると, $s_{k_j} = 0$より部分和部分列は収束.一方で$|s_{2^{m+1}}-s_{2^m}|=1$から,$\sum x_n$は発散する.

2.6 More on Series

2.6.2 Alternating series test

Proposition 2.6.2 (Alternating series test)

$\{x_n\}$は単調減少する正数列とすると
$$\sum (-1)^n x_n$は収束する
proof. 略

2.6.3 Rearrangements

数列の順番を勝手に入れ替えたりカッコをつけたりすると,極限の存在が変わったり,収束先が変わったりする.このような問題を起こさない級数の条件を考える.

Definition 2.6.0

全単射な$\sigma: \mathbb{N} \rightarrow \mathbb{N}$について, $\sum x_{\sigma(n)}$を級数$\sum x_n$の並び替えという.

Proposition 2.6.3

$\sum x_n$を$x$に絶対収束する級数とすると,$\sum x_n$の任意の並び替えはまた$x$に絶対収束する.
prof. 略

Basic Analysis (Jiri Lebl) 五日目 数列の極限と部分列の関係

CC BY-NC-SA 3.0

Limit superior, limit inferior, and Bolzano-Weierstrass

有界かつ発散する数列にもある種の極限を定義する.

2.3.1 Upper and lower limits

有界な数列から単調な部分列を取り出し,その極限をもとの列のある種の極限とする方法.

Definition 2.3.1

$\{x_n\}$ を有界列とする.
$$a_n = \sup\{x_k | k \geq n\}, b_n = \inf\{x_k | k \geq n\}$$
とすると,明らかに$a_n$は講義単調減少し,有界. $b_n$は講義単調増加し,有界.よって極限が存在する.
$$\lim\sup x_n = \lim_{n\rightarrow \infty} a_n \\ \lim\inf x_n = \lim_{n\rightarrow \infty} b_n$$
とする.非有界な数列についても,$\pm \infty$を許せば$\lim\sup, \lim\inf$が定義される.収束列では$\limsup$と$\liminf$は一致する(Th 2.3.5).

Proposition 2.3.2

$\{x_n\}$は有界で$a_n = \sup\{x_k | k \geq n\}, b_n = \inf \{x_k | k \geq n\}$とする.
(i) $\{a_n\}$は有界で単調減少し, $\{b_n\}$は有界で単調増加する.
(ii) $\lim\sup x_n = \inf\{ a_n | n \in \mathbb{N}\}, \lim\inf x_n = \sup \{b_n | n \in \mathbb{N}\}$
(iii) $\liminf x_n \leq \limsup x_n$

proof.

(i) $\{a_n\}$のみ示す. $a_n \leq \sup \{x_n\}$だから上に有界. 下に非有界とすると, $\forall M>0\ \exists N\ s.t.\ \sup \{x_n | n \geq N\} < -M$ このとき$\forall n \geq N\ \ x_n < -M$これは$\{x_n\}$の有界性に反する.また, 一般に$A \subset B \Rightarrow \sup A \leq \sup B$だから,$\{a_n\}$は単調減少する. $\{b_n\}$も同様に示せる.
(ii) 有界で単調増加/減少する列はその上限/下限に収束するから成立
(iii) $a_n, b_n = \sup, \inf \{x_k| k \geq n\}$
から, $a_n \geq b_n$が常に成立.よって$\lim a_n \geq \lim b_n\Leftrightarrow \limsup \{x_n\} \geq \liminf \{x_n\}$

Theorem 2.3.4

$\{x_n\}$が有界列とすると, 部分列$\{x_{n_k}\}$があって,
$$\lim_{k \rightarrow \infty} x_{n_k} = \limsup x_n$$
同様に部分列$\{x_{m_k}\}$があって,
$$\lim x_{m_k} = \liminf x_n$$
が成立する.

proof.

$\lim_{k \rightarrow \infty} x_{m_k} = \limsup x_n$のみ論じる.
$a_n = \sup\{x_k | k \geq n\}$とする. $x = \limsup x_n = \lim a_n$.
$x_n$の部分列$x_{n_k}$を帰納的に定義する.
1. $n_1 = 1$とする.
2. $n_k$が決まっているとき, $a_{n_k + 1} - x_m < \frac{1}{k+1}$を満たす最小の$m\geq k+1$を$n_{k+1}$とする.
ここで,$a_{n_{k-1}+1} \geq a_{n_k}$かつ$a_{n_k} \geq x_{n_k}$より, 任意の$k > 1$に
$$\begin{aligned} |a_{n_k} - x_{n_k}| &=& a_{n_k} - x_{n_k} \\ & \leq & a_{n_{k-1} +1} - x_{n_k} \\ & < & 1 / k \end{aligned}$$
が成立する.($k=1$のときは最左辺は$0$だから結局成立する)
$\{x_{n_k}\}$が$\{a_n\}$と同じ極限$x=\limsup \{x_n\}$に収束することを示す. $\{a_n\}$は$x$に収束するから,その部分列$\{x_{n_k}\}$も$x$に収束する.よって,
$$\forall \epsilon \ \ \exists M_1 \ \ s.t. \ \ k \geq M_1 \Rightarrow |a_{n_k}-x| < \epsilon / 2$$
さらに, $1 /M_2 \leq \epsilon /2$なる$M_2$も存在する.$M = \max\{M_1, M_2\}$とすると,
$$k \geq M \Rightarrow \\ \begin{aligned} |x - x_{n_k}| &\leq |a_{n_k} - x_{n_k}| + |x - a_{n_k}| \\ &< \frac{1}{k} + \frac{\epsilon}{2} \\ &\leq \frac{1}{M_2} + \epsilon /2 \leq \epsilon \end{aligned}$$
以上により示せた.

2.3.2 Using limit inferior and limit superior

Theorem 2.3.5

$\{x_n\}$を有界列とする. $\{x_n\}$が収束する $\Leftrightarrow$ $\limsup x_n = \liminf x_n$.
またこのとき$\limsup x_n = \liminf x_n = \lim x_n$が成立.
proof. 略

Proposition 2.3.6

$\{x_{n_k}\}$を$\{x_n\}$の部分列とすると,
$$\liminf x_n \leq \liminf x_{n_k} \leq \limsup x_{n_k} \leq \limsup x_n$$
proof. 略

Theorem 2.3.7

有界列$\{x_n\}$が$x$に収束する$\Leftrightarrow$任意の部分列が$x$に収束する
proof.

($\Leftarrow$)
$\{x_n\}$それ自体やK-tailも$\{x_n\}$の部分列だから,成立
($\Rightarrow$)
仮定 $\Leftrightarrow \forall \epsilon \ \ \exists N \ \ s.t. \ \ n \geq N \Rightarrow |x_n - x| < \epsilon$
部分列の定義を思い出せば, $n(k)$は単調増加する自然数から自然数への写像だから,$n(N) \geq N$であって, $k \geq N \Rightarrow |x_{n_{k}} -x| \leq |x_n - x| < \epsilon$. よって成立

2.3.3 Bolzano-Weierstrass theorem

Theorem 2.3.8 (Bolzano-Weierstrass)

$\{x_n\}$が有界列であれば, 適当な部分列$\{x_{n_k}\}$は収束する.
proof.

($\{x_n\}$が１次元の実数列であるとき)Th.2.3.4より成立 (区間縮小法を使わない証明!)

しかしこの証明は$\{x_n\}$が二次元以上の点列のときは使えないので,区間縮小法の証明もある.(略)

2.3.4 Infinite limits

非有界な列にも$\limsup, \liminf$を認めると,発散する数列にある種の極限を定義できる.

Definition 2.3.9

$\{x_n\}$が正の無限大に発散する$\Leftrightarrow \forall M > 0 \exists N \ \ .s.t \ \ [n \geq N \Rightarrow x_n > M]$
負の無限大への発散も同様.

Example 2.3.10

$$x_n = \begin{cases} 0 \ \ \ (n : odd) \\ n \ \ \ (n:even) \end{cases}$$
これは無限大に発散しないが, $\limsup x_n = \infty$.

Linear Algebra (D. Cherney et al.) 一日目

CC BY-NC-SA 3.0

Chapter 1. What is Linear Algebra?

線形代数はベクトルと線形関数の研究である

Chapter 2. Systems of Linear Equations

ガウスの掃き出し法の話題

Chapter 3. The Simplex Method

線形連立不等式の話題.最適化やオペレーションリサーチに応用できる.

3.1 Pablo’s Problem

Example 35. (Pablo’s problem restated)

(Pabloは例に出てくる栄養士の名で,アルゴリズムの開発者とかではない)
$x\geq 5, y\geq 7, 15 \leq x+y \leq 25$のもとで, $s = 5x+10y$ を最小にする$x, y$を求める.

3.2 Graphical Solutions

fig.1 $x\geq 5, y\geq 7, 15 \leq x+y \leq 25$ 条件を満たす点を影に塗ったグラフ

$s = 5x + 10y$を最小にするには,$x+y=15$を満たし他の条件を満たす点を探せばよいのは明らかで,この場合は四角形の頂点$(8, 7)$.このように, 最適解が条件を満たす図形の頂点となるのがlinear programming problemの特徴である.

fig.2 $s= 5x + 10y$を追加した図

3.3 Dantzig’s Algorithm

Problem 38

線形関数 $f(x_1, \cdots, x_n)$を$x_i \geq 0$, $Mx = v$ ($M \in M(m, n), v \in \mathbb{R}^m, x = (x_1, ..., x_n)^T$)のもとで最大化する.
この問題は拡大係数行列に行基本変形を施して解ける.

Example 39

$f(x_1, ..., x_n)$ を$c(x_1, ..., x_n) = k$のもとで最大化するというのは,$c=k$が満たされているなら,
$f(x_1, ..., x_n) + \alpha c(x_1, ..., x_n)$を最大化するのと同じこと.$\alpha$をうまく選んで簡単な問題に変形する.

$f(x, y, z, w) = 3x - 3y -z +4w$を,
$$\begin{cases} c_1 = x + y + z + w &= 5 \\ c_2 = x+ 2y + 3z + 2w &= 6\end{cases}$$
をみたしつつ最大化する.
$f$の定義は$-3x + 3y + z - 4w + f = 0$と同値.
$$\left( \begin{array}{} 1 & 1 & 1 & 1 & 0 & 5 \\ 1 & 2 & 3 & 2 & 0 & 6 \\ -3 & 3 & 1 & -4 & 1 & 0\end{array} \right) \Leftrightarrow \begin{cases} c_1 = 5 \\ c_2 = 6 \\ f = 3x - 3y - z + 4w \end{cases}$$
こうして,問題から最後の行が最大化すべき関数$f$で, 他の行が制約条件であるような拡大係数行列を作れた.

Example 41 (Performing EROs)

上の拡大係数行列で, 最後の行の$x, y, z, w$の係数の部分,つまり$-3, 3, 1, -4$の部分がすべて非負で,かつ0が多くなるように行基本変形を施すと,
$$\left( \begin{array}{} 1/2 & 0 & -1/2 & 0 & 0 & 2 \\ 1 & 2 & 3 & 2 & 0 & 6 \\ 0 & 7 & 6 & 0 & 1 & 16\end{array} \right)$$
となって,最後の行の意味は$f = 16 - 7y - 6z$. $y, z \geq 0$だから, 最大の$f$は$f=16$.
$y, z = 0$としたときも制約条件を満たせるか確かめて計算終了.

Basic Analysis (Jiri Lebl) 四日目 数列の極限の性質

CC BY-NC-SA 3.0

2.2 Facts about limits of sequences

2.2.1 Limits and inequalities

Lemma 2.2.1

$a_n \leq x_n \leq b_n$がすべての$n$で成り立つ数列があり,$\{a_n\}, \{b_n\}$が同じ極限に収束するとき,$\{x_n\}$もその極限に収束する
proof. 略

Lemma 2.2.3

$x_n \leq y_n$がすべての$n$で成り立ち,そぜぞれ$x,y$に収束するとき,$x\leq y$
proof. 略

Corollary 2.2.4

(i) $x_n \geq 0$で極限が存在すれば$\lim_{n\rightarrow \infty} x_n \geq 0$
(ii) $a \leq x_n \leq b$で極限が存在すれば $a\leq \lim_{n\rightarrow \infty} x_n \leq b$

2.2.2 Continuity of algebraic operations

Proposition 2.2.5

$\{x_n\}, \{y_n\}$がそれぞれ$x, y$に収束するとき
(i) $(x_n + y_n) \rightarrow x + y$
(ii) $(x_n - y_n) \rightarrow x - y$
(iii) $(x_ny_n) \rightarrow xy$
とくに$\forall n y_n \neq 0, y \neq 0$なら
(iv) $x_n/{y_n} \rightarrow x / y$
proof. 略

Proposition 2.2.6

$x_n \geq 0$な$\{x_n\}$が$x$に収束するとき$\sqrt{x_n} \rightarrow \sqrt{x}$
proof.

$x=0$のときは明らか
$x>0$のとき,
$$|\sqrt{x_n} - \sqrt{x} | = \left| \frac{x_n-x}{\sqrt{x_n}+\sqrt{x}} \right| \leq \frac{1}{\sqrt{x}} |x_n-x|$$
$\sqrt{x}$は有限の正の値なので,$\sqrt{x_n} \rightarrow \sqrt{x}$

Proposition 2.2.7

$\{x_n\}$が$x$に収束するとき$\{|x_n|\}$も収束しその極限は$|x|$.
proof. 略

2.2.4 Some convergence tests

Proposition 2.2.10

0に収束する列$\{a_n\}$があって, $|x_n-x| \leq a_n$なるとき, $x_n \rightarrow x$.
proof.

仮定より$\forall \epsilon >0 \ \ \exists N \ \ s.t. \ \ [n \geq 0 \Rightarrow |a_n-0|]<\epsilon]$
ここで$|x_n-x| \leq |a_n-0|$ を考えれば,$x_n \rightarrow x$が言える.

Proposition 2.2.11

$c > 0$について
(i) $c < 1 \Rightarrow c^n \rightarrow 0$
(ii) $c > 1 \Rightarrow$ 発散
proof. 略

Lemma 2.2.12 (Ratio test for sequences)

$\{x_n\}$について$L := \lim |x_{n+1}|/|x_n|$が存在するとき,
(i) L < 1 なら $x_n \rightarrow 0$
(ii) L > 1 なら $\{x_n\}$は非有界で発散する.
proof. 略

Basic Analysis (Jiri Lebl) 三日目 数列とその収束の定義

CC BY-NC-SA 3.0

Chapter 2 Sequences and Series

2.1 Sequences and limits

---

Definition 2.1.2

数列$\{x_n\}$が$x \in \mathbb{R}$に収束する
$\Leftrightarrow \forall \epsilon > 0 \ \ \exists N \in \mathbb{N} \ \ s.t. \ \ [ n \geq N \Rightarrow |x_n-x|<\epsilon]$

---

Example 2.1.4

$$\lim_{n \rightarrow \infty} \frac{1}{n} = 0$$
proof.
任意の$\epsilon > 0$について,アルキメデス性から, $\frac{1}{N} < \epsilon$ なる$N \in \mathbb{N}$がある,この$N$をそのまま使えば確かに成立.

---

Proposition 2.1.6

収束列の極限は一意である.
proof.
$x, y$ を $\{x_n\}$の極限とする. $x \neq y$ なら, $\epsilon = |x-y|/2 > 0$とする.仮定より,$n \geq N \Rightarrow |x_n - x| < \epsilon$なる$N$が存在する.一方この$N$について$n \geq N \Rightarrow |x_n - y| \geq \epsilon / 2$ これは$y$に収束するという仮定に反する.背理法によって示せた.

---

2.1.1 Monotone sequences

Definition 2.1.9 単調列(monotone sequence, monotonic sequence)

$\{x_n\} \subset \mathbb{R}$が単調増加(increasing)
$\Leftrightarrow \forall n \ \ x_n \leq x_{n+1}$
$\{x_n \} \subset \mathbb{R}$ が狭義単調増加(strictly increasing)
$\Leftrightarrow \forall n \ \ x_n < x_{n+1}$
単調減少,狭義単調減少も同様に定義する.

---

Theorem 2.1.10

単調列$\{x_n\}$が有界である $\Leftrightarrow$ $\{x_n\}$は収束する.
proof.
$\Rightarrow$
単調増加として一般性を失わない.有界性より$a = \sup \{x_n\}$が存在する.上限の定義から
$$\forall \epsilon > 0 \ \ \exists x_m \ \ s.t.\ \ 0\leq a - \epsilon < x_m$$
$n \geq m$ならば$0 \leq a - \epsilon < x_m \leq x_n$であって, $|a - x_n|< \epsilon$が成立.よって$\{x_n\}$は$a$に収束する.

$\Leftarrow$
Prop 2.1.7 (略)

---

2.1.2 Tail of a sequence

Definition 2.1.14

$\{x_n\}$について,$K$-tail ($K \in \mathbb{N}$) あるいは単にtail とは,$\{x_{n+K}\}_{n=1}^\infty$あるいは$\{x_n\}_{n=K+1}^\infty$のことである.

Proposition 2.1.15

$\{x_n\}$について,以下の３つは同値.
(i) $\{x_n\}$は収束する
(ii) $\{x_n\}_{n=K+1}^\infty$は任意の$K$で収束する
(iii) $\{x_n\}_{n=K+1}^\infty$はある$K$で収束する

proof.
(i) $\Rightarrow$ (ii)

極限を$x$とする.
(i) $\Leftrightarrow \forall \epsilon \exists N \ \ s.t. [ n \geq N \Rightarrow |x_n - x| < \epsilon]$
この$N$を固定して考えたとき, $n \geq N+K \geq N \Rightarrow |x_n - x| < \epsilon$よって示せた

(ii) $\Rightarrow$ (iii)

自明

(iii) $\Rightarrow$ (i)

(iii) $\Leftrightarrow \forall \epsilon \exists N \ \ s.t. [ n \geq N \Rightarrow |x_{n+K} - x| < \epsilon]$
この$N$を固定して考えたとき, $M=N+K$とすると, $n \geq M \Rightarrow |x_n-x|<\epsilon$
よって示せた

以上により命題が示せた.

---

2.1.3 Subsequences

Definition 2.1.16

$\{x_n\}$を数列とする, $\{n_i\}$は狭義単調増加する自然数列とする.このとき
$$\{x_{n_i}\}_{i=1}^\infty$$
を$\{x_n\}$の部分列という.

Proposition 2.1.17

$\{x_n\}$を$x$に収束する収束列とすると,任意の部分列は$x$に収束する
証明略

Basic Analysis (Jiri Lebl) 二日目 実数の性質

CC BY-NC-SA 3.0

1.2 The set of real numbers

有理数からの実数の構成は省略して,完備な順序体であるとする.

1.2.2 Archimeddean property

Theorem 1.2.4

(i) $x, y \in \mathbb{R}$ and $x > 0 \Rightarrow \exists n \in \mathbb{N} \ \ s.t. \ \ nx > y$ (Archimedean property)
(ii) $x, y \in \mathbb{R}$ and $x < y \Rightarrow \exists r \in \mathbb{Q} \ \ s.t. \ \ x < r < y$ ($\mathbb{Q}$ is dense in $\mathbb{R}$)

1.2.3 Using supremum and infimum

Definition 1.2.9

(i) $A=\phi \Rightarrow \sup A = -\infty, \inf A = \infty$
(ii) $A$が上に非有界 $\Rightarrow \sup A = \infty$
(iii) $A$が下に非有界 $\Rightarrow \inf A = -\infty$

Proposition 1.2.6

$0<x \in \mathbb{R}$ と有界な集合$A$があるとき, $x+A := \{x+y | y \in A\}, xA :=\{xy| y \in A\}$と定義すると,それぞれの上限,下限は$x$と,$A$の上限,下限の和や積になり,$x < 0$ならば上限と下限が逆転する.

1.2.4 Maxima and minima

Definition

$A \subset \mathbb{R}$について,$\sup A \in A$ならば$\sup A$を$\max A$と書きmaxima(最大値)と呼び, $\inf A \in A$ならば$\inf A$を$\min A$と書きminima(最小値)と呼ぶ.

1.2.5 Exercise

Exercise 1.2.13 (Bernoulli’s inequality)

$1 + x> 0 , n \in \mathbb{N} \Rightarrow (1+x)^n \geq 1 + nx$

proof.
n=1 のときは明らかに成立.
(帰納ステップ)
$$\begin{aligned} (1 + x)^{n+1} &\geq (1+x)(1+nx) \\ &= 1+(n+1)x+nx^2 \\ &\geq 1+(n+1)x \end{aligned}$$
から,n=nで成立すると仮定するとn=n+1でも成立する.
数学的帰納法で示せた.

1.3 Absolute value

$$|x|:= \begin{cases} x \ \ \ \ \ \ (x\geq 0) \\ -x \ \ \ (x < 0) \end{cases}$$
で絶対値を定義する.

Proposition 1.3.2 (Triangle Inequality)

$$|x+y| \leq |x| + |y|$$

Corollary 1.3. 4

$$|x_1 + x_2 + \cdots x_n| \leq |x_1|+|x_2|+ \cdots +|x_n|$$

Definition 1.3.6

$f: D \rightarrow \mathbb{R}$が有界関数
$\Leftrightarrow \exists M \ \ s.t. \ \ \forall x \in D |f(x)|< M$

1.3.1 Exercise

Exercise 1.3.7

$D \neq \phi$, $f,g : D \rightarrow \mathbb{R}$. このとき
$$\sup (f(x)+g(x)) \leq \sup f(x) + \sup g(x)$$

proof.
$b, c$をそれぞれ$f, g$の上界とすると,$\forall x f(x) < b, \forall x g(x)<c$よって$\forall x (f(x)+g(x)) < b+c$よって示せた

Basic Analysis (Jiri Lebl) 一日目 実数の定義 1

Chapter 1. Real Numbers

実数を公理的に定義する

Definition 1.1.1

(i) $\forall x \in S \ \ x \leq x$
(ii) $x \leq y$ and $y \leq z \Rightarrow x \leq z$
(iii) $x \leq y$ and $y \leq x \Rightarrow x = y$
(iv) $x, y \in S \Rightarrow x \leq y$ or $y \leq x$
これらの命題を(i): 反射律 (ii): 推移律 (iii): 対象律 (iv): 全順序律という.

$S$ が$\leq$ を順序関係とする順序集合である
$\Leftrightarrow$ (i),(ii),(iii),(iv)をすべて満たす$S$とその関係の組$(S, \leq)$を全順序集合という.
(本では $<$ の関係を考えていたが,こっちのほうが標準的だろう.)

Definition 1.1.2

全順序集合$S$と部分集合$E$において, $b \in S$ で $\forall x \in E\ \ x \leq b$ なる$b$があるとき,$b$を$E$の上界といい, $E$は上に有界という. また$b_0$が$E$の上界であり,かつ$b_0 \leq b$なら$b$が$E$の上界であるとき,$b_0$を$E$の上限といい,$\sup E$と書く. 下界,下への有界,下限もほとんど同様に定義し, $E$の下限を $\inf E$と書く.

Definition 1.1.3

$S$の任意の上に有界かつ空でない部分集合$E$が常に上限を持つという性質をleast-upper-bound propertyとかcompleteness(完備性) という.

Example 1.1.4

$\{x\in \mathbb{Q} | x^2 < 2\}$ の上限は$S=\mathbb{R}$ とみると $\sqrt{2} \in \mathbb{R}$ だが,$\sqrt{2} \not\in \mathbb{Q}$ から,有理数全体の集合は完備でない.

Definition 1.1.7

体$F$が順序体である
$\Leftrightarrow$ $F$は体であり,かつ
(i) $x, y, z \in F, x< y \Rightarrow x + z < y + z$
(ii) $x, y \in F, x > 0, y> 0 \Rightarrow xy>0$