《計(jì)算方法word教案》word版

1、精品計(jì)算方法第一章 緒 論§1.0 引 言§ 數(shù)值算法概論(1) 計(jì)算方法的研究?jī)?nèi)容、對(duì)象與特點(diǎn)(2) 根本求解步驟§1.2 預(yù)備知識(shí)、誤差(1) 誤差的來源(2) 誤差分析、數(shù)值穩(wěn)定性的分析和說明(3) 誤差的根本概念絕對(duì)誤差 相對(duì)誤差 有效數(shù)字(4) 數(shù)值算法.精品§1.0 引 言¨ 現(xiàn)代科學(xué)的三個(gè)重要組成局部: 科學(xué)理論, 科學(xué)實(shí)驗(yàn), 科學(xué)計(jì)算。它們相輔相成，互相獨(dú)立，可以互相補(bǔ)充又都不可缺少，作為三種科學(xué)研究手段之一的科學(xué)計(jì)算是一門工具性、方法性、邊緣性的新學(xué)科，開展迅速，它的物質(zhì)根底是計(jì)算機(jī)(包括其軟硬件系統(tǒng))，其理論根底主要是計(jì)算數(shù)

2、學(xué)。 ¨ 科學(xué)計(jì)算的核心內(nèi)容是以現(xiàn)代化計(jì)算機(jī)以及數(shù)學(xué)軟件為工具，以數(shù)學(xué)模型為根底進(jìn)行模擬研究。¨ 出現(xiàn)了形如:計(jì)算數(shù)學(xué),計(jì)算物理學(xué),計(jì)算力學(xué),計(jì)算化學(xué), 計(jì)算生物學(xué),計(jì)算地質(zhì)學(xué),計(jì)算經(jīng)濟(jì)學(xué)等許多新學(xué)科及其開展。并已形成一系列專門研究數(shù)學(xué)問題的數(shù)值解法的算法軟件，如目前流行的數(shù)學(xué)軟件主要有以下幾種：符號(hào)運(yùn)算軟件： Mathematica, Maple矩陣處理軟件： Matlab Matlab簡(jiǎn)介統(tǒng)計(jì)處理軟件： SAS, Spss, Origin數(shù)學(xué)CAD軟件： MathCAD等功能強(qiáng)大的著名數(shù)學(xué)軟件。.精品§1.1 數(shù)值算法概論§ 計(jì)算方法的研究?jī)?nèi)容、對(duì)象

3、與特點(diǎn)內(nèi)容：(1) 數(shù)值代數(shù): 求解線性方程組的解法分直接方法和間接方法，求矩陣的特征值與特征向量。(2) 數(shù)值逼近：插值和數(shù)值逼近，數(shù)值微分和數(shù)值積分。(3) 方程求解：非線性方程、常微分方程、偏微分方程數(shù)值解法。對(duì)象：(1) 計(jì)算方法是一門與計(jì)算機(jī)應(yīng)用密切結(jié)合的實(shí)用性很強(qiáng)的學(xué)科； 思維方法是歸納法，核心問題是“誤差或誤差分析。 (2) 計(jì)算方法這門課程討論連續(xù)變量問題又要討論離散變量問題，關(guān)心的是數(shù)值結(jié)果。(3) 計(jì)算方法這門課程已成為近代數(shù)學(xué)的一個(gè)重要分支。 特點(diǎn)：(1) 面向計(jì)算機(jī)將計(jì)算機(jī)上不能執(zhí)行的運(yùn)算化為在計(jì)算機(jī)上可執(zhí)行的運(yùn)算;(2) 有可靠的理論分析收斂性、穩(wěn)定性、誤差分析。因?yàn)?/p>

4、可能采用了近似等價(jià)運(yùn)算,故要進(jìn)行誤差分析,即數(shù)值的性態(tài)及數(shù)值方法的穩(wěn)定性。(3) 要有好的算法，并考慮計(jì)算復(fù)雜性時(shí)間、空間針對(duì)所求解的數(shù)值問題研究在計(jì)算機(jī)上可執(zhí)行的且有效的計(jì)算公式。(4) 要有數(shù)值試驗(yàn).精品§1.1.2 根本求解步驟實(shí)際問題建立數(shù)學(xué)模型構(gòu)造數(shù)值 算法編程上機(jī)計(jì)算結(jié)果說明： (1)數(shù)學(xué)模型是通過科學(xué)實(shí)驗(yàn)或者觀察分析一系列數(shù)據(jù)后，用數(shù)學(xué)作為工具近似地描述客觀事物的一種數(shù)學(xué)表達(dá)式。在數(shù)學(xué)模型中，往往包含了假設(shè)干參量如物體比重、阻力系數(shù)、熱交換系數(shù)等，這些物理參數(shù)通常由實(shí)驗(yàn)儀器測(cè)得，根據(jù)儀器的精密程度，物理參數(shù)確實(shí)定也會(huì)產(chǎn)生一定的誤差。(2)在建立了數(shù)學(xué)模型之后，并不能立刻

5、用計(jì)算機(jī)直接求解，還必須尋找用計(jì)算機(jī)計(jì)算這些數(shù)學(xué)模型的數(shù)值方法，即將數(shù)學(xué)模型中的連續(xù)變量離散化，轉(zhuǎn)化成一系列相應(yīng)的算法步驟，編制出正確的計(jì)算程序，再上機(jī)計(jì)算得出滿意的數(shù)值結(jié)果。(3) 算法：從給定的量出發(fā)，經(jīng)過有限次四那么運(yùn)算及規(guī)定的運(yùn)算順序，最后求出未知量的數(shù)值解，這樣構(gòu)成的完整計(jì)算步驟稱為算法。評(píng)價(jià)算法的兩個(gè)主要標(biāo)準(zhǔn)：計(jì)算速度和計(jì)算精度，此外，還有計(jì)算存貯量等。 一個(gè)面向計(jì)算機(jī),計(jì)算復(fù)雜性好,又有可靠理論分析的算法就是一個(gè)好算法.計(jì)算復(fù)雜性是算法好壞的標(biāo)志，它包括時(shí)間復(fù)雜性(指計(jì)算時(shí)間多少)和空間復(fù)雜性(指占用存儲(chǔ)單元多少)。對(duì)很多數(shù)值問題使用不同算法，其計(jì)算復(fù)雜性將會(huì)大不一樣，例如對(duì)20

