不動点反復 | 微積分 | 天游ヶ丘数理学院

1 不動点と反復列

定義 1.1 (不動点反復). $I$ を開区間とし、 $f:I\to I$ を写像とする。 $f(\alpha)=\alpha$ を満たす $\alpha\in I$ を $f$ の不動点という。初期値 $x_0\in I$ を選び、

x_{n+1}=f(x_n)\qquad(n=0,1,2,\ldots)

によって定まる数列 $(x_n)$ を $f$ と $x_0$ による反復列という。

方程式を $x=f(x)$ の形に書き換えると、方程式の解は $f$ の不動点になります。ただし、反復列を作ることと、その反復列が収束することは別の問題です。

定理 1.2. $I$ を開区間とし、 $f:I\to I$ を写像とする。反復列 $x_{n+1}=f(x_n)$ が $\alpha\in I$ に収束し、 $f$ が $\alpha$ で連続ならば、 $f(\alpha)=\alpha$ である。

証明. 等式 $x_{n+1}=f(x_n)$ の両辺で $n\to\infty$ とする。 $(x_n)$ が $\alpha$ に収束するので $(x_{n+1})$ も $\alpha$ に収束し、 $f$ の $\alpha$ における連続性により $f(x_n)\to f(\alpha)$ となる。したがって $\alpha=f(\alpha)$ である。▨

例 1.3. $I=(-2,2)$ 、 $f(x)=\cos x$ とする。たとえば $x_0=1$ から反復すると

1,\quad 0.540302\ldots,\quad 0.857553\ldots,\quad 0.654290\ldots,\quad 0.793480\ldots,\ldots

となり、数値は $0.739085\ldots$ に近づく。この数値が反復列の極限であることが別に分かれば、定理 1.2により $\cos\alpha=\alpha$ を満たす。

次の図は、縦に $y=f(x)$ まで進み、横に $y=x$ まで進む操作を繰り返したものです。図から収束の様子を観察することはできますが、図だけではすべての反復が収束することを証明することはできません。

2 導関数による局所判定

不動点に近い点で、1回の反復が誤差をどの程度変えるかを差商から調べます。次の定理は不動点の近くに限った保証であり、遠い初期値に対する挙動までは決めません。

定理 2.1. $I$ を開区間とし、 $f:I\to I$ を写像とする。 $f(\alpha)=\alpha$ であり、 $f$ が $\alpha\in I$ で微分可能であるとする。

$|f'(\alpha)|<1$ ならば、 $\alpha$ のある近傍 $U\subset I$ が存在し、任意の $x_0\in U$ から始めた反復列は $U$ に留まり、 $\alpha$ に収束する。
$|f'(\alpha)|>1$ ならば、 $\alpha$ のある近傍 $U\subset I$ が存在し、任意の $x_0\in U\setminus\{\alpha\}$ から始めた反復列は $U$ に留まり続けることができず、有限回の反復で $U$ の外へ出る。

証明.

\lim_{x\to\alpha,\,x\ne\alpha} \left|\frac{f(x)-f(\alpha)}{x-\alpha}\right|=|f'(\alpha)|

である。

(1)を示す。 $|f'(\alpha)|<q<1$ を満たす実数 $q$ を取る。上の極限と $I$ が開区間であることから、ある $\delta>0$ が存在し、 $U=(\alpha-\delta,\alpha+\delta)\subset I$ であり、 $x\in U$ ならば

|f(x)-\alpha|\leq q|x-\alpha|

となる。したがって $x\in U$ ならば $f(x)\in U$ である。任意の $x_0\in U$ に対して帰納的に $x_n\in U$ であり、

|x_n-\alpha|\leq q^n|x_0-\alpha|

となる。 $q^n\to0$ であるから $x_n\to\alpha$ である。

(2)を示す。 $1<q<|f'(\alpha)|$ を満たす実数 $q$ を取る。上の極限と $I$ が開区間であることから、ある $\delta>0$ が存在し、 $U=(\alpha-\delta,\alpha+\delta)\subset I$ であり、 $x\in U\setminus\{\alpha\}$ ならば

|f(x)-\alpha|\geq q|x-\alpha|>0

となる。 $x_0\in U\setminus\{\alpha\}$ から始めた反復列が $U$ に留まり続けると仮定すると、各 $n$ で $x_n\ne\alpha$ であり、

|x_n-\alpha|\geq q^n|x_0-\alpha|

となる。右辺は $n\to\infty$ で限りなく大きくなるが、 $x_n\in U$ ならば $|x_n-\alpha|<\delta$ である。この二つは両立しない。したがって反復列は有限回で $U$ の外へ出る。▨

注意 2.2. $|f'(\alpha)|=1$ の場合、定理 2.1は結論を与えない。たとえば $f(x)=x-x^3$ は $I=(-1,1)$ の自己写像であり、 $f'(0)=1$ である。 $0<|x|<1$ ならば $f(x)$ は $x$ と同符号で $|f(x)|=|x|(1-x^2)<|x|$ なので、 $y_n=|x_n|$ は減少して極限 $L\geq0$ をもつ。反復式から $y_{n+1}=y_n(1-y_n^2)$ であり、極限を取ると $L=L(1-L^2)$ となるため $L=0$ である。したがって反復列は $0$ に収束する。一方、 $f(x)=-x$ は $\mathbb R$ の自己写像であり、 $f'(0)=-1$ であるが、 $x_0\ne0$ ならば $x_0,-x_0,x_0,-x_0,\ldots$ という2周期になる。

