數(shù)值分析課件1 jsff1

數(shù)值計(jì)算方法

與MATLAB應(yīng)用電氣工程學(xué)院

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

一個(gè)算法所需的乘除運(yùn)算總次數(shù)。計(jì)算量是衡量一個(gè)算法好壞的重要指標(biāo)伴隨著計(jì)算機(jī)速度的快速提升，需要求解問題的復(fù)雜程度也在迅速增加。

簡(jiǎn)單問題算法選擇不當(dāng)，導(dǎo)致無法計(jì)算。算法正確，顯著簡(jiǎn)化計(jì)算量。例1已知a0,a1,a2,…,an,

x,計(jì)算多項(xiàng)式：

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

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

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

運(yùn)算量(乘除)

Gauss:3060次；按每年3154萬秒

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

遞推化算法計(jì)算機(jī)適宜進(jìn)行大量重復(fù)的簡(jiǎn)單計(jì)算?？茖W(xué)計(jì)算常用算法遞推化的基本思想：復(fù)雜的計(jì)算過程歸結(jié)為簡(jiǎn)單過程的多次重復(fù)循環(huán)遞推化的優(yōu)勢(shì)：簡(jiǎn)化程序的邏輯結(jié)構(gòu)，同時(shí)也可以加快計(jì)算速度，可以節(jié)省內(nèi)存空間。例：對(duì)給定的X求下列n次多項(xiàng)式的值

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

§1誤差絕對(duì)的準(zhǔn)確和精確數(shù)值分析或數(shù)值計(jì)算，不嚴(yán)格，不準(zhǔn)確的錯(cuò)覺在工程領(lǐng)域中，既不存在也沒有實(shí)際意義?？倳?huì)存在誤差工程實(shí)際的合理性研究的問題所容許，計(jì)算結(jié)果的近似性不可避免否則計(jì)算的結(jié)果就沒有意義。因此研究算法的同時(shí)也要分析誤差。一、誤差的來源

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

2、觀測(cè)誤差

由觀測(cè)產(chǎn)生的誤差。

3、截?cái)嗾`差

當(dāng)數(shù)學(xué)模型不能得到精確解時(shí)，通常要用數(shù)值方法求它的近似解，其近似解與精確解之間的誤差稱為截?cái)嗾`差。如函數(shù)f(x)用Taylor展式的有限項(xiàng)來近似代替。

4、舍入誤差

由于受計(jì)算機(jī)字長(zhǎng)的限制，計(jì)算時(shí)只能取有限位數(shù)進(jìn)行運(yùn)算，由此產(chǎn)生的誤差稱舍入誤差。在數(shù)值計(jì)算中考慮：截?cái)嗾`差

舍入誤差

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

有效數(shù)字的損失,說明上述算法準(zhǔn)確度較低,因此,在計(jì)算時(shí)需要選擇適當(dāng)?shù)挠?jì)算公式,以免這種情況發(fā)生。

類似情況還有其他形式。這些在計(jì)算選擇中均應(yīng)注意。由于計(jì)算機(jī)只能用有限位數(shù)表示一個(gè)數(shù)，在計(jì)算過程中，當(dāng)兩個(gè)數(shù)很接近時(shí)，很有可能相減后所得結(jié)果為0，或者相減后有效數(shù)字位數(shù)大大減小。取四位有效數(shù)字計(jì)算時(shí)

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

而采用計(jì)算機(jī)解題時(shí)，方法不當(dāng)可得：x1=108,x2=0。

在8位十進(jìn)制計(jì)算機(jī)上計(jì)算

計(jì)算機(jī)內(nèi)部計(jì)算時(shí)，要先寫成浮點(diǎn)形式，且要先對(duì)階，對(duì)階時(shí)，后者在8位機(jī)上表示時(shí)為0，則則計(jì)算結(jié)果就是大數(shù)的值。

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

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

x*

與近似值

x的誤差的絕對(duì)值不超過某個(gè)正數(shù)ε，即

|e|=|x*－

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

x*=x±ε，或

。

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

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

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

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

,由于：方程至少有一個(gè)正實(shí)根。

00.51.01.5的符號(hào)

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

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

數(shù)值計(jì)算中有很多對(duì)粗糙近似值逐步精確化的方法。

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

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

是否同號(hào)

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

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

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

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

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