6、階的線性方程組假設(shè)用代數(shù)中的Cramer法那么作為算法求解，其乘除法運(yùn)算次數(shù)需要，假設(shè)用每秒運(yùn)算1億次的計(jì)算機(jī)計(jì)算也要30萬年，這是無法實(shí)現(xiàn)的，而用"計(jì)算方法"中介紹的Gauss消元法求解，其乘除法運(yùn)算次數(shù)只需3 060次，這說明選擇算法的重要性。當(dāng)然有很多數(shù)值方法事先不可能知道其計(jì)算量，故對(duì)數(shù)值方法除理論分析外，還必須通過數(shù)值試驗(yàn)檢驗(yàn)其計(jì)算復(fù)雜性。作為根本要求希望讀者能適當(dāng)做一些計(jì)算機(jī)上的數(shù)值試驗(yàn)，對(duì)加深算法的理解是極有好處的。例1.1：計(jì)算多項(xiàng)式的值。 算法1 由計(jì)算出后再計(jì)算。說明：需乘法6次，加法3次，存儲(chǔ)單元7個(gè)。 算法2 計(jì)算。說明：需乘法3次，加法3次，存儲(chǔ)單

7、元7個(gè)。例1.2：計(jì)算n次多項(xiàng)式的值。 算法 采用：秦九韶算法(1247) (又稱為Horner算法(1819) 計(jì)算。說明：需乘法n次，加法n次，存儲(chǔ)單元n+3個(gè)。上述秦九韶算法的結(jié)構(gòu)是遞歸的，它通過一次式的反復(fù)計(jì)算，逐步降低多項(xiàng)式的次數(shù)，直到歸結(jié)為零次式為止。假設(shè)以多項(xiàng)式的次數(shù)或項(xiàng)數(shù)定義為求值問題的規(guī)模，那么秦九韶算法的特點(diǎn)是，在遞歸計(jì)算的過程中問題的規(guī)模逐次減1。例1.3：計(jì)算在某點(diǎn)的值。數(shù)學(xué)上有如下算法: 算法(1) 算法(2) 顯然：算法1的計(jì)算量N=63次乘法；由于算法2中，故計(jì)算量N=11次乘法。算法2比算法1好。.精品§1.2 預(yù)備知識(shí)和誤差§1.2.1 誤

8、差的來源實(shí)際問題è建立數(shù)學(xué)模型è研究計(jì)算方法è編程上機(jī)計(jì)算è解結(jié)果a) 模型誤差: 在建立數(shù)學(xué)模型過程中,不可能將所有因素均考慮,必然要進(jìn)行必要的簡(jiǎn)化,這就帶來了與實(shí)際問題的誤差。b) 測(cè)量誤差: 測(cè)量參數(shù)時(shí),數(shù)據(jù)帶來的誤差。c) 截?cái)嗾`差: 在設(shè)計(jì)算法時(shí),必然要近似處理,尋求一些簡(jiǎn)化。d) 舍入誤差: 計(jì)算機(jī)的字長(zhǎng)是有限的,每一步運(yùn)算均需四舍五入，由此產(chǎn)出的誤差稱舍入誤差。如：、13，取小數(shù)點(diǎn)8位、16位。截?cái)嗾`差的實(shí)例例1.4： 當(dāng)很小時(shí)，可用作為的近似值，其截?cái)嗾`差小于。 例： ：求的近似值，并估計(jì)誤差。分析：對(duì)函數(shù)用Taylor展開，用多項(xiàng)式近似

9、代替，那么數(shù)值方法的截?cái)嗾`差為。 解：利用展開式的前三項(xiàng)，取n=2， 截?cái)嗾`差為：數(shù)值計(jì)算方法主要討論截?cái)嗾`差和舍入誤差的影響,不討論模型誤差和測(cè)量誤差。.精品§1.2.2 誤差分析的重要性以及數(shù)值穩(wěn)定性一個(gè)數(shù)值方法進(jìn)行計(jì)算時(shí)，由于原始數(shù)據(jù)有誤差，在計(jì)算中這些誤差會(huì)傳播，有時(shí)誤差增長(zhǎng)很快使計(jì)算結(jié)果誤差很大，影響了結(jié)果不可靠.定義一個(gè)算法如果原始數(shù)據(jù)有擾動(dòng)(即誤差)，而計(jì)算過程舍入誤差不增長(zhǎng)，那么稱此算法是數(shù)值穩(wěn)定的.否那么，假設(shè)誤差增長(zhǎng)那么稱算法不穩(wěn)定.例如：計(jì)算并分析誤差 解：由積分估值 由積分性質(zhì)知 設(shè)計(jì)如下兩種算法：算法1：取，按公式 n=0，1，2依次計(jì)算的近似值。設(shè)。假設(shè)計(jì)

10、算過程中不產(chǎn)生新的舍入誤差，那么有n=0，1，2 誤差擴(kuò)散。算法2：從計(jì)算，應(yīng)有 。在運(yùn)算過程中，舍入誤差不增大,數(shù)值穩(wěn)定。 n012345678關(guān)于數(shù)值穩(wěn)定性的算法v 誤差的傳播與積累例：蝴蝶效應(yīng) 紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京就刮起臺(tái)風(fēng)來了？！v 以上是一個(gè)病態(tài)問題例5: , 解：用分部積分公式得遞推式:。 用四位有效數(shù)字計(jì)算: , , , , , , , ,.分析1： 可以估計(jì)出 故 ,。 于是與精確值已經(jīng)面目全非,一位有效數(shù)字也沒有。這是由于如果有誤差,不計(jì)中間再產(chǎn)生的舍入誤差,該誤差隨著計(jì)算過程分別乘以,到時(shí)已經(jīng)變成了,誤差擴(kuò)大了4萬倍。因而該算法不是穩(wěn)定的。分析2：如果遞推

11、式改為,由, ,逐步計(jì)算直到。計(jì)算結(jié)果有四位有效數(shù)字,如果有誤差,其傳播到所引起的誤差僅為。故該算法是穩(wěn)定的。.精品三、誤差的根本概念(1) 誤差與誤差限是精確值, 是它的一個(gè)近似值，稱是近似值的絕對(duì)誤差。簡(jiǎn)稱誤差。誤差是有量綱的,可正可負(fù)。誤差是無法計(jì)算的,但可以估計(jì)出它的一個(gè)上界。即,稱是近似值 的誤差限,即 。(2) 相對(duì)誤差與相對(duì)誤差限稱為近似值的相對(duì)誤差,記作。相對(duì)誤差是個(gè)相對(duì)數(shù),是無量綱的,也可正可負(fù)。相對(duì)誤差的估計(jì),稱為相對(duì)誤差限,即。實(shí)際中, 是未知的,可用來代替。當(dāng)較小時(shí),因兩者的差為: 是的高階無窮小，可忽略不計(jì)。 (3) 有效數(shù)字定義: 如果近似值的誤差限是 (某一數(shù)位的

12、半個(gè)單位),那么稱準(zhǔn)確到小數(shù)點(diǎn)后位,并從第一個(gè)非零的數(shù)字到這一位的所有數(shù)字均為有效數(shù)字。 如： 有三位有效數(shù)字,誤差限;有五位有效數(shù)字,誤差限為。如： 近似值準(zhǔn)確到小數(shù)點(diǎn)后五位，有三位有效數(shù)字。(4) 有效數(shù)字與誤差限的關(guān)系：有n位有效數(shù)字，標(biāo)準(zhǔn)形式為，那么有。有效位數(shù)越多，絕對(duì)誤差限越小。e) 有效數(shù)字與相對(duì)誤差限的關(guān)系：定理1：，假設(shè)有位有效數(shù)字，那么其相對(duì)誤差限為 反之，假設(shè)的相對(duì)誤差限為那么至少具有n位有效數(shù)字。證：因 ，故當(dāng)有n位有效數(shù)字時(shí)， 。 反之，由因此，至少具有n位有效數(shù)字。 證畢定理說明，有效位數(shù)越多相對(duì)誤差限越小。實(shí)例例1 設(shè)= p×101,即m=1，它的絕對(duì)誤

13、差是 0.001 592 6，有即l=3，故x=3.14有3位有效數(shù)字。x=3.14準(zhǔn)確到小數(shù)點(diǎn)后第2位。，有 即m=1,l5，x=3.1416有5位有效數(shù)字。，有 即m=1,l4，x=3.1415有4位有效數(shù)字。這就是說某數(shù)有s位數(shù)，假設(shè)末位數(shù)字是四舍五入得到的，那么該數(shù)有s位有效數(shù)字；例2 指出以下各數(shù)具有幾位有效數(shù)字，及其絕對(duì)誤差限和相對(duì)誤差限： 解 因?yàn)閤1=2.000 40.200 04××10 15，即m=1,l=5,故x=2.000 4有5位有效數(shù)字. a1=2，相對(duì)誤差限x2=0.002 00，絕對(duì)誤差限0.000 005，因?yàn)閙=2，l=3，x2=0.00

14、2 00有3位有效數(shù)字. a1=2，相對(duì)誤差限er=0.002 5×100，因?yàn)閙=4, l=4, x3=9 000有4位有效數(shù)字，a=9，相對(duì)誤差限er0.000 056x4=9 000.00，絕對(duì)誤差限0.005，因?yàn)閙=4，l=6，x4=9 000.00有6位有效數(shù)字，相對(duì)誤差限為er=er0.000 000 56由x3與x4可以看到小數(shù)點(diǎn)之后的0，不是可有可無的，它是有實(shí)際意義的。，精確到103的近似值是多少？解 精確到1030.001，即絕對(duì)誤差限是e0.0005, 故至少要保存小數(shù)點(diǎn)后三位才可以。.精品§ 數(shù)值算法例:求解微分方程: 將其變成數(shù)值問題，即將其“離

15、散化 “離散化是將非數(shù)值問題的數(shù)學(xué)模型化為數(shù)值問題的主要方法，這也是計(jì)算方法的任務(wù)之一。計(jì)算方法的主要任務(wù)1. 將計(jì)算機(jī)上不能執(zhí)行的運(yùn)算化為在計(jì)算機(jī)上可執(zhí)行的運(yùn)算；2. 針對(duì)所求解的數(shù)值問題，研究在計(jì)算機(jī)上可執(zhí)行的且有效的計(jì)算公式；3. 因?yàn)榭赡懿捎昧私频葍r(jià)運(yùn)算,故要進(jìn)行誤差分析,即數(shù)值問題的性態(tài)及數(shù)值 方法的穩(wěn)定性。.精品Matlab簡(jiǎn)介：MATLAB的含義是矩陣實(shí)驗(yàn)室,是Matrix Laboratory的縮寫。它的前身是LINPACK解線性方程和EISPACK解特征值問題的FORTRAN子程序庫。由于它把矩陣當(dāng)成一個(gè)對(duì)象，因此編寫程序更加直觀、方便。1984年正式推出,最新版本為V7.

16、0 Release14.MATLAB具有非常強(qiáng)大和直觀的計(jì)算功能，并且由于其有非常好的擴(kuò)展性能，現(xiàn)在已成為世界上應(yīng)用最廣泛的工程計(jì)算軟件之一。(1)強(qiáng)大的數(shù)值運(yùn)算功能在MATLAB環(huán)境中，有超過500種數(shù)學(xué)、統(tǒng)計(jì)、科學(xué)及工程方面的函數(shù)可使用，函數(shù)的命名表示自然，使得問題和解答像數(shù)學(xué)公式一般簡(jiǎn)單明了，讓用戶可全力發(fā)揮在解題方面，而非浪費(fèi)在電腦操作上。 (2)數(shù)據(jù)分析和可視化功能、文字處理功能MATLAB可以繪制二、三維圖形，與Mathematic和Maple相比，它還能處理光照模型，制作出高品質(zhì)的圖形。功能十分強(qiáng)大。MATLAB Notebook為用戶提供了強(qiáng)大的文字處理功能，并允許WORD訪問

