何回まわせば足りるか - 反復の回数を先に見積もる

縮小写像を反復すれば不動点に近づく。では何回まわせば、小数第 $6$ 位まで合うのか^[2]。

答えは回す前に出せる。縮む比 $k$ と、最初の $1$ 歩の幅だけで決まる。

見積もりを立ててから実際に回し、どれだけ余裕があったかを確かめる。

誤差の評価を作る

$d(f(x),f(y))\le kd(x,y)$、$0\le k<1$ とする^[1]。

$1$ 歩ずつの幅は等比数列でおさえられる。

$$d(x_{n+1},x_n)\le kd(x_n,x_{n-1})\le \cdots \le k^{n}d(x_1,x_0)$$

不動点までの距離は、そこから先の幅を全部足したものより小さい。

$$\begin{array}{rl}d(x_n,x^{\ast })& \le \sum _{j\ge n}d(x_{j+1},x_j)\\ & \le \frac{k^n}{1-k}d(x_1,x_0)\end{array}$$

回す前に分かるので、事前評価と呼ばれる。$k$ と最初の $1$ 歩だけで書けている。

途中まで回したあとなら、もっと締まった形が使える。

$$d(x_n,x^{\ast })\le \frac{k}{1-k}d(x_n,x_{n-1})$$

こちらは事後評価である。実際に縮んだ幅を見るので、見積もりが現実に寄る。

題材を決める

$f(x)=\cos x$ を $[0,1]$ でとる。不動点は $\cos x=x$ の解である^[3]。

縮む比は導関数の最大値から出る。$|f^{\prime }(x)|=|\sin x|$ で、$[0,1]$ での最大は $\sin 1$ である。

$$k=\sin 1=0.841471$$

$1$ に近い。あまり縮まない写像だと分かる。

出発点を $x_0=0.5$ とすると $x_1=\cos 0.5=0.877583$ で、最初の $1$ 歩は $0.377583$ である。

必要な回数を出す

小数第 $6$ 位、つまり誤差 $10^{-6}$ を目標にする。事前評価の式に入れる。

$$\frac{k^n}{1-k}\times 0.377583<10^{-6}$$

$1-k=0.158529$ なので、$k^n<4.1985\times 10^{-7}$ が条件になる。

両辺の対数をとる。$\log$ の底は何でもよい。

$$n>\frac{\ln (4.1985\times 10^{-7})}{\ln 0.841471}=\frac{-14.683}{-0.172538}=85.1$$

$86$ 回である。回す前に、必要な回数が決まった。

実際に回してみる

$x_0=0.5$ から順に計算する。値は $2$ 回ごとに拾う。

不動点は $0.739085$ である^[3]。誤差が $2$ 回ごとに $0.454$ 倍になっている。

$1$ 回あたりでは $0.674$ 倍である。これは不動点での傾き $|\sin 0.739085|=0.6736$ に一致する。

$0.674$ の比で $10^{-6}$ まで縮めるなら、必要なのは $32$ 回ほどになる。

$$n>\frac{\ln (4.183\times 10^{-6})}{\ln 0.673612}=31.4$$

見積もりの $86$ 回に対し、実際は $32$ 回で足りた。$2.7$ 倍の余裕があったことになる。

差が出る理由

$k$ を区間全体での最大値からとったためである。$[0,1]$ の右端では傾きが $0.841$ だが、不動点の近くでは $0.674$ しかない。

反復はすぐ不動点の近くへ入るので、そこから先は小さいほうの比で縮む。事前評価は安全側に振れる。

事後評価を使うと差が縮まる。$6$ 回まわした時点で $d(x_6,x_5)=0.049$ なので、次の値が出る。

$$d(x_6,x^{\ast })\le \frac{0.841471}{0.158529}\times 0.049=0.260$$

実際の誤差 $0.0199$ に対してまだ $13$ 倍ゆるい。それでも事前評価よりは締まっている。

比が 1 に近づくと跳ねる

$k$ を変えて、必要な回数を並べる。目標は同じ $10^{-6}$、最初の $1$ 歩も $0.3776$ とする。

$k$ が $1$ に近づくと回数が跳ね上がる。$0.9$ から $0.99$ へ動かしただけで $12$ 倍になった。

分母の $\ln k$ が $0$ に近づくためである。$k=1-\epsilon$ なら $\ln k\approx -\epsilon$ で、回数は $\epsilon$ に反比例する。

ニュートン法と比べる

同じ方程式を別の反復で解く。$g(x)=x-\cos x$ の零点を探す形にする^[4]。

$$x_{n+1}=x_n-\frac{x_n-\cos x_n}{1+\sin x_n}$$

$x_0=0.5$ から回すと、$x_1=0.755222$、$x_2=0.739136$、$x_3=0.739085$ になる。

誤差を並べると $0.239$、$0.0161$、$0.000051$、$10^{-9}$ 程度である。

桁数が毎回およそ倍になっている。二次収束と呼ばれる速さで、縮小写像の一次収束とは別の型になる^[4]。

$3$ 回で $10^{-6}$ を越えた。$32$ 回と $3$ 回の差が、収束の型の差である。

どちらを選ぶか

ニュートン法が速いが、導関数が要る。零点の近くから始めないと外れることもある^[4]。

縮小写像の反復は遅いかわり、$k<1$ さえ言えればどこから始めても届く^[1]。しかも回数が先に読める。

作用素の方程式では導関数が作れない場面が多い。そのときは、遅くても確実な道を選ぶことになる。

回数の出し方を、比を変えてもう一度たどる。

よくある誤り

比を見積もり、回数を計算し、それから回す。この順番にすると、いつ止めてよいかが最初から分かる。

出典