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

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