17、MATLAB的數(shù)值計(jì)算和可視化結(jié)果，制作科學(xué)性或工程性圖文并茂的文章.(3)高級(jí)、簡(jiǎn)單、高效的程序環(huán)境 做為一種解釋型的程序語言，MATLAB允許使用者在短時(shí)間內(nèi)寫完程序,所花的時(shí)間約為用 FORTRAN或 C 的幾分之一，而且不需要編譯 (compile) 及連接(link) 即能執(zhí)行，同時(shí)包含了更多及更容易使用的內(nèi)建功能。 (4)開放及可延伸的架構(gòu) MATLAB允許使用者接觸它的大多數(shù)的數(shù)學(xué)源代碼，檢查運(yùn)算法，更改現(xiàn)有函數(shù)，甚至參加自己的函數(shù)使 MATLAB成為使用者所需要的環(huán)境。 (5)豐富的工具箱MATLAB的工具箱融合了套裝前軟體的優(yōu)點(diǎn)，與一個(gè)靈活的開放但容易操作之環(huán)境，這些工具箱提

18、供了使用者在特別應(yīng)用領(lǐng)域所需的許多函數(shù)?，F(xiàn)有工具箱有：符號(hào)運(yùn)算利用Maple V的計(jì)算核心執(zhí)行、圖像處理、統(tǒng)計(jì)分析、信號(hào)處理、通信、線性矩陣不等式、偏微分方程、高階譜分析、財(cái)政金融、神經(jīng)網(wǎng)絡(luò)、模擬分析、控制系統(tǒng)、實(shí)時(shí)控制、小波分析、最優(yōu)化、模糊邏輯、分析及合成等30多種。 _END_第二章 方程求根§2.0 引 言§2.1 二分法§2.2 簡(jiǎn)單迭代法§2.3 牛頓Newton法§2.4 其它求根方法迭代過程的加速方法§2.5 作業(yè)講評(píng)§2.0引 言 非線性科學(xué)是當(dāng)今科學(xué)開展的一個(gè)重要研究方向，非線性方程的求根也成為其中一個(gè)重

19、要內(nèi)容。一般而言，非線性方程的求根非常復(fù)雜。 在實(shí)際應(yīng)用中有許多非線性方程的例子，例如1在光的衍射理論the theory of diffraction of light)中,需要求x-tanx=0的根2在行星軌道 planetary orbits的計(jì)算中,對(duì)任意的a和b，需要求x-asinx=b的根3在數(shù)學(xué)中，需要求n次多項(xiàng)式的根。非線性方程的一般形式 這里是單變量 的函數(shù)，它可以是代數(shù)多項(xiàng)式 ()也可以是超越函數(shù)，即不能表示為上述形式的函數(shù)。滿足方程 的x值通常叫做方程的根或解，也叫函數(shù)的零點(diǎn)。.精品§2.1二分法(Bisection Method)1 概念:二分法也稱對(duì)分區(qū)間法

20、、對(duì)分法等，是最簡(jiǎn)單的求根方法，屬于區(qū)間法求根類型。在用近似方法時(shí)，需要知道方程的根所在區(qū)間。假設(shè)區(qū)間a,b含有方程f(x)=0的根，那么稱a,b為f(x)=0的有根區(qū)間；假設(shè)區(qū)間a,b僅含方程f(x)= 0的一個(gè)根，那么稱a,b為f(x)= 0的一個(gè)單根區(qū)間。2根本思想 根的存在定理(零點(diǎn)定理)： f(x)為a,b上的連續(xù)函數(shù)，假設(shè) f(a)·f(b)<0，那么a,b中至少有一個(gè)實(shí)根。如果f(x)在a,b上還是單調(diào)遞增或遞減的，那么f(x)=0僅有一個(gè)實(shí)根。   3構(gòu)造原理直接取區(qū)間a,b的中點(diǎn)x=(a +b)/2作為問題的近似解，那么我們可以估

21、計(jì)出絕對(duì)誤差限僅為區(qū)間長(zhǎng)的一半，即e=(b-a)/2。如果這個(gè)結(jié)果能滿足精度要求，我們就停止進(jìn)一步的計(jì)算；如果不能，就求出f(x),結(jié)果只能是下面三種情況之一：1 f(a)·f(x)<0，此時(shí)我們有x*a,x； 2 f(x)·f(b)<0，此時(shí)我們有x*x,b；3 f(x)=0，此時(shí)x即為問題的精確解。在前兩種情況下，我們可以用x分別替換原問題中的b或a,從而把求解的區(qū)間減小了一半。這樣我們又可以取新區(qū)間a,b的中點(diǎn)。經(jīng)過N次迭代后，剩下的區(qū)間長(zhǎng)為(b- a)/ 。這也是結(jié)果的絕對(duì)誤差限。如此繼續(xù)下去就到達(dá)是有根區(qū)間逐步縮小的目的，在這一些相互包含的子區(qū)間中構(gòu)造

22、收斂的數(shù)列來逼近根 。例求方程的有根區(qū)間.解根據(jù)有根區(qū)間定義，對(duì)方程的根進(jìn)行搜索計(jì)算，結(jié)果如下表：方程的三個(gè)有根區(qū)間為1,2,3,4,5,6.非線性方程f(x)=0求根，包括求超越方程和代數(shù)方程的根x*,方程的根也是f(x)的零點(diǎn)，即f(x*)=0,x*可以是實(shí)根也可以是復(fù)根，本章以求實(shí)根為主。求實(shí)根首先要確定根x*所在區(qū)間，稱為有根區(qū)間。根據(jù)連續(xù)函數(shù)性質(zhì)，假設(shè)f(x)在上連續(xù)，當(dāng)f()f(b)<0時(shí)，為有根區(qū)間,為找到方程f(x)=0的有根區(qū)間,可用逐次搜索法,也就是在x的不同點(diǎn)上計(jì)算f(x),觀察f(x)的符號(hào),如例2.1表中所示,只要在相鄰兩點(diǎn)f反號(hào),那么得到有根區(qū)間,本例得到三個(gè)

