SICP: Exercise 1.35
問題 1.35
（1.2.2 節の）黄金比 \( \phi \) が変換 \( x \mapsto 1 + \frac{1}{x} \) の不動点であることを示し、この事実を使い
fixed-point手続きにより \( \phi \) を計算せよ。
\( f(x) = x \) となる \( x \) を関数 \( f \) の不動点という。グラフを考えると、不動点において $$ \begin{cases} y = f(x) \\ y = x \end{cases} $$ と書けるから、これはグラフ \( y = f(x) \) と直線 \( y = x \) の交点である。また、 $$ f(x),\,f(f(x)),\,f(f(f(x))),\,\cdots $$ と \( f \) を繰り返し作用させていけば不動点 \( x_0 \) に収束していくとき、\( x_0 \) を吸引的不動点というらしい。
方程式の解の探索を不動点探索によって行える場合がある。方程式を変形して \( x = f(x) \) と書くことができ、\( f(x) \) が吸引的不動点を持つならば、不動点探索によって解 \( x \) を求めることができる。
さて、これを黄金比 \( \phi \) を求めるのに利用してみる。1.2.2 節より \( \phi^2 = \phi + 1 \) だったから、両辺を \( \phi \) で割って $$ \phi = 1 + \frac{1}{\phi} $$ したがって、\( f(x) = 1 + \frac{1}{x} \)、つまり \( x \mapsto 1 + \frac{1}{x} \) とおけば \( \phi \) はその不動点である。
実際に計算してみると
;; 不動点探索で求めた黄金比 (define golden-ratio-as-fixed-point (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)) 1.6180327868852458 ;; 正確な黄金比 (define accurate-golden-ratio (/ (+ 1 (sqrt 5)) 2.0)) 1.618033988749895 ;; 誤差 (- golden-ratio-as-fixed-point accurate-golden-ratio) -1.2018646491362972e-6
そこそこの精度で求められている。
黄金比に収束することの証明
詳しい話が Amaca, Edgar Gilbuena, "On rational functions with Golden Ratio as fixed point" (2008). Thesis. Rochester Institute of Technology. に載っていた。問題 1.13 とこの論文を参考にして、上記の関数を繰り返し作用させれば黄金比に収束することが理解できた。
本文の平方根の計算と同様に、上記の \( f \) を \( x \) に \( n \) 回作用させた結果を \( y_n \) と書くことにする。まず、\( n \) が小さいときの \( y_n \) を簡単な分数で表してみる。 \begin{align*} y_1 &= 1 + \frac{1}{x} = \frac{x + 1}{x} \\ y_2 &= 1 + \frac{1}{\displaystyle 1 + \frac{1}{x}} = 1 + \frac{1}{\displaystyle \frac{x + 1}{x}} = 1 + \frac{x}{x + 1} = \frac{2x + 1}{x + 1} \\ y_3 &= 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{x}}} = 1 + \frac{1}{\displaystyle \frac{2x + 1}{x + 1}} = 1 + \frac{x + 1}{2x + 1} = \frac{3x + 2}{2x + 1} \\ y_4 &= 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{x}}}} = 1 + \frac{1}{\displaystyle \frac{3x + 2}{2x + 1}} = 1 + \frac{2x + 1}{3x + 2} = \frac{5x + 3}{3x + 2} \\ y_5 &= 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{x}}}}} = 1 + \frac{1}{\displaystyle \frac{5x + 3}{3x + 2}} = 1 + \frac{3x + 2}{5x + 3} = \frac{8x + 5}{5x + 3} \end{align*}
この辺りまで出してみれば十分だろう。フィボナッチ数を \( F_n \) として、すべての自然数 \( n \) に対して以下が成り立つことが予想できる。 $$ y_n = \frac{F_{n + 1} x + F_n}{F_n x + F_{n - 1}} $$ ただし、 $$ \begin{cases} F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n - 1} + F_{n - 2} \quad (n \geq 2) \end{cases} $$ である。
予想が正しいことを数学的帰納法で示す。
\( n = 1 \) のときは成立している。\( n = k \) のときに成立する、すなわち $$ y_k = \frac{F_{k + 1} x + F_k}{F_k x + F_{k - 1}} $$ であると仮定する。このとき $$ \begin{align*} y_{k + 1} &= 1 + \frac{1}{y_k} = 1 + \frac{F_k x + F_{k - 1}}{F_{k + 1} x + F_k} = \frac{(F_{k + 1} + F_k)x + (F_k + F_{k - 1})}{F_{k + 1} x + F_k} \\ &= \frac{F_{k + 2} x + F_{k + 1}}{F_{k + 1} x + F_k} \end{align*} $$ であるから、仮定の下では \( n = k + 1 \) でも成立する。以上から、すべての自然数 \( n \) に対して $$ y_n = \frac{F_{n + 1} x + F_n}{F_n x + F_{n - 1}} $$ が成立することが示された。
次に $$ \lim_{n \to \infty} y_n = \phi $$ を示す。
問題 1.13 より $$ F_n = \frac{\phi^n - \psi^n}{\sqrt{5}} \quad \left( \phi = \frac{1 + \sqrt{5}}{2}, \, \psi = \frac{1 - \sqrt{5}}{2} \right) $$ であった。
まず、以下の極限を求める。 $$ \lim_{n \to \infty} \frac{F_{n + 1}}{F_n} = \lim_{n \to \infty} \frac{\displaystyle \frac{\phi^{n + 1} - \psi^{n + 1}}{\sqrt{5}}}{\displaystyle \frac{\phi^n - \psi^n}{\sqrt{5}}} = \lim_{n \to \infty} \frac{\phi^{n + 1} - \psi^{n + 1}}{\phi^n - \psi^n} $$ \( \psi \) について $$ -1 = \frac{1 - \sqrt{9}}{2} < \frac{1 - \sqrt{5}}{2} = \psi < 0 \quad \therefore\ |\psi| < 1 $$ したがって \( \lim_{n \to \infty} \psi^n = 0 \) であるから $$ \begin{align*} \lim_{n \to \infty} \frac{F_{n + 1}}{F_n} &= \frac{\displaystyle \lim_{n \to \infty} \phi^{n + 1} - \lim_{n \to \infty} \psi^{n + 1}}{\displaystyle \lim_{n \to \infty} \phi^n - \lim_{n \to \infty} \psi^n} = \frac{\displaystyle \lim_{n \to \infty} \phi^{n + 1} - 0}{\displaystyle \lim_{n \to \infty} \phi^n - 0} = \frac{\displaystyle \lim_{n \to \infty} \phi^{n + 1}}{\displaystyle \lim_{n \to \infty} \phi^n} \\ &= \lim_{n \to \infty} \frac{\phi^{n + 1}}{\phi^n} = \lim_{n \to \infty} \phi = \phi \end{align*} $$
これを利用すると $$ \begin{align*} \lim_{n \to \infty} y_n &= \lim_{n \to \infty} \frac{F_{n + 1} x + F_n}{F_n x + F_{n - 1}} = \lim_{n \to \infty} \frac{F_{n + 1} x + F_n}{F_n x + F_{n - 1}} \cdot \frac{\displaystyle \frac{1}{F_n}}{\displaystyle \frac{1}{F_n}} = \lim_{n \to \infty} \frac{\displaystyle \frac{F_{n + 1}}{F_n} x + 1}{\displaystyle x + \frac{F_{n - 1}}{F_n}} \\ &= \frac{\phi x + 1}{\displaystyle x + \frac{1}{\phi}} = \frac{\phi (\phi x + 1)}{\phi x + 1} = \phi \end{align*} $$
よって、\( \phi \) は関数 \( f(x) = 1 + \frac{1}{x} \) の吸引的不動点である。
