縮めば必ず 1 点に落ち着く、バナッハの不動点定理と反復法

2 点の距離を必ず一定割合まで縮める写像には、動かない点がちょうど 1 つある。しかも、どこから始めて繰り返しても、その点へ落ち着きます^[1]。

存在と一意性と近似手順が、1 つの定理から同時に出てくる。方程式を解く道具としてこれ以上ないほど使い勝手がよい形です^[3]。

縮小写像の定義

距離空間 $(X, d)$ 上の写像 $f : X \to X$ が縮小写像であるとは、ある定数 $0 \leq k < 1$ について次が成り立つことをいいます^[1]。

$d (f (x), f (y)) \leq k d (x, y) (x, y \in X)$

$k$ を縮小率と呼びます。 $k$ 倍のリプシッツ写像なので、縮小写像はいつでも一様連続です。

$k < 1$ が要ります。 $k = 1$ を許すと定理は成り立ちません。等号ぎりぎりで縮まない写像が混じってしまう。

定理の主張

$(X, d)$ を空でない完備距離空間、 $f : X \to X$ を縮小写像とします。このとき $f (x^{*}) = x^{*}$ を満たす $x^{*}$ がただ 1 つ存在する^[1]。

さらに、任意の $x_{0} \in X$ から始めた反復列 $x_{n + 1} = f (x_{n})$ が $x^{*}$ に収束します。

初期値の選び方は結果に効きません。どこから出発しても同じ点へ行き着く。

一意性は 2 行

$f (x^{*}) = x^{*}$ と $f (y^{*}) = y^{*}$ を仮定します。

$d (x^{*}, y^{*}) = d (f (x^{*}), f (y^{*})) \leq k d (x^{*}, y^{*})$

$k < 1$ なので $d (x^{*}, y^{*}) = 0$ 、つまり $x^{*} = y^{*}$ 。使ったのは縮小性だけで、完備性は要りません^[2]。

存在はコーシー列から

$x_{0}$ を勝手にとり、 $x_{n} = f^{n} (x_{0})$ と置きます。縮小性を繰り返し当てると、隣どうしの距離が等比で減る^[1]。

$d (x_{n + 1}, x_{n}) \leq k^{n} d (x_{1}, x_{0})$

三角不等式で $m > n$ の距離を評価すると、等比級数の残りで押さえられます。

$d (x_{m}, x_{n}) \leq \frac{k ^{n}}{1 - k} d (x_{1}, x_{0})$

右辺が $0$ へ行くので ${x_{n}}$ はコーシー列。完備性から極限 $x^{*}$ が存在し、 $f$ が連続なので $f (x^{*}) = x^{*}$ が出ます^[1]。

隣どうしの距離が等比で減る

等比級数の残りで距離を押さえる

コーシー列になる

完備性から極限が存在する

反復のようすを見る

$f (x) = 0.6 x + 1$ をとります。不動点は $x^{*} = 2.5$ 。どこから始めても、階段状に不動点へ寄っていきます。

$y = x$ と $y = f (x)$ の交点が不動点です。傾きが $1$ より小さいので、2 本の直線は必ず 1 回だけ交わる。

誤差の評価

反復をどこで打ち切ってよいかは、2 種類の評価で決まります^[3]。

先験評価は、最初の 1 歩だけから残りを押さえる形です。

$d (x_{n}, x^{*}) \leq \frac{k ^{n}}{1 - k} d (x_{1}, x_{0})$

事後評価は、直前の 1 歩から押さえます。計算しながら精度を確かめるときはこちらが便利。

$d (x_{n}, x^{*}) \leq \frac{k}{1 - k} d (x_{n}, x_{n - 1})$

$k = 0.5$ なら 1 回ごとに誤差が半分になり、 $10$ 回で $1000$ 分の $1$ を切ります。 $k = 0.99$ だと同じ精度に $700$ 回近くかかる。

完備性を外すと崩れる

$X = (0, 1)$ に通常の距離を入れ、 $f (x) = \frac{x}{2}$ をとります。 $k = \frac{1}{2}$ の縮小写像です。

反復列は $0$ へ向かいますが、 $0$ は $X$ に属しません。極限が空間の外に落ちるので、不動点が存在しない^[2]。

