ポタージュを垂れ流す。

マイペースこうしん

ルート2の近似

はじめに

twitterみてたら某青色予備校の模試の問題が回ってきたわけで、

x_1=3y_1=5x_{n+1}=3x_n+2y_n+1y_{n+1}=4x_n+3y_n+2(n=1,2,3,......)により数列{x_n}{y_n}を定義する.
(1)すべての自然数nについて,n<x_n<y_nが成り立つことを示せ.
(2)すべての自然数nについて,y_n^2=2x_n^2+2x_n+1が成り立つことを示せ.
(3) \displaystyle \lim_{n \to \infty}\frac{y_n}{x_n}の値を求めよ.
(4) (3)で求めた値を\alphaとするとき,
\displaystyle \left| \frac{y_n^2}{x_n^2} - \alpha ^2 \right| < \frac{1}{100}ならば\displaystyle \left| \left( \frac{2x_n+1}{y_n} \right) ^2 - \alpha^2 \right|< \frac{1}{80000} であることを示せ.

初めてみたとき80000とかいうのと比較するのヤバwとか思って面白かったので友人に問題投げたら「これペル方程式とかニュートン法とかそういう系の話じゃね」って言われて、まあ考察タイムに入ったというわけですね!ってほとんど友人がやったことをまとめてるだけなんですけどネw

考察してみた

(1)はどうでもいいや()
(2)(3)について。ペル方程式X^2-2Y^2=-1を考えると、(X,Y)=(2x_n+1,y_n)を代入して整理すると、(2)で示す等式になるのでこれらは解になっています。ここで、(X,Y)が十分大きいときを考えると、比\displaystyle \frac{X}{Y}\sqrt{2}に近づいていきます。また、\displaystyle \frac{y_n}{x_n}\sqrt{2}に近づいていきます。
そこで(4)では、これらのうち、どっちの収束が早いか調べてるって感じみたいですね。

と、ここで、折角なのでpythonなんかを使って実際に計算をやってみました!って結果が下の表ですねー

n x_n y_n \displaystyle \frac{y_n}{x_n} \displaystyle \frac{2x_n+1}{y_n}
1 3 5 1.6666666666666667 1.6
2 20 29 1.45 1.4482758620689655
3 119 169 1.4201680672268908 1.4201183431952662
4 696 985 1.4152298850574712 1.4152284263959392
5 4059 5741 1.4143877802414389 1.4143877373279916
6 23660 33461 1.4142434488588336 1.4142434475957084
7 137903 195025 1.4142186899487321 1.4142186899115499
8 803760 1136689 1.4142144421220264 1.414214442120932
9 4684659 6625109 1.414213713314032 1.4142137133139998
10 27304196 38613965 1.414213588270462 1.4142135882704612
11 159140519 225058681 1.4142135668163807 1.4142135668163807
12 927538920 1311738121 1.4142135631354424 1.4142135631354424
13 5406093003 7645370045 1.4142135625038932 1.4142135625038932
14 31509019100 44560482149 1.4142135623955365 1.4142135623955365
15 183648021599 259717522849 1.4142135623769454 1.4142135623769454
16 1070379110496 1513744654945 1.4142135623737557 1.4142135623737557
17 6238626641379 8822750406821 1.4142135623732084 1.4142135623732084
18 36361380737780 51422757785981 1.4142135623731145 1.4142135623731145
19 211929657785303 299713796309065 1.4142135623730985 1.4142135623730985
20 1235216565974040 1746860020068409 1.4142135623730956 1.4142135623730956

\sqrt{2}=1.41421356237309504...

これを見ると確かに右のほうが収束が早そうですね。n=10からもう違いがわかんないんで差をとったやつも下に載せて見ました

n \displaystyle ‖ \frac{y_n}{x_n}-\sqrt{2} ‖ \displaystyle ‖ \frac{2x_n+1}{y_n} - \sqrt{2} ‖
1 0.2524531042935716 0.014213562373095234
2 0.03578643762690481 0.00042045892481934466
3 0.005954504853795672 1.2378941142587863×10^{-5}
4 0.0010163226843760143 3.644035520000699×10^{-7}
5 0.00017421786834370678 1.0727040367086715×10^{-8}
6 2.9886485738428448×10^{-5} 3.157747396898003×10^{-10}
7 5.127575636976189×10^{-6} 9.29567534058151×10^{-12}
8 8.797489312595275×10^{-7} 2.737809978725636×10^{-13}
9 1.509409368605219×10^{-7} 8.215650382226158×10^{-15}
10 2.589736691760436×10^{-8} 4.440892098500626×10^{-16}
11 4.443285517297113×10^{-9} <10^{-16}
12 7.623472964013445×10^{-10} <10^{-16}
13 1.307980390663488×10^{-10} <10^{-16}
14 2.244138208595814×10^{-11} <10^{-16}
15 3.850253449400043×10^{-12} <10^{-16}
16 6.605826996519681×10^{-13} <10^{-16}
17 1.1324274851176597×10^{-13} <10^{-16}
18 1.9317880628477724×10^{-14} <10^{-16}
19 3.3306690738754696×10^{-15} <10^{-16}
20 4.440892098500626×10^{-16} <10^{-16}

こっちだとわかりやすいですね!右のほうが収束がめっちゃ早い。途中から計算結果が0になって表示されなくなっちゃったし。
ここで32桁とかで出せないかなって調べて見たらpythonの構造上16桁以上になると正確な値にならないらしい......残念。