數值分析課件1 jsff1

數值計算方法

與MATLAB應用電氣工程學院

二、算法的優(yōu)劣1.計算量或運算量：

一個算法所需的乘除運算總次數。計算量是衡量一個算法好壞的重要指標伴隨著計算機速度的快速提升，需要求解問題的復雜程度也在迅速增加。

簡單問題算法選擇不當，導致無法計算。算法正確，顯著簡化計算量。例1已知a0,a1,a2,…,an,

x,計算多項式：

1）直接計算運算量（乘法）2）秦九韶算法（南宋1247年）運算量顯然運算量為n。求解線性方程組時原則上可以用行列式解法的克萊姆法則。用這種方法解一個n階方程組，要算n+1個n階行列式的值，計算量為：n(n-1)(n+1)次乘法運算。當變量較少時，計算量增加并不明顯，但是當變量較多時，例如n=20，顯然這不是一個太大的方程組，然而即使每秒十億次的計算機，也要工作千年才能完成。顯然這種算法在實際中是完全沒有意義的。例如：例2

解線性方程組其中，?克蘭姆(Cramer)法則：

運算量(乘除)：?高斯消元法(Gauss)：

運算量(乘除)

Gauss:3060次；按每年3154萬秒

Cramer:2）算法的存儲量計算程序所占用的工作單元的數目——算法的存貯量。或稱占用內存量。盡管計算機能貯存大量信息，目前內存和硬盤容量越來越大，但計算大型算題時也會出現(xiàn)內存緊張問題，因此，盡量節(jié)約存貯量也是設計算法時需要考慮的一個因素。3）算法的邏輯結構雖然計算機能夠自動執(zhí)行極其復雜的計算方案，但計算方案的每個細節(jié)都需要人來預先制定簡單的邏輯結構能使程序結構簡潔清晰會明顯優(yōu)化計算次數。對應用商業(yè)軟件系統(tǒng)，結構簡單的程序可使程序升級和修改非常便利。因此設計算法所要考慮的另一個因素是邏輯結構的復雜性問題。從計算人員的角度來看，總是希望算法的邏輯結構盡量簡化，使得編制程序和使用程序時比較方便。由此可見，雖然計算機功能強大，如果想提高其使用效率，就不能忽視算法的研究。計算量大小、存貯量多少、邏輯結構是否簡單，是評定算法優(yōu)劣的標準。三、算法的遞推性

遞推化算法計算機適宜進行大量重復的簡單計算。科學計算常用算法遞推化的基本思想：復雜的計算過程歸結為簡單過程的多次重復循環(huán)遞推化的優(yōu)勢：簡化程序的邏輯結構，同時也可以加快計算速度，可以節(jié)省內存空間。例：對給定的X求下列n次多項式的值

按降冪的次序排列為設用表示第層（從里數起）的值，因此最里面一層為：令初值則第二層為：第K層為：這種遞推算法不但邏輯結構簡單，而且由于反復使用一個存儲單元存放從而可以節(jié)省內存。

§1誤差絕對的準確和精確數值分析或數值計算，不嚴格，不準確的錯覺在工程領域中，既不存在也沒有實際意義。總會存在誤差工程實際的合理性研究的問題所容許，計算結果的近似性不可避免否則計算的結果就沒有意義。因此研究算法的同時也要分析誤差。一、誤差的來源

1、模型誤差指數學模型與實際問題之間出現(xiàn)的誤差。

2、觀測誤差

由觀測產生的誤差。

3、截斷誤差

當數學模型不能得到精確解時，通常要用數值方法求它的近似解，其近似解與精確解之間的誤差稱為截斷誤差。如函數f(x)用Taylor展式的有限項來近似代替。

4、舍入誤差

由于受計算機字長的限制，計算時只能取有限位數進行運算，由此產生的誤差稱舍入誤差。在數值計算中考慮：截斷誤差

舍入誤差

1）截斷誤差我們知道，許多數學運算（如微分，積分及無窮級數求和等）是通過極限過程來定義的，然而計算機只能完成有限次算術及邏輯運算，因此須將解題方案轉化成算術運算與邏輯運算的有限序列。這種加工常表現(xiàn)為某種無窮過程的“截斷”，由此產生的誤差通常稱為“截斷誤差”。下面以指數展開求和為例說明。指數函數可展開成下列冪級數形式許多數學計算如微分，積分，無窮級數的計算在理論上是無窮過程，而實際計算只能完成有限的運算，截斷誤差也是不可避免的。2）舍入誤差計算機上只能用有限數位來表示一個數，對于計算過程中超出限定位數的尾數都要被舍去而造成誤差，這種誤差稱為舍入誤差。產生較大誤差情形。兩個相近的數相減，兩個數值大小相差很大的數相除以后再乘一個很大的數因此計算時應該避免這種情況發(fā)生。（1）避免兩個非常接近的數進行減法運算設數字a=44.407,b=44.396，各有五位有效數字,若取3位有效數字進行減法運算：V=a-b=44.4-44.4=0.0

有效數字的損失,說明上述算法準確度較低,因此,在計算時需要選擇適當的計算公式,以免這種情況發(fā)生。

類似情況還有其他形式。這些在計算選擇中均應注意。由于計算機只能用有限位數表示一個數，在計算過程中，當兩個數很接近時，很有可能相減后所得結果為0，或者相減后有效數字位數大大減小。取四位有效數字計算時

