計(jì)算方法概論與理論基礎(chǔ)(12)

1、北京科技大學(xué)數(shù)理學(xué)院 衛(wèi)宏儒 ,科學(xué)與工程計(jì)算,公用郵箱： 密碼：lhl213,參考書：請(qǐng)看本教材的參考文獻(xiàn)。,課程性質(zhì)和計(jì)劃,計(jì)算方法,概論,數(shù)值計(jì)算的理論基礎(chǔ),矩陣特征值與特征向量的計(jì)算,方程組及非線性方程的數(shù)值解法,線性方程組的解法,非線性方程求根,數(shù)值逼近與曲線擬合,數(shù)值逼近方法,常微分方程初值(邊值)問題的數(shù)值解法,插值法,數(shù)值積分與數(shù)值微分,計(jì)算方法,概論,數(shù)值計(jì)算的理論基礎(chǔ),矩陣特征值與特征向量的計(jì)算,方程組及非線性方程的數(shù)值解法,線性方程組的解法,非線性方程求根,第一章 計(jì)算方法概論,簡(jiǎn)要地介紹計(jì)算數(shù)學(xué)的一些基本概念。包括計(jì)算數(shù)學(xué)的對(duì)象、應(yīng)用和發(fā)展，計(jì)算機(jī)中數(shù)的浮點(diǎn)運(yùn)算，誤差的

2、基本概念、問題的性態(tài)以及算法的數(shù)值穩(wěn)定性等 ； 1、計(jì)算數(shù)學(xué)引論 計(jì)算數(shù)學(xué)的對(duì)象； 計(jì)算數(shù)學(xué)的應(yīng)用與發(fā)展； 2、算法及其效率 算法；,算法的計(jì)算量 3、機(jī)器數(shù)系 4、誤差的基本概念 誤差的來(lái)源 模型誤差；觀測(cè)誤差；截?cái)嗾`差；舍入誤差。 誤差與有效數(shù)字 誤差（絕對(duì)誤差）；誤差限；相對(duì)誤差；相對(duì)誤差限；有效數(shù)字。,和、差、積、商的誤差； 數(shù)據(jù)的機(jī)器浮點(diǎn)數(shù) 浮點(diǎn)數(shù)的算術(shù)運(yùn)算 5、問題的性態(tài)與算法的數(shù)值穩(wěn)定性 良態(tài)與病態(tài)問題 算法的數(shù)值穩(wěn)定性 數(shù)值計(jì)算中值得注意的事項(xiàng) 6、應(yīng)用實(shí)例與Matlab,計(jì)算機(jī)解決實(shí)際問題的步驟 建立數(shù)學(xué)模型 選擇數(shù)值方法 編寫程序 上機(jī)計(jì)算,實(shí)際問題數(shù)學(xué)問題提供計(jì)算方法 程

3、序設(shè)計(jì)上機(jī)計(jì)算結(jié)果分析,在計(jì)算機(jī)上是否根據(jù)數(shù)學(xué)公式編程就能得到正確結(jié)果?,研究例子:求解線性方程組 其準(zhǔn)確解為x1=x2=x3=1,如把方程組的系數(shù)舍入 成兩位有效數(shù)字,它的解為x1 =-6.222. x2=38.25 x3=-33.65.,數(shù)值分析研究的對(duì)象,研究數(shù)值方法的設(shè)計(jì)、分析和有關(guān)理論基礎(chǔ)與軟件實(shí)現(xiàn)。,計(jì)算方法又稱：計(jì)算數(shù)學(xué)、數(shù)值方法、數(shù)值分析等。 計(jì)算方法的分枝有最優(yōu)化方法、計(jì)算幾何、計(jì)算概率統(tǒng)計(jì)等。,計(jì)算方法的內(nèi)容,連續(xù)系統(tǒng)的離散化 離散性方程的數(shù)值求解,串行計(jì)算方法與并行計(jì)算方法的關(guān)系：并行計(jì)算方法70年代初隨并行計(jì)算機(jī)的出現(xiàn)而產(chǎn)生，是計(jì)算數(shù)學(xué)中最活躍的新領(lǐng)域。,什么是算法和計(jì)

4、算量？,算法：從給定的已知量出發(fā)，經(jīng)過有限次四則運(yùn)算及規(guī)定的運(yùn)算順序，最后求出未知量的數(shù)值解，這樣構(gòu)成的完整計(jì)算步驟稱為算法。 計(jì)算量：一個(gè)算法所需的乘除運(yùn)算總次數(shù)，單位是flop.計(jì)算量是衡量一個(gè)算法好壞的重要標(biāo)準(zhǔn)。 例題：矩陣乘法的計(jì)算量。,規(guī)格化浮點(diǎn)數(shù) x= 0.a1 a2.at10c ai0,1,2,9, a10，Lc U 一般情況： x= 0.a1 a2.atc ,=2,8,10,16, ai0,1,2, -1, Lc U F(,t.L,U)表示以上數(shù)集全體加數(shù)0， 它是計(jì)算機(jī)中使用有限離散集。,計(jì)算機(jī)中的數(shù)系,階碼,尾數(shù),溢出錯(cuò)誤,計(jì)算機(jī)中數(shù)的計(jì)算特點(diǎn) 1. 加法先對(duì)階,后運(yùn)算,再

5、舍入。 2. 乘法先運(yùn)算,再舍入。 3. 不在計(jì)算機(jī)數(shù)系中的數(shù)做四舍五入處理。,例如:在四位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上計(jì)算1+ 104 解: 1+ 104 =0.1000 101+ 0.1000 105 = 0.00001 105 + 0.1000 105 (對(duì)階計(jì)算) = 0.10001 105 = 0.1000 105 = 104,1、模型誤差 2、觀測(cè)誤差 3、截?cái)嗾`差 4、舍入誤差,誤差的來(lái)源,絕對(duì)誤差：e = x* - x , x* 是準(zhǔn)確數(shù) x是近似數(shù) 絕對(duì)誤差限：|e| = |x* - x| 常表示為x= x* 或x* - x x* + 相對(duì)誤差：er =(x*-x)/x* , x*

