Quod Erat Demonstrandum

2009/03/29

大數值的乘階

中四同學在學期初已接觸乘階(factorial) n! 的運算。比如

1! = 1
2! = 1 \times 2 = 2
3! = 1 \times 2 \times 3 = 6
4! = 1 \times 2 \times 3 \times 4 = 24

理論上,這個正整數 n,可以「要幾大,有幾大」;但實際上,我們日常接觸的運算工具,必有其限制;用 EXCEL 2003,只可以算出的最大乘階是

170! \approx 7.2574 \times 10^{306}

這個數字有多大?嗯,據聞太陽壽命還有 50 億年,而 50 億,不過是 5 \times 10^9 而已。

普通的科學計算機有「乘階按鈕」,要算出比如 4!,一按便可。想像一下「乘階按鈕」壞了,我們也可乖乖地按「乘號鍵」。問題是,如果要計算大數目的乘階,比如 170!,我們豈不是要按「乘號鍵」勁多次,以致連「乘號鍵」也可能按壞?(這不過是為了戲劇效果而說的,在生活上,有誰無聊到要計算 170!?數佬唔好呃學生啦!)

原來我們有 Stirling 公式:

\sqrt{2\pi n}(\frac{n}{e})^n

作為大數值乘階 n! 的「近似值」(漸近公式)。

當中的 e 就是歐拉常數(Euler’s number),中六七的同學不會對它陌生,它的數值約為 e \approx 2.718281828。千萬不要誤以為這個是循環小數,可以證明,它是無理數。

略略用 EXCEL 進行探究(時興用語),見下表

20090304gif01

在上表中,大家可以看到:縱使對比較小的 n 值,Stirling 公式也似乎不錯

1! = 1 \approx 0.922137009
2! = 2 \approx 1.919004351
3! = 6 \approx 5.826209591
4! = 24 \approx 23.50617513

隨著 n 值愈來愈大,Stirling 公式得出的數值,我不敢說是愈來愈接近真的 n!,但起碼 [\sqrt{2\pi n}(\frac{n}{e})^n] 和 n! 在數字的位數上(number of digits)似乎是完全吻合。

這裡,我希望用最粗糙的方式介紹 Stirling 公式的來歷。

修應用數學的同學,翻查標準常態表(Standard Normal Table)也會看到

A(z) = \int_0^{z}\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}dx

當明白概率密度函數(probability density function)的意義,立即知

\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}dx = 1

\int_{-\infty}^{\infty}e^{-\frac{x^2}{2}}dx = \sqrt{2\pi} – – – – – – (1)

好了,修純數的同學,做積分的習題時,遇然也會遇上伽瑪(Gamma)函數,即

\Gamma(\alpha) = \int_{0}^{\infty} x^{\alpha - 1}e^{-x}dx – – – – – – (2)
(其中 \alpha > 0)

如果我們代 \alpha 為正整數 n,我們不難得出

\Gamma(n) = (n - 1)! – – – – – – (3)

