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

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