6、 是準(zhǔn)確數(shù), x是近似數(shù) 相對(duì)誤差限r(nóng)：|er/ x*|= |x* - x|/|x*| r 相對(duì)誤差比絕對(duì)誤差更能反映準(zhǔn)確數(shù)與近似數(shù)的差異 例:考慮 1.x* =10, x=11 e=-1 er=-0.1 2.x* =1000, x=1001 e=-1 er=-0.001,誤差定義,如果|e| = |x* - x| 0.5 10-k 稱近似數(shù)x準(zhǔn)確到小數(shù)點(diǎn)后第k位,從這小數(shù)點(diǎn)后第k位數(shù)字直到最左邊非零數(shù)字之間的所有數(shù)字都稱為有效數(shù)字.,有效數(shù)字,用四舍五入得到的數(shù)都是有效數(shù)字 有效數(shù)字越多,誤差越小,計(jì)算結(jié)果越精確.,例如:設(shè) x1=1.73, x2=1.7321, x3=1.7320是其近似

7、值,問它們分別有幾位有效數(shù)字?,四則運(yùn)算的誤差,絕對(duì)誤差：e = x* - x =xdx 相對(duì)誤差：er =(x*-x)/x* dx/x=dlnx 利用這個(gè)關(guān)系可以討論四則運(yùn)算的誤差和函數(shù)的誤差。例如下列式子說明什么誤差結(jié)果? d(x+y)=dx+dy dln(xy)=dlnx+dlny dln(xn)=ndlnx,數(shù)值計(jì)算中值得注意的問題,一、防止相近的兩數(shù)相減 (會(huì)耗失許多有效數(shù)字,可以用數(shù)學(xué)公式化簡(jiǎn)后再做.) 例1: 各有五位有效數(shù)字的23.034與22.993相減. 23.034-22.993=0.041 0.041只有兩位有效數(shù)字,有效數(shù)字的耗失,說明準(zhǔn)確度減小,因此,在計(jì)算時(shí)需要加

8、工計(jì)算公式,以免這種情況發(fā)生. 例2:當(dāng)x較大時(shí),計(jì)算,二、防止大數(shù)吃小數(shù). 當(dāng)兩個(gè)絕對(duì)值相差很大的數(shù)進(jìn)行加法或減法運(yùn)算時(shí),絕對(duì)值小的數(shù)有可能被絕對(duì)值大的數(shù)吃掉從而引起計(jì)算結(jié)果很不可靠. 例:求一元二次方程x2-(108 +1)x+108=0 的實(shí)數(shù)根. 采用因式分解法,很容易得到兩個(gè)根為x1=108,x2=1.如采用字長(zhǎng)為16位的單精度計(jì)算機(jī)來(lái)計(jì)算,求得根為x1108 ,x20.(怎樣計(jì)算可得較好的結(jié)果?) 兩者結(jié)果不同,因?yàn)橛?jì)算機(jī)計(jì)算時(shí)做加減法要 “對(duì)階”,“對(duì)階”的結(jié)果使大數(shù)吃掉了小數(shù).產(chǎn)生了誤差.為了避免由于上述原因引起的計(jì)算結(jié)果嚴(yán)重失真,可以根據(jù)一些具體情況,存在需要把某些算式改寫成