(不過是運用 integration by parts,修純數的同學,試證之。這個伽瑪函數,某程度上是乘階的推廣,比如在上式「老屈」n = 1.5,我們「彷彿」看到 0.5! 的意義不過是 \Gamma(1.5)

好了,要得出 Stirling 公式,其中一個方法,就是把 (1),(2) 兩式扯上關係。

\beta = \alpha - 1,則 (2) 式變成

\Gamma(\alpha)
= \int_{0}^{\infty} x^{\beta}e^{-x}dx
= \int_{0}^{\infty} e^{\beta\ln x - x}dx
= \int_{-\beta}^{\infty} e^{\beta\ln(\beta + y) - (\beta + y)}dy〔這裡代入 x = \beta + y
= \int_{-\beta}^{\infty} e^{\beta(\ln\beta + \ln(1 + \frac{y}{\beta})) - (\beta + y)}dy

好了,係時候用「矛招」。修應用數學的同學,對下式不會陌生:

\ln(1 + u) = u - \frac{u^2}{2} + \frac{u^3}{3} - \dots + \frac{(-1)^{r-1}u^r}{r} + \dots

由上式,非常「老屈」地,我寫出以下關係:

\ln(1 + \frac{y}{\beta}) \approx \frac{y}{\beta} - \frac{y^2}{2\beta^2},於是我們得出

\Gamma(\alpha)
\approx \int_{-\beta}^{\infty} e^{\beta\ln\beta + \beta(\frac{y}{\beta} - \frac{y^2}{2\beta^2}) - (\beta + y)}dy
= e^{\beta\ln\beta - \beta}\int_{-\beta}^{\infty}e^{-\frac{y^2}{2\beta}}dy
= (\frac{\beta}{e})^{\beta}\int_{-\beta}^{\infty}e^{-\frac{y^2}{2\beta}}dy

想像一下,當 \alpha 很大,即 \beta 也大。比較一下 (1) 式,我們可以「感受」到

\int_{-\beta}^{\infty}e^{-\frac{y^2}{2\beta}}dy \approx \sqrt{2\pi\beta}

從而叫我們可以「感受」到

\Gamma(\alpha)
\approx (\frac{\beta}{e})^{\beta}\sqrt{2\pi\beta}

\alpha = n + 1,即 \beta = n,由 (3),得

n! \approx (\frac{n}{e})^n\sqrt{2\pi n}

Striling 公式是也!

上述所謂證明是非常不嚴謹,起碼在取極限的情況交代得極度含糊,似乎是憑「感覺」而已!證明過程應該要有 dominated convergence theorem 來確保極限符號可以走進去積分符號內…(這句也算是不夠嚴謹的一句,高手可指正)要看清楚初等證明,可繼續點撃:

http://johnng.inscyber.net/Stirling.pdf

[SBA 時間]

1. 修純數的同學,上述是對乘階的較精確估計,在課程內的習題中,我們也曾對 n! 的上下限作估計,情況如下:考慮(比方說)f(x) = \ln x 的遞增性(increasing),不難得出以下關係

\ln(n - 1)! < \int_1^n \ln tdt < \ln n!

從而有

(n - 1)! < e^{n\ln n - n + 1} < n!

再推一推,有

e(\frac{n}{e})^n < n! < ne(\frac{n}{e})^n

也可作為 n! 的極度粗糙的近似。同學,嘗試補充上述式子與式子間的步驟。

2. 和乘階關係密切的二項係數(binomial coefficient),運用 Stirling’s formula,當然可以找到計算它「較準確」的漸近公式。但用中學數學知識,也可粗略估計出二項係數的上下限,比如

\frac{4^n}{2n + 1} \le _{2n}C_{n} \le 2(n^n)

中學同學,試使出你的渾身解「數」,證明上式成立。

6 則迴響 »

  1. 老師:
    我是5D班某位應屆會考生, 希望升上中六後能夠自修Applied Maths
    雖然我的成績不算是頂尖 但我對數學非常有興趣 又不想放棄 Chem
    (為了興趣而去自修一科, 說起來很傻吧~)
    想詢問您一些問題 希望老師解答:
    1,只能修AS嗎?
    2,會考成績要達到甚麼水準, 校方才會考慮給我自修?
    3,最遲甚麼時間告知校方, 我想自修Applied Maths?
    謝謝老師

    迴響 由 Patrick Wong — 2009/03/30 @ 10:04 上午 | 回覆

  2. Hi Patrick

    >1,只能修AS嗎?
    不一定,上年有學生自修 AL 及 AS。

    >2,會考成績要達到甚麼水準, 校方才會考慮給我自修?
    先決條件,當然數學成績要優異。

    >3,最遲甚麼時間告知校方, 我想自修Applied Maths?
    最好在中六上學期初去信校方申請。

    迴響 由 johnmayhk — 2009/03/30 @ 2:14 下午 | 回覆

  3. 早前做stat的功課,其中有一個習題是要我們用Central Limit Theorem證明Stirling’s formula

    迴響 由 Justin — 2009/12/17 @ 2:07 下午 | 回覆

  4. In the assignment, we are required to use exponential distribution exp(1) in stead of Poisson.

    迴響 由 Justin — 2009/12/18 @ 12:15 下午 | 回覆

  5. […] Stirling 公式,對大數值 ,我們有 […]

    通告 由 俄羅斯方塊帶給我們的生命教育… « Quod Erat Demonstrandum — 2010/01/01 @ 12:39 上午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: