§E2.7Banach の不動点定理

最終更新

方程式をf(x)=xf(x)=xの形に整理すると、その解は写像ffが動かさない点にあたる。ただし、変形によって解を求めることが難しい場合には、任意の点からffの適用を繰り返して得られる列の極限を調べるという方法がある。この列が収束するかどうかはffの性質に依存し、一般には収束しない。ある実数0≤q<10\leq q<1が存在して、任意の二点の像の距離がもとの二点の距離のqq倍以下になる写像を縮小写像という。空でない完備距離空間の上では、縮小写像はただ一つの不動点をもち、どの点から始めた反復列もその不動点へ収束する。この定理は、解の存在と一意性を同時に与える最も基本的な結果の一つであり、微分方程式や数値計算における逐次近似の根拠として広く用いられる。たとえば、実数直線上の写像f(x)=x/2+1f(x)=x/2+1は縮小比1/21/2の縮小写像であり、その不動点は22である。本記事では、この定理と、反復による近似の精度に関する評価を扱う。

1 縮小写像と反復列

定義 1.1.(X,d)(X,d)を§E2.1 定義 1.1で定める距離空間とする。写像f:X→Xf:X\to Xが縮小写像 (contraction mapping) であるとは、0≤q<10\leq q<1を満たす実数qqが存在して、任意のx,y∈Xx,y\in Xに対して

d(f(x),f(y))≤qd(x,y)d\bigl(f(x),f(y)\bigr)\leq qd(x,y)

が成り立つことをいう。この不等式を満たすqqをffの縮小比 (contraction ratio) という。

注意 1.2. 縮小比は一意とは限らない。qqが縮小比であり、q≤q′<1q\leq q'<1であるならば、q′q'も縮小比である。以下では、縮小比を一つ固定する。

命題 1.3.(X,d)(X,d)を距離空間とし、f:X→Xf:X\to Xを縮小写像とする。このとき、ffは連続写像である。

証明.ffの縮小比qqをとる。任意のx,y∈Xx,y\in Xに対してd(f(x),f(y))≤qd(x,y)≤d(x,y)d(f(x),f(y))\leq qd(x,y)\leq d(x,y)であるから、§E2.4 命題 3.4をL=1L=1として適用すると、ffは連続である。▨

定義 1.4.(X,d)(X,d)を距離空間とし、f:X→Xf:X\to Xを写像とする。等式f(x)=xf(x)=xを満たすx∈Xx\in Xをffの不動点 (fixed point) という。

x0∈Xx_0\in Xに対して、

xn+1=f(xn)(n∈Z≥0)x_{n+1}=f(x_n)\qquad(n\in\mathbb Z_{\geq0})

によって定まる点列(xn)n∈Z≥0(x_n)_{n\in\mathbb Z_{\geq0}}を、x0x_0から始まるffの反復列 (iteration sequence) という。

2 不動点定理と誤差評価

補題 2.1.(X,d)(X,d)を距離空間とし、f:X→Xf:X\to Xを縮小比qqの縮小写像とする。x0∈Xx_0\in Xから始まる反復列(xn)n∈Z≥0(x_n)_{n\in\mathbb Z_{\geq0}}に対して、任意のn∈Z≥0n\in\mathbb Z_{\geq0}について

d(xn,xn+1)≤qnd(x0,x1)d(x_n,x_{n+1})\leq q^n d(x_0,x_1)

が成り立つ。さらに、任意の整数m>n≥0m>n\geq0について

d(xn,xm)≤qn(1−qm−n)1−qd(x0,x1)≤qn1−qd(x0,x1)d(x_n,x_m) \leq \frac{q^n(1-q^{m-n})}{1-q}d(x_0,x_1) \leq \frac{q^n}{1-q}d(x_0,x_1)

が成り立つ。

証明.n=0n=0の場合には最初の不等式は等号で成り立つ。あるn≥0n\geq0について最初の不等式が成り立つならば、縮小写像の定義から

