黄金比
近似値の話の続きです。
以下は、黄金比こと(1+√5)/2の近似値の、分母500までのランキング
分母と分子に同じ値が何度も出てくるのは、フィボナッチ数列というのが関係しています。
フィボナッチ数列は、n番目の項をF[n]とした場合にF[n]+F[n+1]=F[n+2]となる数列で、lim(n→∞)F[n+1]/F[n} = φ(黄金比)という特徴があります。証明はWikipediaとか見てください。
となると、「黄金比の近似値を探す最も良い方法は、フィボナッチ数を何度か計算してF[n+1]/F[n]とすることである」という仮説が立つので、今回はこれを考えてみました。
F[n+1]/F[n]とφとの差をd[n], F[n+1]/F[n]=Fとすると、
d[n] = | φ - F[n+1]/F[n] |
d[n+1] = | φ - F[n+2]/F[n+1] |
= | φ - (F[n+1] + F[n] ) / F[n+1 |
= | φ - 1 - F[n]/F[n+1] |
= | 1/φ - 1/F | (φ-1 = 1/φ)
= | (φ-F) / φF |
= d[n] / φF (1<φ,1<F)
以上より、d[n]はnが大きくなる毎に必ず小さくなる、単調減少というやつです。F[n+1]/F[n]を最適近似だと思ってたら1個前のF[n]/F[n-1]の方が良かった、ということはありません。
次に、x[n]を d[n] = x[n]/F[n] とします。これは、φをF[n+1]/F[n]で近似した際の誤差がどれくらいあるかを分子の差で示したもので、0.5を超えていれば他にもっとφに近くなる分子が存在するということです。
d[n+1] = d[n] / φF なので、
x[n+1]/F[n+1] = x[n]/F[n] * F[n]/F[n+1] * 1/φ
x[n+1] = x[n]/φ
x[n]も単調減少でした。つまり、F[n+1]/F[n]と最適近似の誤差はnを大きくする毎に小さくなり、最終的には常に分母に対して最適な分子を出せるようになるということです。
なお、上記の計算ではフィボナッチ数列の初期値を限定してません。通常の数列は最初の2項が0,1ですが、これを変えて1,3,4,7,11,...の様に構成しても同じことが言えます。