その始めの方. まずx1=√N=q1+1/x2とおく. 但し, q1はNの平方根の最大整数. 同様にx2=(√N+P2)/Q2=q2+1/x3のようにする. (ははぁ. TAOCPの連分数展開のUとVがPとQになっているわけだ.)
順に進んで, xn=(√N+Pn)/Qn=qn+1/xn+1になるというまでは明快だが, その後に
「従って
Pn=qn-1Qn-1-Pn-1,
Qn=qn-1(Pn-1-Pn)+Qn-2
がexpediouslyに得られる」
と書いてある.
上の方の式は11月30日のブログの(4)と(5)の間にあるUn=AnVn-Un-1と同じだが, 下の方の式はどう導くか.
今回のブログはその計算法である.
(0)はxnの標準形である. (1)はxn-1で, そのxnに(0)を代入し, 前回のように計算を続けると(1)の最後になる. (1)の最初と分母を等しいとしたのが(2)で, ただちに(3)と書ける. 分子の√Nの後に続く項を等しいとしたのが(4)で, 途中で(3)を利用する. PnとPn-1を交換したのが上の式(5)だ.
一方, (3)の添字を1減らしたのが(6)で, (3)-(6)が(7),(8)である. 1/Qn-1は, (5)を移項した(9)から(10)のように得られ, これを(8)に代入すると(11)を経て, 下の方の式(12)になるのが分かる.
漸化式はP1=0, Q1=1から始まるが, 問題は, Qn-2があるので, Q0が必要なことだ.
実はQ0=Nなのだが, この計算は次の通り.
これで, 連分数のP,Q,qが次々と求まることになる. なんだかまた久しぶりにこのような計算をした.
0 件のコメント:
コメントを投稿