例 2.3. $f(x)=x^3$ は $\mathbb R$ の自己写像であり、 $0$ は $f'(0)=0$ を満たす不動点である。したがって定理 2.1 (1)により、 $0$ に十分近い初期値から始めた反復列は $0$ に収束する。しかし $x_0=2$ ならば

2,\quad8,\quad512,\quad512^3,\ldots

となり、 $0$ には収束しない。導関数による判定は遠い初期値の挙動を保証しない。

3 同じ方程式の二つの反復

$x^2=5$ は、 $x=5/x$ とも $x=(x+5/x)/2$ とも書き換えることができます。二つの自己写像を正の区間で比較します。

例 3.1. $h:(0,\infty)\to(0,\infty)$ を $h(x)=5/x$ とする。 $x_0>0$ 、 $x_0\ne\sqrt5$ ならば

x_1=\frac5{x_0},\qquad x_2=\frac5{x_1}=x_0

であり、 $x_0$ と $x_1$ は異なる。したがって反復列は2周期であり、収束しない。

$g:(0,\infty)\to(0,\infty)$ を

g(x)=\frac12\left(x+\frac5x\right)

とする。任意の $x>0$ に対して

g(x)-\sqrt5=\frac{(x-\sqrt5)^2}{2x}

が成り立つ。 $g$ による反復列では、誤差 $e_n=x_n-\sqrt5$ が

e_{n+1}=\frac{e_n^2}{2x_n}

を満たす。

証明. $h(h(x))=5/(5/x)=x$ である。 $h(x_0)=x_0$ ならば $x_0^2=5$ となり、 $x_0>0$ から $x_0=\sqrt5$ となるため、仮定した $x_0\ne\sqrt5$ では $x_0$ と $x_1$ は異なる。

$g$ については

g(x)-\sqrt5 =\frac{x^2+5-2\sqrt5x}{2x} =\frac{(x-\sqrt5)^2}{2x}

となる。この恒等式に $x=x_n$ を代入すると誤差の等式を得る。

さらに相加平均と相乗平均の関係により $g(x)\geq\sqrt5$ である。 $x\geq\sqrt5$ ならば

g(x)-x=\frac{5-x^2}{2x}\leq0

であるから、 $(x_n)_{n\geq1}$ は $\sqrt5$ 以上に留まる単調減少数列である。したがって極限 $L>0$ が存在し、定理 1.2により $L=g(L)$ である。よって $L^2=5$ であり、 $L=\sqrt5$ となる。また $x_n\geq\sqrt5$ なので

0\leq e_{n+1}\leq\frac{e_n^2}{2\sqrt5}\qquad(n\geq1)

である。この具体的な二次誤差評価は上の恒等式から従う。▨

導関数を計算すると $g'(\sqrt5)=0$ ですが、この等式だけから一般の反復法が二次収束するとはいえません。ここで得た二次誤差評価は、 $g$ に固有の恒等式によるものです。

閑話休題：縮小写像と地図 地図上の点を実際の床の点へ対応させる操作を、床全体から床全体への写像とみなす。写像が床上の任意の2点間の距離を同じ比 $q<1$ 以下に縮め、床を完備距離空間として扱うことができるならば、地図と実際の位置が一致する点がただ一つ存在し、どの点から反復してもその点へ収束する。

一般には、空でない完備距離空間 $(X,d)$ の自己写像 $T:X\to X$ と一様な定数 $0\leq q<1$ が、すべての $x,y\in X$ に対して

d(Tx,Ty)\leq qd(x,y)

を満たすとき、§E2.7 定理 2.2 (Banach の不動点定理)が不動点の一意性と任意の初期値からの収束を保証する。自己写像であること、空間が完備であること、および一様な縮小比があることのいずれかを外した地図には、この結論をそのまま用いることはできない。

注意 3.2.定理 2.1は不動点の近傍における判定であり、遠い初期値からの収束、別の不動点への収束、周期的な挙動または一般の収束率を決めない。一般の誤差評価、停止条件および Newton 法の二次収束には、この記事で扱った局所判定とは別の仮定が必要である。

4 反復を調べるときの確認

反復を始める前に、選んだ関数が初期値を含む区間をその区間自身へ写すかを確かめます。
数列の数項を計算し、収束、別の不動点への移動、または周期的な挙動を区別します。数値の観察だけで収束を結論せず、保証に必要な仮定を確かめます。
導関数による判定を用いるときは、不動点における $|f'(\alpha)|$ と $1$ を比較します。 $|f'(\alpha)|=1$ の場合と遠い初期値の場合には、この判定だけでは結論しません。

§C1.8不動点反復

1 不動点と反復列

2 導関数による局所判定

3 同じ方程式の二つの反復

4 反復を調べるときの確認

例題

演習

前提記事