縮小率を 1 にすると崩れる

$X = [1, \infty)$ に $f (x) = x + \frac{1}{x}$ をとります。 $x \neq = y$ なら $∣ f (x) - f (y) ∣ < ∣ x - y ∣$ が成り立ちます。

それでも不動点はありません。 $f (x) = x$ は $\frac{1}{x} = 0$ を要求しますが、そんな $x$ はない。

距離を狭義に縮めるだけでは足りず、一定の割合 $k < 1$ で縮める必要があります。ただし $X$ がコンパクトなら、狭義に縮めるだけで不動点が出る^[3]。

縮小写像

$d (f (x), f (y)) \leq k d (x, y)$ 、 $k < 1$ 。完備なら不動点がある

狭義に縮めるだけ

$d (f (x), f (y)) < d (x, y)$ 。コンパクトでないと不動点がないことがある

例：ピカール・リンデレーフの定理

初期値問題 $x^{'} (t) = f (t, x (t))$ 、 $x (τ) = ξ$ を積分方程式に書き直します^[1]。

$x (t) = ξ + \int_{τ}^{t} f (s, x (s)) d s$

右辺を作用素 $K$ と見ると、解を求める問題が $K (x) = x$ という不動点の問題になります。

$C (I)$ に上限ノルムを入れると完備。 $f$ が第 2 引数についてリプシッツ連続なら、区間 $I$ を短くとることで $K$ が縮小写像になります^[1]。

不動点定理から解の存在と一意性が同時に出ます。反復列 $x_{n + 1} = K (x_{n})$ がピカールの逐次近似にあたる。

例： $2$ を反復で出す

$f (x) = \frac{1}{2} (x + \frac{2}{x})$ を $[1, 2]$ で考えます。不動点は $2$ 。

$x_{0} = 1$ から始めると $1.5$ 、 $1.41666 \dots$ 、 $1.414215 \dots$ と進みます。ニュートン法の形なので実際にはもっと速い。

縮小写像の枠組みが保証するのは、少なくとも等比では縮むということ。速さの上乗せは、写像ごとの性質から出ます。

一般化

$f$ 自身が縮小写像でなくても、ある $n$ で $f^{n}$ が縮小写像なら不動点はあります^[3]。

$X$ をコンパクト集合にとると、条件を $d (f (x), f (y)) < d (x, y)$ までゆるめられます^[3]。

逆関数定理や陰関数定理の証明でも、写像を摂動の形に整えてから縮小写像の原理を当てる筋道が使われます。

$X = R$ 、 $f (x) = x + 1$ について正しいのはどれですか。

縮小写像で不動点を 1 つ持つ
$∣ f (x) - f (y) ∣ = ∣ x - y ∣$ なので縮小写像ではなく、不動点もない
$R$ が完備なので不動点がある

__RESULT__

平行移動は距離をまったく変えません。 $k = 1$ にあたるので縮小写像の条件を満たさず、 $x + 1 = x$ を満たす $x$ もない。 $R$ が完備でも、写像の側の条件が欠ければ定理は使えません。

縮むという 1 つの不等式から、存在も一意性も近似の速さも出てくる。仮定が軽いぶん応用範囲が広く、微分方程式から数値計算まで顔を出します。

参考

*Banach's contraction principle. Picard-Lindelöf theorem*. MMG511, Chalmers tekniska högskola.

Vladimir Matveev. *Banachscher Fixpunktsatz*. Metrische Geometrie, Friedrich-Schiller-Universität Jena.

Contracting-mapping principle. Encyclopedia of Mathematics.

距離を一定割合まで縮める写像には、動かない点がちょうど 1 つ。しかもどこから始めて繰り返しても、そこへ落ち着きます。存在と一意性と近似手順が同時に出てくるので、方程式を解く道具として使い勝手がよい。一意性は 2 行、存在は隣どうしの距離が等比で減ることからコーシー列を作ります。完備性を外すと $(0,1)$ の上の $x/2$ が、縮小率を $1$ にすると $[1,\infty)$ の上の $x + 1/x$ が反例になる。先験評価と事後評価、ピカール・リンデレーフの定理への当て方まで並べました。