d(xn+1,xn+2)=d(f(xn),f(xn+1))≤qd(xn,xn+1)≤qn+1d(x0,x1)d(x_{n+1},x_{n+2}) =d\bigl(f(x_n),f(x_{n+1})\bigr) \leq qd(x_n,x_{n+1}) \leq q^{n+1}d(x_0,x_1)

を得る。したがって、数学的帰納法によって最初の不等式が成り立つ。

m>n≥0m>n\geq0とする。三角不等式と最初の不等式により、

d(xn,xm)≤∑j=nm−1d(xj,xj+1)≤d(x0,x1)∑j=nm−1qj=qn(1−qm−n)1−qd(x0,x1)≤qn1−qd(x0,x1)\begin{aligned} d(x_n,x_m) &\leq\sum_{j=n}^{m-1}d(x_j,x_{j+1})\\ &\leq d(x_0,x_1)\sum_{j=n}^{m-1}q^j\\ &=\frac{q^n(1-q^{m-n})}{1-q}d(x_0,x_1)\\ &\leq\frac{q^n}{1-q}d(x_0,x_1) \end{aligned}

が成り立つ。▨

定理 2.2 (Banach の不動点定理).(X,d)(X,d)を空でない完備距離空間とし、f:X→Xf:X\to Xを縮小比qqの縮小写像とする。このとき、ffはただ一つの不動点x∗∈Xx^*\in Xをもつ。さらに、任意のx0∈Xx_0\in Xから始まる反復列はx∗x^*に収束する。

証明.x0∈Xx_0\in Xを任意にとり、xn+1=f(xn)x_{n+1}=f(x_n)によって反復列(xn)n∈Z≥0(x_n)_{n\in\mathbb Z_{\geq0}}を定める。補題 2.1により、整数m>n≥0m>n\geq0に対して

d(xn,xm)≤qn1−qd(x0,x1)d(x_n,x_m)\leq\frac{q^n}{1-q}d(x_0,x_1)

である。m<nm<nの場合には距離の対称律を用い、m=nm=nの場合にはd(xn,xn)=0d(x_n,x_n)=0を用いる。§B1.7 定理 2.1によりqn→0q^n\to0であるから、(xn)(x_n)は§E2.5 定義 1.1で定める Cauchy 列である。XXは完備であるため、xn→x∗x_n\to x^*を満たすx∗∈Xx^*\in Xが存在する。

命題 1.3によりffは連続である。したがって、§E2.4 命題 1.3の連続性から点列連続性を導く向きにより、f(xn)→f(x∗)f(x_n)\to f(x^*)である。一方、f(xn)=xn+1f(x_n)=x_{n+1}であり、(xn+1)n∈Z≥0(x_{n+1})_{n\in\mathbb Z_{\geq0}}は(xn)n∈Z≥0(x_n)_{n\in\mathbb Z_{\geq0}}の部分列であるから、§E2.3 命題 2.3によりxn+1→x∗x_{n+1}\to x^*である。§E2.3 命題 1.3によってf(x∗)=x∗f(x^*)=x^*を得る。

y∗∈Xy^*\in Xもffの不動点であるとする。縮小不等式により

d(x∗,y∗)=d(f(x∗),f(y∗))≤qd(x∗,y∗)d(x^*,y^*) =d\bigl(f(x^*),f(y^*)\bigr) \leq qd(x^*,y^*)

である。したがって、(1−q)d(x∗,y∗)≤0(1-q)d(x^*,y^*)\leq0である。1−q>01-q>0であり、§E2.1 命題 1.2によりd(x∗,y∗)≥0d(x^*,y^*)\geq0であるからd(x∗,y∗)=0d(x^*,y^*)=0であり、x∗=y∗x^*=y^*である。x0x_0は任意であったため、任意の出発点から始まる反復列が、この一意な不動点へ収束する。▨

