數學建模課件算法基礎.ppt

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