數值分析

數值分析

數學下屬學科
數值分析研究求解數學模型的算法及有關理論,它伴随計算機的發展而發展。在工程計算中,用數值方法求解數學問題(數學模型)得到廣泛應用.對絕大多數問題而言,要獲得解析解并非易事,而從應用角度看,求得一個數學模型的數值解已經足夠了.
    中文名:數值分析 外文名:numerical analysis 适用領域:計算數學 所屬學科: 研究分析:用計算機求解數學數值計算方法 研究對象:數字計算機求解數學問題的理論 應用學科:數學

簡介

數值分析的目的是設計及分析一些計算的方式,可針對一些問題得到近似但夠精确的結果。以下是一些會用利用數值分析處理的問題:

數值天氣預報中會用到許多先進的數值分析方法。

計算太空船的軌迹需要求出常微分方程的數值解。

汽車公司會利用電腦模拟汽車撞擊來提升汽車受到撞擊時的安全性。電腦的模拟會需要求出偏微分方程的數值解。

對沖基金會利用各種數值分析的工具來計算股票的市值及其變異程度。

航空公司會利用複雜的最佳化算法決定票價、飛機、人員分配及用油量。此領域也稱為作業研究。

保險公司會利用數值軟件進行精算分析。

直接法叠代法

直接法和叠代法

考慮以下問題

3x+4=28

要求解未知數x

3x+4=28.

減4得3x=24.

除以3得x=8.

開立方x=2.

若是用叠代法,可用叠代法求解f(x)=3x−24,初值為a=0,b=3,f(a)=−24,f(b)=57。

ab中點f(中點)

031.5−13.875

1.532.2510.17...

1.52.251.875−4.22...

1.8752.252.06252.32...

計算到目前為止,問題的解是界于1.875及2.0625之間,若繼續往下算,可以得到更精确的答案。

直接法利用固定次數的步驟求出問題的解。這些方式包括求解線性方程組的高斯消去法及QR算法,求解線性規劃的單純形法等。若利用無限精度算術的計算方式,有些問題可以得到其精确的解。不過有些問題不存在解析解(如五次方程),也就無法用直接法求解。在電腦中會使用浮點數進行運算,在假設運算方式穩定的前提下,所求得的結果可以視為是精确解的近似值。

叠代法是通過從一個初始估計出發尋找一系列近似解來解決問題的數學過程。和直接法不同,用叠代法求解問題時,其步驟沒有固定的次數,而且隻能求得問題的近似解,所找到的一系列近似解會收斂到問題的精确解。會利用審斂法來判别所得到的近似解是否會收斂。一般而言,即使使用無限精度算術的計算方式,叠代法也無法在有限次數内得到問題的精确解。

在數值分析中用到叠代法的情形會比直接法要多。例如像牛頓法、二分法、雅可比法、廣義最小殘量方法(GMRES)及共轭梯度法等等。在計算矩陣代數中,大型的問題一般會需要用叠代法來求解。

離散化

許多時候需要将連續模型的問題轉換為一個離散形式的問題,而離散形式的解可以近似原來的連續模型的解,此轉換過程稱為離散化。例如求一個函數的積分是一個連續模型的問題,也就是求一曲線以下的面積若将其離散化變成數值積分,就變成将上述面積用許多較簡單的形狀(如長方形、梯形)近似,因此隻要求出這些形狀的面積再相加即可。

例如在二小時的賽車比賽中,記錄了三個不同時間點的賽車速度,如下表:

時間

0:20

1:00

1:40

km/h

140

150

180

利用離散化的方式,可以假設賽車在0:00到0:40之間的速度、0:40到1:20之間的速度及1:20到2:00之間的速度分别為三個定值,因此前40分鐘的總位移可近似為(2/3h×140km/h)=93.3公裡。可依此方式近似二小時内的總位移為93.3公裡+100公裡+120公裡=313.3公裡。位移是速度的積分,而上述的作法是用黎曼和進行數值積分的一個例子。

誤差

誤差是數值分析的重要主題之一。誤差的形成可分為幾種不同的原因。

舍入誤差

當進行數值分析的設備隻能用有限位數來表示一個實數時,就會出現舍入誤差(Round-off error),例如用可顯示十位數字的計算器計算1/3,所得到的結果0.333333333,和實際數值的誤差就是舍入誤差。即使進行數值分析的設備用浮點數來表示實數,仍無法完全避免舍入誤差的問題。

離散化誤差

若叠代法的數值分析算到某一程度就中止計算,或是使用一些近似的數學程序,程序所得結果和精準解不同,就會出現截尾(Truncation)誤差。将問題離散化後,由于離散化問題的解不會和原問題的解完全一様,因此會出現離散化誤差。例如用叠代法計算3x3+4=28的解,在計算幾次後我們認為其解為1.99,就會有0.01的截尾誤差。

一旦有了誤差,誤差就會借着計算繼續的擴散。例如一個計算機中的加法是不準的,則a+b+c+d+e的計算也一定不準。例如剛剛計算3x+4=28的解為1.99,若後續的運算需要用到3x+4=28的解,用1.99代入所得的結果也會不準。當用近似的方式處理數學式時就會出現截尾誤差。

以積分為例,完全精準的積分需要求出曲線下方無限個梯形的面積和,但用在數值分析中會用有限個梯形的面積和來近似無限個梯形的面積和,此時就會出現截尾誤差。若要對一個函數進行微分,其微分量需要趨近于0,但實務上隻能選擇很小的微分量。

領域研究

數值分析依其待求解的問題不同,分為不同的領域。

内插法:假設一點鐘的氣溫為20度,三點鐘時為14度,可以用線性内插法推測一點半及二點鐘時的氣溫分别是18.5度及17度。

外推法:假設某國家國内生産總值平均每年成長百分之五,去年國内生産總值為一百萬元,可推測今年的國内生産總值為一百零五萬元。

回歸分析:給定幾個二維座标上的點,回歸分析就是設法找到一條最接近這些點的直線。

最佳化:有一個賣飲料的小販,若每杯飲料100元,每天可以賣197杯飲料,若飲料單價增加1元,每天就會少賣1杯飲料。飲料定價為148.5元時,其每天的收入為最大值。不過由于飲料單價需為正整數,因此飲料定價可定為149元,對應每天的收入為22,052元。

微分方程:假設在一房間中的不同位置放置一百個風扇,然後在房間中放置一根羽毛,羽毛會依房間中氣流而移動,而房間中的氣流可能相當複雜。不過每一秒量測一次羽毛附近空氣的速度,假設羽毛下一秒是等速的直線運動,即可求得下一秒時羽毛的位置,再量測當時羽毛附近空氣的速度,……。這種方法稱為歐拉方法,常使用在常微分方程的數值分析。

函數求值

數值分析中最簡單的問題就是求出函數在某一特定數值下的值。最直覺的方法是将數值代入函數中計算,不過有時此方式的效率不佳。像針對多項式函數的求值,較有效率的方式是秦九韶算法,可以減少乘法及加法的次數。若是使用浮點數,很重要的是是估計及控制舍入誤差。

求解方程

另一種常見的問題是求特定方程式的解。首先會依方程式是否線性來區分,例如方程式2x+5=3是線性方程式,而2x25=3是非線性方程式。此領域許多的研究都和求解線性方程組有關。直接法是線性方程組的系數以矩陣來表示,再利用矩陣分解的方式求解,這些方法包括高斯消去法、LU分解,對于對稱矩陣(或埃爾米特矩陣)及正定矩陣可以用喬萊斯基分解,非方陣的矩陣則可以用QR分解。叠代法包括有雅可比法、高斯–塞德叠代法、逐次超松馳法(SOR)及共轭梯度法,一般會用在大型的線性方程組中。

求根算法是要解一非線性方程,其名稱是因為函數的根就是使其值為零的點。若函數本身可微且其導數是已知的,可以用牛頓法求解,其他的方法包括二分法、割線法等。線性化則是另一種求解非線性方程的方法。

求解特征值

許多重要的問題可以用奇異值分解或特征分解來表示。例如有些圖像壓縮算法就是以奇異值分解為基礎。統計學中對應的工具稱為主成分分析。

最優化

最優化問題的目的是要找到使特定目标函數有最大值(或最小值)的點,一般而言這個點需符合一些約束。

依目标函數及約束條件的不同,最佳化又可以再細分:例如線性規劃處理目标函數及約束條件均為線性的情形,常用單純形法來求解。若目标函數及約束條件其中有一項為非線性,就是非線性規劃的範圍。

有約束條件的問題可以利用拉格朗日乘數轉換為沒有約束條件的問題。

積分計算

數值積分的目的是在求一定積分的值。一般常用牛頓-寇次公式,包括辛普森積分法、高斯求積等。上述方式是利用分治法來處理積分問題,也就是将大範圍的積分切割成許多小範圍的積分,再進行計算。不過在高維度時,上述作法可能會因為要作許多的計算而變得不實用(也就是維數之咒所描述的情形),此時可以采用蒙地卡羅方法或半蒙地卡羅方法。(可參照蒙地卡羅積分,或是适用于高維度的稀疏網格法。)

微分方程

數值分析也會用近似的方式計算微分方程的解,包括常微分方程及偏微分方程。

常微分方程往往會使用叠代法,已知曲線的一點,設法算出其斜率,找到下一點,再推出下一點的資料。歐拉方法是其中最簡單的方式,較常使用的是龍格-庫塔法。

偏微分方程的數值分析解法一般都會先将問題離散化,轉換成有限元素的次空間。可以透過有限元素法、有限差分法及有限體積法,這些方法可将偏微分方程轉換為代數方程,但其理論論證往往和泛函分析的定理有關。另一種偏微分方程的數值分析解法則是利用離散傅立葉變換或快速傅立葉變換。

相關詞條

相關搜索

其它詞條