縮小写像と漸化式

$a_0=0$、$a_{n+1}=\sqrt{a_n+2}$ とする。次の値は数値計算による（以下切り捨て）。

$2$ との差は、1 回ごとにおよそ $\frac14$ 倍になっている。

$a_0=2$、$a_{n+1}=1+\frac1{a_n}$ とすると
$$ a_1=1+\frac12=\frac32,\quad a_2=1+\frac23=\frac53,\quad a_3=1+\frac35=\frac85,\quad a_4=1+\frac58=\frac{13}8,\quad a_5=\frac{21}{13} $$
であり、小数では $1.5$、$1.666\ldots$、$1.6$、$1.625$、$1.615\ldots$ と、増えたり減ったりしながら $1.618\ldots$ に近づく。極限の候補は $\alpha=1+\frac1\alpha$、すなわち $\alpha^2-\alpha-1=0$ の正の解 $\alpha=\frac{1+\sqrt5}2=1.6180\ldots$（黄金比）である。分子と分母には Fibonacci 数 $1,2,3,5,8,13,21,\dots$ が並んでいる。

1. $f(x)=\sqrt{x+2}$、$I=[0,2]$。$f$ は増加関数で $f(0)=\sqrt2=1.414\ldots$、$f(2)=2$ なので、$f(I)=[\sqrt2,2]\subset I$ である。$f'(x)=\frac1{2\sqrt{x+2}}$ は $x\ge0$ で $\frac1{2\sqrt2}=0.3535\ldots$ 以下なので、$k=\frac1{2\sqrt2}$ の縮小写像である。不動点は $\sqrt{\alpha+2}=\alpha$ から $\alpha=2$。
2. $f(x)=1+\frac1x$、$I=\bigl[\frac32,2\bigr]$。$f$ は減少関数で $f\bigl(\frac32\bigr)=\frac53$、$f(2)=\frac32$ なので、$f(I)=\bigl[\frac32,\frac53\bigr]\subset I$ である。$|f'(x)|=\frac1{x^2}\le\frac1{(3/2)^2}=\frac49$ なので、$k=\frac49$ の縮小写像である。不動点は $\alpha=\frac{1+\sqrt5}2$。
3. $f(x)=\cos x$、$I=[0,1]$。$f$ は $[0,1]$ で減少し、$f(0)=1$、$f(1)=\cos1=0.5403\ldots$ なので $f(I)=[\cos1,1]\subset I$ である。$|f'(x)|=\sin x\le\sin1=0.8414\ldots$ なので、$k=\sin1$ の縮小写像である。

1. $a_{n+1}=\sqrt{a_n+2}$、$a_0=0$：$k=\frac1{2\sqrt2}$、$|a_0-\alpha|=2$ なので $|a_n-2|\le2\bigl(\frac1{2\sqrt2}\bigr)^n$ である。$n=4$ では右辺は $2\cdot\frac1{64}=0.03125$ で、実際の差 $2-a_4=0.0096\ldots$（ex-cmr-sqrt-values）はその範囲に入っている。
2. $a_{n+1}=1+\frac1{a_n}$、$a_0=2$：$k=\frac49$、$|a_0-\alpha|=2-\alpha=0.3819\ldots$ なので、$n=4$ で $|a_4-\alpha|\le\bigl(\frac49\bigr)^4\cdot0.3819\ldots=0.0149\ldots$ である。実際は $|a_4-\alpha|=|1.625-1.6180\ldots|=0.0069\ldots$ である（数値計算）。
3. $a_{n+1}=\cos a_n$、$a_0=1$：$\alpha=0.739085\ldots$（数値計算）、$k=\sin1$ なので $|a_n-\alpha|\le(\sin1)^n(1-\alpha)$ である。$n=10$ では右辺は $0.0464\ldots$、実際の差は $a_{10}-\alpha=0.7442\ldots-0.7390\ldots=0.0051\ldots$ である。

$a_{n+1}=\cos a_n$、$a_0=1$ で、誤差を $0.001$ 未満にしたいとする。$a_1=\cos1=0.5403\ldots$ なので $|a_1-a_0|=0.4596\ldots$、$k=\sin1=0.8414\ldots$ である。prop-cmr-a-posteriori の右辺 $\frac{k^n}{1-k}\cdot0.4596\ldots$ が $0.001$ 未満になる最小の $n$ は $n=47$ である（数値計算）。よって $a_{47}$ は、$\alpha$ の値を知らなくても誤差 $0.001$ 未満と保証される。
実際には $n=15$ で誤差は $0.001$ 未満になっている（数値計算）。評価 $k=\sin1$ は区間の端 $x=1$ での値で、$\alpha$ の近くでは $|f'(\alpha)|=\sin\alpha=0.673\ldots$ とより小さいため、保証は控えめになる。保証が控えめでも、「確実にこれ以下」と言えることに価値がある。

$f(x)=2x-1$ の不動点は $\alpha=1$ である。しかし $a_0=1.1$ から始めると
$$ a_1=1.2,\quad a_2=1.4,\quad a_3=1.8,\quad a_4=2.6,\quad a_5=4.2 $$
と $1$ から離れていく。$a_{n+1}-1=2(a_n-1)$ なので、差は 1 回ごとに 2 倍になる。$|f'|=2>1$ で、縮小写像でない。

$f(x)=\frac x2+1$ を $I=[0,1]$ で考える。$|f'|=\frac12<1$ だが、$f(1)=1.5$ は $I$ の外にある。不動点は $\frac\alpha2+1=\alpha$ から $\alpha=2$ で、やはり $I$ の外である。$a_0=0$ から始めると $1,\ 1.5,\ 1.75,\ 1.875,\dots$ と $I$ を出て $2$ に近づく。thm-cmr-contraction の証明の段 1 で使った $\varphi(q)\le0$（$q=1$ では $\varphi(1)=0.5>0$）が成り立たない。

$f(x)=\frac x2$ を、左端 $0$ を含まない区間 $I=(0,1]$ で考える。$0< x\le1$ なら $0<\frac x2\le\frac12$ なので、$f(I)=\bigl(0,\frac12\bigr]\subset I$ であり、$f$ は $I$ を $I$ に写す。また $|f(x)-f(y)|=\frac12|x-y|$ なので、$k=\frac12$ の縮小写像である。
ところが $f(x)=x$ とすると $\frac x2=x$ から $x=0$ であり、$0$ は $I$ に入っていないので、$f$ は $I$ の中に不動点をもたない。$a_0=1$ から始めると $a_1=\frac12$、$a_2=\frac14$、$a_3=\frac18$、…、$a_n=\frac1{2^n}$ であり、数列はすべて $I$ の中にあるが、近づく先の $0$ は $I$ の外である。
thm-cmr-contraction の証明の段 1 では、左端 $p$ が $I$ に入っていることを使って $\varphi(p)=f(p)-p\ge0$ としていた。この例では左端 $0$ が $I$ にないので、この段が使えない。

$f(x)=x+\frac1x$ を $I=[1,\infty)$ で考える。$x\ge1$ なら $f(x)\ge1$ なので $f$ は $I$ を $I$ に写し、$f'(x)=1-\frac1{x^2}$ は $0\le f'(x)<1$ を満たす。しかし $f(x)=x$ とすると $\frac1x=0$ となり、不動点はない。実際 $a_0=1$ から $2,\ 2.5,\ 2.9,\ 3.24\ldots,\ 3.55\ldots$ と増え続ける（数値計算）。
$f'(x)<1$ ではあっても、$x$ を大きくすると $f'(x)$ は $1$ にいくらでも近づくので、区間全体で使える 1 つの $k<1$ がとれない。また $I=[1,\infty)$ は端を含むが有界でなく、$[p,q]$ の形の区間ではない。thm-cmr-contraction の仮定「ある $k<1$ で縮小写像」「有界な閉区間 $[p,q]$」がどちらも満たされていない。
どちらか一方だけを外しても、この現象は起こらない。有界な閉区間 $[p,q]$ なら、thm-cmr-contraction の証明の段 1 は $k$ を使っていないので、$f$ が連続で $I$ を $I$ に写しさえすれば不動点は存在する。逆に、$[1,\infty)$ のように端を含むが有界でない区間でも、1 つの $k<1$ がとれれば不動点は存在する（Banachの不動点定理。本記事では証明しない）。この例で不動点がないのは、区間が有界でないうえに、1 つの $k<1$ がとれないからである。