23、有根區(qū)間,分別為1,23,45,6.4根本步驟假設(shè)f(x)=0，在區(qū)間a,b中只有一個(gè)根，且滿足f(a)f(b)<0，那么利用二分法構(gòu)造求根過程為： While(|a-b|>eps) x=(a+b)/2 計(jì)算f(x) 假設(shè)(|f(x)|<eps) 那么 x為解 假設(shè)f(x)*f(b)<0 修正區(qū)間為x,b 假設(shè)f(a)*f(x)<0 修正區(qū)間為a,xEnd while 按上述步驟求根的方法稱為二分法，假設(shè)記做了k次二分區(qū)間處理得到的有根區(qū)間為，那么有二分法對(duì)應(yīng)的求根數(shù)列算式為 , k=0,1,2,。5誤差估計(jì)與分析 第1步產(chǎn)生的有誤差 第 k 步產(chǎn)生的有誤差對(duì)于給

24、定的精度 e ,可估計(jì)二分法所需的步數(shù) k ： 注：用二分法求根，最好先給出 f (x) 草圖以確定根的大概位置。或用搜索程序，將a, b分為假設(shè)干小區(qū)間，對(duì)每一個(gè)滿足 f (ak)·f (bk) < 0 的區(qū)間調(diào)用二分法程序，可找出區(qū)間a, b內(nèi)的多個(gè)根，不必要求 f (a)·f (b) < 0 。6 例題例1 證明方程1xsinx0在區(qū)間0,1內(nèi)有一個(gè)根，使用二分法求誤差不超過0.5×104的根要迭代多少次？證明 令f(x)1xsinx， f(0)=1>0，f(1)=sin1<0 f(x)=1xsinx=0在0，1有根.又 f¢

25、;(x)=1cosx>0(xÎ0.1),故f(x)0在區(qū)間0，1內(nèi)有唯一實(shí)根.給定誤差限e0.5×10-4，有只要取n14. 例2： 在有一個(gè)零點(diǎn)， ，用二分法計(jì)算結(jié)果如下：             n有根區(qū)間  11.0,2.021.0,1.531.25,1.541.25,1.37551.3125,1.37537561.34375,1.37571.359375,1.37581.359375,1.3671875.精品二分法的優(yōu)點(diǎn)：就是不管含

26、根區(qū)間a , b多大總能求出滿足要求的根，且對(duì)函數(shù)的要求不高，計(jì)算簡(jiǎn)單；缺點(diǎn)：不能求重根，其收斂速度在數(shù)列xn越靠近根時(shí)越慢。二分法一般常用于為方程提供初始近似值當(dāng)計(jì)算出的近似根比擬準(zhǔn)確時(shí)，再用其他方法對(duì)近似根做快速進(jìn)一步精化。.精品§2.2簡(jiǎn)單迭代法1 不動(dòng)點(diǎn)迭代法的思想 將方程 改寫成等價(jià)的形式 ，那么的根 也滿足方程 ，反之亦然。稱為的不動(dòng)點(diǎn)。而求 的根的問題就成為求的不動(dòng)點(diǎn)問題。 2 不動(dòng)點(diǎn)迭代法的根本過程 選取初值，以公式 進(jìn)行迭代，稱為迭代函數(shù)，假設(shè)收斂到，那么 就是 的不動(dòng)點(diǎn)，這種方法就稱為不動(dòng)點(diǎn)迭代法。 將 轉(zhuǎn)化為的方法可以是多種多樣的，例： 在 上有以下方法：(1)

27、 (2) (3) (4) 取 ，有的收斂，有的發(fā)散，有的快，有的慢。例1： 用迭代法求解方程(1) 將原方程化為等價(jià)方程顯然迭代法發(fā)散(2) 如果將原方程化為等價(jià)方程仍取初值依此類推,得 已經(jīng)收斂,故原方程的解為.可以發(fā)現(xiàn),同樣的方程不同的迭代格式有不同的結(jié)果. 這與迭代函數(shù)的構(gòu)造有關(guān)。迭代法是非線性方程求根中各類迭代法的根底，其涉及的處理方法，概念和理論都易于推廣。 3 迭代法的幾何意義記 它們交點(diǎn)的橫坐標(biāo)p即為方程的根。例2 用迭代法求方程x54x20的最小正根.計(jì)算過程保存4位小數(shù).,即 ,此時(shí)迭代發(fā)散.建立迭代格式 此時(shí)迭代收斂.解 建立迭代格式 取初值x0=1得: 取 4 迭代過程的

28、收斂性 從前面的分析可知，收斂的迭代數(shù)列xk的極限是方程f(x)的根，但計(jì)算機(jī)是不能做無窮次計(jì)算，因此迭代法一般只能求出具有任意固定精度的根的近似值，這樣在給定精度后，了解迭代進(jìn)行的次數(shù)即何時(shí)終止迭代才能得到滿足要求的近似根就顯得非常重要。定理假設(shè)迭代函數(shù) (x), (x)ÎCa, b滿足下面條件:( I ) 當(dāng) xÎa, b 時(shí)，(x)Îa, b；( II ) $ 0 £ L < 1 使得 |(x) | £ L < 1 對(duì) " xÎa, b 成立。那么任取x0Îa, b，由xk+1 =(xk) 得到的

29、序列收斂于(x) 在a, b上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：. 2. 證：由迭代格式和條件，有 xk+1-xk|(xk)- xk|               |(xk)- (x*) +(x*)- xk|               | x*-xk-(xk)+(x*)|      

