kanetaiの二次記憶装置

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

複素数(complex number)

Math

平面幾何の(競技)プログラミングをするとき、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)はオイラー関数)

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

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

複素関数(complex function)