關於20世紀最偉大的算法簡述

關於20世紀最偉大的算法簡述

一、蒙特卡洛方法

1946年,美國拉斯阿莫斯國家實驗室的三位科學家John von Neumann,Stan Ulam 和 Nick Metropolis 共同發明,被稱為蒙特卡洛方法。

蒙特·卡羅方法(Monte Carlo method),也稱統計模擬方法,是二十世紀四十年代中期由於科學技術的發展和電子計算機的發明,而被提出的一種以概率統計理論為指導的一類非常重要的數值計算方法。是指使用隨機數(或更常見的偽隨機數)來解決很多計算問題的方法。

蒙特卡羅方法解題過程的三個主要步驟:(1)構造或描述概率過程;(2)實現從已知概率分佈抽樣;(3)建立各種估計量。

關於20世紀最偉大的算法簡述

二、單純形法

單純形法是由美國數學家G.B.丹齊克(1914~ )於1947年提出來的,它與蘇聯數學家Л.Β.坎託羅維奇(1912~ )於1938年提出的解乘數法相類似。

單純形法,可按現代電子計算機標準程序求解線性規劃模型的一般方法。分為代數形式的單純形法和表格形式的單純形法。前者提供基本算法所依據的邏輯規則,適用於在電子計算機上進行求解運算;後者將變量和數據列成表格,適用於筆算。兩者在數學上是等價的。

單純形法的一般解題步驟可歸納如下:①把線性規劃問題的約束方程組表達成典範型方程組,找出基本可行解作為初始基可行解。②若基本可行解不存在,即約束條件有矛盾,則問題無解。③若基本可行解存在,從初始基本可行解作為起點,根據最優性條件和可行性條件,引入非基變量取代某一基變量,找出目標函數值更優的另一基本可行解。④按步驟3進行迭代,直到對應檢驗數滿足最優性條件(這時目標函數值不能再改善),即得到問題的最優解。⑤若迭代過程中發現問題的目標函數值無界,則終止迭代。

關於20世紀最偉大的算法簡述

三、Krylov 子空間迭代法

1950年:美國國家標準局數值分析研究所的,馬格努斯Hestenes,愛德華施蒂費爾和科尼利厄斯的Lanczos,發明了Krylov子空間迭代法。

Krylov子空間迭代法是用來求解形如Ax=b 的方程,A是一個n*n 的矩陣,當n充分大時,直接計算變得非常困難,而Krylov方法則巧妙地將其變為Kxi+1=Kxi+b-Axi的迭代形式來求解。

關於20世紀最偉大的算法簡述

四、矩陣計算的分解方法

1951年,阿爾斯通橡樹嶺國家實驗室的Alston Householder提出,矩陣計算的分解方法。

這個算法證明了任何矩陣都可以分解為三角、對角、正交和其他特殊形式的矩陣,該算法的意義使得開發靈活的矩陣計算軟件包成為可能。

關於20世紀最偉大的算法簡述

五、快速排序算法

由C. A. R. Hoare在1962年提出,它的基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。

關於20世紀最偉大的算法簡述

六、快速傅立葉變換

快速傅里葉變換是1965年由J.W.庫利和T.W.圖基提出的,快速傅里葉變換 (fast Fourier transform), 即利用計算機計算離散傅里葉變換(DFT)的高效、快速計算方法的統稱,簡稱FFT。採用這種算法能使計算機計算離散傅里葉變換所需要的乘法次數大為減少,特別是被變換的抽樣點數N越多,FFT算法計算量的節省就越顯著。

計算離散傅里葉變換的快速方法,有按時間抽取的FFT算法和按頻率抽取的FFT算法。前者是將時域信號序列按偶奇分排,後者是將頻域信號序列按偶奇分排。它們都藉助於的兩個特點:一是週期性;二是對稱性,這裡符號*代表其共軛。這樣,便可以把離散傅里葉變換的計算分成若干步進行,計算效率大為提高。

關於20世紀最偉大的算法簡述

七、快速多極算法

1987年:Greengard,和耶魯大學的Rokhlin發明了快速多極算法。此快速多極算法用來計算“經由引力或靜電力相互作用的N 個粒子運動的精確計算——例如銀河系中的星體,或者蛋白質中的原子間的相互作用”。

關於20世紀最偉大的算法簡述


分享到:


相關文章: