フーリエ変換のプログラム

質問

プログラム言語の種類は問いません。
入力数値データを読み込み(ファイルからでも直接入力によるものでもかまいません)、
フーリエ変換を行うプログラムの基本的な考え方を教えてください(プログラムそのものは求めません。考え方を教えてください)。
　しばらくの間フーリエ変換について勉強してはいるものの、まだよく理解していない状況ですし、プログラムに関してもまだまだ未熟者です。
しかし、どちらも勉強しながらこのプログラムを作ってみようと思っています。
　けれども、フーリエ変換の指数関数を用いた式だと虚数を扱わなければならないし、
sin, cosを使った式だと計算量が膨大になってしまいそうで(指数関数を用いた式でもそんなに変わらないとは思いますが)、
どこから手をつければよいかまったく見当がつきません。
考え方を教えていただければ結構ですので、よろしくお願いします。

回答No.2

noname#11476 · ベストアンサー

このスペースで全部をご説明するのはとても大変なので、

Numerical Recipies in C
ニューメリカルレシピ・イン・シー
～Ｃ言語による数値計算のレシピ～
ＩＳＢＮ４－８７４０８－５６０－１
技術評論社

という本をご紹介します。ちょっと高い（５，０００円）ですが、この手の数値計算の基礎はこの本が一つあれば十分まかなえるもので、Ｃ言語を対象とはしていますが、考え方を中心にまとめてありますので、どの言語でも使えます（事実この本は昔はfortranを対象としていた）。
基礎から実践的な方法までを詳しく解説してあり、この分野ではバイブルというべき本です。

ご質問のような、虚数の扱いをどうするのか、sin,cosの計算量をどうやって減らすのか（これには離散高速フーリエ変換：ＤＦＦＴがその解となります）など詳しく解説されいます。
サンプルプログラムまでついていますから、間違いなくプログラムが書けるところまで手ほどきしてくれる名著です。

では。

回答No.3

kei_

#2 さんの紹介している本は、英語版なら無料で公開してますよ。

FFT(Fast Fourier Transform) は Chap. 12,
その応用は Chap. 13 に書いてあります。

参考URL：

http://www.library.cornell.edu/nr/nr_index.cgi

回答No.1

ranx

大きな問題は分割して小さくしましょう。
基本中の基本です。
銀行のオンラインシステムでも、スペースシャトルの制御プログラムでも
そうやって作られています．．．多分。