系 2.3.(X,d)(X,d)を空でない完備距離空間とし、f:X→Xf:X\to Xを縮小比qqの縮小写像とする。x0∈Xx_0\in Xから始まる反復列を(xn)n∈Z≥0(x_n)_{n\in\mathbb Z_{\geq0}}とし、ffの不動点をx∗x^*とする。このとき、次の評価が成り立つ。

  1. すべてのn∈Z≥0n\in\mathbb Z_{\geq0}に対して、事前評価 d(xn,x∗)≤qn1−qd(x0,x1)d(x_n,x^*)\leq\frac{q^n}{1-q}d(x_0,x_1) が成り立つ。
  2. すべてのn∈Z≥1n\in\mathbb Z_{\geq1}に対して、事後評価 d(xn,x∗)≤q1−qd(xn−1,xn)d(x_n,x^*)\leq\frac{q}{1-q}d(x_{n-1},x_n) が成り立つ。

証明. 事前評価について、補題 2.1により、m>nm>nならば

d(xn,xm)≤qn1−qd(x0,x1)d(x_n,x_m)\leq\frac{q^n}{1-q}d(x_0,x_1)

である。§E2.1 命題 1.3から

∣d(xn,xm)−d(xn,x∗)∣≤d(xm,x∗)\bigl|d(x_n,x_m)-d(x_n,x^*)\bigr|\leq d(x_m,x^*)

を得る。m→∞m\to\inftyとするとd(xm,x∗)→0d(x_m,x^*)\to0であるから、実数列(d(xn,xm))m>n(d(x_n,x_m))_{m>n}はd(xn,x∗)d(x_n,x^*)に収束する。この実数列は、§E2.1 命題 1.2と上の評価により、すべてのm>nm>nについて

0≤d(xn,xm)≤qn1−qd(x0,x1)0\leq d(x_n,x_m)\leq\frac{q^n}{1-q}d(x_0,x_1)

を満たす。したがって§E2.5 補題 5.4によりd(xn,x∗)d(x_n,x^*)も同じ上界を満たし、事前評価を得る。

事後評価について、n≥1n\geq1を固定し、y0=xn−1y_0=x_{n-1}から始まる反復列を(yk)k∈Z≥0(y_k)_{k\in\mathbb Z_{\geq0}}とする。反復列の定義によりyk=xn−1+ky_k=x_{n-1+k}であり、y1=xny_1=x_nである。定理 2.2により(yk)(y_k)もx∗x^*に収束する。事前評価を(yk)(y_k)のk=1k=1に適用すると、

d(xn,x∗)=d(y1,x∗)≤q1−qd(y0,y1)=q1−qd(xn−1,xn)d(x_n,x^*) =d(y_1,x^*) \leq\frac{q}{1-q}d(y_0,y_1) =\frac{q}{1-q}d(x_{n-1},x_n)

を得る。▨

3 例

例 3.1 (一様な縮小比の必要性). 通常の距離を入れたR\mathbb R上でf(x)=x+1f(x)=x+1と定めると、任意のx,y∈Rx,y\in\mathbb Rに対して

∣f(x)−f(y)∣=∣x−y∣|f(x)-f(y)|=|x-y|

が成り立つ。しかし、f(x)=xf(x)=xを満たす実数は存在しない。したがって、縮小比としてq=1q=1を許すと、完備で空でない空間でも不動点の存在は従わない。

各点の対で距離が真に小さくなるという条件も、一様な縮小比の代わりにならない。X=[1,∞)X=[1,\infty)にR\mathbb Rからの制限距離を入れ、f(x)=x+1/xf(x)=x+1/xと定める。x∈Xx\in Xならばf(x)≥2f(x)\geq2であるから、f(X)⊆Xf(X)\subseteq Xである。XXはR\mathbb Rの閉部分集合であるため、§E2.5 定理 3.2により完備である。相異なるx,y∈Xx,y\in Xではxy>1xy>1であるから、

∣f(x)−f(y)∣=∣x−y∣(1−1xy)<∣x−y∣|f(x)-f(y)| =|x-y|\left(1-\frac1{xy}\right) <|x-y|

である。一方、任意のx∈Xx\in Xに対してf(x)>xf(x)>xであるから、ffは不動点をもたない。係数1−1/(xy)1-1/(xy)はx,yx,yを大きくすると11に近づくため、すべての点の対に共通するq<1q<1は存在しない。

例 3.2 (完備性と非空性の必要性).X=(0,1]X=(0,1]にR\mathbb Rからの制限距離を入れ、f(x)=x/2f(x)=x/2と定める。0<x≤10<x\leq1ならば0<x/2≤1/20<x/2\leq1/2であるから、f(X)⊆Xf(X)\subseteq Xである。§E2.5 例 6.2によりXXは完備でない。写像ffは縮小比1/21/2の縮小写像であるが、不動点方程式x/2=xx/2=xの解x=0x=0はXXに属さない。したがって、完備性を外すと不動点の存在は従わない。

空距離空間X=∅X=\emptyset上の空写像f:X→Xf:X\to Xは、任意のx,y∈Xx,y\in Xに関する縮小不等式を満たし、XXは完備である。しかし、XXには不動点が存在しない。したがって、空間が空でないという仮定も必要である。

例 3.3 (反復列と誤差評価). 通常の距離を入れたR\mathbb R上でf(x)=x/2+1f(x)=x/2+1と定める。写像ffは縮小比q=1/2q=1/2の縮小写像であり、不動点方程式x=x/2+1x=x/2+1の解はx∗=2x^*=2である。

x0=0x_0=0から始まる反復列では、x1=1x_1=1、x2=3/2x_2=3/2、x3=7/4x_3=7/4である。数学的帰納法により

xn=2−21−nx_n=2-2^{1-n}

が成り立つため、実際の誤差はd(xn,x∗)=21−nd(x_n,x^*)=2^{1-n}である。

d(x0,x1)=1d(x_0,x_1)=1であるから、系 2.3で得た事前評価は

d(xn,x∗)≤(1/2)n1−1/2=21−nd(x_n,x^*)\leq\frac{(1/2)^n}{1-1/2}=2^{1-n}

を与える。また、n≥1n\geq1ではd(xn−1,xn)=21−nd(x_{n-1},x_n)=2^{1-n}であるから、事後評価は

d(xn,x∗)≤1/21−1/221−n=21−nd(x_n,x^*)\leq\frac{1/2}{1-1/2}2^{1-n}=2^{1-n}

を与える。この反復列では、二つの評価がいずれも実際の誤差と一致する。

4 演習

問題 4.1 (反復と事前評価).X=[0,1]X=[0,1]にR\mathbb Rからの制限距離を入れ、f(x)=x/3+1/3f(x)=x/3+1/3と定める。ffが縮小写像であることを示し、不動点x∗x^*を求めよ。さらに、x0=0x_0=0から始まる反復列について、d(x2,x∗)d(x_2,x^*)の実際の値と事前評価を比較せよ。

解答.

0≤x≤10\leq x\leq1ならば1/3≤f(x)≤2/31/3\leq f(x)\leq2/3であるから、f(X)⊆Xf(X)\subseteq Xである。任意のx,y∈Xx,y\in Xに対して

∣f(x)−f(y)∣=13∣x−y∣|f(x)-f(y)|=\frac13|x-y|

であるため、ffは縮小比q=1/3q=1/3の縮小写像である。不動点方程式x=x/3+1/3x=x/3+1/3の解はx∗=1/2x^*=1/2である。

x1=1/3x_1=1/3、x2=4/9x_2=4/9であるから、実際の誤差は

d(x2,x∗)=∣49−12∣=118d(x_2,x^*)=\left|\frac49-\frac12\right|=\frac1{18}

である。一方、d(x0,x1)=1/3d(x_0,x_1)=1/3であるから、事前評価は

(1/3)21−1/3⋅13=118\frac{(1/3)^2}{1-1/3}\cdot\frac13=\frac1{18}

を与える。この場合には、事前評価の上界が実際の誤差と一致する。▨

参考文献

  1. Stefan Banach, Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales, Fundamenta Mathematicae 3 (1922), 133–181.Banach の不動点定理を参考にした。
  2. 松坂和夫『集合・位相入門』新装版, 岩波書店, 2018.完備距離空間と縮小写像の標準的な扱いを参考にした。
  3. Stephen Willard, General Topology, Dover Publications, 2004, originally published 1970.完備性と不動点定理の位相空間論における位置づけを参考にした。

前提記事