連分数2：連分数展開と最良近似
はじめに
この記事では 前回の記事 の続きとして実数の連分数展開の性質について簡単にまとめていきます。
復習
まず正則連分数について 前回の記事 からわかることを簡単にまとめておきましょう。
数列$p_n,q_n$を
$$\begin{pmatrix}
p_{-1}&p_0\\q_{-1}&q_0
\end{pmatrix}
=\begin{pmatrix}
1&a_0\\0&1
\end{pmatrix}$$
および漸化式
\begin{align}
p_n&=a_np_{n-1}+p_{n-2}\\
q_n&=a_nq_{n-1}+q_{n-2}
\end{align}
によって定めると
\begin{align}
\frac{p_nx+p_{n-1}}{q_nx+q_{n-1}}
&=[a_0;\ a_1,\ a_2,\ \ldots,\ a_n,\ x]\\
&=a_0+\frac1{a_1}\p\frac1{a_2}\p\cc\p\frac1{a_n}\p\frac1x
\end{align}
が成り立つ。
特にこの分数$p_n/q_n$のことを連分数$[a_0;\ a_1,\ a_2,\ \ldots]$の$n$次の収束分数と言うのでした。
$$p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1}$$
収束連分数
$$x=[a_0;\ a_1,\ a_2,\ \ldots]\quad(a_n\geq0)$$
に対し
$$\frac{p_0}{q_0}<\frac{p_2}{q_2}<\frac{p_4}{q_4}<\cdots< x<\cdots
<\frac{p_5}{q_5}<\frac{p_3}{q_3}<\frac{p_1}{q_1}$$
や
$$\frac{a_{n+2}}{q_nq_{n+2}}\leq\l|x-\frac{p_n}{q_n}\r|\leq\frac1{q_nq_{n+1}}$$
が成り立つ。
連分数展開
いま実数$x$を整数部分$a_n$と小数部分$1/x_n\ (1< x_n\leq\infty)$に分け
\begin{align}
x&=a_0+\frac1{x_1}\\
x_1&=a_1+\frac1{x_2}\\
x_2&=a_2+\frac1{x_3}\\
&\ \ \vdots
\end{align}
と整数列$a_n$を定めていくと
\begin{align}
x
&=a_0+\dfrac1{x_1}\\
&=a_0+\dfrac1{a_1+\dfrac1{x_2}}\\
&=a_0+\dfrac1{a_1+\dfrac1{a_2+\dfrac1{x_3}}}\\
&\ \ \vdots
\end{align}
と変形していくことができ、これによって以下のような連分数が得られます。
任意の実数$x$に対し、$a_0$を除き$a_n\geq1$を満たすような整数列$a_n$が存在し
\begin{align}
x&=[a_0;a_1,a_2,a_3,\ldots]\\
&=a_0+\dfrac1{a_1+\dfrac1{a_2+\dfrac1{a_3+\cd}}}
\end{align}
が成り立つ。これを$x$の連分数展開と言う。
上のように$x_n$の整数部分として構成した整数列$a_n$に対し、連分数
$$[a_0;a_1,a_2,a_3,\ldots]$$
の収束分数を$p_n/q_n$とおくと補題1より
\begin{align}
x
&=a_0+\frac1{a_1}\p\frac1{a_2}\p\cc\p\frac1{a_{n+1}}\p\frac1{x_{n+2}}\\
&=\frac{p_{n+1}x_{n+2}+p_n}{q_{n+1}x_{n+2}+q_n}
\end{align}
が成り立つのであった。
また補題2に注意すると
\begin{align}
x-\frac{p_n}{q_n}
&=\frac{(p_{n+1}q_n-p_nq_{n+1})x_{n+2}}{q_n(q_{n+1}x_{n+2}+q_n)}\\
&=\frac{(-1)^n}{q_n(q_{n+1}+\frac{q_n}{x_{n+2}})}
\end{align}
が成り立つので
$$\l|x-\frac{p_n}{q_n}\r|\leq\frac1{q_nq_{n+1}}\to0\quad(n\to\infty)$$
を得る。
簡単な性質
ちなみに実数の連分数展開は次のような一意性を持つことが知られています(証明は簡単なので省略)。
無理数$x$に対し、その連分数展開は一意的である。
また有理数$x$に対し、その連分数展開は
\begin{align}
x
&=[a_0;\ a_1,\ \ldots,\ a_n]\\
&=[a_0;\ a_1,\ \ldots,\ a_n-1,\ 1]
\end{align}
という形の$2$通りで尽くされる(ただし$n=0$または$a_n\geq2$とした)。
また連分数展開の一意性は有理数が無限に続く連分数展開を持たないことも意味しているので、次のようなことが言えたりします。
実数$x$が無理数であることと、その連分数展開が無限に続くことは同値である。
最後に一つだけ簡単にわかる性質として地味に重要な次の事実を紹介しておきましょう。
実数$x$の(連分数展開に関する)収束分数$p_n/q_n$は既約分数である。
補題2から$p_n,q_n$の公約数は$|p_nq_{n-1}-p_{n-1}q_n|=1$を割り切るので$\gcd(p_n,q_n)=1$となることがわかる。
最良近似の法則
連分数展開の特筆すべき性質としてその収束分数が実数の(第$2$種)最良近似を与えるという法則があります。
以下でそのことについて簡単にまとめていきましょう。
既約分数$p/q$が実数$x$の第$1$種最良近似であるとは、任意の$0< q'\leq q$かつ$p/q\neq p'/q'$なる有理数$p'/q'$に対し
$$\l|x-\frac pq\r|<\l|x-\frac{p'}{q'}\r|$$
を満たすことを言う。
また既約分数$p/q$が実数$x$の第$2$種最良近似であるとは、任意の$0< q'\leq q$かつ$p/q\neq p'/q'$なる有理数$p'/q'$に対し
$$|qx-p|<|q'x-p'|$$
を満たすことを言う。
実数$x$の収束分数$p_n/q_n\ (\neq x)$と任意の$0< q\leq q_{n+1}$なる既約分数$\frac pq\neq\frac{p_n}{q_n},\frac{p_{n+1}}{q_{n+1}}$に対し
$$|q_nx-p_n|\leq|qx-p|$$
が成り立つ。また等号成立条件は
$$x=\frac{p_{n+1}}{q_{n+1}}\quad\text{かつ}\quad
\frac pq=\frac{p_{n+1}-p_n}{q_{n+1}-q_n}$$
である。
$$\begin{pmatrix}p\\q\end{pmatrix}
=\begin{pmatrix}
p_n&p_{n+1}\\
q_n&q_{n+1}
\end{pmatrix}
\begin{pmatrix}X\\Y\end{pmatrix}$$
なる$X,Y$を取ると、$p_nq_{n+1}-p_{n+1}q_n=\pm1$より
$$\begin{pmatrix}X\\Y\end{pmatrix}
=\pm\begin{pmatrix}
q_{n+1}&-p_{n+1}\\
-q_n&p_n
\end{pmatrix}
\begin{pmatrix}p\\q\end{pmatrix}$$
が成り立つので$X,Y$は$0$でない整数となり、また
$$q_nX+q_{n+1}Y=q\leq q_{n+1}$$
より$X$と$Y$は異符号かつ
$$\frac{p_n}{q_n}< x\leq\frac{p_{n+1}}{q_{n+1}}
\quad\text{または}\quad
\frac{p_{n+1}}{q_{n+1}}\leq x<\frac{p_n}{q_n}$$
より$q_nx-p_n$と$q_{n+1}x-p_{n+1}$も異符号であることに注意すると
\begin{align}
|qx-p|
&=|(q_nx-p_n)X+(q_{n+1}x-p_{n+1})Y|\\
&=|(q_nx-p_n)X|+|(q_{n+1}x-p_{n+1})Y|\\
&\geq|(q_nx-p_n)X|\\
&\geq|q_nx-p_n|
\end{align}
が成り立つ。
また等号成立条件は$x=\frac{p_{n+1}}{q_{n+1}}$かつ$|X|=1$であり、このとき$0< q\leq q_{n+1}$に注意すると$(X,Y)=(-1,1)$でなければならないことがわかる。
実数$x$の連分数展開の収束分数$p_n/q_n\ (n\geq1)$は$x$の第$2$種最良近似であり、また$p_0/q_0=a_0$が$x$の第$2$種最良近似となることと$x-a_0<\frac12$が成り立つことは同値である。
逆に$x$の任意の第$2$種最良近似$p/q$はある収束分数$p_n/q_n$に等しい。
ただし有理数$x$の連分数展開
$$x=[a_0;\ a_1,\ \ldots,\ a_n]$$
は$n=0$または$a_n\geq2$であるものとします。
$p_0/q_0$に関する主張や$x=p_n/q_n$のときの前半の主張は簡単なので、$n\geq1$かつ$x\neq p_n/q_n$としてよい。
いま
$$x=\frac{p_{n+1}}{q_{n+1}}\quad\Longrightarrow\quad a_{n+1}\geq2$$
としていたことに注意すると、上の補題の等号が成立するとき
$$q=q_{n+1}-q_n=(a_{n+1}-1)q_n+q_{n-1}>q_n$$
が成り立つので、少なくとも$q\leq q_n$においては等号は成立しない、つまり$p_n/q_n$は$x$の第$2$種最良近似であることがわかる。
また上の補題から$q_n< q< q_{n+1}$なる第$2$種最良近似分数は存在しないこともわかるので、$x$の第$2$種最良近似は収束分数で尽くされることになる。
より強い近似について
このように任意の収束分数は第$2$種最良近似を与えることがわかりましたが、さらに収束分数の半分以上は次のようなより強い近似を与えることもわかります。
実数$x$に対し、その連続する収束分数$p_n/q_n,\ p_{n+1}/q_{n+1}$の少なくとも一方は
$$\l|x-\frac pq\r|<\frac1{2q^2}$$
を満たす。逆にこの不等式を満たす既約分数$p/q$はある収束分数に等しい。
前半の主張について
もし連続する収束分数が共に
$$\l|x-\frac{p_n}{q_n}\r|\geq\frac1{2q_n^2},\quad
\l|x-\frac{p_{n+1}}{q_{n+1}}\r|\geq\frac1{2q_{n+1}^2}$$
を満たすとすると、$x,\frac{p_n}{q_n},\frac{p_{n+1}}{q_{n+1}}$の大小に注意すると
\begin{align}
\frac1{q_nq_{n+1}}
&=\frac{|p_{n+1}q_n-p_nq_{n+1}|}{q_nq_{n+1}}\\
&=\l|\frac{p_{n+1}}{q_{n+1}}-\frac{p_n}{q_n}\r|\\
&=\l|\frac{p_{n+1}}{q_{n+1}}-x\r|+\l|x-\frac{p_n}{q_n}\r|\\
&\geq\frac12\l(\frac1{q_{n+1}^2}+\frac1{q_n^2}\r)
\end{align}
が成り立つので
$$0\geq\l(\frac1{q_{n+1}}-\frac1{q_n}\r)^2$$
つまり$q_n=q_{n+1}$となって矛盾。
なお$q_0=q_1=1$のときのみ例外となるが、その場合は
$$\frac{p_0}{q_0}=a_0,\quad \frac{p_1}{q_1}=a_0+1$$
に注意すると、そのどちらかは
$$\l|x-\frac pq\r|<\frac12$$
を満たすことがわかる。
以上より前半の主張を得る。
後半の主張について
後半の主張については
$$\l|x-\frac pq\r|<\frac1{2q^2}$$
を満たすような既約分数$p/q$が$x$の第$2$種近似であることを示せばよい。
いま既約分数$p'/q'\neq p/q$が
$$|q'x-p'|\leq|qx-p|$$
を満たすとすると
\begin{align}
\frac1{qq'}
&\leq\frac{|pq'-p'q|}{qq'}=\l|\frac pq-\frac{p'}{q'}\r|\\
&\leq\l|\frac pq-x\r|+\l|x-\frac{p'}{q'}\r|\\
&<\frac1{2q}\l(\frac1q+\frac1{q'}\r)
\end{align}
が成り立つので、これを整理することで$q< q'$でなければならない、つまり$p/q$は$x$の第$2$種近似であることが示された。
ちなみに$n\geq1$において
$$\l|x-\frac{p_n}{q_n}\r|\leq\frac1{q_nq_{n+1}}<\frac1{a_nq_n^2}$$
と評価できるので、$a_n$の値によってはより強い不等式を満たす収束分数を得ることもできます。
第$1$種最良近似について
ちなみに収束分数(主近似分数)$p_n/q_n$に加えて中間近似分数
$$\frac{\la p_{n-1}+p_{n-2}}{\la q_{n-1}+q_{n-2}}\quad(0<\la< a_n)$$
というものを考えることで第$1$種最良近似も連分数由来の分数によって尽くされることが知られています。
有理数$\frac ab,\frac cd,\frac pq$が
$$\frac ab<\frac pq<\frac cd\quad\text{かつ}\quad ad-bc=-1$$
を満たすとき
$$q\geq b+d$$
が成り立つ。
$$\begin{pmatrix}p\\q\end{pmatrix}
=\begin{pmatrix}
a&c\\b&d
\end{pmatrix}
\begin{pmatrix}X\\Y\end{pmatrix}$$
つまり
$$\begin{pmatrix}X\\Y\end{pmatrix}
=\begin{pmatrix}
-d&c\\b&-a
\end{pmatrix}
\begin{pmatrix}p\\q\end{pmatrix}$$
とおいたとき
$$\frac ab<\frac pq<\frac cd$$
に注意すると$X,Y$は共に正の整数となるので
$$q=bX+dY\geq b+d$$
を得る。
実数$x$の任意の第$1$種最良近似$p/q$は
$$\frac pq=\frac{\la p_{n-1}+p_{n-2}}{\la q_{n-1}+q_{n-2}}\quad
\l(\frac{a_n}2<\la\leq a_n\r)$$
と表せるもの、または$a_n$が偶数であり
$$[a_{n-1};\ a_{n-2},\ \ldots,\ a_1]<[a_{n+1};\ a_{n+2},\ \ldots]$$
を満たすような$n$に対する
$$\frac pq=\frac{\la p_{n-1}+p_{n-2}}{\la q_{n-1}+q_{n-2}}\quad
\l(\la=\frac{a_n}2\r)$$
によって尽くされる。
簡単のため以下$n$が奇数である場合のみ考える($n$が偶数のときはいくつかの不等号を逆にして考えればよい)。
このとき
$$\frac{p_{n-1}}{q_{n-1}}<\frac{p_{n+1}}{q_{n+1}}< x<\frac{p_n}{q_n}$$
および加比の理から
$$\frac{p_{n-1}}{q_{n-1}}
<\frac{p_n+p_{n-1}}{q_n+q_{n-1}}
<\frac{2p_n+p_{n-1}}{2q_n+q_{n-1}}
<\cdots
<\frac{a_{n+1}p_n+p_{n-1}}{a_{n+1}q_n+q_{n-1}}
=\frac{p_{n+1}}{q_{n+1}}$$
が成り立つことに注意する。
いま$0\leq\la\leq a_{n+1}$なる整数$\la$を任意に取り
$$\frac{p'}{q'}=\frac{\la p_n+p_{n-1}}{\la q_n+q_{n-1}}$$
とおくと、$p_nq_{n-1}-q_nq_{n-1}=1$より$p_nq'-q_np'=1$が成り立つので、上の補題より任意の$q< q'+q_n$なる有理数$p/q$に対し
$$\frac pq\leq\frac{p'}{q'}< x\quad\text{または}\quad x<
\frac{p_n}{q_n}\leq\frac pq$$
が成り立つ。
特に$\max\{q_n,q'\}< q< q'+q_n$なる第$1$種最良近似$p/q$は存在せず、また$p'/q'$が第$1$種最良近似であることと$p'/q'$が
$$x-\frac{p'}{q'}<\frac{p_n}{q_n}-x$$
を満たすことは同値であることがわかる。
またこの不等式は
\begin{align}
&\frac{p_n}{q_n}-\frac{p'}{q'}=\frac1{q_n(\la q_n+q_{n-1})}\\
<{}&2\l(\frac{p_n}{q_n}-x\r)=\frac{2x_{n+2}}{q_n(q_{n+1}x_{n+2}+q_n)}
\end{align}
と変形すると
\begin{align}
q_n
&<(2\la q_n+2q_{n-1}-q_{n+1})x_{n+2}\\
&=((2\la-a_{n+1})q_n+q_{n-1})x_{n+2}
\end{align}
と整理できるので
- $2\la< a_{n+1}$のとき、$(2\la-a_{n+1})q_n+q_{n-1}\leq q_{n-1}-q_n<0$より不適
- $2\la>a_{n+1}$のとき、$(2\la-a_{n+1})q_n+q_{n-1}\geq q_{n-1}+q_n>q_n$より適当
- $2\la=a_{n+1}$のとき、
$$\frac{q_n}{q_{n-1}}=[a_n;\ a_{n-1},\ldots,\ a_1]< x_{n+2}=[a_{n+2};\ a_{n+3},\ \ldots]$$
が必要十分
であることがわかる。
また$\la=a_n/2$に関する条件は次のような事実から簡単に判定することができます(証明略)。
実数$x,y$の連分数展開
$$x=[a_0;\ a_1,\ a_2,\ \ldots],\quad y=[b_0;\ b_1,\ b_2,\ \ldots]$$
が
$$a_k=b_k\quad(0\leq k< n),\quad a_n< b_n$$
を満たすとき
$$\begin{array}{ll}
x< y&(n:\text{偶数})\\
x>y&(n:\text{奇数})
\end{array}$$
が成り立つ。
ただし例外として
$$x=[a_0;\ a_1,\ a_2,\ \ldots,\ a_n-1,\ 1],\quad y=[a_0;\ a_1,\ a_2,\ \ldots,\ a_n]$$
のときは$x=y$が成り立つ。
この記事を高評価した人
この記事に送られたバッジ
投稿者
