ルートと無限連分数メモ
ルートの入った無理数を無限連分数で表現しようという面白い記事があったのでメモ． また，収束条件を満たすかあたりも残しておく．
環境
- Windows10
- python 3.8
ルートを求めるテク
求めたいルートの数字を記事のように$\sqrt{10}$として， 自然数と無理数の和から成り立っていると考える．どちらも正値とする．
$$ \sqrt{10} = n + b $$
両辺の二乗は
式変形すると
$\sqrt{3^{2}} < \sqrt{10} < \sqrt{4^{2}}$より$n=3$とする．
次にこの式を
- 左辺の$b$を$b_{i+1}$
- 右辺の$b$を$b_{i}$
という更新式としてみる．
収束を可視化
収束の証明をふっとばして収束の様子を可視化する．
$$ \sqrt{10} = 3+b $$
のbの更新式をインデックスを変えながら可視化する．
初期値$b_{0} = 0$とする． ここで，$\sqrt{10}-3 = 0.1622776601683795$へ収束していく．
import numpy as np import matplotlib.pyplot as plt %matplotlib inline bs = [0] i_s = np.arange(0, 6+1) for i in i_s[1:]: bs.append(1/(6+bs[-1])) plt.hlines(np.sqrt(10) - 3, 0, i_s[-1], linestyles="--") print(np.sqrt(10) - 3) plt.plot(i_s, bs) plt.grid(True) plt.ylim(0.1621, 0.1623) plt.show()
表にすると
| $b_{i}$ | 分数表記 | 小数(double) |
|---|---|---|
| $b_{0}$ | $0$ | 0 |
| $b_{1}$ | $\frac{1}{6}$ | 0.16666666666666666 |
| $b_{2}$ | $\frac{6}{37}$ | 0.16216216216216214 |
| $b_{3}$ | $\frac{37}{228}$ | 0.16228070175438597 |
| $b_{4}$ | $\frac{228}{1405}$ | 0.16227758007117438 |
| $b_{\infty}$ | - | $\sqrt{10}-3=0.1622776601683795$ |
無限連分数で表現
無理数$b_{i+1}$については無限連分数で表現できる．
よって$\sqrt{10}$は
自然数nを変えても収束するか？
$$ \sqrt{10} = n + b $$
の形であれば問題ない．nが有理数やbが負数でも収束する．
$n=3$を$n=2$へ変えてみる．
$$ 10 = 2^{2} + b(2 \cdot 2 + b)\\ $$
この場合，更新式は次のように変わる．，
収束を可視化する． $\sqrt{10} - 2 = 1.1622776601683795$へ収束していく．
code:
import numpy as np import matplotlib.pyplot as plt %matplotlib inline bs = [0] i_s = np.arange(0, 10+1) for i in i_s[1:]: bs.append(6/(4+bs[-1])) plt.hlines(np.sqrt(10) - 2, 0, i_s[-1], linestyles="--", label="$\sqrt{10}-2$") print(np.sqrt(10) - 2) plt.plot(i_s, bs) plt.grid(True) plt.ylim(1.15, 1.164) plt.legend() plt.savefig("convergence_sqrt(10)-2.png") plt.show()
計算結果の$[b_{0}, b_{5}]$を表にまとめる．
| $b_{i}$ | 分数表記 | 小数(double) |
|---|---|---|
| $b_{0}$ | $0$ | 0 |
| $b_{1}$ | $\frac{3}{2}=1+\frac{1}{2}$ | 1.5 |
| $b_{2}$ | $\frac{12}{11} = 1+\frac{1}{11}$ | 1.0909090909090908 |
| $b_{3}$ | $\frac{33}{28}=1+\frac{5}{28}$ | 1.1785714285714286 |
| $b_{4}$ | $\frac{168}{145}=1+\frac{23}{145}$ | 1.1586206896551723 |
| $b_{5}$ | $\frac{435}{374}=1+\frac{61}{374}$ | 1.1631016042780749 |
| $b_{\infty}$ | - | $\sqrt{10}-2=1.1622776601683795$ |
収束していくが，仮分数となるので分子が大きくになりにくく$n=3$のときよりも収束が遅い．
無限連分数で表現すると
連分数の理論
参考：http://argent.shinshu-u.ac.jp/lecture/files/pdf/cfracb5.pdf
まず用語の定義．
次の形の連分数を正則な連分数という．
$a_{0}, a_{1}, \cdots $を要素という．これは実数，複素数，関数でも問題ない．
有限な連分数で要素を$a_{0}, \cdots, a_{n}$までもつものをn階の連分数という． 要素数は$a_{0}$も含めるのでn+1個になる．
式にすると次になり，右辺は省略記法である．
同様にして無限連分数は次のように表記される．
有限連分数はなんらかの実数となり，すべての要素が有理数であれば有理数をつかった連分数になるので有理数となる．
連分数の中の最初の要素から途中（k番目）までの要素まで連分数を断片という． k番目までで固定されるので，断片は有限・無限問わず有限連分数となる．
逆に，途中要素から最後までを剰余という． 有限連分数であれば$a_{n}$までで有限連分数になり， 無限連分数の場合は終わりがないので$a_{0} = a_{k}$とした無限連分数になる．
無限連分数は剰余を使って次のように書ける．
正準表現と収束子（近似子）
有限連分数は有理関数なので分母を表す多項式と分子を表す多項式の比で表現できる．
有利連分数を単純な分数の形で表現することを正準表現と呼ぶ．
0階の連分数を
$$ [ a_{0} ] = a_{0} = \frac{a_{0}}{1} $$
n階の連分数は
ここで，剰余$r_{1}$は有限連分数なので次の正準表現で表されるとする．
$$ r_{1} = \frac{p'}{q'} $$
これを代入して有限の連分数$[a_{0}; a_{1}, a_{2}, \cdots, a_{n}]$の正準表現とする．
正準表現の分子分母は次のように対応している．
ちなみに，$[a_{0}, a_{1}]$の正準表現は
断片の正準表現を考える． 断片は有限連分数になるので正準表現可能である．
これを連分数のk階の$収束子（近似子）$という． 無限連分数の場合は，kは無限まで存在する．
n階の有限連分数$\alpha$には$n+1$の収束子が存在する．
Theorem1 収束市の形の規則（漸化式）
次の漸化式が成立する．
proof:
帰納法を使う．
k=2のとき：
$k < n$のとき成り立つと仮定し$k=n$でも成立するかを確認する．
$n-1$階剰余$r_{1}$のr階の収束子を$p'_{r}/q'_{r}$で表す． これにより$k=2$のときの$p'/q'$を一般化できる．
もとの連分数のn階の収束子を考える．
よって，
n-1階剰余の連分数でも仮定は成立するので
※$[a_{1}; a_{2}, \cdots, a_{n}]$の収束子なので$a_{n-1}$でなく$a_{n}$になる．
これを代入すると，
よって任意の$2 \leq k$でも定理が成り立つ．
note: -1階数の収束子を$p{-1}=1,q{-1}=0$とおくと．$k=1$でも成立する．
$\sqrt{10}$の断片$[3,6,6,6]$で確認
| k | 正準表現 | $p_{k}$ | $q_{k}$ |
|---|---|---|---|
| 0 | $\frac{3}{1}$ | 3 | 1 |
| 1 | $\frac{19}{6}$ | 19 | 6 |
| 2 | $\frac{117}{37}$ | $6\cdot19+3=117$ | $6\cdot 6+1=37$ |
| 3 | $\frac{721}{228}$ | $6\cdot 117+19=721$ | $6\cdot 37+6=228$ |
Theorem2
すべての$k\geq 0$に対して
が成立する．
proof:
定理1の第1式を 倍する．
第2式を 倍する．
差分を計算すると
前インデックスの符号反転であることがわかる．
$-1$階数も考慮してk=0の開始点をみると
$$ q_{0}p_{-1} - p_{0}q_{-1} = 1 \cdot 1 - a_{1} \cdot 0\ = +1 $$
よって，定理2が成立．
で割ると次の系が成立する．
Corollary1: すべての$k \leq 1$に対して
この系からわかることは
- 偶数階数収束子は直後(k, 直前でも同じ)の奇数階数収束子より小さい．（偶数階数収束子は，奇数階数収束子にとって下界である）
- 奇数階数収束子は直後(k)の偶数階数収束子より大きい．（奇数階数収束子は，偶数階数収束子にとって上界である）
| k | 偶数階$\frac{p_{2k}}{q_{2k}}$ | 不等号 | 奇数階$\frac{p_{2k+1}}{q_{2k+1}}$ |
|---|---|---|---|
| 0 | $\frac{3}{1}=3$ | < | $\frac{19}{6}=3.1666666666666665$ |
| 2 | $\frac{117}{37}=3.1621621621621623$ | < | $\frac{721}{228}=3.162280701754386$ |
Theorem3
すべての$k \geq 1$に対して
proof:
定理1の第1式を$q_{k-2}$倍する．
第2式を$p_{k-2}$倍する．
これらの差は
定理2より
系2の結果から - 奇数階数収束子は減少列（kが増えるごとに小さくなる） - 偶数階数収束子は増大列（kが増えるごとに大きくなる）
よって，この2つの列は互いに近づく（収束）．（$a_{k}$が正値の場合）
| k | 偶数階$\frac{p_{2k}}{q_{2k}}$ |
|---|---|
| 0 | $\frac{3}{1}=3$ |
| 2 | $\frac{117}{37}=3.1621621621621623$ |
| k | 奇数階$\frac{p_{2k+1}}{q_{2k+1}}$ |
|---|---|
| 1 | $\frac{19}{6}=3.1666666666666665$ |
| 3 | $\frac{721}{228}=3.162280701754386$ |
Theorem4
系1，系2をまとめると
系2から - 奇数階収束子は減少列 - 偶数階収束子は増大列
系1から - 奇数階収束子は直後の偶数階収束子より大きい - 偶数階収束子は直後の奇数階収束子より小さい
よって，すべての奇数階収束子はすべての偶数階収束子よりも大きい．
有限連分数$\alpha$に対して - すべての偶数階収束子は$\alpha$よりも小さい - すべての奇数階収束子は$\alpha$よりも大きい
import numpy as np import matplotlib.pyplot as plt %matplotlib inline def renbu_1(a, k=0): ''' [a; a, a, ...] ''' if k<= 0: return a return a + 1/ renbu_1(a, k=k-1) def renbu_2(a0, a1, k=0): ''' [a0;a1,a1,...] ''' if k<= 0: return a0 return a0 + 1/ renbu_1(a1, k=k-1) ks = np.arange(0, 10+1) renbus = [] for k in ks: renbus.append(renbu_2(6,3,k)) #even plt.plot(ks[::2], renbus[::2], label="even") # odd plt.plot(ks[1::2], renbus[1::2], label="odd") plt.grid(True) plt.ylim(6.29, 6.34) plt.legend() plt.savefig("convergence_odd_even.png") plt.show()
Theorem5
任意のk$(1 \leq k \leq n)$に対して
- $r_{k}$は$a_k$から始まる剰余（有限連分数）
Theorem1を剰余を使って拡張して表記できる． また，実は無限連分数でも成立する．
proof:
有限連分数を剰余を使って書き直す．
右辺の ] まではk-1階収束子で表される．
Theorem1より
よってTheorem5が成立．
Theorem6
任意の$k\geq 1$ に対して
$a_0$を除いて逆順の連分数となるもの．
proof:
帰納法を使う．
$k=1$のとき：
$$ \frac{q_{1}}{q_{0}} = \frac{a_{1}}{1} = a_{1} = [a_{1}] $$
k-1でこの定理が成り立つと仮定しk番目で成立するか確認する．
定理1の第2式を$q_{k-1}$で割る．
よって，成立．
無限連分数
無限連分数$[a_{0}; a_{1}, a_{2} , \cdots ]$に対して収束子は
に対応している． すべての収束子は何かの実数になる． もし列が収束するなら（それが一意な極限$\alpha$）を持っているなら， その$\alpha$を連分数の値であると考えて，
$$ \alpha = [a_{0}; a_{1}, a_{2}, \cdots ] $$
と書ける．そのとき無限連分数もまた収束するという． 逆に，定まった極限を持たない場合は発散するという．
Theorem7
もし無限連分数が収束するなら、その剰余もまたすべて収束する。 逆に、無限連分数の少なくとも一つの剰余が収束するなら、その無限連分数自身 が収束している。
proof: 無限連分数のn-1階収束子を$\frac{p_{n-1}}{q_{n-1}}$とする．
$$ [a_{0}; a_{1}, a_{2}, \cdots, a_{n-1} ]= \frac{p_{n-1}}{q_{n-1}} $$
残りの剰余$r_{n}$のk階収束子を$p'_{k}/q'_{k}$とする．
$$ [a_{n}; a_{ n +1}, a_{n+2}, \cdots a_{n+k} ]= \frac{p'_{k}}{q'_{k}} $$
無限連分数の$n+k$階収束子はTheorem5より
もし剰余$r_{n}$が収束するなら
$$ \lim_{k\to \infty} \frac{p'_{k}}{q'_{k}} = r_{n} $$
無限連分数の収束子も何らかの値に収束する
また，Therom５が無限連分数にも成立する．
Theorem8
収束する無限連分数の値はすべての偶数回数収束子よりも大きく，奇数階数収束子よりも小さい．
Theorem4から導ける．
Theorem9
定理２の系1から次を導ける．
収束する無限連分数の値$\alpha$は任意の$n-1> k \geq 0 $に対して次の不等式を満たす． なお，$a_{1} > 0$より$q_{k} > 0, k>1$を仮定する．
系１のインデックスを進めて絶対値をとると導出できる．
Theorem10 無限連分数が収束する必要十分条件
$a_{i} > 0,( i\leq 1) $の場合 無限連分数が収束する必要十分条件は， 無限連分数の要素の級数
が発散すること.
proof:
Theorem4から無限連分数が収束する必要十分条件は 奇数階収束子と偶数階収束子の2つの列が同じ極限を持つことになる．
同じ極限を持つ場合，系1の式は0に近づいていく．
そうすると右辺分母が
のときのみである．これが収束するための必要十分条件になる．
級数が何らかの値に収束すると仮定する． つまり$0< a_{k}<1$の場合を考える． Thorem1の式より
このとき
すなわち
の2通りが考えられる．
前者の場合
不等式にすると
後者の場合 を考えると
で置きかえると
左辺を式変形すると
まとめると
したがって，すべての場合で
$$ q_{k} < \frac{1}{1-a_{k} }q_{l} , (\text{ where } l < k) $$
が成り立つ． これを$k_{0} < s < r < \cdots < m < l $のように繰り返すと
$$ q_{l} < \frac{1}{1-a_{l} }q_{m} , (\text{ where } m < l) $$
これを繰り返して両辺の積は
$$ q_{k}q_{l} \cdots q_{r} < \frac{q_{l} }{1-a_{k} } \frac{q_{m} }{1-a_{l} } \cdots \frac{q_{s}}{1-a_{r} } $$
分子が消せるので
$\sum_{n=1}^{\infty} a_{n}$が収束するなら$\prod_{n=1}^{\infty} (1+a_{n})$も収束する． $\prod_{n=1}^{\infty}\frac{1}{(1- a_{n})}$も収束する．
3.1 無限積の絶対収束 https://genkuroki.github.io/documents/Calculus/02%20series.pdf
よって，
$$ \frac{1}{(1-a_{k}) (1-a_{l})\cdots (1-a_{r})} \leq \prod_{n=k_{0}}^{\infty} (1-a_{n}) = \lambda $$
$q_{0}, q_{1},\cdots q_{k_{0}-1}$中の最大のものを$Q$と書けば
$$ q_{k} < \lambda Q, (k \geq k_{0}) $$
そして，
$$ q_{k}q_{k+1} < \lambda^{2} Q^{2} < \infty, (k \geq k_{0}) $$
よって，要素の級数が収束する場合，その無限連分数は発散する．
系1の第2式と$a_{i} > 0$の仮定より $q_{k} > q_{k-2}, (k \geq 1)$
これは$k \geq 2$で成立しているので
$$ q_{2} > q_{0} \\ q_{3} > q_{1} $$
ここで最小のものを$c$とれば
$$ c=\mathrm{min}(q_{0}, q_{1}) $$
$$ q_{k} \geq c, (k \geq 0) $$
が成り立つ．
系1第2式の を$c$に置き換えると次の不等式が成立，
$$ q_{k} \geq q_{k-2} + ca_{k}, (k \geq 2) $$
ここで偶数階収束子は
$$ q_{2} \geq q_{0} + c a_{2}\\ q_{4} \geq q_{2} + c a_{4} \geq q_{0} + c(a_{2}+a_{4}) \\ \vdots \\ q_{2k} \geq q_{0} + c \sum_{n=1}^{k}a_{2n} $$
奇数階収束子は
$$ q_{3} \geq q_{1} + ca_{3}\\ q_{5} \geq q_{3} + ca_{5} \geq q_{1} + c(a_{3}+a_{5}) \\ \vdots \\ q_{2k+1} \geq q_{1} + c\sum_{n=1}^{k}a_{2n+1} $$
この2つの不等式を足すと
$$ q_{2k} + q_{2k+1} \geq q_{0} + q_{1} + c\sum_{n=1}^{2k+1}a_{n}\\ q_{2k} + q_{2k+1} > c\sum_{n=1}^{2k+1}a_{n} $$
すべてのkで書き換えると
のとき
$$ 2q_{k} > c \sum_{n=1}^{k}a_{n} $$
のとき
また， より
級数が発散するという仮定だったので
収束の精度についてはヒンチン本の第2章6,7節に書かれてる．
