Sep 13, 2012

ทำ Recursion บนการ Integral

ฟังก์ชัน factorial นั้นมีนิยามง่ายๆ ตรงไปตรงมาคือ ผลคูณของจำนวนเต็มบวกตั้งแต่ 1 ไปจนถึง n
factorial n = product [1..n]
ซึ่งถ้าสังเกตดูซักหน่อย จะพบว่ามันสามารถเขียนนิยามเป็น recursion ได้
factorial 1 = 1
factorial n = n * factorial (n - 1)
ตอนนี้เราอาจเพิ่มนิยามที่ว่า 0! = 1 เพื่อความสะดวกในการกระจายพจน์สำหรับคำนวณความน่าจะเป็น

แต่ทั้งหมดนี้จะมีปัญหาอยู่อย่างนึง ตรงที่ทุกอย่างเป็น discrete math หมดเลย นั่นคือเราไม่สามารถหาอะไรอย่าง 0.5! ได้

ถ้าดูจากที่มาและการใช้งานของมัน (ส่วนมากเป็นเรื่องความน่าจะเป็นนั่นแหละ) ก็อาจนับว่าไม่มีปัญหา แต่สำหรับ pure math แล้ว มันก็น่าจะมีอะไรซักอย่างมาตอบคำถามตรงนี้ได้นะ



โชคดี (?) ที่เรามีเลขมหัศจรรย์อย่าง e ซึ่งมีสมบัติประหลาดอย่าง
e^x = d/dx e^x
ดูๆ ไปแล้ว มันก็คล้ายกับ fixed-point combinator ที่เคยพูดไว้ในตอนก่อนๆ เพียงแต่เปลี่ยนจาก function call เป็นการ diff-integral แทน โดยมี terminate point อย่าง
integral 1/e^x dx from 0 to infinity = - 1/e^infinity + 1/e^0
                                     = 1
นี่ทำให้เราสามารถเขียน recursion ในรูปของ integral ได้ เช่น
Gamma(n) = integral 1/e^t t^(n-1) dt from 0 to infinity
ลองดูสมบัติของมันโดยทำการ integral เข้าไป จะได้ว่า
Gamma(n) = integral 1/e^t t^(n-1) dt from 0 to infinity
         = integral u dv from 0 to infinity            ; let u = 1/e^t, dv = t^(n-1) dt
         = (limit u*v for x from 0 to infinity) - integral v du from 0 to infinity
         = (1/n)(1/e^infinity infinity^n - 1/e^0 0^n) - integral v du from 0 to infinity
         = 0 - integral v du from 0 to infinity
         = (1/n) integral 1/e^t t^n dt from 0 to infinity
         = Gamma(n+1)/n
ดังนั้น จะเห็นว่า
Gamma(1) = 1
Gamma(n) = (n-1) * Gamma(n-1) = (n-1)(n-2) * Gamma(n-2) = ...
ซึ่งก็คือ
factorial(n) = Gamma(n+1)


ถึงตอนนี้ก็คงตอบคำถามได้แล้วว่า 0.5! นั้น สามารถหาค่าได้จาก
Gamma(3/2) = (1/2) * Gamma(1/2)

Gamma(1/2) = integral 1/e^t 1/sqrt(t) dt from 0 to infinity
           = 2 * integral 1/e^u^2 du from 0 to infinity      ; let du = 1/sqrt(t)
           = integral 1/e^u^2 du from -infinity to infinity
           = sqrt(pi)

Gamma(3/2) = sqrt(pi)/2
ตอนพยายามหาค่าของ Gamma(1/2) ต้องใช้ความรู้เรื่อง double integral และการแปลงระนาบเข้าช่วย ลองศึกษาเทคนิคที่นี่

ข้อดีของการเขียนในรูป integral นี่มีอีกอย่าง คือถ้ารู้สึกว่าพิสูจน์ห่าค่าตรงๆ แบบนี้มันยากไป จะเลี่ยงไปใช้ Riemann integral เพื่อประมาณค่าแทนก็ย่อมได้ครับ