計(jì)算方法word教案

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

2、學(xué)。 ¨ 科學(xué)計(jì)算的核心內(nèi)容是以現(xiàn)代化計(jì)算機(jī)以及數(shù)學(xué)軟件為工具，以數(shù)學(xué)模型為基礎(chǔ)進(jìn)行模擬研究。¨ 出現(xiàn)了形如:計(jì)算數(shù)學(xué),計(jì)算物理學(xué),計(jì)算力學(xué),計(jì)算化學(xué), 計(jì)算生物學(xué),計(jì)算地質(zhì)學(xué),計(jì)算經(jīng)濟(jì)學(xué)等許多新學(xué)科及其發(fā)展。并已形成一系列專(zhuān)門(mén)研究數(shù)學(xué)問(wèn)題的數(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ù)值算法概論§1.1.1 計(jì)算方法的研究?jī)?nèi)容、

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

4、差分析）。因?yàn)榭赡懿捎昧私频葍r(jià)運(yùn)算,故要進(jìn)行誤差分析,即數(shù)值的性態(tài)及數(shù)值方法的穩(wěn)定性。(3) 要有好的算法，并考慮計(jì)算復(fù)雜性（時(shí)間、空間）針對(duì)所求解的數(shù)值問(wèn)題研究在計(jì)算機(jī)上可執(zhí)行的且有效的計(jì)算公式。(4) 要有數(shù)值試驗(yàn)§1.1.2 基本求解步驟實(shí)際問(wèn)題建立數(shù)學(xué)模型構(gòu)造數(shù)值 算法編程上機(jī)計(jì)算結(jié)果說(shuō)明： (1)數(shù)學(xué)模型是通過(guò)科學(xué)實(shí)驗(yàn)或者觀察分析一系列數(shù)據(jù)后，用數(shù)學(xué)作為工具近似地描述客觀事物的一種數(shù)學(xué)表達(dá)式。在數(shù)學(xué)模型中，往往包含了若干參量如物體比重、阻力系數(shù)、熱交換系數(shù)等，這些物理參數(shù)通常由實(shí)驗(yàn)儀器測(cè)得，根據(jù)儀器的精密程度，物理參數(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)過(guò)有限次四則運(yùn)算及規(guī)定的運(yùn)算順序，最后求出未知量的數(shù)值解，這樣構(gòu)成的完整計(jì)算步驟稱(chēng)為算法。評(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ù)值問(wèn)題使用不同算法，其計(jì)算復(fù)雜性將會(huì)大不一樣

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

