Collatzの問題

ドイツのLothar Collatzという数学者が1937年に提示したとのことで、まだ証明がされていないらしい。予想は以下のようにシンプル。

任意の自然数の初期値nに対して、以下の操作を繰り返すことにより、有限回の操作で必ず1に達する。

  • nが偶数の場合、2で割る
  • nが奇数の場合、3倍して1を足す

CoffeeScriptによるコードの例

いくつかの初期値に対するnの変化

 

ネイピア数

概要

ネイピア数(Napier’s constant)は自然対数の底で、一般に記号eで表される。オイラー数(Euler’s number)と呼ばれることもある。

(1)    \begin{equation*} e = 2.7182818284590452353602874 \cdots \end{equation*}

定義

ヤコブ・ベルヌーイによる定義。

(2)    \begin{equation*} e = \lim_{n \to \infty} \left( 1 + \frac{1}{n} \right) ^n \end{equation*}

性質

(3)    \begin{equation*} \frac{d}{dx} e^x = e_x \end{equation*}

(4)    \begin{equation*} \int e^x = e_x + {\rm const} \end{equation*}

(5)    \begin{equation*} \frac{d}{dx} \ln x = \frac{1}{x} \end{equation*}

(6)    \begin{equation*} \int \frac{dx}{x} = \ln x + {\rm const} \end{equation*}

テイラー展開

(7)    \begin{eqnarray*} e^x &=& \sum_{n=0}^{\infty} \frac{x^n}{n!} \\ &=& 1 + \frac{x}{1!} + \frac{x^2}{2!}+ \frac{x^3}{3!} \cdots \end{eqnarray*}

 

三角関数 – 加法定理

加法定理の一覧

(1)   \begin{eqnarray*} \sin ( \alpha \pm \beta) &=& \sin \alpha \cos \beta \pm \cos \alpha \sin \beta \\ \cos ( \alpha \pm \beta ) &=& \cos \alpha \cos \beta \mp \sin \alpha \sin \beta \end{eqnarray*}

導出

第1ステップ – 等式の一つを導出

まず、以下のような図を考える。

math_trigonometry_additiontheorem_1

ABの長さを余弦定理で表す。

(2)   \begin{equation*} ( \cos \alpha - \cos \beta )^2 + ( \sin \alpha - \sin \beta )^2 = 1^2 + 1^2 - 2 \cos (\alpha - \beta) \end{equation*}

これより以下を得るが、これは加法定理のうちの一つに対応している。

(3)   \begin{equation*} \cos (\alpha - \beta) = \cos \alpha \cos \beta + \sin \alpha \sin \beta \end{equation*}

なお上式は、cosの性質からαとβの大小関係に関わらず成り立つ。

第2ステップ – 符号の反転

式(3)でβ → – βと置くと以下を得る。

(4)   \begin{equation*} \cos (\alpha + \beta) = \cos \alpha \cos \beta - \sin \alpha \sin \beta \end{equation*}

第3、4ステップ – cosからsinへの変換と符号の反転

式(3)でα → α+π/2と置くと以下を得る。

(5)   \begin{eqnarray*} \cos \left( \alpha + \frac{\pi}{2} - \beta \right) &=& \cos \left( \alpha + \frac{\pi}{2} \right) \cos \beta - \sin \left( \alpha + \frac{\pi}{2} \right) \sin \beta \\ - \sin ( \alpha - \beta ) &=& - \sin \alpha \cos \beta + \cos \alpha \sin \beta \\ \sin ( \alpha - \beta ) &=& \sin \alpha \cos \beta - \cos \alpha \sin \beta \end{eqnarray*}

また上式においてβ → – βと置くと以下を得る。

(6)   \begin{eqnarray*} \sin ( \alpha + \beta ) &=& \sin \alpha \cos \beta + \cos \alpha \sin \beta \end{eqnarray*}

これで加法定理に関する4つの式が得られた。

一般角への拡張

αやβが第3象限、第4象限にあるときは、それらからπ/2、πを減じて冒頭の図に対応させ、式変形をすることで同じ解を得る。

例えば下図のように、αが第3象限、βが第1象限にあるケースを考える。

math_trigonometry_additiontheorem_2

ここでα = α’ + π/2と置けば、α’について加法定理が成り立つことが分かっているので、

(7)   \begin{eqnarray*} \sin ( \alpha ' \pm \beta) &=& \sin \alpha ' \cos \beta \pm \cos \alpha ' \sin \beta \\ \cos ( \alpha ' \pm \beta ) &=& \cos \alpha ' \cos \beta \mp \sin \alpha ' \sin \beta \end{eqnarray*}

αとα’の関係より、

(8)   \begin{eqnarray*} \sin \left( \alpha - \frac{\pi}{2} \pm \beta \right) &=& \sin \left( \alpha - \frac{\pi}{2} \right) \cos \beta \pm \cos \left( \alpha - \frac{\pi}{2} \right) \sin \beta \\ \cos \left( \alpha - \frac{\pi}{2} \pm \beta \right) &=& \cos \left( \alpha - \frac{\pi}{2} \right) \cos \beta \mp \sin \left( \alpha - \frac{\pi}{2} \right) \sin \beta \end{eqnarray*}

これらより、以下の下方定理がこのケースについて成り立つことが示される。

(9)   \begin{eqnarray*} - \cos ( \alpha \pm \beta) &=& - \cos \alpha \cos \beta \pm \sin \alpha \sin \beta \\ \sin ( \alpha \pm \beta ) &=& \sin \alpha \cos \beta \pm \cos \alpha \sin \beta \end{eqnarray*}

 

直線のパラメータ表示と操作

直線のパラメータ表示

