《蒙卡特羅方法》PPT課件.ppt

第一章蒙特卡羅方法概述 蒙特卡羅方法的基本思想蒙特卡羅方法的收斂性 誤差蒙特卡羅方法的特點蒙特卡羅方法的主要應(yīng)用范圍作業(yè) 第一章蒙特卡羅方法概述 蒙特卡羅方法又稱隨機抽樣技巧或統(tǒng)計試驗方法 半個多世紀(jì)以來 由于科學(xué)技術(shù)的發(fā)展和電子計算機的發(fā)明 這種方法作為一種獨立的方法被提出來 并首先在核武器的試驗與研制中得到了應(yīng)用 蒙特卡羅方法是一種計算方法 但與一般數(shù)值計算方法有很大區(qū)別 它是以概率統(tǒng)計理論為基礎(chǔ)的一種方法 由于蒙特卡羅方法能夠比較逼真地描述事物的特點及物理實驗過程 解決一些數(shù)值方法難以解決的問題 因而該方法的應(yīng)用領(lǐng)域日趨廣泛 蒙特卡羅方法的基本思想 二十世紀(jì)四十年代中期 由于科學(xué)技術(shù)的發(fā)展和電子計算機的發(fā)明 蒙特卡羅方法作為一種獨立的方法被提出來 并首先在核武器的試驗與研制中得到了應(yīng)用 但其基本思想并非新穎 人們在生產(chǎn)實踐和科學(xué)試驗中就已發(fā)現(xiàn) 并加以利用 兩個例子例1 蒲豐氏問題例2 射擊問題 打靶游戲 基本思想計算機模擬試驗過程 例1 蒲豐氏問題 為了求得圓周率 值 在十九世紀(jì)后期 有很多人作了這樣的試驗 將長為2l的一根針任意投到地面上 用針與一組相間距離為2a l a 的平行線相交的頻率代替概率P 再利用準(zhǔn)確的關(guān)系式 求出 值其中 為投計次數(shù) n為針與平行線相交次數(shù) 這就是古典概率論中著名的蒲豐氏問題 一些人進行了實驗 其結(jié)果列于下表 例2 射擊問題 打靶游戲 設(shè)r表示射擊運動員的彈著點到靶心的距離 r 表示擊中r處相應(yīng)的得分?jǐn)?shù) 環(huán)數(shù) f r 為該運動員的彈著點的分布密度函數(shù) 它反映運動員的射擊水平 該運動員的射擊成績?yōu)橛酶怕收Z言來說 是隨機變量 r 的數(shù)學(xué)期望 即 現(xiàn)假設(shè)該運動員進行了 次射擊 每次射擊的彈著點依次為r1 r2 rN 則 次得分g r1 g r2 g rN 的算術(shù)平均值代表了該運動員的成績 換言之 為積分的估計值 或近似值 在該例中 用 次試驗所得成績的算術(shù)平均值作為數(shù)學(xué)期望的估計值 積分近似值 基本思想 由以上兩個例子可以看出 當(dāng)所求問題的解是某個事件的概率 或者是某個隨機變量的數(shù)學(xué)期望 或者是與概率 數(shù)學(xué)期望有關(guān)的量時 通過某種試驗的方法 得出該事件發(fā)生的頻率 或者該隨機變量若干個具體觀察值的算術(shù)平均值 通過它得到問題的解 這就是蒙特卡羅方法的基本思想 當(dāng)隨機變量的取值僅為1或0時 它的數(shù)學(xué)期望就是某個事件的概率 或者說 某種事件的概率也是隨機變量 僅取值為1或0 的數(shù)學(xué)期望 因此 可以通俗地說 蒙特卡羅方法是用隨機試驗的方法計算積分 即將所要計算的積分看作服從某種分布密度函數(shù)f r 的隨機變量 r 的數(shù)學(xué)期望通過某種試驗 得到 個觀察值r1 r2 rN 用概率語言來說 從分布密度函數(shù)f r 中抽取 個子樣r1 r2 rN 將相應(yīng)的 個隨機變量的值g r1 g r2 g rN 的算術(shù)平均值作為積分的估計值 近似值 為了得到具有一定精確度的近似解 所需試驗的次數(shù)是很多的 通過人工方法作大量的試驗相當(dāng)困難 甚至是不可能的 因此 蒙特卡羅方法的基本思想雖然早已被人們提出 卻很少被使用 本世紀(jì)四十年代以來 由于電子計算機的出現(xiàn) 使得人們可以通過電子計算機來模擬隨機試驗過程 把巨大數(shù)目的隨機試驗交由計算機完成 使得蒙特卡羅方法得以廣泛地應(yīng)用 在現(xiàn)代化的科學(xué)技術(shù)中發(fā)揮應(yīng)有的作用 計算機模擬試驗過程 計算機模擬試驗過程 就是將試驗過程 如投針 射擊 化為數(shù)學(xué)問題 在計算機上實現(xiàn) 以上述兩個問題為例 分別加以說明 例1 蒲豐氏問題例2 射擊問題 打靶游戲 由上面兩個例題看出 蒙特卡羅方法常以一個 概率模型 為基礎(chǔ) 按照它所描述的過程 使用由已知分布抽樣的方法 得到部分試驗結(jié)果的觀察值 求得問題的近似解 例 蒲豐氏問題 設(shè)針投到地面上的位置可以用一組參數(shù) x 來描述 x為針中心的坐標(biāo) 為針與平行線的夾角 如圖所示 任意投針 就是意味著x與 都是任意取的 但x的范圍限于 0 a 夾角 的范圍限于 0 在此情況下 針與平行線相交的數(shù)學(xué)條件是 針在平行線間的位置 如何產(chǎn)生任意的 x x在 0 a 上任意取值 表示x在 0 a 上是均勻分布的 其分布密度函數(shù)為 類似地 的分布密度函數(shù)為 因此 產(chǎn)生任意的 x 的過程就變成了由f1 x 抽樣x及由f2 抽樣 的過程了 由此得到 其中 1 2均為 0 1 上均勻分布的隨機變量 每次投針試驗 實際上變成在計算機上從兩個均勻分布的隨機變量中抽樣得到 x 然后定義描述針與平行線相交狀況的隨機變量s x 為如果投針 次 則是針與平行線相交概率 的估計值 事實上 于是有 例 射擊問題 設(shè)射擊運動員的彈著點分布為用計算機作隨機試驗 射擊 的方法為 選取一個隨機數(shù) 按右邊所列方法判斷得到成績 這樣 就進行了一次隨機試驗 射擊 得到了一次成績 r 作 次試驗后 得到該運動員射擊成績的近似值 蒙特卡羅方法的收斂性 誤差 蒙特卡羅方法作為一種計算方法 其收斂性與誤差是普遍關(guān)心的一個重要問題 收斂性誤差減小方差的各種技巧效率 收斂性 由前面介紹可知 蒙特卡羅方法是由隨機變量X的簡單子樣X1 X2 XN的算術(shù)平均值 作為所求解的近似值 由大數(shù)定律可知 如X1 X2 XN獨立同分布 且具有有限期望值 E X 則即隨機變量X的簡單子樣的算術(shù)平均值 當(dāng)子樣數(shù) 充分大時 以概率1收斂于它的期望值E X 誤差 蒙特卡羅方法的近似值與真值的誤差問題 概率論的中心極限定理給出了答案 該定理指出 如果隨機變量序列X1 X2 XN獨立同分布 且具有有限非零的方差 2 即f X 是X的分布密度函數(shù) 則 當(dāng)N充分大時 有如下的近似式其中 稱為置信度 1 稱為置信水平 這表明 不等式近似地以概率1 成立 且誤差收斂速度的階為 通常 蒙特卡羅方法的誤差 定義為上式中與置信度 是一一對應(yīng)的 根據(jù)問題的要求確定出置信水平后 查標(biāo)準(zhǔn)正態(tài)分布表 就可以確定出 下面給出幾個常用的 與的數(shù)值 關(guān)于蒙特卡羅方法的誤差需說明兩點 第一 蒙特卡羅方法的誤差為概率誤差 這與其他數(shù)值計算方法是有區(qū)別的 第二 誤差中的均方差 是未知的 必須使用其估計值來代替 在計算所求量的同時 可計算出 減小方差的各種技巧 顯然 當(dāng)給定置信度 后 誤差 由 和N決定 要減小 或者是增大N 或者是減小方差 2 在 固定的情況下 要把精度提高一個數(shù)量級 試驗次數(shù)N需增加兩個數(shù)量級 因此 單純增大N不是一個有效的辦法 另一方面 如能減小估計的均方差 比如降低一半 那誤差就減小一半 這相當(dāng)于N增大四倍的效果 因此降低方差的各種技巧 引起了人們的普遍注意 后面課程將會介紹一些降低方差的技巧 效率 一般來說 降低方差的技巧 往往會使觀察一個子樣的時間增加 在固定時間內(nèi) 使觀察的樣本數(shù)減少 所以 一種方法的優(yōu)劣 需要由方差和觀察一個子樣的費用 使用計算機的時間 兩者來衡量 這就是蒙特卡羅方法中效率的概念 它定義為 其中c是觀察一個子樣的平均費用 顯然越小 方法越有效 蒙特卡羅方法的特點 優(yōu)點能夠比較逼真地描述具有隨機性質(zhì)的事物的特點及物理實驗過程 受幾何條件限制小 收斂速度與問題的維數(shù)無關(guān) 具有同時計算多個方案與多個未知量的能力 誤差容易確定 程序結(jié)構(gòu)簡單 易于實現(xiàn) 缺點收斂速度慢 誤差具有概率性 在粒子輸運問題中 計算結(jié)果與系統(tǒng)大小有關(guān) 能夠比較逼真地描述具有隨機性質(zhì)的事物的特點及物理實驗過程 從這個意義上講 蒙特卡羅方法可以部分代替物理實驗 甚至可以得到物理實驗難以得到的結(jié)果 用蒙特卡羅方法解決實際問題 可以直接從實際問題本身出發(fā) 而不從方程或數(shù)學(xué)表達(dá)式出發(fā) 它有直觀 形象的特點 受幾何條件限制小 在計算s維空間中的任一區(qū)域Ds上的積分時 無論區(qū)域Ds的形狀多么特殊 只要能給出描述Ds的幾何特征的條件 就可以從Ds中均勻產(chǎn)生N個點 得到積分的近似值 其中Ds為區(qū)域Ds的體積 這是數(shù)值方法難以作到的 另外 在具有隨機性質(zhì)的問題中 如考慮的系統(tǒng)形狀很復(fù)雜 難以用一般數(shù)值方法求解 而使用蒙特卡羅方法 不會有原則上的困難 收斂速度與問題的維數(shù)無關(guān) 由誤差定義可知 在給定置信水平情況下 蒙特卡羅方法的收斂速度為 與問題本身的維數(shù)無關(guān) 維數(shù)的變化 只引起抽樣時間及估計量計算時間的變化 不影響誤差 也就是說 使用蒙特卡羅方法時 抽取的子樣總數(shù)N與維數(shù)s無關(guān) 維數(shù)的增加 除了增加相應(yīng)的計算量外 不影響問題的誤差 這一特點 決定了蒙特卡羅方法對多維問題的適應(yīng)性 而一般數(shù)值方法 比如計算定積分時 計算時間隨維數(shù)的冪次方而增加 而且 由于分點數(shù)與維數(shù)的冪次方成正比 需占用相當(dāng)數(shù)量的計算機內(nèi)存 這些都是一般數(shù)值方法計算高維積分時難以克服的問題 具有同時計算多個方案與多個未知量的能力 對于那些需要計算多個方案的問題 使用蒙特卡羅方法有時不需要像常規(guī)方法那樣逐個計算 而可以同時計算所有的方案 其全部計算量幾乎與計算一個方案的計算量相當(dāng) 例如 對于屏蔽層為均勻介質(zhì)的平板幾何 要計算若干種厚度的穿透概率時 只需計算最厚的一種情況 其他厚度的穿透概率在計算最厚一種情況時稍加處理便可同時得到 另外 使用蒙特卡羅方法還可以同時得到若干個所求量 例如 在模擬粒子過程中 可以同時得到不同區(qū)域的通量 能譜 角分布等 而不像常規(guī)方法那樣 需要逐一計算所求量 誤差容易確定 對于一般計算方法 要給出計算結(jié)果與真值的誤差并不是一件容易的事情 而蒙特卡羅方法則不然 根據(jù)蒙特卡羅方法的誤差公式 可以在計算所求量的同時計算出誤差 對干很復(fù)雜的蒙特卡羅方法計算問題 也是容易確定的 一般計算方法常存在著有效位數(shù)損失問題 而要解決這一問題有時相當(dāng)困難 蒙特卡羅方法則不存在這一問題 程序結(jié)構(gòu)簡單 易于實現(xiàn) 在計算機上進行蒙特卡羅方法計算時 程序結(jié)構(gòu)簡單 分塊性強 易于實現(xiàn) 收斂速度慢 如前所述 蒙特卡羅方法的收斂速度為 一般不容易得到精確度較高的近似結(jié)果 對于維數(shù)少 三維以下 的問題 不如其他方法好 誤差具有概率性 由于蒙特卡羅方法的誤差是在一定置信水平下估計的 所以它的誤差具有概率性 而不是一般意義下的誤差 在粒子輸運問題中 計算結(jié)果與系統(tǒng)大小有關(guān) 經(jīng)驗表明 只有當(dāng)系統(tǒng)的大小與粒子的平均自由程可以相比較時 一般在十個平均自由程左右 蒙特卡羅方法計算的結(jié)果較為滿意 但對于大系統(tǒng)或小概率事件的計算問題 計算結(jié)果往往比真值偏低 而對于大系統(tǒng) 數(shù)值方法則是適用的 因此 在使用蒙特卡羅方法時 可以考慮把蒙特卡羅方法與解析 或數(shù)值 方法相結(jié)合 取長補短 既能解決解析 或數(shù)值 方法難以解決的問題 也可以解決單純使用蒙特卡羅方法難以解決的問題 這樣 可以發(fā)揮蒙特卡羅方法的特長 使其應(yīng)用范圍更加廣泛 蒙特卡羅方法的主要應(yīng)用范圍 蒙特卡羅方法所特有的優(yōu)點 使得它的應(yīng)用范圍越來越廣 它的主要應(yīng)用范圍包括 粒子輸運問題 統(tǒng)計物理 典型數(shù)學(xué)問題 真空技術(shù) 激光技術(shù)以及醫(yī)學(xué) 生物 探礦等