7、存儲(chǔ)單元7個(gè)。例1.2：計(jì)算n次多項(xiàng)式的值。 算法 采用：秦九韶算法(1247) (又稱(chēng)為Horner算法(1819) 計(jì)算。說(shuō)明：需乘法n次，加法n次，存儲(chǔ)單元n+3個(gè)。上述秦九韶算法的結(jié)構(gòu)是遞歸的，它通過(guò)一次式的反復(fù)計(jì)算，逐步降低多項(xiàng)式的次數(shù)，直到歸結(jié)為零次式為止。若以多項(xiàng)式的次數(shù)（或項(xiàng)數(shù)）定義為求值問(wèn)題的規(guī)模，則秦九韶算法的特點(diǎn)是，在遞歸計(jì)算的過(guò)程中問(wèn)題的規(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í)和誤差§

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

9、Taylor展開(kāi)，用多項(xiàng)式近似代替，則數(shù)值方法的截?cái)嗾`差為。 解：利用展開(kā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ì)算過(guò)程舍入誤差不增長(zhǎng)，則稱(chēng)此算法是數(shù)值穩(wěn)定的.否則，若誤差增長(zhǎng)則稱(chēng)算法不穩(wěn)定.例如：計(jì)算并分析誤差 解：由積分估值 由積分性質(zhì)知 設(shè)計(jì)如下兩種算法：算法1：取，按公式 （n=0，1，2）依次計(jì)算的

10、近似值。設(shè)。假設(shè)計(jì)算過(guò)程中不產(chǎn)生新的舍入誤差，則有（n=0，1，2） 誤差擴(kuò)散。算法2：從計(jì)算，應(yīng)有 。在運(yùn)算過(guò)程中，舍入誤差不增大,數(shù)值穩(wěn)定。 n00.1820.1820.18210.0880.0900.08820.0580.0500.05830.04310.0830.043140.0343-0.1650.034350.02841.0250.028460.024-4.9580.02470.02124.9330.02180.019-124.5400.019關(guān)于數(shù)值穩(wěn)定性的算法v 誤差的傳播與積累例：蝴蝶效應(yīng) 紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京就刮起臺(tái)風(fēng)來(lái)了？！v 以上是一個(gè)病態(tài)問(wèn)題例5:

11、, 解：用分部積分公式得遞推式:。 用四位有效數(shù)字計(jì)算: , , , , , , , ,.分析1： 可以估計(jì)出 故 ,。 于是與精確值已經(jīng)面目全非,一位有效數(shù)字也沒(méi)有。這是由于如果有誤差,不計(jì)中間再產(chǎn)生的舍入誤差,該誤差隨著計(jì)算過(guò)程分別乘以,到時(shí)已經(jīng)變成了,誤差擴(kuò)大了4萬(wàn)倍。因而該算法不是穩(wěn)定的。分析2：如果遞推式改為,由, ,逐步計(jì)算直到。計(jì)算結(jié)果有四位有效數(shù)字,如果有誤差,其傳播到所引起的誤差僅為。故該算法是穩(wěn)定的。三、誤差的基本概念(1) 誤差與誤差限是精確值, 是它的一個(gè)近似值，稱(chēng)是近似值的絕對(duì)誤差。簡(jiǎn)稱(chēng)誤差。誤差是有量綱的,可正可負(fù)。誤差是無(wú)法計(jì)算的,但可以估計(jì)出它的一個(gè)上界。即,稱(chēng)

12、是近似值 的誤差限,即 。(2) 相對(duì)誤差與相對(duì)誤差限稱(chēng)為近似值的相對(duì)誤差,記作。相對(duì)誤差是個(gè)相對(duì)數(shù),是無(wú)量綱的,也可正可負(fù)。相對(duì)誤差的估計(jì),稱(chēng)為相對(duì)誤差限,即。實(shí)際中, 是未知的,可用來(lái)代替。當(dāng)較小時(shí),因兩者的差為: 是的高階無(wú)窮小，可忽略不計(jì)。 (3) 有效數(shù)字定義: 如果近似值的誤差限是 (某一數(shù)位的半個(gè)單位),則稱(chēng)準(zhǔn)確到小數(shù)點(diǎn)后位,并從第一個(gè)非零的數(shù)字到這一位的所有數(shù)字均為有效數(shù)字。 如： 3.14有三位有效數(shù)字,誤差限=0.005;3.1416有五位有效數(shù)字,誤差限為0.00005。如： 近似值準(zhǔn)確到小數(shù)點(diǎn)后五位，有三位有效數(shù)字。(4) 有效數(shù)字與誤差限的關(guān)系：有n位有效數(shù)字，標(biāo)準(zhǔn)形

13、式為，則有。有效位數(shù)越多，（絕對(duì)）誤差限越小。e) 有效數(shù)字與相對(duì)誤差限的關(guān)系：定理1：，若有位有效數(shù)字，則其相對(duì)誤差限為 反之，若的相對(duì)誤差限為則至少具有n位有效數(shù)字。證：因 ，故當(dāng)有n位有效數(shù)字時(shí)， 。 反之，由因此，至少具有n位有效數(shù)字。 證畢定理說(shuō)明，有效位數(shù)越多相對(duì)誤差限越小。實(shí)例例1 設(shè)= p=3.1415926近似值x=3.140.314×101,即m=1，它的絕對(duì)誤差是 0.001 592 6，有即l=3，故x=3.14有3位有效數(shù)字。x=3.14準(zhǔn)確到小數(shù)點(diǎn)后第2位。又近似值x=3.1416，它的絕對(duì)誤差是0.0000074，有 即m=1,l5，x=3.1416有5

14、位有效數(shù)字。而近似值x=3.1415，它的絕對(duì)誤差是0.0000926，有 即m=1,l4，x=3.1415有4位有效數(shù)字。這就是說(shuō)某數(shù)有s位數(shù)，若末位數(shù)字是四舍五入得到的，那么該數(shù)有s位有效數(shù)字；例2 指出下列各數(shù)具有幾位有效數(shù)字，及其絕對(duì)誤差限和相對(duì)誤差限： 2.000 4 0.002 009 0009 000.00解 因?yàn)閤1=2.000 40.200 04×101, 它的絕對(duì)誤差限0.000 05=0.5×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，

15、x2=0.002 00有3位有效數(shù)字. a1=2，相對(duì)誤差限er=0.002 5x3=9 000，絕對(duì)誤差限為0.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，不是可有可無(wú)的，它是有實(shí)際意義的。例3 ln2=0.69314718，精確到103的近似值是多少？解 精確到1030.001，即絕對(duì)誤差限是e0.0005, 故至少要保留小數(shù)點(diǎn)后三位

16、才可以。ln2=0.693§1.2.4 數(shù)值算法例:求解微分方程: 將其變成數(shù)值問(wèn)題，即將其“離散化” “離散化”是將非數(shù)值問(wèn)題的數(shù)學(xué)模型化為數(shù)值問(wèn)題的主要方法，這也是計(jì)算方法的任務(wù)之一。計(jì)算方法的主要任務(wù)1. 將計(jì)算機(jī)上不能執(zhí)行的運(yùn)算化為在計(jì)算機(jī)上可執(zhí)行的運(yùn)算；2. 針對(duì)所求解的數(shù)值問(wèn)題，研究在計(jì)算機(jī)上可執(zhí)行的且有效的計(jì)算公式；3. 因?yàn)榭赡懿捎昧私频葍r(jià)運(yùn)算,故要進(jìn)行誤差分析,即數(shù)值問(wèn)題的性態(tài)及數(shù)值 方法的穩(wěn)定性。Matlab簡(jiǎn)介：MATLAB的含義是矩陣實(shí)驗(yàn)室,是Matrix Laboratory的縮寫(xiě)。它的前身是LINPACK（解線性方程）和EISPACK（解特征值問(wèn)題）的F

17、ORTRAN子程序庫(kù)。由于它把矩陣當(dāng)成一個(gè)對(duì)象，因此編寫(xiě)程序更加直觀、方便。1984年正式推出,最新版本為V7.0 Release14.MATLAB具有非常強(qiáng)大和直觀的計(jì)算功能，并且由于其有非常好的擴(kuò)展性能，現(xiàn)在已成為世界上應(yīng)用最廣泛的工程計(jì)算軟件之一。(1)強(qiáng)大的數(shù)值運(yùn)算功能在MATLAB環(huán)境中，有超過(guò)500種數(shù)學(xué)、統(tǒng)計(jì)、科學(xué)及工程方面的函數(shù)可使用，函數(shù)的命名表示自然，使得問(wèn)題和解答像數(shù)學(xué)公式一般簡(jiǎn)單明了，讓用戶可全力發(fā)揮在解題方面，而非浪費(fèi)在電腦操作上。 (2)數(shù)據(jù)分析和可視化功能、文字處理功能MATLAB可以繪制二、三維圖形，與Mathematic和Maple相比，它還能處理光照模型，制

18、作出高品質(zhì)的圖形。功能十分強(qiáng)大。MATLAB Notebook為用戶提供了強(qiáng)大的文字處理功能，并允許WORD訪問(wèn)MATLAB的數(shù)值計(jì)算和可視化結(jié)果，制作科學(xué)性或工程性圖文并茂的文章.(3)高級(jí)、簡(jiǎn)單、高效的程序環(huán)境 做為一種解釋型的程序語(yǔ)言，MATLAB允許使用者在短時(shí)間內(nèi)寫(xiě)完程序,所花的時(shí)間約為用 FORTRAN或 C 的幾分之一，而且不需要編譯 (compile) 及連接(link) 即能執(zhí)行，同時(shí)包含了更多及更容易使用的內(nèi)建功能。 (4)開(kāi)放及可延伸的架構(gòu) MATLAB允許使用者接觸它的大多數(shù)的數(shù)學(xué)源代碼，檢查運(yùn)算法，更改現(xiàn)有函數(shù)，甚至加入自己的函數(shù)使 MATLAB成為使用者所需要的環(huán)境

19、。 (5)豐富的工具箱MATLAB的工具箱融合了套裝前軟體的優(yōu)點(diǎn)，與一個(gè)靈活的開(kāi)放但容易操作之環(huán)境，這些工具箱提供了使用者在特別應(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 其它求根方法（迭代過(guò)程的加速方法）

20、67;2.5 作業(yè)講評(píng)§2.0引 言 非線性科學(xué)是當(dāng)今科學(xué)發(fā)展的一個(gè)重要研究方向，非線性方程的求根也成為其中一個(gè)重要內(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ù)。滿足方程

21、 的x值通常叫做方程的根或解，也叫函數(shù)的零點(diǎn)。§2.1二分法(Bisection Method)1 概念:二分法也稱(chēng)對(duì)分區(qū)間法、對(duì)分法等，是最簡(jiǎn)單的求根方法，屬于區(qū)間法求根類(lèi)型。在用近似方法時(shí)，需要知道方程的根所在區(qū)間。若區(qū)間a,b含有方程f(x)=0的根，則稱(chēng)a,b為f(x)=0的有根區(qū)間；若區(qū)間a,b僅含方程f(x)= 0的一個(gè)根，則稱(chēng)a,b為f(x)= 0的一個(gè)單根區(qū)間。2基本思想 根的存在定理(零點(diǎn)定理)： f(x)為a,b上的連續(xù)函數(shù)，若 f(a)·f(b)<0，則a,b中至少有一個(gè)實(shí)根。如果f(x)在a,b上還是單調(diào)遞增或遞減的，則f(x)=0僅有一個(gè)實(shí)根

22、。   3構(gòu)造原理直接取區(qū)間a,b的中點(diǎn)x=(a +b)/2作為問(wèn)題的近似解，那么我們可以估計(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即為問(wèn)題的精確解。在前兩種情況下，我們可以用x分別替換原問(wèn)題中的b或a,從而把求解的區(qū)間減小了一半。這樣我們又可以取新區(qū)間a,b的中點(diǎn)。經(jīng)過(guò)N次迭代

23、后，剩下的區(qū)間長(zhǎng)為(b- a)/ 。這也是結(jié)果的絕對(duì)誤差限。如此繼續(xù)下去就達(dá)到是有根區(qū)間逐步縮小的目的，在這一些相互包含的子區(qū)間中構(gòu)造收斂的數(shù)列來(lái)逼近根 。例求方程的有根區(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ū)間，稱(chēng)為有根區(qū)間。根據(jù)連續(xù)函數(shù)性質(zhì)，若f(x)在上連續(xù)，當(dāng)f()f(b)<0時(shí)，為有根區(qū)間,為找到方程f(x)=0的有根區(qū)間,可用逐次搜

24、索法,也就是在x的不同點(diǎn)上計(jì)算f(x),觀察f(x)的符號(hào),如例2.1表中所示,只要在相鄰兩點(diǎn)f反號(hào),則得到有根區(qū)間,本例得到三個(gè)有根區(qū)間,分別為1,23,45,6.4基本步驟假設(shè)f(x)=0，在區(qū)間a,b中只有一個(gè)根，且滿足f(a)f(b)<0，則利用二分法構(gòu)造求根過(guò)程為： While(|a-b|>eps) x=(a+b)/2 計(jì)算f(x) 若(|f(x)|<eps) 則 x為解 若f(x)*f(b)<0 修正區(qū)間為x,b 若f(a)*f(x)<0 修正區(qū)間為a,xEnd while 按上述步驟求根的方法稱(chēng)為二分法，若記做了k次二分區(qū)間處理得到的有根區(qū)間為，則有

25、二分法對(duì)應(yīng)的求根數(shù)列算式為 , k=0,1,2,。5誤差估計(jì)與分析 第1步產(chǎn)生的有誤差 第 k 步產(chǎn)生的有誤差對(duì)于給定的精度 e ,可估計(jì)二分法所需的步數(shù) k ： 注：用二分法求根，最好先給出 f (x) 草圖以確定根的大概位置。或用搜索程序，將a, b分為若干小區(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è)根，使用二分法求誤差不超過(guò)0.5×104的根要迭代多少次？證明 令f(x)1xsinx

26、， f(0)=1>0，f(1)=sin1<0 f(x)=1xsinx=0在0，1有根.又 f¢(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.01.52.37521.0,1.51.25-1.7968731.25,1.51.3750.162

27、1141.25,1.3751.3125-0.8483951.3125,1.3751.34375-0.3509861.34375,1.3751.359375-0.0964171.359375,1.3751.36718750.0323681.359375,1.36718751.36328125-0.03215二分法的優(yōu)點(diǎn)：就是不管含根區(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)迭代

28、法的思想 將方程 改寫(xiě)成等價(jià)的形式 ，則的根 也滿足方程 ，反之亦然。稱(chēng)為的不動(dòng)點(diǎn)。而求 的根的問(wèn)題就成為求的不動(dòng)點(diǎn)問(wèn)題。 2 不動(dòng)點(diǎn)迭代法的基本過(guò)程 選取初值，以公式 進(jìn)行迭代，稱(chēng)為迭代函數(shù)，若收斂到，則 就是 的不動(dòng)點(diǎn)，這種方法就稱(chēng)為不動(dòng)點(diǎn)迭代法。 將 轉(zhuǎn)化為的方法可以是多種多樣的，例： 在 上有以下方法：(1) (2) (3) (4) 取 ，有的收斂，有的發(fā)散，有的快，有的慢。例1： 用迭代法求解方程(1) 將原方程化為等價(jià)方程顯然迭代法發(fā)散(2) 如果將原方程化為等價(jià)方程仍取初值依此類(lèi)推,得 已經(jīng)收斂,故原方程的解為.可以發(fā)現(xiàn),同樣的方程不同的迭代格式有不同的結(jié)果. 這與迭代函數(shù)的構(gòu)造

29、有關(guān)。迭代法是非線性方程求根中各類(lèi)迭代法的基礎(chǔ)，其涉及的處理方法，概念和理論都易于推廣。 3 迭代法的幾何意義記 它們交點(diǎn)的橫坐標(biāo)p即為方程的根。例2 用迭代法求方程x54x20的最小正根.計(jì)算過(guò)程保留4位小數(shù).分析 容易判斷1，2是方程的有根區(qū)間.若建立迭代格式,即 ,此時(shí)迭代發(fā)散.建立迭代格式 此時(shí)迭代收斂.解 建立迭代格式 取初值x0=1得: 取 4 迭代過(guò)程的收斂性 從前面的分析可知，收斂的迭代數(shù)列xk的極限是方程f(x)的根，但計(jì)算機(jī)是不能做無(wú)窮次計(jì)算，因此迭代法一般只能求出具有任意固定精度的根的近似值，這樣在給定精度后，了解迭代進(jìn)行的次數(shù)即何時(shí)終止迭代才能得到滿足要求的近似根就顯得

30、非常重要。定理假設(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) 得到的序列收斂于(x) 在a, b上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：. 2. 證：由迭代格式和條件，有 xk+1-xk|(xk)- xk|         &

31、#160;     |(xk)- (x*) +(x*)- xk|               | x*-xk-(xk)+(x*)|               | x*-xk|-|(xk)- (x*)|         

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

33、#160;    證得結(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ù)列來(lái)估計(jì)誤差的，它可用較小的迭代運(yùn)算但到滿足精度的近似解。特別當(dāng) L時(shí)，有不等式            | x* -xk|xk-xk-1 |此時(shí)可用更簡(jiǎn)單的不等式

34、60; |xk-xk-1 | 成立與否終止迭代，由于這個(gè)判別具有簡(jiǎn)單易處理特點(diǎn)。實(shí)用中，一般不管是否有 L成立，都用|xk-xk-1 |是否小于某個(gè)充分小的數(shù)來(lái)作為終止條件，它通常也能求出滿足精度的根。 注：定理?xiàng)l件很難保證，可將a, b縮小，定義局部收斂性：若在 x* 的某d 領(lǐng)域 Bd = x | | x - x* | £ d 有ÎC1a, b 且 |(x*) | < 1，則由"x0ÎBd 開(kāi)始的迭代收斂。即調(diào)整初值可得到收斂的結(jié)果。簡(jiǎn)單迭代法的優(yōu)點(diǎn)是理論豐富算法簡(jiǎn)單，易于推廣；缺點(diǎn)是不易找到收斂最快迭代函數(shù)和局部收斂。簡(jiǎn)單迭代法主要用于迭代的

35、理論分析上。85§2.3 牛頓(Newton)法1 基本思想:將非線性方程逐步線性化而形成迭代公式 Taylor 展開(kāi).取的近似根，將f (x)在點(diǎn)做一階Taylor展開(kāi): 將看成高階小量，則 于是可得著名的牛頓迭代公式： 相應(yīng)的迭代函數(shù)為 2 牛頓法幾何意義是：(牛頓法亦稱(chēng)切線法) 只要 f ÎC1，每一步迭代都有f '( xk ) ¹ 0，而且 ，則 x*就是 f 的根。牛頓迭代公式算法1: 初始化. x0, M,置i:=02: 如果|f(xi)|，則停止. 3: 計(jì)算xi+1:=xi-f(xi)/f'(xi)4: 如果|xi+1-xi|<

36、; OR |f(xi)|，則停止.5: i:=i+1, 轉(zhuǎn)至3.例1： 求解f(x)=ex-1.5-tan-1x 的零點(diǎn)。（初始點(diǎn)x0=-7.0）解： f'(x)=-0.702×10-1，f '(x)=ex-(1+x2)-1 計(jì)算結(jié)果如下表：(取|f(x)<=10-10|)k x f(x) 0 -7.0000 -0.07018881 -10.6771 -0.02256662 -13.2792 -0.004366023 -14.0537 -0.000239024 -14.1011 -7.99585e-0075 -14.1013 -9.00833e-012注：New

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

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

39、用Newton下山法.具體做法是取，每次縮減成一半，并檢驗(yàn)是否成立，若成立則做下一步.§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)加速方法有的迭代過(guò)程雖然收斂，但速度很慢，因此迭代過(guò)程的加速是一個(gè)重要課題。設(shè)是根的某個(gè)近似值，用迭代公式校正一次得 ，根據(jù)微分中值定理，有其中 介于 與 之間

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

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

42、 §3 作業(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ì)中的各種問(wèn)題. 分類(lèi)：線性方程組的解法可分為直接法和迭代法兩種方法.(a) 直接法：對(duì)于給定的方程組，在沒(méi)有舍入誤差的假設(shè)下，能在預(yù)定的運(yùn)算次數(shù)內(nèi)求得精確解.最基本的直接法是Gauss消去法，重要的直接法全都受到Gauss消去法的啟發(fā).計(jì)算代價(jià)高.(b) 迭代法：基于一定的遞推格式，產(chǎn)生逼近方程組精確解的近似序列.收斂性是其為迭代法的前提，此外，存在收斂速度與誤差估計(jì)

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

44、MethodP31.cpp 迭代次數(shù) x1 x2 x30 0 0 01 0.72 0.83 0.842 0.971 1.07 1.153 1.057 1.1571 1.24824 1.08535 1.18534 1.282825 1.095098 1.195099 1.2941386 1.098338 1.198337 1.2980397 1.099442 1.199442 1.2993358 1.099811 1.199811 1.2997779 1.099936 1.199936 1.29992410 1.099979 1.199979 1.29997511 1.099993 1.1999

45、93 1.29999112 1.099998 1.199998 1.29999713 1.099999 1.199999 1.29999914 1.1 1.2 1.315 1.1 1.2 1.3 4 Jocobi迭代公式:設(shè)方程組AX=b, 通過(guò)分離變量的過(guò)程建立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,其中

46、，A=(aij)n為非奇異陣，X=(x1,x2,xn)T, b=(b1,b2,bn)T將系數(shù)陣A分解為: A=U+D+L,U為上三角矩陣，D為對(duì)角矩陣，L為下三角矩陣.于是AX=b可改寫(xiě)為(U+D+L)X=b X=D-1b-D-1(U+L)X由此可得矩陣形式的Jocobi迭代公式： Xk+1=BX(k)+f §3.2 高斯-塞德?tīng)朑auss-Seidel迭代法注意到利用Jocobi迭代公式計(jì)算時(shí)，已經(jīng)計(jì)算好的值，而Jocobi迭代公式并不利用這些最新的近似值計(jì)算，仍用.這啟發(fā)我們可以對(duì)其加以改進(jìn),即在每個(gè)分量的計(jì)算中盡量利用最新的迭代值，得到上式稱(chēng)為Gauss-Seidel迭代法.其

47、矩陣形式是X=-(D+L)-1UX+(D+L)-1b, Xk+1=BX(k)+f .迭代次數(shù) x1 x2 x3 0 0 0 0 1 0.72 0.902 1.1644 2 1.04308 1.167188 1.282054 3 1.09313 1.195724 1.297771 4 1.099126 1.199467 1.299719 5 1.09989 1.199933 1.299965 6 1.099986 1.199992 1.299996 7 1.099998 1.199999 1.299999 8 1.1 1.2 1.3§3.3 超松馳迭代法SOR方法1 基本思想:逐次超松

48、弛迭代法(Successive Over Relaxation Method,簡(jiǎn)寫(xiě)為SOR)可以看作帶參數(shù)的高斯-塞德?tīng)柕?，是G-S方法的一種修正或加速.是求解大型稀疏矩陣方程組的有效方法之一.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)于用高斯-塞德?tīng)柗椒ㄓ?jì)算一個(gè)分量的公式.若對(duì)某個(gè)參數(shù)，作與加權(quán)的平均,即 (2)其中，稱(chēng)為松弛因子.用(1)式代入(2)式，就得到解方程組AX=b的逐次超松弛迭代公式： (3)顯然，當(dāng)取=1時(shí)，式(3)就是高斯-塞德?tīng)柕?3 例題

49、分析:利用SOR方法解方程組 (1)其準(zhǔn)確解為X*=1, 1, 2.建立與式(1)相等價(jià)的形式： (2)據(jù)此建立迭代公式： (3)利用SOR算法，取迭代初值,=1.5,迭代結(jié)果如下表. 逐次超松弛迭代法次數(shù) x1 x2 x3 1 0.625000 0.062500 1.750000 2 0.390625 0.882813 1.468750 3 1.017578 0.516602 1.808594 4 0.556885 0.880981 1.710449 5 1.023712 0.743423 1.868103 6 0.746250 0.908419 1.838737 7 0.997715 0.

50、860264 1.913894 8 0.864050 0.936742 1.908605 9 0.986259 0.922225 1.945523 10 0.928110 0.958649 1.947493 11 0.985242 0.955944 1.966198 12 0.961661 0.973818 1.969521 13 0.988103 0.974699 1.979289 14 0.979206 0.983746 1.982172 15 0.991521 0.985318 1.987416 16 0.988509 0.990038 1.989513 17 0.994341 0.991414 1.992397 18 0.993538 0.993946 1.993806 19 0.996367 0.994950 1.9