縮めるだけで答えがひとつに決まる〜バナッハの不動点定理

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

$d (T x, T y) \leq q d (x, y) (\forall x, y \in X)$

このとき $T$ には不動点がただひとつ存在し、どこから始めても反復 $x_{n + 1} = T x_{n}$ がそこへ収束します^[2]。

線形性は要りません。距離空間であること、完備であること、そして縮小率が $1$ より真に小さいこと。仮定はこの 3 つだけです。

証明

任意の $x_{0}$ から始めて $x_{n + 1} = T x_{n}$ と反復します^[1]。隣り合う項の距離が幾何級数で縮む。

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

三角不等式で $m$ 個先まで足すと、公比 $q$ の等比級数で押さえられます。

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

右辺は $n \to \infty$ で $0$ に落ちるので、 $(x_{n})$ はコーシー列です^[2]。 $X$ の完備性から極限 $\tilde{x}$ が存在する。

$T$ は縮小写像なので連続です。 $x_{n + 1} = T x_{n}$ の両辺で極限をとれば $\tilde{x} = T \tilde{x}$ 。

一意性も出ます。 $T x = x$ と $T y = y$ なら $d (x, y) = d (T x, T y) \leq q d (x, y)$ で、 $q < 1$ から $d (x, y) = 0$ 。

誤差がその場で分かる

存在と一意性だけでなく、誤差の大きさまで書けます^[2]。知られている評価は 2 つ。

$d (x_{n}, \tilde{x}) \leq \frac{q ^{n}}{1 - q} d (x_{1}, x_{0}), d (x_{n + 1}, \tilde{x}) \leq \frac{q}{1 - q} d (x_{n + 1}, x_{n})$

左が事前評価です。最初の 1 歩の大きさだけで、 $n$ 回後の誤差が読めます。何回まわせばよいかを、走らせる前に決められる。

右が事後評価です。直前の 2 項の差から、いま残っている誤差が分かる。実際の計算ではこちらのほうが精度が出ます^[1]。

収束は 1 次で、速さは $q$ そのもの^[2]。 $q$ が $1$ に近いほど、必要な反復回数が増えます。

$q < 1$ を $q = 1$ に緩めると壊れる

「 $x \neq = y$ なら $d (T x, T y) < d (x, y)$ 」という条件では足りません^[1]。距離は縮むのに、一定の割合では縮まないから。

$[1, \infty)$ の上で $T (x) = x + 1/ x$ をとる。 $[1, \infty)$ は $R$ の閉集合なので完備。

$x < y$ のとき $∣ T x - T y ∣ = ∣ y - x ∣ (1 - \frac{1}{x y}) < ∣ y - x ∣$ が成り立ちます。距離は必ず縮む。

ところが $T x = x$ は $1/ x = 0$ を意味し、解がありません^[1]。 $x$ が大きいところで縮小率が $1$ に近づくため、一定の $q$ がとれない。

定義域がコンパクトなら、この弱い条件でも不動点が存在します^[1]。上の例は定義域が有界でないところが効いています。

完備性も外せない

$X$ の完備性がないと、コーシー列の行き先が空間の外へ出ます。

$(0, 1]$ の上で $T (x) = x /2$ をとる。縮小率 $1/2$ の縮小写像ですが、反復は $0$ へ向かい、 $0$ は定義域にありません。

完備でない空間では、反復列が「近づいてはいるが着かない」状態になる。存在を保証する足場が抜けています。

縮小写像

$q < 1$ が一定。完備なら不動点がただひとつ存在し、反復がそこへ収束する

距離が縮むだけの写像

$q = 1$ を許す形。 $[1, \infty)$ 上の $x + 1/ x$ のように、不動点がないことがある

応用：微分方程式の解の存在

いちばん有名な応用がピカール・リンデレフの定理です^[2]。初期値問題を積分方程式に書き直します。

$y (t) = y_{0} + \int_{t_{0}}^{t} f (s, y (s)) d s$

右辺を $y$ に対する作用素 $Φ$ と見ると、解はちょうど $Φ$ の不動点。 $f$ が $y$ についてリプシッツ連続なら、区間を短くとることで $Φ$ が縮小写像になります。

$C [t_{0} - δ, t_{0} + δ]$ は最大値ノルムで完備なので、定理が使えます。解の存在と一意性が同時に出るところが強み^[1]。

反復はピカールの逐次近似そのものです。 $y_{0}$ から始めて積分をくり返すと、解へ収束していく。

応用：ニュートン法と逆関数定理

反復の形をした手続きは、たいていこの定理の枠に入ります^[2]。

ニュートン法は $x_{n + 1} = x_{n} - f (x_{n}) / f^{'} (x_{n})$ という反復です。右辺を写像と見て、解の近くで縮小写像になる条件を確かめる、という筋道になります。

逆関数定理も同じ形です^[1]。恒等写像に小さいリプシッツ摂動を足したものが、双リプシッツな同相になる、という主張から出ます。

積分方程式の可解性、動的計画法の値反復、経済学の均衡の存在。反復が縮むかどうかだけを見る、という共通の型があります^[1]。

問題を「 $T x = x$ を解く」形に書き直す

$T$ が縮小写像になる範囲を探す

反復して解を作り、誤差を評価する

$[1, \infty)$ 上の $T (x) = x + 1/ x$ に不動点がないのはなぜですか。

定義域が完備でないから
縮小率が一定の $q < 1$ でとれないから
$T$ が連続でないから

__RESULT__

$[1, \infty)$ は閉集合なので完備で、 $T$ は連続です。距離は必ず縮むものの、 $x$ が大きくなるほど縮小率が $1$ に近づくため、全体で使える定数 $q$ がとれません。

よくある誤り

距離が縮めば不動点があると思う。一定の

q < 1

が要ります。

完備性を落としても使えると思う。

(0, 1]

上の

x /2

で行き先が消えます。

線形性が必要だと思う。距離空間であれば足ります。

初期値の選び方で行き先が変わると思う。どこから始めても同じ不動点に着きます。

事前評価と事後評価を同じものだと思う。使う量も精度も違います。

q

が

1

に近くても回数は変わらないと思う。必要な反復回数は

q

で大きく変わります。

定義域が

T

で保たれることを確かめない。

T (X) \subseteq X

は仮定の一部です。

参考文献

Banach fixed-point theorem. Wikipedia（英語）.

Fixpunktsatz von Banach. Wikipedia（ドイツ語）.

距離が一定の割合で縮む写像には、不動点がただひとつあって、どこから始めても反復がそこへ着きます。線形性は要らず、完備であることと縮小率が $1$ より真に小さいことだけ。事前評価と事後評価で誤差がその場で読めること、$[1, \infty)$ 上の $x + 1/x$ のように縮小率が一定でないと壊れること、そしてピカールの逐次近似やニュートン法がこの枠に収まるところまで。