ทฤษฎีบทสังวัตนาการ

ทฤษฎีบทสังวัตนาการ (convolution theorem) เป็นทฤษฎีบทที่กล่าวว่าการแปลงฟูรีเย ของฟังก์ชันสังวัตนาการจะเท่ากับผลคูณของการแปลงฟูรีเย กล่าวคือ สังวัตนาการในโดเมนหนึ่งสอดคล้องกับผลคูณในอีกโดเมนหนึ่ง เช่น สังวัตนาการในโดเมนเวลาสอดคล้องกับผลคูณในโดเมนความถี่

${\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}$

โดยในที่นี้ ${\mathcal {F}}(f)$ แทนการแปลงฟูรีเยของ f และในทางกลับกันก็จะได้ว่า

${\mathcal {F}}\{f\cdot g\}={\mathcal {F}}\{f\}*{\mathcal {F}}\{g\}$

และก็ใช้กับการแปลงฟูรีเยผกผันได้ ${\mathcal {F}}^{-1}$ ได้เช่นกัน

$f*g={\mathcal {F}}^{-1}{\big \{}{\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}{\big \}}$

ทฤษฎีบทนี้ยังใช้ได้กับการแปลงอีกหลายแบบ ได้แก่ การแปลงลาปลัส, การแปลงลาปลัสสองทาง, การแปลง Z, การแปลงเมลลิน และ การแปลงฮาร์ตลีย์

ในการวิเคราะห์ฮาร์มอนิก ทฤษฎีบทนี้สามารถนำไปประยุกต์ใช้กับการแปลงฟูรีเยที่กำหนดบนอาบีเลียนกรุปแบบจำกัดได้อีกด้วย

ทฤษฎีบทสังวัตนาการสามารถใช้เพื่อลดความซับซ้อนของการคำนวณได้ เช่น สำหรับการคำนวณลำดับยาว $n$ หากคำนวณตามคำจำกัดความของสังวัตนาการแล้วจะต้องทำการคำนวณทั้งหมด $2n-1$ คู่ ดังนั้นความซับซ้อนในการคำนวณของการคูณจะเป็น ${\mathcal {O}}(n^{2})$ แต่ถ้าแปลงลำดับไปเป็นโดเมนความถี่โดยใช้การแปลงฟูรีเยแล้ว ก็แค่นำมาคูณกันเท่านั้น เมื่อรวมการคำนวณการแปลงฟูรีเยแบบเร็วแล้ว ความซับซ้อนในการคำนวณทั้งหมดเป็น ${\mathcal {O}}(n\log n)$

พิสูจน์

ให้ $f$ และ $g$ อยู่ในปริภูมิ L¹(Rⁿ) แล้วให้ $F$ เป็นผลการแปลงฟูรีเยของ $f$ ส่วน $G$ เป็นผลการแปลงฟูรีเยของ $g$

$F(\nu )={\mathcal {F}}\{f\}=\int _{\mathbb {R} ^{n}}f(x)e^{-2\pi ix\cdot \nu }\,\mathrm {d} x$

$G(\nu )={\mathcal {F}}\{g\}=\int _{\mathbb {R} ^{n}}g(x)e^{-2\pi ix\cdot \nu }\,\mathrm {d} x,$

โดยที่จุดระหว่าง x และ ν แสดงถึงผลคูณภายในบน Rⁿ

$h(z)=\int \limits _{\mathbb {R} }f(x)g(z-x)\,\mathrm {d} x$

แล้วจะได้ว่า

$\int \!\!\int |f(z)g(x-z)|\,dx\,dz=\int |f(z)|\int |g(z-x)|\,dx\,dz=\int |f(z)|\,\|g\|_{1}\,dz=\|f\|_{1}\|g\|_{1}.$

ดังนั้นตามทฤษฎีบทของฟูบีนี จะได้ว่า $h\in L^{1}(\mathbb {R} ^{n})$ ดังนั้นการแปลงฟูรีเย $H$ จึงได้จากนิยามโดยการคำนวณปริพันธ์เป็น

${\begin{aligned}H(\nu )={\mathcal {F}}\{h\}&=\int _{\mathbb {R} }h(z)e^{-2\pi iz\cdot \nu }\,dz\\&=\int _{\mathbb {R} }\int _{\mathbb {R} ^{n}}f(x)g(z-x)\,dx\,e^{-2\pi iz\cdot \nu }\,dz.\end{aligned}}$

จะเห็นว่า $|f(x)g(z-x)e^{-2\pi iz\cdot \nu }|=|f(x)g(z-x)|$ ดังนั้นเราสามารถนำทฤษฎีบทของฟูบินีมาใช้กับตัวแปรข้างต้นได้อีกครั้ง (กล่าวคือ สลับลำดับการหาปริพันธ์)

$H(\nu )=\int _{\mathbb {R} }f(x)\left(\int _{\mathbb {R} ^{n}}g(z-x)e^{-2\pi iz\cdot \nu }\,dz\right)\,dx.$

แทนค่า $y=z-x$ - $dy=dz$

$H(\nu )=\int _{\mathbb {R} }f(x)\left(\int _{\mathbb {R} }g(y)e^{-2\pi i(y+x)\cdot \nu }\,dy\right)\,dx$

$=\int _{\mathbb {R} }f(x)e^{-2\pi ix\cdot \nu }\left(\int _{\mathbb {R} }g(y)e^{-2\pi iy\cdot \nu }\,dy\right)\,dx$

$=\int _{\mathbb {R} }f(x)e^{-2\pi ix\cdot \nu }\,dx\int _{\mathbb {R} }g(y)e^{-2\pi iy\cdot \nu }\,dy$

ปริพันธ์ของทั้งสองก้อนนี้ก็คือ $F(\nu )$ และ $G(\nu )$ ดังนั้นได้ว่า

$H(\nu )=F(\nu )\cdot G(\nu )$