30、60;        | x*-xk|-|(xk)- (x*)|               | x*-xk|-L|xk- x*|               (1-L)| x*-xk|因?yàn)?#160;  0<L<1，所以有 另一方面， xk+1-

31、xk|(xk)-(xk-1)|L|xk-xk-1|                    證得結(jié)論1。反復(fù)應(yīng)用上式結(jié)果，有xk+1-xkL|xk-xk-1| Lk |x1-x0|可以得到結(jié)論。證畢定理給出了收斂迭代數(shù)列xk的誤差估計(jì)式，利用它，在給定精度后，要使| x*-xk|，只要計(jì)算到或 第一式可以得到迭代次數(shù)的值應(yīng)取多大，但這樣得到的值往往偏大，第二式是用剛算出的數(shù)列來估計(jì)誤差的，它可用較小的迭代運(yùn)算

32、但到滿足精度的近似解。特別當(dāng) L時(shí)，有不等式            | x* -xk|xk-xk-1 |此時(shí)可用更簡(jiǎn)單的不等式  |xk-xk-1 | 成立與否終止迭代，由于這個(gè)判別具有簡(jiǎn)單易處理特點(diǎn)。實(shí)用中，一般不管是否有 L成立，都用|xk-xk-1 |是否小于某個(gè)充分小的數(shù)來作為終止條件，它通常也能求出滿足精度的根。 注：定理?xiàng)l件很難保證，可將a, b縮小，定義局部收斂性：假設(shè)在 x* 的某d 領(lǐng)域 Bd = x | | x - x* | £ d 有ÎC1a,

33、 b 且 |(x*) | < 1，那么由"x0ÎBd 開始的迭代收斂。即調(diào)整初值可得到收斂的結(jié)果。簡(jiǎn)單迭代法的優(yōu)點(diǎn)是理論豐富算法簡(jiǎn)單，易于推廣；缺點(diǎn)是不易找到收斂最快迭代函數(shù)和局部收斂。簡(jiǎn)單迭代法主要用于迭代的理論分析上。.精品§2.3 牛頓(Newton)法1 根本思想:將非線性方程逐步線性化而形成迭代公式 Taylor 展開.取的近似根，將f (x)在點(diǎn)做一階Taylor展開: 將看成高階小量，那么 于是可得著名的牛頓迭代公式： 相應(yīng)的迭代函數(shù)為 2 牛頓法幾何意義是：(牛頓法亦稱切線法) 只要 f ÎC1，每一步迭代都有f '( xk

34、 ) ¹ 0，而且 ，那么 x*就是 f 的根。牛頓迭代公式算法1: 初始化. x0, M,置i:=02: 如果|f(xi)|，那么停止. 3: 計(jì)算xi+1:=xi-f(xi)/f'(xi)4: 如果|xi+1-xi|< OR |f(xi)|，那么停止.5: i:=i+1, 轉(zhuǎn)至3.例1： 求解f(x)=ex-1x 的零點(diǎn)。初始點(diǎn)x0=-7.0解： f'(x×10-1，f '(x)=ex-(1+x2)-1 計(jì)算結(jié)果如下表：(取|f(x)<=10-10|)k x f(x) 0 -7.0000 1 -10.6771 2 -13.2792 3

35、 -14.0537 4 -14.1011 5 -14.1013 注：Newton's Method 收斂性依賴于x0 的選取。 例2： 求解的近似值，精度為。初始點(diǎn)x0=10解: 該問題可轉(zhuǎn)化為求解二次方程： x2-115=0的正根，相應(yīng)的牛頓迭代公式為: 取初值x0=10,經(jīng)3次迭代得近似值: k x f(x)0 10 -151 10.75 52 10.7238 3 10.7238 3牛頓下山法 其中，稱為下山因子，為保證迭代過程中下山成功，即使|f(xk)|>|f(xk+1)|成立，必須選取適當(dāng)?shù)南律揭蜃? 取中依次挑取下山因子.Newton法是一種局部收斂方法，通常要求初始

36、近似在解附近才保證迭代序列收斂.為擴(kuò)大收斂范圍，使對(duì)任意迭代序列收斂，通?？梢?yún)?shù)，并將Newton迭代改為 其中，稱為下山因子，式()稱為Newton下山法.通常可選擇使，計(jì)算時(shí)可取,直到滿足要求為止.由此得到的序列由于滿足下山條件，故它是收斂的，但它只是線性收斂.例 用Newton下山法求的解，取，計(jì)算精確到解 由于,由式()得Newton下山法為,假設(shè)用Newton法(=1)迭代3步那么求得解的近似=1.324 72.現(xiàn)用，用=1,那么得=17.9,且f(0.6)=-1.384,而不滿足下山條件.通過試算，當(dāng)時(shí)，滿足以下計(jì)算時(shí)參數(shù),且當(dāng)Newton法不收斂時(shí)，使用Newton下山法.具

37、體做法是取，每次縮減成一半，并檢驗(yàn)是否成立，假設(shè)成立那么做下一步.精品§2.4 其它求根方法1.正割法：Newton's Method是二階收斂方法，每步都要計(jì)算 f 和 f '，相當(dāng)于2個(gè)函數(shù)值，比擬費(fèi)時(shí),同時(shí)在很多情況下計(jì)算函數(shù)的導(dǎo)數(shù)值比擬困難?，F(xiàn)考慮牛頓法的一種修改，用 f 的值近似f '，可少算一個(gè)函數(shù)值。但需要2個(gè)初值 x0 和 x1。割線的斜率為: 2.艾特肯(Aitken)加速方法有的迭代過程雖然收斂，但速度很慢，因此迭代過程的加速是一個(gè)重要課題。設(shè)是根的某個(gè)近似值，用迭代公式校正一次得 ，根據(jù)微分中值定理，有其中 介于 與 之間。 假設(shè) 改變不

38、大，近似地取某個(gè)近似，那么有假設(shè)將校正值 再校正一次，又得 ，由于 在兩式中消去 ，得到 由此推得：在計(jì)算了及之后，可用上式右端作為的新近似，記作，一般情形是由計(jì)算， ，記該方法稱為艾特肯加速方法。 可以證明：它說明序列 的收斂速度比 的收斂速度快。 .精品作業(yè)講評(píng)1、方程在附近有根，將方程寫成以下三種不同的等價(jià)形式： ； ； 試判斷以上三種格式迭代函數(shù)的收斂性，并選出一種較好的格式。解： 令，那么，故迭代收斂； 令，那么，故迭代收斂； 令，那么，故迭代發(fā)散。以上三中以第二種迭代格式較好。2.4 設(shè)在方程的根的附近有連續(xù)的一階導(dǎo)數(shù)，且，證明迭代公式具有局部收斂性.證：因，又由在的附近連續(xù)，那么

39、存在的某鄰域：，使得都有成立.于是， 由此可知，當(dāng)時(shí)，. 2.6 試證用牛頓法求方程在1，3內(nèi)的根具有線性收斂性.證：令，因此，根據(jù)Newton方法有: 由于,故.于是 從而得證. 線性方程組的解法 引言 §3.1 雅可比(Jacobi)迭代法 §3.2 高斯-塞德爾(Gauss-Seidel)迭代法§3.3 超松馳迭代法 §3.7 三角分解法§3.4 迭代法的收斂性 §3.8 追趕法 §3.5 高斯消去法 §3.9 其它應(yīng)用 §3.6 高斯主元素消去法 §3.10 誤差分析 §3 作

40、業(yè)講評(píng)3 §3.11 總結(jié) .精品§3.0 引 言 重要性：解線性代數(shù)方程組的有效方法在計(jì)算數(shù)學(xué)和科學(xué)計(jì)算中具有特殊的地位和作用.如彈性力學(xué)、電路分析、熱傳導(dǎo)和振動(dòng)、以及社會(huì)科學(xué)及定量分析商業(yè)經(jīng)濟(jì)中的各種問題. 分類：線性方程組的解法可分為直接法和迭代法兩種方法.(a) 直接法：對(duì)于給定的方程組，在沒有舍入誤差的假設(shè)下，能在預(yù)定的運(yùn)算次數(shù)內(nèi)求得精確解.最根本的直接法是Gauss消去法，重要的直接法全都受到Gauss消去法的啟發(fā).計(jì)算代價(jià)高.(b) 迭代法：基于一定的遞推格式，產(chǎn)生逼近方程組精確解的近似序列.收斂性是其為迭代法的前提，此外，存在收斂速度與誤差估計(jì)問題.簡(jiǎn)單實(shí)用

41、,誘人. .精品 雅可比Jacobi迭代法 (AX=b)1 根本思想:與解f(x)=0 的不動(dòng)點(diǎn)迭代相類似,將AX=b改寫為X=BX+f 的形式,建立雅可比方法的迭代格式：Xk+1=BX(k)+f ,其中，B稱為迭代矩陣.其計(jì)算精度可控,特別適用于求解系數(shù)為大型稀疏矩陣(sparse matrices)的方程組.2 問題:(a) 如何建立迭代格式？ (b) 向量序列Xk是否收斂以及收斂條件?3 例題分析:考慮解方程組 (1)其準(zhǔn)確解為X*=1, 1.2, 1.3.建立與式(1)相等價(jià)的形式： (2)據(jù)此建立迭代公式： (3) 取迭代初值,迭代結(jié)果如下表. JocabiMet 迭代次數(shù) x1 x

42、2 x30 0 0 0 4 Jocobi迭代公式:設(shè)方程組AX=b, 通過別離變量的過程建立Jocobi迭代公式，即 由此我們可以得到Jacobi迭代公式：Jacobi迭代公式的算法1: 初始化. n, (aij), (bj), (x1) , M.2: 執(zhí)行k=1直到M為止. 執(zhí)行i=1直到n為止. ; 執(zhí)行i=1直到n為止. ; 輸出k, (xi).另外，我們也可以建立Jacobi迭代公式的矩陣形式.設(shè)方程組AX=b,其中，A=(aij)n為非奇異陣，X=(x1,x2,xn)T, b=(b1,b2,bn)T將系數(shù)陣A分解為: A=U+D+L,U為上三角矩陣，D為對(duì)角矩陣，L為下三角矩陣.于是

43、AX=b可改寫為(U+D+L)X=b X=D-1b-D-1(U+L)X由此可得矩陣形式的Jocobi迭代公式： Xk+1=BX(k)+f §3.2 高斯-塞德爾Gauss-Seidel迭代法注意到利用Jocobi迭代公式計(jì)算時(shí)，已經(jīng)計(jì)算好的值，而Jocobi迭代公式并不利用這些最新的近似值計(jì)算，仍用.這啟發(fā)我們可以對(duì)其加以改良,即在每個(gè)分量的計(jì)算中盡量利用最新的迭代值，得到上式稱為Gauss-Seidel迭代法.其矩陣形式是X=-(D+L)-1UX+(D+L)-1b, Xk+1=BX(k)+f .迭代次數(shù) x1 x2 x3 0 0 0 04.精品§3.3 超松馳迭代法SOR

44、方法1 根本思想:逐次超松弛迭代法(Successive Over Relaxation Method,簡(jiǎn)寫為SOR)可以看作帶參數(shù)大型稀疏矩陣方程組的有效方法之一.2 SOR算法的構(gòu)造:設(shè)方程組AX=b, 其中，A=(aij)n為非奇異陣，X=(x1,x2,xn)T, b=(b1,b2,bn)T.假設(shè)已算出x(k)， (1)相當(dāng)于用高斯-塞德爾方法計(jì)算一個(gè)分量的公式.假設(shè)對(duì)某個(gè)參數(shù)，作與加權(quán)的平均,即 (2)其中，稱為松弛因子.用(1)式代入(2)式，就得到解方程組AX=b的逐次超松弛迭代公式： (3)顯然，當(dāng)取=1時(shí)，式(3)就是高斯-塞德爾迭代公式.3 例題分析:利用SOR方法解方程組

