數值分析

數值分析，是指在數學分析問題中，對使用數值近似演算法的研究。巴比倫泥板YBC 7289是關於數值分析的最早數學作品之一，它給出了 formula_1 在六十進位制下的一個數值逼近，formula_1是一個邊長為1的正方形的對角線，在西元前1800年巴比倫人也已在巴比倫泥板上計算勾股數formula_3，即直角三角形的三邊長比。數值分析延續了實務上數學計算的傳統。巴比倫人利用巴比倫泥板計算formula_1的近似值，而不是精確值。在許多實務的問題中，精確值往往無法求得，或是無法用有理數表示。數值分析的目的不在求出正確的答案，而是在其誤差在一合理範圍的條件下找到近似解。在所有工程及科學的領域中都會用到數值分析。像天體力學研究中會用到常微分方程，最最佳化會用在投資組合管理中，數值線性代數是資料分析中重要的一部份，而隨機微分方程及馬可夫鏈是在醫藥或生物學中生物細胞模擬的基礎。在電腦發明之前，數值分析主要是依靠大型的函式表及人工的內插法，但在二十世紀中被電腦的計算所取代。不過電腦的內插演演算法仍然是數值分析軟體中重要的一部份。簡介.數值分析的目的是設計及分析一些計算的方式，可針對一些問題得到近似但夠精確的結果。以下是一些會用利用數值分析處理的問題：直接法和迭代法.直接法利用固定次數的步驟求出問題的解。這些方式包括求解線性方程組的高斯消去法及，求解線性規劃的單純形法等。若利用無限精度算術的計算方式，有些問題可以得到其精確的解。不過有些問題不存在解析解，也就無法用直接法求解。在電腦中會使用浮點數進行運算，在假設運算方式穩定的前提下，所求得的結果可以視為是精確解的近似值。迭代法是透過從一個初始估計出發尋找一系列近似解來解決問題的數學過程。和直接法不同，用迭代法求解問題時，其步驟沒有固定的次數，而且只能求得問題的近似解，所找到的一系列近似解會收斂到問題的精確解。會利用審斂法來判別所得到的近似解是否會收斂。一般而言，即使使用無限精度算術的計算方式，迭代法也無法在有限次數內得到問題的精確解。在數值分析中用到迭代法的情形會比直接法要多。例如像牛頓法、二分法、雅可比法、廣義最小殘量方法及共軛梯度法等。在計算矩陣代數中，大型的問題一般會需要用迭代法來求解。離散化.許多時候需要將連續模型的問題轉換為一個離散形式的問題，而離散形式的解可以近似原來的連續模型的解，此轉換過程稱為離散化。例如求一個函式的積分是一個連續模型的問題，也就是求一曲線以下的面積若將其離散化變成數值積分，就變成將上述面積用許多較簡單的形狀近似，因此只要求出這些形狀的面積再相加即可。例如在二小時的賽車比賽中，記錄了三個不同時間點的賽車速度，如下表利用離散化的方式，可以假設賽車在0:00到0:40之間的速度、0:40到1:20之間的速度及1:20到2:00之間的速度分別為三個定值，因此前40分鐘的總位移可近似為(formula_6h × 140 km/h) = 93.3 公里。可依此方式近似二小時內的總位移為93.3 公里 + 100 公里 + 120 公里 = 313.3 公里。位移是速度的積分，而上述的作法是用黎曼和進行數值積分的一個例子。誤差的產生及傳播.誤差是數值分析的重要主題之一。誤差的形成可分為幾種不同的原因。捨入誤差.當進行數值分析的裝置只能用有限位數來表示一個實數時，就會出現捨入誤差，例如用可顯示十位數字的計算器計算formula_7，所得到的結果0.333333333，和實際數值的誤差就是捨入誤差。即使進行數值分析的裝置用浮點數來表示實數，仍無法完全避免捨入誤差的問題。截尾及離散化誤差.若迭代法的數值分析算到某一程度就中止計算，或是使用一些近似的數學程式，程式所得結果和精準解不同，就會出現。將問題離散化後，由於離散化問題的解不會和原問題的解完全一様，因此會出現。例如用迭代法計算formula_8的解，在計算幾次後認為其解為1.99，就會有0.01的截尾誤差。一旦有了誤差，誤差就會藉著計算繼續的擴散。例如一個計算機中的加法是不準的，則formula_9的計算也一定不準。例如剛剛計算formula_8的解為1.99，若後續的運算需要用到formula_8的解，用1.99代入所得的結果也會不準。當用近似的方式處理數學式時就會出現截尾誤差。以積分為例，完全精準的積分需要求出曲線下方無限個梯形的面積和，但用在數值分析中會用有限個梯形的面積和來近似無限個梯形的面積和，此時就會出現截尾誤差。若要對一個函式進行微分，其微分量需要趨近於0，但實務上只能選擇很小的微分量。數值穩定性及良置問題.數值穩定性是數值分析中一個重要的主題。若一演演算法中不論什麼原因產生了誤差，此誤差不會在運算中明顯增加，此演演算法為數值穩定的演演算法。若問題為良置。原始問題及求解問題演演算法都可以分為良置及非良置，任何的組合都是允許的。一個求解良置問題的演演算法可能是數值穩定的，也可能是數值不穩定的。數值分析的重點就是找到適定性問題的數值穩定演演算法。例如，計算2的平方根本身是一個適定性問題。許多求解的演演算法都是從一個初始的近似值formula_12開始去求解，例如formula_13，再繼續計算formula_14、formula_15等。巴比倫法就是一個具有此特性的演演算法。另一個方法，先稱之為X方法，演演算法為formula_16。以下分別用初始值 formula_13及formula_18，用二種方式進行幾次迭代。可觀察到不論初始值多少，巴比倫法都可以快速的收斂，但X方法在初始值為1.4時收斂的很慢，在初始值為1.42時X方法會發散。因此巴比倫法是數值穩定的方法，而X方法是數值不穩定的方法。領域研究.數值分析依其待求解的問題不同，分為不同的領域。函式求值.數值分析中最簡單的問題就是求出函式在某一特定數值下的值。最直覺的方法是將數值代入函式中計算，不過有時此方式的效率不佳。像針對多項式函式的求值，較有效率的方式是秦九韶演算法，可以減少乘法及加法的次數。若是使用浮點數，很重要的是是估計及控制捨入誤差。內插法、外推法、曲線擬合及回歸.內插法求解以下的問題：有一未知函式在一些特定位置下的值，求未知函式在已知數值的點之間某一點的值。外推法類似內插法，但需要知道數值的點是在其他已知數值點的範圍以外。一般而言外推法的誤差會大於內插法。曲線擬合是在已知一些資料的條件下，找到一條曲線完全符合現有的資料，資料可能是一些特定位置及其對應的值，也可能是其他資料，例如角度或曲率等。回歸分析類似曲線擬合，也是根據一些特定位置及其對應的值，要找到對應曲線。但回歸分析考慮到資料可能有誤差，因此所得的的曲線不需要和資料完全符合。一般會使用最小方差法來進行回歸分析。求解方程及方程組.另一種常見的問題是求特定方程式的解。首先會依方程式是否線性來區分，例如方程式 formula_19是線性方程式，而formula_20是非線性方程式。此領域許多的研究都和求解線性方程組有關。直接法是線性方程組的係數以矩陣來表示，再利用矩陣分解的方式求解，這些方法包括高斯消去法、LU分解，對於對稱矩陣及共軛梯度法，一般會用在大型的線性方程組中。求根演演算法是要解一非線性方程，其名稱是因為函式的根就是使其值為零的點。若函式本身可微且其導數是已知的，可以用牛頓法求解，其他的方法包括二分法、割線法等。線性化則是另一種求解非線性方程的方法。求解特徵值或奇異值問題.許多重要的問題可以用奇異值分解或特徵分解來表示。例如有些影象壓縮演演算法就是以奇異值分解為基礎。統計學中對應的工具稱為主成分分析。最最佳化.最最佳化問題的目的是要找到使特定目標函式有最大值的點，一般而言這個點需符合一些約束。依目標函式及約束條件的不同，最佳化又可以再細分：例如線性規劃處理目標函式及約束條件均為線性的情形，常用單純形法來求解。若目標函式及約束條件其中有一項為非線性，就是非線性規劃的範圍。有約束條件的問題可以利用拉格朗日乘數轉換為沒有約束條件的問題。積分計算.數值積分的目的是在求一定積分的值。一般常用牛頓－寇次公式，包括辛普森積分法、高斯求積等。上述方式是利用分治法來處理積分問題，也就是將大範圍的積分切割成許多小範圍的積分，再進行計算。不過在高維度時，上述作法可能會因為要作許多的計算而變得不實用微分方程.數值分析也會用近似的方式計算微分方程的解，包括常微分方程及偏微分方程。往往會使用迭代法，已知曲線的一點，設法算出其斜率，找到下一點，再推出下一點的資料。尤拉方法是其中最簡單的方式，較常使用的是龍格－庫塔法。偏微分方程數值方法一般都會先將問題離散化，轉換成有限元素的次空間。可以透過有限元素法、有限差分法及有限體積法，這些方法可將偏微分方程轉換為代數方程，但其理論論證往往和泛函分析的定理有關。另一種偏微分方程的數值分析解法則是利用離散傅立葉變換或快速傅立葉變換。軟體.20世紀末，大部份數值分析的演演算法都已用許多不同的程式語言實現。軟體庫包含了許多數值分析演演算法的程式，大部份是Fortran及C語言的程式。商業產品也實現了許多不同的數值分析演演算法，包括國際數學及統計程式庫數字型檔及軟體庫，GNU科學數值庫則是自由軟體的數值分析演演算法軟體庫。數值分析的商用應用程式包括MATLAB、、LabVIEW及IDL等，自由軟體或開源軟體的數值分析應用程式則包括FreeMat、Scilab、GNU Octave 及一些Python的衍生版本。各應用程式的效能有很大的差異：一般而言向量及矩陣的運算都很快，而各應用程式純量運算的速度差異則可能會超過10倍以上。許多計算機代數系統的軟體由於使用無限精度算術的計算方式，可以得到比一般軟體更準確的結果。電子試算表的軟體也可以處理一部份簡單的數值分析問題。