読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

複素数(complex number)

平面幾何の(競技)プログラミングをするとき、2次元ベクトルの代わりとして使えるので便利。
C++ならstd::complexをtypedefしときゃ、演算子を定義する手間が省ける。
回転変換なども、回転の1次変換を暗記しておくより、複素数極形式で考える方がわかりやすいと思う。

基本性質

  •  z = x + iy
  •  |z| = \sqrt{x^2 + y^2}
  •  |z|^2 = z\bar{z}
  •  {\rm Re}(z) = \frac{1}{2}(z+\bar{z})
  •  {\rm Im}(z) = \frac{1}{2i}(z-\bar{z})
  • (拡張)三角不等式 |\sum_i z_i| \leq \sum_i |z_i|
  •  |z_1z_2|=|z_1||z_2| \arg z_1z_2 = \arg z_1 + \arg z_2
  •  |\frac{z_1}{z_2}|=\frac{|z_1|}{|z_2|} \arg \frac{z_1}{z_2} = \frac{\arg z_1}{\arg z_2}

オイラーの公式(Euler's formula)

  •  z = x + iy = |z|(\cos \theta + i \sin \theta ) = |z|e^{i\theta} \theta = \arg{z} = \tan^{-1}\frac{y}{x} + 2n\pi
    •  |e^{i\theta}| = 1

 z e^{i\theta}= (x + iy)e^{i\theta} = (x+iy)(\cos \theta + i\sin \theta) = (x\cos \theta - y\sin \theta)+i(x\sin \theta + y\cos \theta)なので、回転の1次変換が
 \left[ \begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]
で表せることがわかる。
特に i = (\cos \frac{\pi}{2} + i\sin \frac{\pi}{2}) = e^{i\frac{\pi}{2}} zi = |z|e^{i(\arg z + \frac{\pi}{2})} = (x+iy)i = -y + ixなので、
 [ x, y ]^Tの正規化法線ベクトルは \pm \frac{1}{\sqrt{x^2 + y^2}}[-y, x]^T

ド・モアブルの定理(de Moivre's formula)

  •  z^n = |z|^n (\cos n\theta + i\sin n\theta) = |z|^n e^{in\theta}

1のn乗根

  • 1のn乗根 z = (\cos \frac{2k\pi}{n} + i \sin \frac{2k\pi}{n}) = e^i(\frac{2k\pi}{n}) 0\leq k < n

(証明)
 z^n = 1 より |z|^n = 1
 z = e^{i\theta}とおけば、ド・モアブルの定理より
 z^n = e^{in\theta} = (\cos n\theta + i \sin n \theta) = 1
従って、 n\theta = k 2\pi
よって、 \theta = \frac{2k\pi}{n}
 k=1,2, \cdots, n-1 k=nのとき、 e^{i0} = e^{i2\pi}となってループするため) (証明終わり)
特に1の3乗根は \omega = 1, \frac{-1\pm\sqrt{3}i}{2}
1の n乗根 \xi_n^0=1, \xi_n^1, \xi_n^2, \cdots , \xi_n^{n-1}は、
複素平面での単位円上の点で、1を頂点の一つとして持ち、正 n角形を形成する。なので、

  •  \sum_{j=0}^{n-1}\xi_n^j
  • 1の原始 n乗根(primitive root) :自然数 nに対し m(< n)乗しても決して 1 にならず、n 乗して初めて 1 になるような 1の累乗根
  •  \xi_n ^ kが1の原始 n乗根⇔ \gcd(n, k)=1すなわち n,kは互いに素
  • 1の原始 n乗根の数 =  \phi (n)(1から nまでの自然数 nと互いに素であるものの数) ( \phi(n)オイラー関数)

1の原始 n乗根の一つを \xiとすると、

  •  \sum_{j=0}^{n-1}\xi^j = 1

複素関数(complex function)