V=a-b=44.41-44.40=0.01例3:設x為正數,當x較大時,計算算式改為：上述兩數a、b分別為1972和1971的開平方，取三位有效數字代入右端計算：取四位有效數字代入右端計算：差別不大此外還有x較大時：其他的有：x接近于0時：，（2）防止大數吃掉小數在上機計算時，有時計算中用到的數其數量級可能相差很大，由于計算機字長有限，或在實際應用中，定義的數字長度一定，如不注意運算次序，就可能出現(xiàn)當兩個絕對值相差很大的數進行加法或減法運算時,絕對值小的數被絕對值大的數“吃掉”，從而使得計算結果不可靠。例4:解一元二次方程采用因式分解法,得到兩個根為：x1=108,x2=1。

而采用計算機解題時，方法不當可得：x1=108,x2=0。

在8位十進制計算機上計算

計算機內部計算時，要先寫成浮點形式，且要先對階，對階時，后者在8位機上表示時為0，則則計算結果就是大數的值。

(3)防止接近于零的數做除數(4)

防止兩個相差很大的數相除然后再乘一個很大的數二、誤差限1）絕對誤差設x*為精確值（或準確值），x為x*的近似，稱e=x*-x為近似值x的絕對誤差。絕對誤差限：如果精確值

x*

與近似值

x的誤差的絕對值不超過某個正數ε，即

|e|=|x*－

x|≤ε。則精確值也可表示為

x*=x±ε，或

。

在給定的允許誤差下近似值x和真值x*可以看成是“重合”的，或者說在滿足允許誤差的情況下，結果x是“準確”的。這就是工程中的準確的概念。例如：近似值x1=123.456和x2=0.0123456。它們的絕對誤差限分別為：2）相對誤差絕對誤差有時不能說明誤差的程度，這時需要用到相對誤差的概念。例如：某廠生產某種產品1000件，不合格產品10件；另一種產品2000件，不合格產品10件，雖然絕對誤差相同，但相對誤差是不同的：10/1000=1%；10/2000=0.5%

三、有效數字誤差限和有效數字均能表示一個數字的精確程度，但其意義是有所區(qū)別的。在數值計算中,求出一個近似值后，我們希望明確其準確程度。對于（1）若取誤差為則該近似值有三位數是準確的，有3位有效數字。（2）近似值取誤差為其誤差絕對值小于

（3）若取近似值為其誤差為雖然給出的是5個數字，但其誤差絕對值超過了小數點后第四位的半個單位，因此其最后一位是不準確的，僅有四位有效數字。四舍五入的概念。第二章方程求解§1引言問題求解：多項式——代數方程無解析解經常對簡單的二次方程

有解析解而對無解析解非數值解數值計算方法特點：概念十分簡單，不需要引入許多復雜的數學知識。適合于在數字計算機上進行計算。(遞推化)有時不能得出結果，這個問題將在后面多種計算問題中進行具體的討論。(方法不當)數值計算一般來說只能得到近似解——但可以改善——選擇計算方法——精確的結果。例如：對方程f(x)求解。稱為它的根或函數的零點。數值解法兩步：先確定根的某個粗糙的近似值即初始近似值，然后再將初始近似值采取某種方法逐步加工成滿足所需精度的結果?！皰呙琛狈ㄇ蟾某跏冀浦怠８姆植伎赡苁呛軓碗s的，假設方程在某個區(qū)間(a,b)內有且僅有一個實單根，從左端點a出發(fā)，按預選的步長h一步一步地向右求取函數值，進行一次根的“掃描”，至到所求的根必在點與之間或作為根的初始近似值

,由于：方程至少有一個正實根。

00.51.01.5的符號

負負負正在區(qū)間（1.0,1.5）內必有一個實根。取初始根。例2.1考察方程掃描中，步長的選擇是關鍵。只要步長選得足夠小，——可以得到具有任意精度的近似根。

例如將步長選為計算問題的允許誤差，則最終得到的兩個邊界值均可滿足誤差要求。但步長小時計算量增大。因此如果精度要求比較高就不宜采用這種方法。

數值計算中有很多對粗糙近似值逐步精確化的方法。

§2二分法假定方程在區(qū)間（a,b）內有且僅有一個根

取其中點將區(qū)間（a,b）分為兩半

是否同號

判斷(1)同號說明根在右側，取新的求根區(qū)間（x0,b)

記為（a1,b1)(2)異號說明根在左側，新的求根區(qū)間（a,x0)

記為（a1,b1)如此反復下去，便可以得到一系列有根區(qū)間。每次二分求根區(qū)間縮小一半近似解序列誤差只要求根區(qū)間的長度小于關于允許誤差將能“準確”滿足則近似解注：《莊子天下篇》有這樣一個命題：“一尺之棰，日取其半，萬世不竭。”實際上也說明二分法可以得到任意精度的近似解，其極限即為根的真值。例2.2用二分法求方程在區(qū)間內的實根。要求準確到小數點后第2位。即允許誤差為0.005，書上給出了計算結果。顯然只要便能達到所要的精度

特點：求根區(qū)間縮小的速度很快，較少計算次數可得達精度要求，與直接掃描相比優(yōu)勢明顯?！?迭代法迭代法是一種逐次逼近法,求解非線性代數方程常用方法。原理：原方程變形作為固定的校正公式,反復校正根的近似值,使之逐步接近精確值,最后得到滿足精度要求的結果。同樣方程在設將方程變形為以下形式：附近的一個根。

KXKKXK012341.51.357211.330861.325881.3249456781.324761.324731.324721.32472對于方程一般形式設法將它化為下列形式如果給出根的某個近似值代入上式右端有：解序列