はじめましての方ははじめまして。東京大学工学部計数工学科B3のT.S.と申します。
この記事は
物工/計数 Advent Calendar 2020
の5日目の記事として書かれました。
4日目の記事はこちら↓です。
肉体労働のすすめ！
今回は学科で学習したBanachの不動点定理とその周辺のことをまとめてみました。記事を読むにあたって必要な知識は距離やノルムや内積、完備性の定義を知っていれば十分な内容になっています。
筆者は数学に関しても記事を書くことに関しても全くの初心者です。何か間違いがありましたらご指摘お願いします。
まずは縮小写像と不動点を定義します。
集合$X$で定義された自己写像$T:X \to X$に対して、$z \in X$が存在して$T(z) = z$を満たすとき、$z$は$T$の不動点であるという。$T$の不動点全体からなる集合を$Fix(T) = \{z \in X \mid F(z) = z\}$と表す。
$(X,d)$を距離空間とする。このとき写像$T:X \to X$が$X$上の縮小写像であるとは、ある実数$\kappa \in [0,1)$が存在して、$d(T(x),T(y)) \leq \kappa d(x,y)$が任意の$x,y \in X$について成り立つことをいう。
縮小写像は連続であることに注意しましょう。
$(\because \forall \epsilon > 0, \forall x,y \in X,
d(x,y)<\epsilon \Rightarrow d(T(x),T(y)) \leq \kappa d(x,y) < \kappa \epsilon < \epsilon)$
縮小写像$T$の不動点が存在するとき、その点を$\bar{x}$とおくと任意の$x \in X$について
$d(T(x),\bar{x}) = d(T(x), T(\bar{x})) \leq \kappa d(x,\bar{x}) < d(x, \bar{x}) $
となります。ここから任意の点が縮小写像によってその不動点に近づいていくイメージを持つことができます。
空間に強い仮定をおけば不動点は唯一つ存在することが示せます。これがBanachの不動点定理です。
$(X,d)$を空でない完備距離空間とする。
このとき$X$上の縮小写像$T$はただ１つの不動点$\bar{x}$を持ち、任意の$x \in X$に対して$\lim_{k \to \infty}T^k(x) = \bar{x}$となる。
(存在）$x_0 \in X$を任意にとり、点列$(x_n)_{n \in \N}$を$x_k := T^k(x)$と定義すると、
$d(x_k, x_{k+1}) = d(T(x_{k-1}),T(x_k)) \leq \kappa d(x_{k-1},x_k)$
$\therefore d(x_k, x_{k+1}) \leq \kappa^k d(x_0,x_1)$
よって$m > n > 0$のとき
$d(x_n, x_m) \leq \sum_{j=n}^{m-1}d(x_j,x_{j+1})$ $(\because 三角不等式)$
$\leq \sum_{j=n}^{m-1}\kappa^jd(x_0, x_1) = \kappa^n \frac{1-\kappa^{m-n}}{1-\kappa}d(x_0, x_1) \to 0 \,\,(n,m \to \infty)$
$\therefore (x_n)_{n \in \N}$はCauchy列。
$X$は完備なのでCauchy列は収束し$\bar{x} := \lim_{k \to \infty}x_k \in X$が存在する。
$T$は連続なので$T(\bar{x}) = \lim_{k \to \infty}T(x_k) = \lim_{k \to \infty}x_{k+1} = \bar{x}$
よって$\bar{x} \in Fix(T) \neq \emptyset$.
(一意性)
$\bar{x},\bar{y} \in Fix(T)$とすると$d(\bar{x},\bar{y}) = d(T(\bar{x}),T(\bar{y})) \leq \kappa d(\bar{x}, \bar{y})$
$0 \leq \kappa < 1$であるから$d(\bar{x},\bar{y}) = 0$となり$\bar{x} = \bar{y}$ (証明終)
以降$\mathcal{H}$を完備な実内積空間(実Hilbert空間)とし、$x,y \in \mathcal{H}$の内積を$\langle x,y \rangle$, $x$のノルムを$\|x\|$と書くこととします。
縮小写像の仮定をほんの少しだけ緩めたものとして非拡大写像があります。
写像$T:\mathcal{H} \to \mathcal{H}$が$\mathcal{H}$上の非拡大写像であるとは、$\|T(x)-T(y)\| \leq \|x-y\|$が任意の$x,y \in \mathcal{H}$について成り立つことをいう。
$\mathcal{H} := \R$, $T_1:\R \to \R: x \mapsto x+1$を考えると、$T_1$は
$\|T_1(x)-T_1(y)\| = \|(x+1)-(y+1)\| = \|x-y\|$
を満たすので非拡大写像ですが、明らかに不動点を持ちません。ここから縮小写像の$\kappa < 1$が本質的な仮定であることがわかります。
ここで任意の点が縮小写像によってその唯一つの不動点に近づいていくことを思い出し、そこからもう一つの一般化を考えることができます。
写像$T:\mathcal{H} \to \mathcal{H}$が$\mathcal{H}$上の準非拡大写像であるとは、$Fix(T)$が空ではなく、任意の$x \in \mathcal{H}$ $z \in Fix(T)$に対して$\|T(x)-z\| \leq \|x-z\|$が成り立つことをいう。
しかし実際は非拡大写像が不動点を持てば準非拡大写像となります。
非拡大写像$T:\mathcal{H} \to \mathcal{H}$が$Fix(T) \neq \emptyset$を満たすとき、任意の$x \in \mathcal{H}$ $z \in Fix(T)$に対して
$\|T(x)-z\| = \|T(x)-T(z)\| \leq \|x-z\|$ (証明終わり)
自然な疑問として、準非拡大写像の不動点集合に興味が湧きます。（湧いて）
準非拡大写像$T:\mathcal{H} \to \mathcal{H}$の不動点集合$Fix(T)$は
$Fix(T) = \bigcap_{y \in \mathcal{H}}\left\{x \in \mathcal{H} \mid \langle y-T(y), x \rangle \leq \frac{\|y\|^2 - \|T(y)\|^2}{2}\right\}$
と表現できる。特に$Fix(T)$は閉凸集合である。
任意の$y \in \mathcal{H}$について$\left\{x \in \mathcal{H} \mid \langle y-T(y), x \rangle \leq \frac{\|y\|^2 - \|T(y)\|^2}{2}\right\}$は閉凸集合であり、閉凸集合の任意個の共通部分集合は閉凸集合である。よって等号を確認すれば良い。
$(\subset)$ $x \in Fix(T)$とする。任意の$y \in \mathcal{H}$に対して
$0 \leq \|y-x\|^2 - \|T(y)-x\|^2$
$\leq \|y\|^2 + \|x\|^2 - 2\langle y,x \rangle -\|T(y)\|^2 -\|x\|^2 + 2\langle T(y),x\rangle$
$= \|y\|^2 - \|T(y)\|^2 -2\langle y-T(y),x \rangle$
$\therefore \langle y-T(y), x \rangle \leq \frac{\|y\|^2 - \|T(y)\|^2}{2}$
$y \in \mathcal{H}$は任意なので$Fix(T) \subset \bigcap_{y \in \mathcal{H}}\left\{x \in \mathcal{H} \mid \langle y-T(y), x \rangle \leq \frac{\|y\|^2 - \|T(y)\|^2}{2}\right\}$.
$(\supset)$ $x \in \bigcap_{y \in \mathcal{H}}\left\{x \in \mathcal{H} \mid \langle y-T(y), x \rangle \leq \frac{\|y\|^2 - \|T(y)\|^2}{2}\right\}$とすると、任意の$y \in \mathcal{H}$に対して
$2\langle y-T(y),x\rangle \leq \|y\|^2 - \|T(y)\|^2$
ここで$y := x$とすれば
$2\langle x-T(x), x \rangle \leq \|x\|^2 - \|T(x)\|^2$
$= \|x\|^2 - \|T(x)-x+x\|^2$
$=\|x\|^2 - \|T(x)-x\|^2 - \|x\|^2 - 2\langle T(x)-x,x\rangle$
$\therefore \|T(x)-x\|^2 \leq 0$
よって$x = T(x)$であり$x \in Fix(T)$である。(証明終わり)
準非拡大写像$T$の不動点集合$Fix(T)$の濃度は$|Fix(T)| = 1$または$|Fix(T)| \geq \aleph$となる。
$z_1, z_2 \in Fix(T)$を相異なる2点としたとき、$f:[0,1] \to Fix(T)$を$f(t) = tz_1+(1-t)z_2$とすれば$Fix(T)$は閉凸集合なので$f$はwell-definedであり、明らかに単射なので$|Fix(T)| \geq |[0,1]| = \aleph$ (証明終わり)
最後に(準)非拡大写像の不動点近似定理を紹介しておきます。
非拡大写像$T:\mathcal{H} \to \mathcal{H}$の不動点集合$Fix(T)$が空でないとき、$\sum_{n \in \Z_{\geq 0}}\alpha_n(1-\alpha_n) = \infty$を満たす任意の実数列$(\alpha_n)_{n\in \Z_{\geq 0}} \subset [0,1]$と任意の初期値$x_0 \in \mathcal{H}$を用いて
$x_{n+1} := (1-\alpha_n)x_n + \alpha_n T(x_n)$によって生成される点列$(x_n)_{n=0}^{\infty}$は、$Fix(T)$の1点$\bar{x}$が存在して、任意の$y \in \mathcal{H}$に対して$\lim_{n \to \infty}\langle x_n-\bar{x},y\rangle = 0$となる。(これを$(x_n)_{n=0}^{\infty}$が$\bar{x}$に弱収束するという。)
このアルゴリズムは$(x_n)_{n=0}^{\infty}$が$\bar{x}$に収束すること$(\lim_{n \to \infty}\|x_n - \bar{x}\| = 0)$までは保証しませんが、どの座標成分を見ても収束することを保証してくれます。($\mathcal{H}$が有限次元の場合は同じ意味になります。)
積読していた本の中から手頃な演習問題を解いて記事にしました。(ア)
不動点定理は多くの場合その存在を保証する定理ですが、(代表的な例としてBrouwerの不動点定理)定理1や3ではその不動点に(弱)収束するアルゴリズムを証明で具体的に与えてくれています。定理1の応用には常微分方程式の解の存在と一意性に関するピカールの逐次近似法や逆関数定理があります。また定理3の応用として閉凸集合上の微分可能な凸関数の最小化問題に対する射影勾配法があり、そのアルゴリズムは特に信号処理などに応用されています。
関数解析や最適化理論は純粋な数学としての楽しみ方だけではなく物理学や工学、また今流行りの†機械学習†などに応用が沢山あるので皆さんも勉強して人生を最適化しましょう。
山田功:工学のための関数解析, 数理工学社(2009)