《數(shù)學建模課件算法基礎(chǔ).ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)學建模課件算法基礎(chǔ).ppt（65頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第八章 算法基礎(chǔ),西北工業(yè)大學 應(yīng)用數(shù)學系 聶玉峰,算法概念,數(shù)學建模競賽的過程 算法的概念 算法的分類 算法的評價,1.1 建模競賽的過程,實際上是命題人（某個領(lǐng)域的專家）提出實際問題 參賽人首先讀題，分析問題，依照自己的理解準確闡述問題； 辨析問題中的主要矛盾和次要矛盾，并在合理假設(shè)的條件下，運用各種數(shù)學理論、工具和方法，建立起問題中不同量之間的約束關(guān)系，進而得到完備的數(shù)學模型； 在研究模型解的存在性與惟一性 如何求其解 利用解對模型的正確性進行評價。,1.2 算法的概念,當數(shù)學模型的分析解得不到時，使用計算機進行求解。我們不會做的計算機肯定不會做，只有當我們會做，但因為數(shù)據(jù)計算量太大時，
2、把自己的求解過程（算法）編寫成程序，計算機將其編譯、運行得到計算結(jié)果。 所謂（串行）算法就是求解一個問題類的無二義性的有窮過程，這里過程明確無歧義的描述由有限操作（算術(shù)運算、邏輯運算、字符運算、讀寫操作等）及有限操作對象合成的按一定順序執(zhí)行的有限序列。 原始的可以變化的有限操作對象就是有限輸入數(shù)據(jù)，它所有可能允許的變化構(gòu)成求解的問題類。,1.3 算法的分類,對給定的輸入數(shù)據(jù)，算法運行后得到的數(shù)據(jù)結(jié)果也是有限的，這樣可以把算法看成有限輸入數(shù)據(jù)和有限輸出結(jié)果之間的對應(yīng)關(guān)系。 將以浮點算術(shù)運算為主的算法稱為數(shù)值型算法，如線性方程組的求解，數(shù)值積分的計算，微分方程初邊值問題的求解等。其它算法稱為非數(shù)值
3、型算法，如排序問題，匹配查找問題等。,1.4 算法的評價,算法在保證可靠的大前提下再評價其優(yōu)劣才是有價值的。 數(shù)值型算法的可靠性 算法的收斂性、穩(wěn)定性、誤差估計等 算法必須在有限的時間內(nèi)得到計算結(jié)果，如果某問題類的一個求解過程是無限長，需要將其截斷得到求解算法，并產(chǎn)生截斷誤差。 算法的收斂性就是研究當運行時間趨于無限長時，算法的解是否趨于真實解，即截斷誤差是否趨于零。 非數(shù)值型算法的可靠性更為強調(diào)對于整體問題類算法計算結(jié)果的正確性。,算法的評價（2）,評價一個可靠算法的優(yōu)劣，應(yīng)該考慮其時間復(fù)雜度（計算機運行時間）、空間復(fù)雜度（占據(jù)計算機存儲空間的多少）以及邏輯復(fù)雜度（影響程序開發(fā)的周期以及維護
4、）。,2數(shù)值型算法的收斂階,迭代是構(gòu)造數(shù)值問題算法的基本思想之一，迭代的結(jié)果是得到問題解的一個近似序列. 如果對于問題類中任一問題，迭代次數(shù)k趨于無窮大時序列極限存在，并且就是該問題的準確解，則稱該迭代算法收斂到問題的解。,2.1 數(shù)列收斂階的定義,2.2 舉例,2.3 2階收斂舉例,2.4 算法的收斂階,類似地，如果收斂的數(shù)列是由迭代算法產(chǎn)生的，定義數(shù)列的收斂階為算法的收斂階。不過需要注意，算法是對問題類的算法，不是針對一個特定問題的，這樣算法的收斂階應(yīng)該是由該算法生成的序列都具有的共同特征。,2.5 時間花費與收斂速度,對于不同的算法，若每一迭代步的時間花費相當，從收斂階的定義可以知道，收
5、斂階高的算法花費較少的時間；對于同階的算法，漸近常數(shù)小者花費較少的時間。,2.6 向量序列的極限,2.7 范數(shù)概念,2.8 常用向量范數(shù),2.9 等價性定理、收斂速度,2.10 常用的矩陣范數(shù),3 誤差及數(shù)值算法的穩(wěn)定性,誤差的產(chǎn)生 模型建立時因舍去次要矛盾會產(chǎn)生模型誤差； 模型中包含一些參數(shù)是通過儀表觀測得到的，產(chǎn)生觀測誤差； 算法必須在有限步內(nèi)執(zhí)行結(jié)束，這樣需要將無窮過程截斷為有限過程，產(chǎn)生截斷誤差； 在用計算機實現(xiàn)數(shù)值算法的過程中，由于計算機表示浮點數(shù)采用的是固定有限字長，因而僅能夠區(qū)分有限個信息，準確表示在某個有限范圍內(nèi)的某些有理數(shù)，不能準確表示數(shù)學中的所有實數(shù)，這樣在計算機中表示的原
6、始輸入數(shù)據(jù)、中間計算數(shù)據(jù)、以及最終輸出結(jié)果必然產(chǎn)生誤差，稱此類誤差為舍入誤差。 得到的計算結(jié)果是這些誤差綜合影響下的數(shù)據(jù)。,3.2 浮點數(shù)系,浮點數(shù)系是計算機常用的實數(shù)表示系統(tǒng)，一個浮點數(shù)的表示由正負號、有限小數(shù)形式的尾數(shù)、以及確定小數(shù)點位置的階碼三部分組成. 設(shè)在某一浮點系統(tǒng)中, 尾數(shù)占t位二進制數(shù)(未計算尾數(shù)的符號位), 階數(shù)占s位二進制數(shù)(未計算階數(shù)的符號位), 實數(shù)的浮點表示共需要ts2位的二進制數(shù)位.,3.3 溢出,3.4 單精度數(shù),單精度實數(shù)用32位的二進制數(shù)據(jù)表示浮點數(shù)的這三個信息, 其中數(shù)值符號和階碼符號各占1位, 尾數(shù)占t=23位, 階碼數(shù)值占s7位. 這樣，除零外, 單精度
7、實數(shù)的量級不大于1038不小于1038. 當輸入、輸出或中間計算過程中出現(xiàn)量級大于1038的數(shù)據(jù)時, 因單精度實數(shù)無法正確表示該數(shù)據(jù), 將導(dǎo)致程序的非正常停止, 稱此現(xiàn)象為上溢(Overflow). 而當出現(xiàn)量級小于10-38的非零數(shù)據(jù)時, 一般計算機將該數(shù)置為零, 精度損失, 稱此現(xiàn)象為下溢(Underflow). 當數(shù)據(jù)有可能出現(xiàn)上溢或下溢時, 可通過乘積因子變換數(shù)據(jù), 使之正常表示. 67位有效數(shù)字,3.5 初值誤差,由于誤差傳播研究困難，經(jīng)常研究某種假設(shè)下誤差的傳播規(guī)律。如初值誤差傳播是在每一步都準確計算的假設(shè)下，即不考慮截斷誤差和由運算進一步引入的舍入誤差，研究誤差傳播規(guī)律。,3.6
8、 數(shù)值穩(wěn)定性,舍入誤差分析是非常繁雜困難的, 而舍入誤差不可避免, 運算量又相當大, 為此, 人們提出了數(shù)值穩(wěn)定性這一概念對舍入誤差是否影響產(chǎn)生可靠的結(jié)果進行定性分析. 一個算法, 如果在運算過程中舍入誤差在一定條件下能夠得到控制, 或者舍入誤差的增長不影響產(chǎn)生可靠的結(jié)果, 則稱該算法是數(shù)值穩(wěn)定的, 否則稱其為數(shù)值不穩(wěn)定.,3.7 數(shù)值穩(wěn)定舉例,不穩(wěn)定算法結(jié)果,I1-I10近似值分別如下： 0.0883920 0.0580400 0.0431333 0.0343333 0.0283333 0.0250000 0.0178571 0.0357143 -0.0674603 0.4373016,算法
9、2,Matlab 算出的精確解,穩(wěn)定性不同于顯著性,對算法的穩(wěn)定性分析，其實就是給原始數(shù)據(jù)一個小擾動，分析計算結(jié)果變化的程度,若很大則算法不穩(wěn)定，若可以接受，則算法穩(wěn)定. 這里需要指出，算法的穩(wěn)定性不同于建立模型過程中因素的顯著性分析.,數(shù)值型算法設(shè)計注意事項,對于一個數(shù)值型算法除了其正確性（如收斂性）外，研究其效率（如收斂速度）、魯棒性（如穩(wěn)定性）是很重要的，同時程序設(shè)計或?qū)崿F(xiàn)時如下幾個問題也不可忽視： 1）減少計算次數(shù)以縮短計算時間,2）避免相近數(shù)相減,避免相近數(shù)相減舉例,3）盡可能避免大數(shù)吃小數(shù),其它,4）避免很小的數(shù)做分母，防止溢出出現(xiàn)； 5）正確使用實數(shù)相等的比較,5 數(shù)值型算法構(gòu)造
10、的常用基本思想,掌握數(shù)值型算法構(gòu)造的基本思想將會有利于提出針對具體問題的有效快速算法,關(guān)于迭代的解釋,在這個過程中，首先我們用到了逼近的思想，將一個常量（方程的一個根）看成變量的極限，這個變量的每一個值是常量的近似值，不過它愈來愈近似的好. 當然你也可以看出這個過程其實也用到了兩個思想：動與靜的思想，極限的思想. 其次也用到了問題轉(zhuǎn)換的思想，將函數(shù)的零點（方程的根）轉(zhuǎn)換為另一個函數(shù)的不動點. 最后借助不動點問題產(chǎn)生迭代序列，即使用迭代的思想產(chǎn)生逼近序列.,線性方程組,5.2 直與曲的思想,該法除了使用逼近的思想外，還用到了以直代曲的思想，用一系列的直線近似曲線，這些直線是曲線的一系列切線，特點
11、是切點越來越和方程的一個根接近,舉例,5.3 分段處理的思想,5.4 修正的思想,修正的思想在常微分方程數(shù)值解中使用非常之多，它屬于預(yù)估校正類算法,5.5 組合的思想,對精度較低的解近似進行組合，以期望得到近似精度高的解近似. 一個典型的例子是龍貝格求積算法.,進一步說明,在這一組公式中，每一個式子的第二式就是用精度較低的兩個近似通過組合得到精度較高的近似. 這個組合的推出，由每一個公式的第一個式子可以看出是用了修正的思想，修正量是對分后改進量的一個分數(shù)倍數(shù). 它還用了以直代曲的思想、化整為零的思想，以得到復(fù)化梯形法計算公式,，,5.6 自適應(yīng)的思想,自適應(yīng)在算法構(gòu)造中是非常重要的思想，它在構(gòu)
12、造算法時也同時兼顧了局部特征. 以計算積分為例，當使用復(fù)化梯形公式時，我們總希望函數(shù)值變化較大的地方使用較多的節(jié)點，即使用較小的步長，變化平坦的地方，步長較大一些，用較少的節(jié)點. 顯然用等步長的梯形公式效率就低，因為它忽視了函數(shù)變化的快慢，即局部特征.,算法的評價,同一問題可用不同算法解決，在分析了算法的可靠性之后，就需要對其效率進行分析，算法分析的目的在于選擇合適的算法和改進算法. 一個算法的效率評價主要從時間復(fù)雜度和空間復(fù)雜度來考慮.,6.1 時間復(fù)雜度,1）時間頻度 算法執(zhí)行所開銷的時間，從理論上是很難算出來的，而上機運行測試可以得到時間花費的準確結(jié)果. 但我們不可能也沒有必要對每個算法
13、都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了. 并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多. 一個算法中的語句執(zhí)行次數(shù)稱為算法時間頻度，記為T(n)，其中 n是問題的規(guī)模，它是算法執(zhí)行時所需存儲空間的度量. 符號T(n)表示算法的語句頻度是問題規(guī)模的函數(shù)，它是算法需要完成多少工作的度量.,2）時間復(fù)雜度,在時間頻度中，當問題規(guī)模n不斷變化時，時間頻度T(n)也會不斷變化. 為研究它變化時呈現(xiàn)的規(guī)律性，引入時間復(fù)雜度的概念. 算法的時間頻度是問題規(guī)模n的某個函數(shù)T(n)，若有某個輔助函數(shù)g(n)， 使得當n趨近于無窮大
14、時，T(n)/g(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)，記作T(n)=O(g(n)，稱O(g(n) 為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度.,舉例,時間復(fù)雜度的漸進常數(shù)之比,說明,在算法中，若語句執(zhí)行次數(shù)為一個常數(shù)，與求解規(guī)模沒關(guān)系，則時間復(fù)雜度為O(1). 即算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)，此類算法的時間復(fù)雜度是O(1). 例子表明，在時間頻度不相同時，時間復(fù)雜度也有可能相同. 在算法分析時，往往對算法的時間復(fù)雜度和漸近時間復(fù)雜度不予區(qū)分，而經(jīng)常是將漸近時間復(fù)雜度T(n)=O(g(n)簡稱為時
15、間復(fù)雜度，其中函數(shù)g(n)一般選為算法中頻度最大的語句頻度.,常見的不同時間復(fù)雜度的效率,按數(shù)量級遞增排列的時間復(fù)雜度有：常數(shù)階O(1)，線性階O(n)，線性對數(shù)階O(nlogn)，平方階O(n2),立方階O(n3)，指數(shù)階O(2n)和 n!. 隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低,比較圖1,比較圖2,比較圖3,比較圖4,給定數(shù)據(jù)規(guī)模n，執(zhí)行給定時間復(fù)雜度的算法耗時比較,給定數(shù)據(jù)規(guī)模n，執(zhí)行給定時間復(fù)雜度的算法耗時比較,6.2 問題的規(guī)模,時間復(fù)雜度是問題規(guī)模n的函數(shù). 我們將標識問題類中不同問題大小的參數(shù)定義為問題的規(guī)模. 如計算兩個向量的點乘積，那么一個向量
16、的分量個數(shù)n就是它的規(guī)模參數(shù)；計算兩個矩陣的乘法，矩陣的行數(shù)和列數(shù)就是該問題的規(guī)模；如若計算方陣的乘法，它的行數(shù)或者列數(shù)就是該問題規(guī)模；求解一個線性方程組，線形方程組的階數(shù)就是其規(guī)模；對一組數(shù)進行排序，這一組數(shù)的個數(shù)就是其規(guī)模，等等. 問題的規(guī)模不同于求解一個問題的算法的空間復(fù)雜度，算法的空間復(fù)雜度涉及到除原始數(shù)據(jù)外所需要額外增加的存儲空間. 原始數(shù)據(jù)量是問題規(guī)模的單調(diào)增加函數(shù),6.3 時間復(fù)雜度分析,考慮算法的漸進時間復(fù)雜度，即隨著問題規(guī)模的增大時間頻度的變化趨勢，通常時間耗費是問題規(guī)模的單調(diào)增加函數(shù)，因而算法中的一些與問題規(guī)模無關(guān)的語句執(zhí)行時間可以不予考慮，因為該語句的頻度是O(1). 由
17、于編譯系統(tǒng)對循環(huán)語句中循環(huán)次數(shù)的控制在編譯時已經(jīng)計算好，所以時間復(fù)雜性分析時可以不予考慮. 當對漸進常數(shù)的大小不關(guān)心，僅考慮其漸進階數(shù)時，只需分析循環(huán)中某一個語句的執(zhí)行頻度. 這也從另一個側(cè)面說明數(shù)量級分析并不是算法分析的全部內(nèi)容，它僅考慮了數(shù)量級最高項的級，忽略其系數(shù)，更忽略了低階項.,例1 計算兩個向量點乘積的算法,問題規(guī)模為n，全部統(tǒng)計時算法復(fù)雜度為O(n+1)，忽略循環(huán)外的語句時算法復(fù)雜度為O(n)，顯然他們的量級相同. 這里對步進循環(huán)語句只考慮循環(huán)體中語句的執(zhí)行次數(shù)，忽略該語句中步長加1、終值判別、控制轉(zhuǎn)移等成分,例2 計算一個n維行向量和兩個n階方矩陣的乘積.,問題規(guī)模為n，算法時
18、間復(fù)雜度為O(2n2+2n)，忽略外循環(huán)時，算法復(fù)雜度為O(2n2)，顯然它們具有相同的漸進階，且漸進常數(shù)相同；如果僅考慮內(nèi)循環(huán)的一條語句，算法復(fù)雜度為O(n2)，雖然依然保證同階，但漸進常數(shù)發(fā)生了改變,例3 矩陣乘積,例4 計算n階方陣下三角部分元素之和,算法復(fù)雜度為O(n(n+1)/2+1). 該算法分析時，內(nèi)循環(huán)參數(shù)雖沒有和問題規(guī)模直接相關(guān)，但它和外循環(huán)參數(shù)i相關(guān)，i與問題規(guī)模是相關(guān)的，這樣內(nèi)循環(huán)參數(shù)j間接和問題規(guī)模相關(guān). 算法分析時一定得注意循環(huán)控制參數(shù)與問題規(guī)模間的間接相關(guān)性.,例5 計算向量分量的正弦值的最大值,問題規(guī)模為n，算法復(fù)雜度O(3n-2). 這里統(tǒng)計語句頻度時，沒有區(qū)分
19、正弦值計算與比較、數(shù)值操作上執(zhí)行時間的差異，顯然后者花費較少的時間. 這也就是說即使每一個語句的頻度都統(tǒng)計上，算法復(fù)雜度也是一個粗略的估計. 如果進一步考慮正弦值如何計算，那么算法的復(fù)雜度量級不會變化，但漸進常數(shù)必然改變，這是由于計算一個正弦值需要確定的時間，與問題規(guī)模無關(guān). 可見算法描述的越精細，分析出的時間頻度越能反映時間耗費狀態(tài).,說明2,語句“max=t”實際上是條件執(zhí)行的，只有條件“tmax”成立時才執(zhí)行. t是有原始數(shù)據(jù)計算出的，這說明對于一個具體的算例，即問題類中的一個具體問題，語句頻度還與初始數(shù)據(jù)有關(guān). 類似的問題還很多，如匹配查找問題、排序問題等. 上面我們實際上假設(shè)條件語句
20、“max=t”一定執(zhí)行，也就是說考慮的是最壞的一種情形，所得復(fù)雜性結(jié)論對于問題類中所有問題來說都是正確的(作為其上界).,說明3,最壞情況下的時間復(fù)雜度稱為問題類的最壞時間復(fù)雜度. 一般不特別說明，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度.正如前面所討論的，這樣做的原因是：最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比它更長. 另一種思路是使用平均復(fù)雜度，平均時間復(fù)雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運行時間. 如對于算例5，語句“max=1”、“t=sin(x(i)”、“tmax ?”是一定執(zhí)行的，對于語句“max=t”是否執(zhí)行的概率相等，這樣算法復(fù)雜度為O(1+2(n-1)+(n-1)/2)=O(5(n-1)/2+1). 和最壞時間復(fù)雜度相比，具有相同的量級，漸進常數(shù)不同.,
數(shù)學建模課件算法基礎(chǔ).ppt
