{"id":10538,"date":"2013-09-03T09:33:00","date_gmt":"2013-09-03T09:33:00","guid":{"rendered":"http:\/\/melotopia.net\/b\/?p=10538"},"modified":"2013-09-03T09:33:00","modified_gmt":"2013-09-03T09:33:00","slug":"%ec%88%98%ec%b9%98%ed%95%b4%ec%84%9d4-%eb%b9%a0%eb%a5%b8-%ed%91%b8%eb%a6%ac%ec%97%90-%eb%b3%80%ed%99%98","status":"publish","type":"post","link":"http:\/\/melotopia.net\/b\/?p=10538","title":{"rendered":"\uc218\uce58\ud574\uc11d4 – \ube60\ub978 \ud478\ub9ac\uc5d0 \ubcc0\ud658"},"content":{"rendered":"
\n
\n

\n \uc774 \uae00\uc740 \ub2e4\uc74c \uae00\uc744 \uc870\uae08 \ub354 \uace0\uccd0\uc11c \ub2e4\uc2dc \uc4f4 \uac83\uc774\ub2e4.
\n \n<\/p>\n

\n
\n http:\/\/snowall.tistory.com\/501
\n <\/a>\n<\/p>\n

\n \ud30c\uc774\uc36c \uad6c\ud604 \uc608\uc81c\ub294 \uc0dd\uac01\uc911\uc774\ub2e4.
\n \n<\/p>\n

\n \uc65c 4\ubc88\uc774 \uba3c\uc800 \uc62c\ub77c\uc654\ub290\ub0d0\ub294 \uc911\uc694\ud55c \ubb38\uc81c\uac00 \uc544\ub2c8\ub2e4. \ub098\ub3c4 \ubaa8\ub978\ub2e4.
\n \n<\/p>\n

\n\n<\/p>\n

\n # Elementary Numerical analysis 4
\n
\n # based on Python
\n
\n # (C) 2013. Keehwan Nam, Dept. of physics, KAIST.
\n
\n # snowall@gmail.com \/ snowall@kaist.ac.kr<\/p>\n

# Fast Fourier Transform<\/p>\n

# \ud478\ub9ac\uc5d0 \ubcc0\ud658\uc740 \uc801\ubd84\ubcc0\ud658\uc774\ub2e4. \ub2e4\uc2dc\ub9d0\ud574\uc11c, \uc801\ubd84\uc744 \uc798 \uc218\ud589\ud558\uba74 \ud478\ub9ac\uc5d0 \ubcc0\ud658\uc740 \uacc4\uc0b0\ub41c\ub2e4.<\/p>\n

# 0\ubd80\ud130 1\uae4c\uc9c0 \uad6c\uac04\ub9cc \uc0dd\uac01\ud574 \ubcf4\uc790.<\/p>\n

# F1(k) = Integrate f(x)cos(kx)dx from 0 to 1
\n
\n # F2(k) = Integrate f(x)sin(kx)dx from 0 to 1<\/p>\n

# \uc704\uc758 \ub450 \uc218\ub97c k\ub97c \uc815\ud574\ub193\uace0 \uc801\ubd84\ud558\uba74 \ub41c\ub2e4. \ud558\uc9c0\ub9cc \ud604\uc2e4\uc740 \uadf8\ub807\uac8c \ub9cc\ub9cc\ud558\uc9c0 \uc54a\uc740\ub370, 1\uac1c\uc758 k\uc5d0 \ub300\ud574\uc11c\ub9cc \ud478\ub9ac\uc5d0 \uacc4\uc218\ub97c \uad6c\ud558\ub294 \uac83\uc774 \uc544\ub2c8\ub77c, k\uc5d0 \ub300\ud55c \ud568\uc218\ub97c \uad6c\ud574\uc57c \ud558\ub294 \uc0ac\ud0dc\uac00 \ubc8c\uc5b4\uc9c0\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n

# \ub530\ub77c\uc11c, \ub2e4\uc74c\uacfc \uac19\uc774 \ud558\uc790. \uc870\uae08 \ubc14\uafbc\ub2e4.<\/p>\n

# F = F1+i*F2
\n
\n # \uc5ec\uae30\uc11c i\ub294 \uc81c\uacf1\ud558\uba74 -1\uc774 \ub098\uc624\ub294 \ud5c8\uc218 \ub2e8\uc704\uc774\ub2e4.
\n
\n # \uc774\ub807\uac8c \ub418\uba74 F\ub294 \uc624\uc77c\ub7ec \uacf5\uc2dd\uc744 \uc0ac\uc6a9\ud574\uc11c \ub2e4\uc74c\uacfc \uac19\uc774 \uc4f8 \uc218 \uc788\ub2e4.
\n
\n # F(k) = Integrate f(x)exp(ikx)dx from 0 to 1
\n
\n # \uc774\uc81c, \uc774 \ud568\uc218\ub97c \uc798 \uc801\ubd84\ud558\uba74 \ub418\ub294\ub370, \uc6b0\ub9ac\ub294 \uc9c0\uae08 \uc218\uce58\ud574\uc11d\uc744 \uacf5\ubd80\ud558\uace0 \uc788\uc73c\ubbc0\ub85c \uc218\uce58\uc801\uc73c\ub85c \uc801\ubd84\ud558\uba74 \ub41c\ub2e4.<\/p>\n

# 0\ubd80\ud130 1\uae4c\uc9c0\ub97c N\ub4f1\ubd84\ud558\uba74 dx = 1\/N\uc774\uace0 k\ub294 k\/N\ub85c \uc0dd\uac01\ud560 \uc218 \uc788\ub2e4.
\n
\n # F(k) = Summation f(x)exp(ikx\/N) over integer x from x = 0 to x = N
\n
\n # \uc704\uc758 \uacf5\uc2dd\uc744 \uc774\uc0b0 \ud478\ub9ac\uc5d0 \ubcc0\ud658Discrete Fourier Transform\uc774\ub77c\uace0 \ud55c\ub2e4.<\/p>\n

# N\ub4f1\ubd84\ub41c \uad6c\uac04\uc740 k\uac00 N\uac1c \uc788\uc73c\ubbc0\ub85c, N\uac1c\uc758 k\uac12\uc5d0 \ub300\ud55c \uac01\uac01\uc758 \ud568\uc218\ub97c \uacc4\uc0b0\ud558\uae30 \uc704\ud574\uc11c N\uac1c\uc758 \uac12\uc744 \ub354\ud574\uc57c \ud55c\ub2e4. \uc989, N*N\ubc88\uc758 \uacc4\uc0b0\uc774 \ud544\uc694\ud558\ub2e4.<\/p>\n

# \uc774\uc81c exp(ikx\/N)\uc744 \uc544\uc8fc \uc798 \uad00\ucc30\ud574\uc57c \ud55c\ub2e4.<\/p>\n

# f(x)exp(ikx\/N)\ub97c \uacc4\uc0b0\ud560 \ub54c, \uc798 \uad00\ucc30\ud574\ubcf4\uba74 \uac19\uc740 \uac12\ub4e4\uc774 \ubc18\ubcf5\ub418\ub294 \uac83\uc744 \uc54c \uc218 \uc788\ub2e4. k\uc5d0 \ub300\ud55c \uac12\uc744 \uacc4\uc0b0\ud55c \ud6c4 k+1\uc5d0 \ub300\ud55c \uac12\uc744 \uacc4\uc0b0\ud55c\ub2e4\uba74, f(x)exp(i(k+1)x\/N)=f(x)exp(ikx\/N)exp(ix\/N) \uc774\ub2e4.
\n
\n # http:\/\/snowall.tistory.com\/501
\n
\n # \uc774\uc81c, \uac00\ub839 \uc810\uc774 4\uac1c\ub9cc \uc788\ub2e4 \uce58\uace0, exp(ikx\/N)\uc744 \ub300\ucda9 \ud241\uccd0\uc11c w(k*x)\ub77c \uce58\uace0 \uadf8\ub0e5 \ub300\uc785\ud574\ubcf4\uc790.<\/p>\n

# F(0)=f(0)w(0)+f(1)w(1*0)+f(2)w(1*0)+f(3)w(1*0)
\n
\n # F(1)=f(0)w(0*1)+f(1)w(1*1)+f(2)w(2*1)+f(3)w(3*1)
\n
\n # F(2)=f(0)w(0*2)+f(1)w(1*2)+f(2)w(2*2)+f(3)w(3*2)
\n
\n # F(3)=f(0)w(0*3)+f(1)w(1*3)+f(2)w(2*3)+f(3)w(3*3)<\/p>\n

# \ubb54\uac00 \uc788\uc5b4 \ubcf4\uc778\ub2e4\uba74, \uacc4\uc0b0\uc744 \uc644\uc131\ud558\uc790.<\/p>\n

# F(0)=f(0)w(0)+f(1)w(0)+f(2)w(0)+f(3)w(0)
\n
\n # F(1)=f(0)w(0)+f(1)w(1)+f(2)w(2)+f(3)w(3)
\n
\n # F(2)=f(0)w(0)+f(1)w(2)+f(2)w(0)+f(3)w(2)
\n
\n # F(3)=f(0)w(0)+f(1)w(3)+f(2)w(2)+f(3)w(1)<\/p>\n

# \uc798 \ubcf4\uba74 \ubc18\ubcf5\ub418\ub294 \uac83\ub4e4\uc774 \ubcf4\uc778\ub2e4\ub294 \uc0ac\uc2e4\uc744 \uc54c \uc218 \uc788\ub2e4.
\n
\n # \ub530\ub77c\uc11c \ubc18\ubcf5\ub418\ub294 \ubd80\ubd84\uc744 \ubbf8\ub9ac \uacc4\uc0b0\ud558\uace0 \uc7ac\ud65c\uc6a9\ud558\uba74 \ub41c\ub2e4.<\/p>\n

# E1=f(0)w(0)+f(2)w(0)
\n
\n # E2=f(0)w(0)+f(2)w(2)
\n
\n # E3=f(1)w(0)+f(3)w(0)
\n
\n # E4=f(1)w(1)+f(3)w(3)<\/p>\n

# F(0)=E1+E3
\n
\n # F(1)=E2+E4
\n
\n # F(2)=E1+E3*w(2)
\n
\n # F(3)=E2+E4*w(2)<\/p>\n

# \uc6d0\ub798\ub294 16\ubc88\uc758 \uacf1\uc148\uacfc 12\ubc88\uc758 \ub367\uc148\uc774 \uc788\uc5c8\ub294\ub370, \uc798 \uace0\ucce4\ub354\ub2c8 10\ubc88\uc758 \uacf1\uc148\uacfc 8\ubc88\uc758 \ub367\uc148\uc73c\ub85c \uc904\uc5b4\ub4e4\uc5c8\ub2e4.
\n
\n # \ub9cc\uc57d \uc810\uc758 \uc218\uac00 \uc218\uc2ed\ub9cc\uac1c\ub85c \ub298\uc5b4\ub09c\ub2e4\uba74, \uc544\ub9c8 \uadf8 \ud6a8\uc728\uc740 \ub9e4\uc6b0 \uc88b\uc544\uc9c8 \uac83\uc774\ub2e4. \uc989 N*N\ubc88\uc758 \uc5f0\uc0b0\uc774 N*logN\ubc88\uc758 \uc5f0\uc0b0\uc73c\ub85c \ud655 \uc904\uc5b4\ub4e4\uac8c \ub41c\ub2e4.
\n
\n # \uc774 \uc54c\uace0\ub9ac\uc998\uc740 Cooley-Tukey \uc54c\uace0\ub9ac\uc998\uc758 \ud2b9\uc218\ud55c \uacbd\uc6b0\uc774\uba70, \uac00\uc6b0\uc2a4\uac00 \ucd5c\ucd08\uc5d0 \ubc1c\uacac\ud558\uace0 \ucfe8\ub9ac\uc640 \ud29c\ud0a4\uac00 \ub098\uc911\uc5d0 \ub2e4\uc2dc \ubc1c\uacac\ud588\ub2e4.
\n
\n # http:\/\/ko.wikipedia.org\/wiki\/\uace0\uc18d_\ud478\ub9ac\uc5d0_\ubcc0\ud658<\/p>\n

# \ud30c\uc774\uc36c \uad6c\ud604\uc740 \uc0dd\ub7b5\ud55c\ub2e4.<\/p>\n

# http:\/\/docs.scipy.org\/doc\/numpy\/reference\/routines.fft.html \ud30c\uc774\uc36c\uc5d0\uc11c\ub294 numpy \ud328\ud0a4\uc9c0\uc5d0\uc11c \uc81c\uacf5\ud55c\ub2e4.<\/p>\n

\n<\/p>\n

\n
\n
\n\"\uc2e0\uace0\"
\n<\/a>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

\uc774 \uae00\uc740 \ub2e4\uc74c \uae00\uc744 \uc870\uae08 \ub354 \uace0\uccd0\uc11c \ub2e4\uc2dc \uc4f4 \uac83\uc774\ub2e4. http:\/\/snowall.tistory.com\/501 \ud30c\uc774\uc36c \uad6c\ud604 \uc608\uc81c\ub294 \uc0dd\uac01\uc911\uc774\ub2e4. \uc65c 4\ubc88\uc774 \uba3c\uc800 \uc62c\ub77c\uc654\ub290\ub0d0\ub294 \uc911\uc694\ud55c \ubb38\uc81c\uac00 \uc544\ub2c8\ub2e4. \ub098\ub3c4 \ubaa8\ub978\ub2e4. # Elementary Numerical analysis 4 # based on Python # (C) 2013. Keehwan Nam, Dept. of physics, KAIST. # snowall@gmail.com \/ snowall@kaist.ac.kr # Fast Fourier Transform # \ud478\ub9ac\uc5d0 \ubcc0\ud658\uc740 \uc801\ubd84\ubcc0\ud658\uc774\ub2e4. \ub2e4\uc2dc\ub9d0\ud574\uc11c, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2],"tags":[],"class_list":["post-10538","post","type-post","status-publish","format-standard","hentry","category-academic"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8o6gA-2JY","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/posts\/10538","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10538"}],"version-history":[{"count":0,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=\/wp\/v2\/posts\/10538\/revisions"}],"wp:attachment":[{"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10538"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10538"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/melotopia.net\/b\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10538"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}