9、另一種等價(jià)的形式.,.,三、防止接近零的數(shù)做除數(shù) 分母接近零的數(shù)會(huì)產(chǎn)生溢出錯(cuò)誤,因而產(chǎn)生大的誤差,此時(shí)可以用數(shù)學(xué)公式化簡(jiǎn)后再做.,四、注意計(jì)算步驟的簡(jiǎn)化,減小運(yùn)算次數(shù)。,簡(jiǎn)化計(jì)算步驟是提高程序執(zhí)行速度的關(guān)鍵，它不僅可以節(jié)省時(shí)間，還能減少舍入誤差。 例1：計(jì)算9255的值，若逐個(gè)相乘要用254次乘法，但若寫成 9255 = 9 92 94 98 916 932 964 9128 只需做14次乘法運(yùn)算即可。 例2：設(shè)A、B、C、D分別是1020、 2050、 501、 1100的矩陣，試按不同的算法求矩陣乘積E=ABCD. 解：由矩陣乘法的結(jié)合律，可有如下算法 1. E=(AB)C)D. 計(jì)算量N

10、=11500flop 2. E=A(B(CD). 計(jì)算量N=125000flop 3. E=(A(BC)D. 計(jì)算量N=2200flop,矩陣乘積AB的計(jì)算量分析,a11 a12 a13 a1n a21 a22 a23 a2n . . . am1 am2 amm-1 amn,b11 b12 b13 b1s b21 b22 b23 b2s . . . bn1 bn2 bnn-1 bns,=cijms,因?yàn)?cij=aik bkj 計(jì)算量為N 所以上面A mn B ns的計(jì)算量為N= m n s,第二章 數(shù)值計(jì)算的理論基礎(chǔ),泛函分析這門現(xiàn)代數(shù)學(xué)學(xué)科，雖然起源于世紀(jì)，但形成一門系統(tǒng)的數(shù)學(xué)卻是世紀(jì)的事

11、；它從早期數(shù)學(xué)的許多分枝中抽取精華，并且不斷地加以系統(tǒng)化成為更一般的抽象形式。而數(shù)值計(jì)算卻是一門實(shí)用學(xué)科，主要以來(lái)自實(shí)際的數(shù)值問題為研究對(duì)象，雖然計(jì)算中用了非常復(fù)雜的現(xiàn)代工具，但本質(zhì)上只是數(shù)的四則運(yùn)算。表面上看來(lái)這兩門學(xué)科沒有什么聯(lián)系，但事實(shí)上數(shù)值計(jì)算發(fā)生革命性變化的原因之一，正是運(yùn)用了泛函分析。 本章介紹泛函分析中的一些基本概念。這一方面有利于后面各章中對(duì)數(shù)值問題的討論；另一方面，通過數(shù)值問題導(dǎo)出泛函分析的一些概念，也有利于我們理解泛函分析的一些內(nèi)容。這樣可以培養(yǎng)我們建立和運(yùn)用現(xiàn)代數(shù)學(xué)知識(shí)的意識(shí)。,、距離與極限 距離是常見的概念之一。幾何中線段的長(zhǎng)度是其兩個(gè)端點(diǎn)的距離，一個(gè)實(shí)數(shù)與其近似值的絕

12、對(duì)誤差也是距離。仔細(xì)研究來(lái)自通常距離的一些結(jié)論，會(huì)發(fā)現(xiàn)它們所依賴的基礎(chǔ)距離定義是很簡(jiǎn)單的，如果拋開直觀的幾何假設(shè)，可以把普通的距離概念推廣到任何一個(gè)集合中的兩個(gè)元素。 定義如下：,設(shè)X是一個(gè)非空集合，如果對(duì)任何一對(duì)元素，X，都有一個(gè)實(shí)數(shù)（，）與之對(duì)應(yīng)，而且滿足下面兩個(gè)條件： （）非負(fù)性（，），且（，）的充要條件是。 （）成立三角不等式 （，）（，）（，），X 則稱（，）是和兩個(gè)元素之間的距離，而稱定義了距離的非空集合X為度量空間或距離空間。記為（X，），此時(shí)X中的元素可稱為點(diǎn)。,根據(jù)上面的定義，容易得出距離還有對(duì)稱性，即（，）（，），這與通常的幾何距離是一致的。定義抽取了通常距離概念中最本質(zhì)的

13、內(nèi)容，利用這定義不但可以描述通常的距離，而且可以很容易地將這距離概念推廣到抽象的距離空間上。距離是衡量集合中兩個(gè)元素“相差”多少的一個(gè)量，這種“相差”含義就是廣義的距離。它一般可以根據(jù)具體的集合和要討論的問題來(lái)定義，需要指出的是，同一集合上可以定義出幾種不同的距離。例如，由平面上的二維點(diǎn)組成的集合X中，對(duì)任意的，X，可定義出至少如下三種距離(P26,例2-1)。 （例2-2;2-3;2-4)。,極限 微積分中的極限描述的是一組變?cè)淖兓厔?shì)，其本質(zhì)是通過“充分靠近”某個(gè)固定量引入的，而體現(xiàn)“靠近”的描述正是距離的意思。因此，可以在距離空間中引入極限概念。,定義2-3；定理2-1,2、壓縮映射,

