3次元の点 $P(x,y,z)$ を回転した点を $P'(x',y',z')$ とします。$P$ を4元数 $p = w+ix+jy+kz$，$P'$ を $p' = w'+ix'+jy'+kz'$ に対応させます。$w, w'$ は任意の実数ですが，$w = w' = 0$ とすると計算が楽です。次の乗算で3次元の回転を表せます。

\[p' = qpq^{-1}\]

ここで

\[q = \cos\frac{\theta}{2}+(ia+jb+kc)\sin\frac{\theta}{2}\]

\[a^{2}+b^{2}+c^{2} = 1\]

$\boldsymbol{v} = (a,b,c)$ は回転軸で，$\theta$ は回転角です。なお，$\left|q\right|^{2} = 1$ なので $q^{-1} = \overline{q}$ になります。

思ったこと

独学するより授業で習ったほうが早いのウケるww でも社会に出たら授業なんて受けられないんですよね…(◞‸◟)

[ 2013/07/03 20 : 13 ] 数学系 | TB : 0 | CM : 0

フーリエ解析 2: C++ で高速フーリエ変換 (FFT)

1 まえがき

ブログの更新間隔は忙しさに比例する法則 (←経験則)。5月からアルバイトを始め、さらに同じく5月から外国語の文献を講読してスライドにまとめる必修科目に追われ、それ以外のことを何もしていませんでしたorz 久々のブログ更新です。

そろそろ高速フーリエ変換 (FFT) の自前ライブラリを用意しないとなぁ…と思っていました。しかし、FFT の原理は正直言ってまだ完全には理解していません。そのため、「高速フーリエ変換 C++」でググってみたのですが、すぐに理想的な実装が見つかりました。

c++で高速フーリエ変換, fft - yattの日記

めでたしめでたし。なのですが、とりあえず私も実装してみたいなぁと思って実装してみました。といっても、ほとんど上記ブログの実装と変わりありません。ついにネタ切れで他者ブログのパクりに走ってしまいましたorz 丸パクりだと意味がないので、自分なりに機能を追加しています。イテレータとコピーコンストラクタに対応しただけですけど。

2 フーリエ変換

2.1 フーリエ変換

フーリエ変換とは、複素関数 (または実関数) から別の複素関数への変換です。関数 $f: \mathbb{C} \to \mathbb{C}$ のフーリエ変換を $F: \mathbb{C} \to \mathbb{C}$ とすると、フーリエ変換は次の積分で表されます。ここで $i^{2}=-1$ です。

\[F\left(\omega\right) = \int_{-\infty}^{\infty}f\left(t\right)e^{-i\omega t}dt\]

フーリエ変換には逆変換 (フーリエ逆変換) が存在し、次の積分によって $F\left(\omega\right) $ から $f\left(t\right)$ を得ることができます。 (例外はありますが細かいことは気にしない。)

\[f\left(t\right) = \frac{1}{2\pi}\int_{-\infty}^{\infty}F\left(\omega\right)e^{i\omega t}d\omega\]

この演算にどんな意味があるかというと、例えば $f\left(t\right)$ が時間 $t$ の関数 (時系列信号) であれば、$F\left(\omega\right)$ は角周波数 $\omega$ の関数 (スペクトル) になります。

2.2 離散フーリエ変換

離散フーリエ変換 (DFT) とは、離散信号に対して行うフーリエ変換みたいなものです。

時系列信号 $f\left(t\right)$ のある時間区間 (半開区間) $\left[t_{0}, t_{0}+\Delta t\right) = \left\{t \mid t_{0} \le t < t_{0}+\Delta t\right\}$ 内の $N$ 点をサンプリングしたものを $x_{n}$ とします (ここで $n \in \left\{n \in \mathbb{N} \mid 0 \le n < N\right\}$)。

\[x_{n} = f\left(t_{0}+\frac{n}{N}\Delta t\right)\]

$x_{n}$ の離散フーリエ変換 $X_{k}$ は次のようになります (ここで $k \in \left\{k \in \mathbb{N} \mid 0 \le k < N\right\}$)。

\[X_{k} = \sum_{n=0}^{N-1}x_{n}\exp\left(-i\frac{2\pi}{N}kn\right)\]

離散フーリエ逆変換 (IDFT) は次のようになります (ここで $n \in \left\{n \in \mathbb{N} \mid 0 \le n < N\right\}$)。

\[x_{n} = \frac{1}{N}\sum_{k=0}^{N-1}X_{k}\exp\left(i\frac{2\pi}{N}kn\right)\]

2.3 高速フーリエ変換

高速フーリエ変換 (FFT) とは、離散フーリエ変換 (DFT) を高速に計算するアルゴリズムです。DFT の計算量は $O\left(N^{2}\right)$ となり、大きなデータに対しては非常に時間がかかります。FFT は計算手順を工夫することによって計算量を $O\left(N\log N\right)$ に下げました。ただし、FFT においては、サンプル点数 $N$ は 2 のべき乗に制限されます ($N \in \left\{2^{n} \mid n \in \mathbb{N}\right\}$)。

続き →

[ 2012/06/19 23 : 18 ] 数学系 | TB : 0 | CM : 0

自作問題1: 扇形

ケーキ作りの手伝いでボウルを見ていたら幾何学についての自作問題を思いつきました。LaTeX で書いた PDF ファイルをうpしました。

blog_20120328_0.pdf: PDF ファイル
blog_20120328_0.7z: LaTeX ソースファイル (7z アーカイブ)

なお、弧の記号を出す LaTeX コマンドは『弧ABを記号で表すTeXコマンド』 (よしいずの雑記帳さん) からお借りしました。

1 問題

半径 $r$ の円がある。この円の中心 $O$ から半直線が 2 本伸びている。それぞれの半直線と円の交点をそれぞれ $A$, $B$ とする。鋭角 $\angle AOB$ を $\theta$ とする ($0 < \theta < \pi$)。点 $O$ から線分 $\overline{AB}$ に垂線を引き、線分 $\overline{AB}$ と垂線との交点を $C$, 弧 $\stackrel{\Large\mbox{$\frown$}}{AB}$ と垂線との交点を $D$ とする。 (図1)