たとえば2次元の直線のパラメータ表示は、以下のように一つのパラメータtに対してxとyが計算される方法。

    $$ \left\{ \begin{align*} x = a t + b \\ y = c t + d \end{align} \right. $$

直線の決定

通過点と方向が与えられた場合

直線が通過すべき点(px, py)と、直線の方向(vx, vy)が与えられた場合のパラメータ表示を決定する。

通過点でパラメータがt = 0とすればpxとpyが定まり、tが1単位増えた時のxとyの増分が直線の方向に対応することから、以下のように表される。

    $$ \left\{ \begin{align*} x = v_x t + p_x \\ y = v_y t + p_y \end{align} \right. $$

なおこれらを、パラメータtに対応した直線状の点の位置ベクトル{\bf x}、通過点の位置ベクトル{\bf p}、方向ベクトル{\bf v}で表示すると下記のようになる。

    \[{\bf x} = {\bf v} t + {\bf p}\]

2つの通過点が与えられた場合

2つの点p(px, py)とq(qx, qy)が与えられた場合の直線のパラメータ表示を決定する。

点pでt = 0、点qでt = 1とすれば、以下の式が得られる。

    $$ \left\{ \begin{align*} x = (q_x - p_x) t + p_x \\ y = (q_y - p_y) t + p_y \end{align} \right. $$

これをベクトル表示すれば以下の通り。

    \[{\bf x} = ( {\bf q} - {\bf p} ) t + {\bf p}\]

直線の式との関係

一般に直線の式は以下で与えられる。

    \[ax + by + c = 0\]

一方で媒介変数された直線の式からパラメーターを消去すると以下のようになる。

    \[\frac{x - p_x}{v_x} = \frac{y - p_y}{v_y}\]

これを変形すると、先の直線の式との対応関係がわかる。

    \[v_y x - v_x y -v_x p_x + v_y p_y = 0\]

交点の特定

以下の2つの直線の交点を求める。

    $$ \left\{ \begin{align*} {\bf x}_1 = {\bf v}_1 t_1 + {\bf p}_1 \\ {\bf x}_2 = {\bf v}_2 t_2 + {\bf p}_2 \end{align} $$

これを要素表示に展開する。

    $$ \left\{ \begin{align*} x_1 = v_{1x} t_1 + p_{1x} \\ y_1 = v_{1y} t_1 + p_{1y} \\ x_2 = v_{2x} t_2 + p_{2x} \\ y_2 = v_{2y} t_2 + p_{2y} \end{align} $$

ここでx1 = x2、y1 = y2と置いて、t1、t2を未知数とした以下の方程式を得る。

    $$ \left\{ \begin{align*} v_{1x} t_1 + p_{1x} = v_{2x} t_2 + p_{2x} \\ v_{1y} t_1 + p_{1y} = v_{2y} t_2 + p_{2y} \end{align} $$

この方程式を行列で表示すると以下の通り。

    \[\left[ \begin{array}{cc} v_{1x} & -v_{2x} \\ v_{1y} & -v_{2y} \end{array} \right] \left[ \begin{array}{c} t_1 \\ t_2 \end{array} \right] = \left[ \begin{array}{c} p_{2x} - p_{1x} \\ p_{2y} - p_{1y} \end{array} \right] = \left[ \begin{array}{c} \Delta p_x \\ \Delta p_y \end{array} \right]\]

これを解いて以下を得る。

    $$ \left\{ \begin{align*} t_1 = \frac{-v_{2y} \Delta p_x + v_{2x} \Delta p_y}{-v_{1x}v_{2y} + v_{1y} v_{2x}} \\ t_2 = \frac{-v_{1y} \Delta p_x + v_{1x} \Delta p_y}{-v_{1x}v_{2y} + v_{1y} v_{2x}} \end{align} \right. $$

これらの式は分母がゼロのときは解をもたないが、これは{\bf v}_1{\bf v}_2を90度回転させたベクトルが直角であること、すなわち2つの直線の方向が平行であることを示している。

さらに2つの直線がまったく一致するときは、分母・分子ともゼロとなり、解は不定となる。

ここで、交点の座標を確認する。

    $$ \begin{align*} x &= v_{1x} t_1 + p_{1x} = v_{2x} t_2 + p_{2x} \\ &= \frac{v_{1y} v_{2x} p_{1x} - v_{1x} v_{2y} p_{2x} + v_{1x} v_{2x}(p_{2y} - p_{1y})} {-v_{1x} v_{2y} + v_{1y} v_{2x}} \\ y &= v_{1y} t_1 + p_{1y} = v_{2y} t_2 + p_{2y} \\ &= \frac{v_{1y} v_{2y} (p_{2x} - p_{1x}) - v_{1x} v_{2y} p_{1y} + v_{1y} v_{2x} p_{2y}} {-v_{1x} v_{2y} + v_{1y} v_{2x}} \end{align} $$

当然この結果は、パラメータ表示の2直線からパラメータt1、t2を消去して陰関数表示をした以下の方程式の解と一致する。

    $$ \left\{ \begin{align*} v_{1y} x - v_{1x} y = v_{1y} p_{1x} - v_{1x} p_{1y} \\ v_{2y} x - v_{2x} y = v_{2y} p_{2x} - v_{2x} p_{2y} \end{align} \right. $$

 

交点の位置

パラメータ表示の場合、基準点においてt = 0とし、方向ベクトルの先、あるいはそれに相当する2つ目の点においてt = 1などとすれば、基準点から方向ベクトルの先のtは正の値、逆方向ではtが負の値になる。

これを利用して、二つの直線の交点が基準点より前方/後方どちらの側にあるか、あるいは半直線に交点が存在するか、といった判定が容易に可能となる。

math_geom_line1

 

ベクトルの内積

ベクトルの内積の表現には、要素表示を用いたものと幾何的なものの2つがある。

    $$ {\bf a} \cdot {\bf b} = a_x b_x + a_y b_y + a_z b_z = | {\bf a} | | {\bf b} | \cos \theta $$

2つの表現が等価であることを証明するのに、下図のように2つのベクトルで張られた三角形の\oberline{AB}の長さを考える。

math_vector_innerprod_1

まずベクトルの成分で計算した場合は、

    $$ \begin{align*} \overline{AB}^2 &= (a_x - b_x)^2 + (a_y - b_y)^2 + (a_z - b_z)^2 \\ &= a_x^2 + a_y^2 + a_z^2 + b_x^2 + b_y^2 + b_z^2 - 2 a_x b_x - 2 a_y b_y - 2 a_z b_z \end{align} $$

また余弦定理を用いて計算した場合は、a = | {\bf a} | , \: b = | {\bf b} |として以下のようになる。

    $$ \begin{align*} \overline{AB}^2 &= a^2 + b^2 - 2ab \cos \theta \\ &= a_x^2 + a_y^2 + a_z^2 + b_x^2 + b_y^2 + b_z^2 - 2ab \cos \theta \end{align} $$

上記2つが等しいことから、以下が得られる。

    $$ a_x b_x + a_y b_y + a_z b_z = ab \cos \theta $$

2次元の場合は、z成分を0とおいてx成分とy成分のみについて考えればよい。

 

三角関数 – 余弦定理

概要

三角形の2辺a、bとそのなす角θが与えられたとき、3つ目の辺cの長さは以下で求められる。

    $$ c^2 = a^2 + b^2 - 2ab \cos \theta $$

鋭角の場合

下図のように、辺a、bとそのなす角θが与えられているとき、3つ目の辺cとそれらとの関係を考える。

math_cosine_formula_1

辺cは上図右の直角三角形の斜辺なので、以下の式が成り立つ。

    $$ \begin{align*} c^2 &= ( b \sin \theta )^2 + ( a - b \cos \theta )^2 \\ &= b^2 \sin ^2 \theta + a^2 + b^2 \cos ^2 \theta - 2ab \cos \theta \\ &= a^2 + b^2 - 2ab \cos \theta \end{align} $$

鈍角の場合

下図のようになす角が鈍角の場合を考える。

math_cosine_formula_2

    $$ \begin{align*} c^2 &= \left[ b \sin ( \pi - \theta ) \right]^2 + \left[ b \cos ( \pi - \theta ) + a \right]^2 \\ &= (b \sin \theta )^2 + (-b \cos \theta + a)^2 \\ &= b^2 \sin ^2 \theta + b^2 \cos ^2 \theta + a^2 - 2ab \cos \theta \\ &= a^2 + b^2 - 2ab \cos \theta \end{align} $$

 

前後左右の判定

前後の判定

ある点が運動しているとき、着目する他の点が進行方向の前方にあるのか、後方にあるのかを判定したい時があるが、2次元の場合は、ベクトルの内積を使うとこの判定が簡単にできる。

以下の図で、点sがvの方向に進んでいるとき、点pが前方/後方のいずれにあるかを判定する。

math_linear_tool_ahead_behind

sを起点としたベクトルvと、sから見たpの相対的な位置ベクトルの内積を考えると、

    $$ {\bf v} \cdot ( {\bf p} - {\bf s} ) = | {\bf v} | | {\bf p} - {\bf s} | \cos \theta $$

上式で0≤θ≤90度の範囲であればpはsの前方にあり、このときcosθ≥0。また90度<θ≤180度の範囲ならpはsの後方にあり、cosθ<0となる。
内積を計算する角は、ベクトルvとpのなす角なので、pがsの左右どちらにあるかは問わない。

以上のことから、進行方向のベクトルvと、自身から見た相対的な着目点の位置ベクトルの内積が正なら着目点は前方に、負なら後方にあることになる(ゼロならば真横)。

    $$ {\bf v} \cdot ( {\bf p} - {\bf s} ) \left\{ \begin{align*} &> 0 \: \rightarrow \: {\rm front} \\ &= 0 \: \rightarrow \: {\rm side} \\ &< 0 \: \rightarrow \: {\rm behind} \end{align} \right. $$

左右の判定

方向ベクトルvを90度回転させた上で上記の前後判定を行うことで左右判定が可能になる。

ベクトルを90度回転させる方法はこちら

右へ回転させたベクトルに対して前方なら元の方向ベクトルの右、後方なら元の方向ベクトルの左と判定できる。

 

2つのベクトルが平行かどうか確かめる

2次元の場合

2次元の場合、2つのベクトルが平行かどうかを確かめるには、いずれか一方を90度回転させて、それが他のベクトルと直角であるかどうかを確かめるとよい(→ベクトルを90度回転させる方法)。

以下の2つのベクトルが平行かどうかを確認するには、

    $$ \begin{align*} {\boldsymbol u} = (u_x , u_y) \\ {\boldsymbol v} = (v_x , v_y) \end{align} $$

たとえば{\boldsymbol v}を90度回転させて内積がゼロかどうかを確認する。

    $$ (u_x , u_y) \cdot (v_y , -v_x) = 0? $$

なお、この式は、2つのベクトルの外積のx-y平面に垂直な成分(z成分)を計算していることになる。

    $$ {\boldsymbol u} \times {\boldsymbol v} = \left| \begin{array}{ccc} {\boldsymbol i} & {\boldsymbol j} & {\boldsymbol k} \\ u_x & u_y & u_z \\ v_x & v_y & v_z \end{array} \right| = (u_y v_z - u_z v_y , u_z v_x - u_x v_z , u_x v_y - u_y v_x) $$

この2次元の2つのベクトルの場合、外積の絶対値はz成分の大きさにほかならず、その値は\sin \thetaに対応することから、この値がゼロの場合は\theta = 0すなわち平行を意味する。

なお数値計算上は、内積値の絶対値がある小さな値より小さいかどうかを判定することになる。

一般的な方法

2つのベクトルが平行な時、そのなす角がゼロとなることから以下が成り立つ。

(1)    \begin{equation*} | {\boldsymbol a} \cdot {\boldsymbol b | = | {\boldsymbol a} | \cdot | {\boldsymbol b} | \cos \theta = | {\boldsymbol a} | \cdot | {\boldsymbol b} | \end{equation*}

この等式についても、小さな値との比較で判定する。

 

直角なベクトルを作り出す

下図のように互いに直交する2つのベクトルを考える。

math_linear_tool_1

これらのベクトルが直角であるためには、内積がゼロとなればよい。

    $$ {\bf v} \cdot {\bf u} = | {\bf v} | | {\bf u} | cos \frac{\pi}{2} = 0 $$

成分表示すれば

    $$ {\bf v} \cdot {\bf u} = v_x u_x + v_y u_y = 0 $$

これを満足する最もわかりやすいベクトル{\bf u}は、{\bf v}の要素を入れ替えて、何れか片方をマイナスとしたもの。

    $$ {\bf u} = (v_y , -v_x) \ {\rm or} \ (-v_y , v_x) $$

ここで要素を入れ替えた後のy成分をマイナスとしたベクトルは、元のベクトルを90度右に回転させたもので、x成分をマイナスとしたベクトルは、元のベクトルを90度左に回転させたもの。

math_linear_tool_right_angle2

これは回転行列を使って確かめることもできる。ただし以下の式で、+は左回り、-は右回りの回転であることに注意。

    $$ \left[ \begin{array}{rr} \cos \left( \pm \frac{\pi}{2} \right) & -\sin \left( \pm \frac{\pi}{2} \right)\\ \sin \left( \pm \frac{\pi}{2} \right) & \cos \left( \pm \frac{\pi}{2} \right) \end{array} \right] \left[ \begin{array}{c} v_x & v_y \end{array} \right] = \left[ \begin{array}{rr} 0 & \mp 1 \\ \pm 1 & 0 \end{array} \right] \left[ \begin{array}{c} v_x & v_y \end{array} \right] = \left[ \begin{array}{c} \mp v_y & \pm v_x \end{array} \right] $$