【計算機科學(xué)導(dǎo)論-基于計算思維的思想與方法（第4版） 課件 ch08】問題求解的近似計算

計算機科學(xué)導(dǎo)論基于計算思維的思想與方法問題求解的近似計算第八章新工科建設(shè)之路·計算機類系列教材01定積分的近似計算定積分的近似計算01一、近似計算方法根據(jù)定積分定義推算出求解定積分近似值表達式定積分的近似計算01一、近似計算方法1.矩形積分法定積分的近似計算01一、近似計算方法1.矩形積分法定積分的近似計算01一、近似計算方法1.矩形積分法定積分的近似計算01一、近似計算方法2.梯形積分法梯形積分法是把曲邊梯形分成若千個小窄曲邊梯形，每個小窄曲邊梯形面積用小直邊梯形面積來近似代替，然后將每個直邊梯形面積相加，從而得到定積分的近似值，其幾何圖形如圖8-2所示。定積分的近似計算01一、近似計算方法3.拋物線積分法雖然梯形積分法比矩形積分法的誤差小，但還是不夠精確。如果每段改用與凸起相接近的二次曲線來近似，這就是拋物線積分法，也稱為辛普森(Simpson)方法，如圖8-3所示。定積分的近似計算01二、計算求解方法1.編程求解方法這里仍以定積分的近似計算為例，討論利用計算機實現(xiàn)矩形積分法中右端點求和法的實現(xiàn)方法?；舅惴ú襟E如下。定積分的近似計算01二、計算求解方法2.工具軟件方法Matlab全稱為MatrixLaboratory(矩陣試驗室)，是當今最受控制系統(tǒng)設(shè)計和仿真領(lǐng)域青睞的工具軟件，可用于數(shù)值計算、數(shù)據(jù)建模、數(shù)字仿真、數(shù)據(jù)處理、工程與科學(xué)繪圖等，為眾多科學(xué)領(lǐng)域提供了全面的解決方案，代表了當今國際科學(xué)計算軟件的先進水平；Maple是目前世界上最通用的數(shù)學(xué)和工程計算軟件之一，在數(shù)學(xué)和科學(xué)領(lǐng)域享有盛譽，有“數(shù)學(xué)家的軟件”之稱；Mathematica是世界上通用計算系統(tǒng)中最強大的系統(tǒng)，擁有強大的數(shù)值計算和符號運算能力，在科技和其他領(lǐng)域產(chǎn)生了深刻的影響。這里簡要介紹運用Matlab求定積分計算的基本方法。02有限元方法有限元方法021.有限元方法的理論基礎(chǔ)有限元方法是一種用于求解微分方程組數(shù)值解的數(shù)值技術(shù)。有限元方法是基于數(shù)值計算發(fā)展起來的一種近似數(shù)值方法，用來解決力學(xué)、數(shù)學(xué)中的帶有特定邊界條件的偏微分方程問題，而這些偏微分方程是工程實踐中常見的固體力學(xué)和流體力學(xué)問題的基礎(chǔ)。一、有限元方法的基本概念有限元方法022.有限元方法的解題思想有限元方法基于變分原理，它將求解域看成是由許多稱為有限元的小的互聯(lián)子域組成的，并且對每一單元假定一個合適而簡單的近似解，然后推導(dǎo)求解這個域總的滿足條件(如結(jié)構(gòu)的平衡條件)，從而得到原問題的解。一、有限元方法的基本概念有限元方法021.局部與整體的計算思維有限元方法的關(guān)鍵思想是離散化，它完美體現(xiàn)了局部與整體的哲學(xué)思想，若要解決整體問題，必須先研究局部問題。把復(fù)雜的結(jié)構(gòu)看成由有限個單元組成的整體，化整為零、集零為整是有限元方法的基本思想，這種思想為我們處理復(fù)雜工程問題提供了一種基本思路。二、有限元方法的計算思維有限元方法022.單元與組合體的計算思維有限元方法將連續(xù)方程的求解域離散為有限個由單元組成的組合體，以此組合體來模擬和逼近原求解域。由于各單元本身具有不同的幾何形狀，并且各單元間可以按照各種不同的聯(lián)結(jié)方式組合，所以這個組合體可以模擬幾何形狀復(fù)雜的求解域，并且原問題單元劃分越細，單元數(shù)越多，求解的逼近程度越高。二、有限元方法的計算思維03隨機事件及其概率隨機事件及其概率03一、隨機事件我們把對一個客觀事物進行的“試驗”“調(diào)查”或“觀測”統(tǒng)稱為“試驗”。一個試驗知道可能產(chǎn)生的所有結(jié)果，而且這個試驗在相同條件下可以重復(fù)進行，這樣的試驗稱為“隨機試驗”。“隨機試驗”產(chǎn)生的結(jié)果稱為“隨機事件”，一般用A，B，C…表示。1.什么是隨機事件隨機事件及其概率03一、隨機事件隨機事件具有如下3個重要特征：(1)具有重復(fù)性：可以在相同條件下，反復(fù)進行多次試驗；(2)沒有確定性：在一次試驗(觀察)中，隨機事件可能發(fā)生或不發(fā)生，結(jié)果具有偶然性；(3)統(tǒng)計規(guī)律性：在大量重復(fù)試驗(觀察)中，隨機事件的發(fā)生具有某種統(tǒng)計規(guī)律性。2.隨機事件的特征隨機事件及其概率03一、隨機事件隨機事件的關(guān)系是指事件A與事件B的包含、相等、互斥、互逆這4個方面的相互關(guān)系。3.隨機事件的關(guān)系對于同一個樣本空間S的任意兩個事件A和B，并具有以下3種運算關(guān)系：(1)并(或和)；(2)積(或交)；(3)差(或減)。4.隨機事件的運算隨機事件及其概率03二、隨機概率1.概率的統(tǒng)計定義為了揭示概率統(tǒng)計規(guī)律，我們希望尋求一種合適的數(shù)來表示事件發(fā)生的可能性的大小。通過大量反復(fù)試驗，隨機事件具有以下兩個重要特征。(1)在一次試驗中，隨機事件的發(fā)生具有偶然性。(2)在大量反復(fù)試驗中，隨機事件的發(fā)生具有統(tǒng)計規(guī)律性。隨機事件及其概率03二、隨機概率2.概率的性質(zhì)隨機事件及其概率03二、隨機概率3.古典概型古典概型在數(shù)學(xué)上可表示為：根據(jù)古典概型的特點，可以定義任一隨機事件的概率。隨機事件及其概率03三、隨機變量1.隨機變量的定義隨機事件及其概率03三、隨機變量2.離散型隨機變量隨機事件及其概率03三、隨機變量3.連續(xù)型隨機變量04蒙特卡羅方法蒙特卡羅方法04一、蒙特卡羅方法的概念1.求解思想蒙特卡羅方法是以概率統(tǒng)計理論為指導(dǎo)的一類非常重要的數(shù)值計算方法，所以在解決實際問題時的模擬方法主要有兩部分：一是用蒙特卡羅方法模擬某一過程，產(chǎn)生滿足該隨機過程概率分布的隨機變量；二是用統(tǒng)計方法估計模型的數(shù)字特征，從而得到實際問題的數(shù)值解。蒙特卡羅方法04一、蒙特卡羅方法的概念2.求解方法蒙特卡羅方法與傳統(tǒng)的確定性算法解決問題的思路截然不同，是基于概率論及數(shù)理統(tǒng)計來解決計算問題的方法，是一種應(yīng)用隨機數(shù)進行仿真試驗的方法，在具體實現(xiàn)上常采用以下兩種方法。(1)模擬隨機過程(2)獲取概率統(tǒng)計蒙特卡羅方法04二、蒙特卡羅方法求定積分1.蒙特卡羅積分蒙特卡羅方法04二、蒙特卡羅方法求定積分2.數(shù)值積分法的選擇4種數(shù)值積分計算公式。05圓周率的近似計算圓周率的近似計算05一、圓周率的計算史1.試驗法時期圓是最簡單、最基本的曲邊圖形，其量度問題在幾何學(xué)中占有相當重要的位置。今天數(shù)學(xué)上的許多成果，得益于人類對于幾何形狀的認識與探測過程中，實現(xiàn)了從“直”到“曲”，從“有限”到“無限”這一歷史性的跨越。此后，經(jīng)過歷代數(shù)學(xué)家的相繼探索，推算出的圓周率數(shù)值日益精確。圓周率的近似計算05一、圓周率的計算史2.幾何法時期魏晉時期，中國古代數(shù)學(xué)家劉徽利用算籌，采用稱為“割圓術(shù)(CyclotomicMethou)”的計算方法，在劉徽之后200年的南北朝時期，我國古代天文學(xué)家、數(shù)學(xué)家祖沖之利用劉徽的“割圓術(shù)”，繼續(xù)分割，內(nèi)接多邊形的周長還會增加。在全憑手工計算的古代，能取得如此精確的計算，是人類在幾何學(xué)的處理方法和思想觀念上突破和跨越了從“直”到“曲”，從“有限”到“無限”的結(jié)果。圓周率的近似計算05一、圓周率的計算史3.分析法時期圓周率的近似計算05一、圓周率的計算史4.計算機法時期1946年，世界上第一臺電子計算機ENIAC誕生，并得到飛速發(fā)展，從此開啟了現(xiàn)代科學(xué)的新時代，人工計算圓周率的歷史從此結(jié)束。人們用計算機求解圓周率的值，即使在普通的微機上，求得上萬位的圓周率的值也是輕而易舉的事。只要提供足夠多的機時，就可以將圓周率的值計算到任意多位。圓周率的近似計算05二、研究計算圓周率的意義1.檢驗計算機系統(tǒng)的性能利用圓周率π的求解檢驗計算機硬件和軟件的性能是一項具有重要意義的工作。例如，在486Dx/100微機上計算5萬位π值，大約需要6小時，運行中任何一個微小的機器故障都將導(dǎo)致錯誤的結(jié)果。因而，這對于計算機的運行速度以及運行的可靠、穩(wěn)定性都是一個很好的檢驗手段。由此可以看出，高精度π值計算可作為檢驗和比較計算機性能的一個標準計算。圓周率的近似計算05二、研究計算圓周率的意義2.研究圓周率的值隨機分布性質(zhì)關(guān)于圓周率的各位小數(shù)的隨機分布的性質(zhì)，目前還主要依賴于統(tǒng)計分析，計算的位數(shù)越多，統(tǒng)計分析的結(jié)果就越可靠。用圓周率的小數(shù)位計算的效果最好。有兩個致命弱點：周期不夠長，分布不夠均勻。這對于一般的應(yīng)用影響不大，但對某些重要的科學(xué)計算將會產(chǎn)生不能容忍的誤差，因此，在必要時用圓周率或由圓周率生成的其他數(shù)作為隨機數(shù)似乎更為理想。06仿生學(xué)算法仿生學(xué)算法06一、遺傳算法的基本方法1.遺傳算法流程遺傳算法流程包括編碼生成初始種群、個體、適應(yīng)度、選擇、交叉和變異，如圖8-9所示。仿生學(xué)算法06一、遺傳算法的基本方法2.遺傳算法編碼遺傳算法不能直接處理問題的參數(shù)，必須把參數(shù)轉(zhuǎn)換成遺傳空間的、由基因按一定結(jié)構(gòu)組成的染色體或個體。這一轉(zhuǎn)換操作被稱為編碼(Code)或者問題的表示(Representation)。在遺傳算法中的編碼有位串編碼和符號編碼兩種方式。仿生學(xué)算法06二、群體智能優(yōu)化算法概念1.蟻群優(yōu)化算法概念蟻群優(yōu)化算法是一種隨機通用試探法，屬于分布式智能模擬算法，可用于求解各種不同的組合優(yōu)化問題。有人根據(jù)蟻群優(yōu)化算法求解144個城市的最短回路問題，求得解的結(jié)果同其他方法求得的解一樣精確，由此說明蟻群優(yōu)化算法是求解組合優(yōu)化的可行算法。仿生學(xué)算法06二、群體智能優(yōu)化算法概念2.粒子群優(yōu)化算法概念粒子群優(yōu)化算法(ParticleSwarmOptimization，PSO)也稱為粒子群算法、微粒群優(yōu)化算法，粒子群優(yōu)化算法是通過模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機搜索算法，基本思想是模擬鳥群的捕食行為，即一群鳥在隨機搜索食物，在這個區(qū)域里只有一塊食物，但所有的鳥都不知道食物在哪里，但是它們知道當前的位置離食物還有多遠，那么找到食物的最優(yōu)策略是什么呢?顯然，最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。因此，研究該算法的意義在于利用位置和速度的變化，模擬鳥群遷移中個體行為和群體行為之間的相互影響。仿生學(xué)算法06二、群體智能優(yōu)化算法概念3.