14、例2-5；2-6,G的映內(nèi)性和壓縮性,例2-7,定義2-6,3、內(nèi)積 (1)線性空間 通常集合中的元素并非是沒有任何聯(lián)系的一堆“東西”，有些集合的元素之間可以進(jìn)行運(yùn)算，例如實(shí)數(shù)集中的元素就有加法和乘法等運(yùn)算，當(dāng)把看成是一般的集合，并抽取實(shí)數(shù)上的某些運(yùn)算性質(zhì)，就得到比集合更為豐富的內(nèi)容線性空間。 具體定義見P29頁(yè)。例2-8；2-9；2-10。,復(fù)習(xí)線性相關(guān)，線性無(wú)關(guān)，線性子空間，基，生成子空間的定義。 定義2-8，例2-11，2-12。,定義：設(shè)X是實(shí)數(shù)域R上的線性空間，如果任取， X，都對(duì)應(yīng)著一個(gè)實(shí)數(shù)（，）滿足條件： （）對(duì)稱性：（，）（，） （）齊次可加性：（，）（，）（，） ，R，X （

15、）正定性：對(duì)任何X，有（，），且（，）當(dāng)且僅當(dāng)， 則稱（，）是X中的內(nèi)積。稱定義了內(nèi)積的線性空間為內(nèi)積空間。,（2）內(nèi)積空間與元素的夾角,例：向量?jī)?nèi)積的定義。還有例2-13。,定理中的不等式稱為不等式。 按例2-13中所定義的向量空間和函數(shù)空間上的內(nèi)積 ，可以得到兩個(gè)重要不等式。 見P31：；,定義：內(nèi)積空間兩個(gè)元素的夾角；,定義：內(nèi)積空間兩個(gè)元素正交；,定義：內(nèi)積空間的正交元素組；,定理：內(nèi)積空間中的正交元素組一定線性無(wú)關(guān)。,4、范數(shù) 范數(shù)是與距離相類似的概念，不過范數(shù)是定義在線性空間上的，它利用了線性空間的代數(shù)結(jié)構(gòu)，范數(shù)的本質(zhì)是描述線性空間中元素的“長(zhǎng)度”或“大小”，它也能表示元素之間的距

16、離。在誤差估計(jì)和迭代法的收斂性研究中具有很重要的作用。,幾個(gè)基本概念及性質(zhì),1. 向量范數(shù)： 對(duì)任一向量X，按一定規(guī)則確定一個(gè)實(shí)數(shù)與其相對(duì)應(yīng)，該實(shí)數(shù)記為|X|，若|X|滿足下面三個(gè)性質(zhì)： （1）|X|0，|X|=0當(dāng)且僅當(dāng)X=0。 （2）對(duì)任意實(shí)數(shù) ，| X|=| | |X|。 （3）對(duì)任意向量YRn， |X+Y|X|+|Y|。 則稱該實(shí)數(shù)|X|為向量X的范數(shù). 2 .矩陣范數(shù)：,三種常用的向量范數(shù)：,例 ：設(shè) x=(1 , -4, 0, 2)T 求它的向量范數(shù),三種常用的矩陣范數(shù)：,例 ：設(shè) A，求它的矩陣范數(shù) .,例2-15,矩陣范數(shù)的性質(zhì)：,譜半徑： 設(shè) nn 階矩陣A的特征值為i(i=1,2,3n),則稱 (A)=MAX | i| 為矩陣A的譜半徑.1 in 矩陣范數(shù)與譜半徑之間的關(guān)系為: (A) |A|.,幾個(gè)定理及定義,設(shè)x(k)為 Rn中的向量序列, x(*)為Rn中的向量 對(duì)矩陣也有類似的結(jié)論.,如果 矩陣 A=(aij)滿足