45、(1)其準(zhǔn)確解為X*=1, 1, 2.建立與式(1)相等價(jià)的形式： (2)據(jù)此建立迭代公式： (3)利用SOR算法，取迭代初值,=1.5,迭代結(jié)果如下表. 逐次超松弛迭代法次數(shù) x1 x2 x3 1 GS迭代法須迭代85次得到準(zhǔn)確值X*=1, 1, 2;而SOR方法只須55次即得準(zhǔn)確值.由此可見，適當(dāng)?shù)剡x擇松弛因子，SOR法具有明顯的加速收斂效果. .精品§3.4 迭代法的收斂性1. 向量和矩陣范數(shù) (a) 向量范數(shù) Rn空間的向量范數(shù) | · | ,對(duì)任意, 滿足以下條件： (正定性) (齊次性) 三角不等式 常見的向量范數(shù)有：(1) 列范數(shù)：(2) 譜范數(shù)：(歐幾里德范

46、數(shù)或向量的長(zhǎng)度,模)(3) 行范數(shù)：(4) p范數(shù): 上述范數(shù)的幾何意義是:=max(|x2-x1|,|y2-y1|) ;=|x2-x1|+|y2-y1| ;. 向量序列依坐標(biāo)收斂于向量x* 的充要條件是向量序列依范數(shù)收斂于向量x*,即.(b) 矩陣范數(shù) 空間的向量范數(shù) | · | ,對(duì)任意, 滿足以下條件：常見的矩陣范數(shù)有： (行和范數(shù)) (列和范數(shù)) (譜范數(shù)) 假設(shè)A對(duì)稱，那么有. 矩陣A的譜半徑記為,r(A) =,其中l(wèi)i 為A 的特征根。2. 迭代法根本定理 設(shè)有方程組X=BX+f,對(duì)于任意初始向量X(0)及任意f,迭代公式X(k+1)=BX(k)+f收斂的充要條件是<

47、;1,為矩陣B的譜半徑.證：設(shè)X*為方程組X=BX+f的準(zhǔn)確解，即 X*=BX*+f.對(duì)于任意初始向量X(0)及任意f,迭代公式X(k+1)=BX(k)+f,于是， 由此可得,迭代法收斂的充要條件是.即,<1. 上述定理是線性方程組迭代解法收斂性分析的根本定理，然而由于的計(jì)算往往比擬困難，盡管有各種方法估計(jì)的上界，但往往偏聽偏大而不實(shí)用，由此導(dǎo)致定理的理論價(jià)值勝于實(shí)用價(jià)值，為滿足實(shí)際判斂的需要，有如下定理. (迭代收斂的充分條件) 設(shè)有迭代公式X(k+1)=BX(k)+f，如果|B|<1,那么對(duì)于任意初始向量X(0)及任意f, 迭代公式均收斂.3. 從方程組的系數(shù)矩陣A判斷迭代收斂

48、性實(shí)際中要求解的某些線性方程組，其系數(shù)矩陣往往具有一些特點(diǎn)，如系數(shù)矩陣為對(duì)稱正定、對(duì)角元素占優(yōu)等.由這些方程組系數(shù)矩陣的特殊性，使得我們可以直接從方程組的系數(shù)矩陣A出發(fā)來討論迭代法的收斂性. 設(shè)，滿足 且至少有一個(gè)i值，使得 成立，那么稱A為對(duì)角占優(yōu)矩陣；假設(shè) ,那么稱A為嚴(yán)格對(duì)角占優(yōu)矩陣. 如果為嚴(yán)格對(duì)角占優(yōu)矩陣，那么對(duì)任意的初值x(0),解方程組AX=B的Jacobi法、Guess-Seidel迭代法均收斂. HW: 3.1 3.2 3.3上機(jī)實(shí)習(xí) .精品§3.5 高斯消去法 1 根本思想:用高斯消去法求解線性方程組的根本思想是設(shè)法消去方程組的系數(shù)矩陣A的主對(duì)角線下的元素，而將A

49、x=b化為等價(jià)的上三角形方程組，然后再通過回代過程便可以獲得方程組的解.這種解線性方程組的方法，常稱為高斯消去法(Gaussian Elimination).2 例題分析:利用高斯消去法求解方程組: (1)利用ri-,i (2)利用ri-,i (3)利用ri-,i (4)顯然，方程組(4)與(1)是等價(jià)的，其系數(shù)矩陣為上三角狀的，易于求解.稱以上過程為高斯消去法的消去過程.通過方程組(4)的回代求解，可以得到準(zhǔn)確解為X*=1, -3, -2,1T. 這一過程為高斯消去法的回代過程. 2 高斯消去法算法的構(gòu)造:記方程組AX=b為A(1)X=b(1), 其中，A(1)和b(1)的元素分別記為Ste

50、p1:第一次消元 設(shè)，將增廣矩陣的第i行減去倍，(i=2,n),目的是將增廣矩陣的第一列內(nèi)除每一個(gè)元素不變外，其余全部消為零，得到A(2)X=b(2),即其中 Step2:第k次消元() 設(shè)第k-1次消元已完成，且，得到A(k)X=b(k),即計(jì)算因子， 如此反復(fù)，經(jīng)過n-1次消元之后得到一個(gè)與原方程組等價(jià)的上三角形方程組.Step3:回代 只要就可以回代求解3 高斯消去法算法Step1消元:對(duì)k=1,2,n-1 假設(shè)那么停止計(jì)算 對(duì)i=k+1,k+2,n 計(jì)算因子;對(duì)j=k+1,k+2,n 計(jì)算;Step2回代: 對(duì)i=n,n-1,1 高斯消去法的條件(1) 假設(shè)A的所有順序主子式均不為0，那么高斯消元無需換行即可進(jìn)行到底，且得到唯一解.(2) 假設(shè)消元過程中允許對(duì)增廣矩陣進(jìn)行行交換，那么方程組Ax=b可用消去法求解的充要條件是A可逆.精品§3.6 高斯主元素消去法1 主元素及其選取