第2章 計(jì)算方法

1、 第二章第二章 科學(xué)計(jì)算方法科學(xué)計(jì)算方法 科學(xué)研究、工程技術(shù)以及其它方面的大量的實(shí)際科學(xué)研究、工程技術(shù)以及其它方面的大量的實(shí)際應(yīng)用都要涉及到應(yīng)用都要涉及到計(jì)算計(jì)算?？茖W(xué)計(jì)算與科學(xué)實(shí)驗(yàn)，理論?？茖W(xué)計(jì)算與科學(xué)實(shí)驗(yàn)，理論研究共同成為科學(xué)方法論的基本環(huán)節(jié)研究共同成為科學(xué)方法論的基本環(huán)節(jié). 它們互相補(bǔ)充，它們互相補(bǔ)充，互相依賴，又相對(duì)獨(dú)立互相依賴，又相對(duì)獨(dú)立. 其中，其中，數(shù)值方法的主要內(nèi)容是研究求解數(shù)學(xué)模數(shù)值方法的主要內(nèi)容是研究求解數(shù)學(xué)模型的算法及有關(guān)理論。型的算法及有關(guān)理論。 科學(xué)計(jì)算過(guò)程描述為：科學(xué)計(jì)算過(guò)程描述為：實(shí)際實(shí)際問(wèn)題問(wèn)題數(shù)學(xué)數(shù)學(xué)模型模型數(shù)值數(shù)值方法方法計(jì)算結(jié)計(jì)算結(jié)果分析果分析 2.1 2

2、.1 緒論緒論 計(jì)算機(jī)程序設(shè)計(jì)的核心是算法計(jì)算機(jī)程序設(shè)計(jì)的核心是算法. 評(píng)價(jià)算法的兩個(gè)評(píng)價(jià)算法的兩個(gè)主要標(biāo)準(zhǔn)是主要標(biāo)準(zhǔn)是速度和精度速度和精度，速度涉及計(jì)算量，速度涉及計(jì)算量，精精度涉及誤差度涉及誤差. 誤差有誤差有數(shù)據(jù)誤差數(shù)據(jù)誤差和和方法誤差。方法誤差。數(shù)據(jù)誤差是由計(jì)數(shù)據(jù)誤差是由計(jì)算機(jī)機(jī)器數(shù)字長(zhǎng)有限所致；方法誤差是由算機(jī)機(jī)器數(shù)字長(zhǎng)有限所致；方法誤差是由“近近似似” 產(chǎn)生，近似是數(shù)值計(jì)算方法的一大特點(diǎn)。產(chǎn)生，近似是數(shù)值計(jì)算方法的一大特點(diǎn)。這是因數(shù)值計(jì)算時(shí)不必要有時(shí)也不可能取精確這是因數(shù)值計(jì)算時(shí)不必要有時(shí)也不可能取精確值。值。1. 來(lái)源來(lái)源 一、一、誤差的來(lái)源和分類(lèi)誤差的來(lái)源和分類(lèi) 來(lái)源于來(lái)源于科

3、學(xué)計(jì)算過(guò)程的四個(gè)主要的環(huán)節(jié)科學(xué)計(jì)算過(guò)程的四個(gè)主要的環(huán)節(jié) ：數(shù)數(shù)學(xué)模型的建立、有關(guān)數(shù)據(jù)的獲取、近似計(jì)算方學(xué)模型的建立、有關(guān)數(shù)據(jù)的獲取、近似計(jì)算方法（數(shù)值方法）的確立、數(shù)值計(jì)算的進(jìn)行。法（數(shù)值方法）的確立、數(shù)值計(jì)算的進(jìn)行。2. 分類(lèi)分類(lèi) 分為分為: 模型誤差、觀測(cè)誤差、截?cái)嗾`差和舍入誤差模型誤差、觀測(cè)誤差、截?cái)嗾`差和舍入誤差 其中截?cái)嗾`差（又稱方法誤差）其中截?cái)嗾`差（又稱方法誤差）,它是由求其它是由求其近似近似 所致；舍入誤差通常是四舍五入所致所致；舍入誤差通常是四舍五入所致此兩此兩類(lèi)誤差即為數(shù)值分析所研究的計(jì)算誤差類(lèi)誤差即為數(shù)值分析所研究的計(jì)算誤差. 二、絕對(duì)誤差與相對(duì)誤差二、絕對(duì)誤差與相對(duì)誤差

4、 定義定義1 設(shè)實(shí)數(shù)設(shè)實(shí)數(shù) x* 為某一數(shù)據(jù)的準(zhǔn)確值，它的為某一數(shù)據(jù)的準(zhǔn)確值，它的近似值為近似值為 x，稱稱 e(x)= x x* 為為 x 的的絕對(duì)誤差絕對(duì)誤差，簡(jiǎn)，簡(jiǎn)稱誤差稱誤差. 絕對(duì)誤差僅考慮近似值與準(zhǔn)確值的差異，而相對(duì)誤差絕對(duì)誤差僅考慮近似值與準(zhǔn)確值的差異，而相對(duì)誤差還考慮數(shù)據(jù)本身的大小，相對(duì)誤差常用百分?jǐn)?shù)表示還考慮數(shù)據(jù)本身的大小，相對(duì)誤差常用百分?jǐn)?shù)表示. 在實(shí)在實(shí)際測(cè)量或計(jì)算時(shí)，可根據(jù)具體情況估計(jì)際測(cè)量或計(jì)算時(shí)，可根據(jù)具體情況估計(jì) e(x) 或或 er(x) 的大的大小范圍小范圍. 當(dāng)當(dāng) x*0 時(shí)，稱時(shí)，稱|)()(xxexer為為 x 的的相對(duì)誤差相對(duì)誤差.則稱則稱 (x) 為

5、為 x 的的絕對(duì)誤差限絕對(duì)誤差限. 當(dāng)當(dāng) x*0 時(shí)，稱時(shí)，稱定義定義2 設(shè)設(shè) x 為準(zhǔn)確值為準(zhǔn)確值 x* 的近似值，如果的近似值，如果 )( | | )(|xxxxe|)()(xxxr為為 x 相對(duì)誤差限相對(duì)誤差限. 說(shuō)明：說(shuō)明：當(dāng)絕對(duì)誤差限當(dāng)絕對(duì)誤差限 (x) 已知時(shí)，通常相對(duì)誤差限已知時(shí)，通常相對(duì)誤差限 r(x)仍然是未知的，所以在處理具體問(wèn)題時(shí)，由于準(zhǔn)仍然是未知的，所以在處理具體問(wèn)題時(shí)，由于準(zhǔn)確值未知，可以用近似值代替，即用確值未知，可以用近似值代替，即用 x 代替代替 x* 。例例 1 零件的質(zhì)量取決于參數(shù)零件的質(zhì)量取決于參數(shù) x，設(shè)設(shè) x 的標(biāo)定值為的標(biāo)定值為 1 個(gè)個(gè)單位單位.

6、生產(chǎn)中允許參數(shù)有一定誤差，由此將零件分成生產(chǎn)中允許參數(shù)有一定誤差，由此將零件分成 A，B，C 三個(gè)等級(jí)，等級(jí)由相對(duì)誤差限決定，三個(gè)等級(jí)，等級(jí)由相對(duì)誤差限決定，A等為等為1%，B 等為等為5%，C 等為等為10%. 試確定三個(gè)等級(jí)的零試確定三個(gè)等級(jí)的零件參數(shù)允許變化的范圍件參數(shù)允許變化的范圍. A 等：等：x 0. 99，1. 01，B 等：等：x 0. 95，1. 05C 等：等：x 0. 9，1. 1. 解解 由題設(shè)，標(biāo)定值由題設(shè)，標(biāo)定值 x*= 1，根據(jù)相對(duì)誤差限定義根據(jù)相對(duì)誤差限定義將三個(gè)相對(duì)誤差限分別代入，得將三個(gè)相對(duì)誤差限分別代入，得|rxxx 有有 )1 ()1 (rrxxx例例2

7、 測(cè)量一物體的長(zhǎng)度是測(cè)量一物體的長(zhǎng)度是954cm，問(wèn)測(cè)量數(shù)據(jù)的相對(duì)誤差限問(wèn)測(cè)量數(shù)據(jù)的相對(duì)誤差限是多大？是多大？ 0. 00053 = 0. 053% 解解 因?yàn)閷?shí)際問(wèn)題所截取的近似數(shù)，其因?yàn)閷?shí)際問(wèn)題所截取的近似數(shù)，其絕對(duì)誤差限絕對(duì)誤差限一般不超過(guò)最小刻度的半個(gè)單位一般不超過(guò)最小刻度的半個(gè)單位，所以當(dāng)，所以當(dāng) x = 954 cm 時(shí)，有時(shí)，有 (x)= 0.5cm，而而x 的相對(duì)誤差滿足的相對(duì)誤差滿足 0 50 0005241954.( ).rex L所以，測(cè)量數(shù)據(jù)的相對(duì)誤差限可確定為所以，測(cè)量數(shù)據(jù)的相對(duì)誤差限可確定為 r(x)= 0. 053% 通常，通常，若近似值若近似值 x 的絕對(duì)誤差限

8、是某一位上的絕對(duì)誤差限是某一位上的半個(gè)單位的半個(gè)單位，該位到，該位到 x 的第一位非零數(shù)字一共有的第一位非零數(shù)字一共有 n 位，則稱近似值位，則稱近似值 x 有有 n 位有效數(shù)字位有效數(shù)字. 例如，考慮例如，考慮 的不同近似值的不同近似值. 取三位數(shù)取三位數(shù) x3 = 3.14，有有三、三、有效數(shù)字有效數(shù)字于是近似值于是近似值 x3 有有 3位有效數(shù)字位有效數(shù)字231021005.0 x 例如例如 0. 0031207，293. 7048，兩個(gè)數(shù)可表示為兩個(gè)數(shù)可表示為 0. 3120710 2 ，0. 293704810 3 注注: 浮點(diǎn)數(shù)在計(jì)算機(jī)程序中常用浮點(diǎn)數(shù)在計(jì)算機(jī)程序中常用 em 代替

9、代替 10m 。 實(shí)數(shù)的實(shí)數(shù)的浮點(diǎn)表示法浮點(diǎn)表示法: 0.a1a2an 10m 其中第一部分其中第一部分0.a1a2an是是尾數(shù)部尾數(shù)部 且a1非零非零,第二部分第二部分10m是是定位部定位部，用來(lái)確定小數(shù)點(diǎn)的位置用來(lái)確定小數(shù)點(diǎn)的位置. 例如例如 0. 31207e 2 ，0. 2937048e + 3表示規(guī)格化浮點(diǎn)數(shù)表示規(guī)格化浮點(diǎn)數(shù) 0. 3120710 2 ，0. 293704810 3 由定義由定義3易知：易知：若若 x 為準(zhǔn)確值為準(zhǔn)確值 x* 的按的按“四舍五入四舍五入”原則而得到的近似值，且原則而得到的近似值，且 x 的第一位非零數(shù)字到末的第一位非零數(shù)字到末尾一共有尾一共有 n 位，

10、則位，則 x 有有 n 位有效數(shù)字位有效數(shù)字. 定義定義3 3 設(shè)設(shè) x 可表示為可表示為規(guī)格化浮點(diǎn)數(shù)規(guī)格化浮點(diǎn)數(shù)形式形式 x = 0.a1a2an 10m （2.1.1）其中，其中，a1，a2，an 都是都是0 9 中的任一整數(shù)，中的任一整數(shù)，且且 a1 0. 若若 x 的絕對(duì)誤差滿足：的絕對(duì)誤差滿足： （2.1.2）則稱近似數(shù)則稱近似數(shù) x 具有具有 n 位有效數(shù)字位有效數(shù)字. nmxx1021例如，例如， 的近似值的近似值 x = 3. 142 有有4位有效數(shù)字位有效數(shù)字. 定理定理 1 設(shè)設(shè) x 是是有效數(shù)字位數(shù)為有效數(shù)字位數(shù)為 n 的近似數(shù)，其表的近似數(shù)，其表達(dá)式為式（達(dá)式為式（2.

11、1.1）. 則它的則它的相對(duì)誤差滿足相對(duì)誤差滿足 （2.1.3）反之，若近似數(shù)反之，若近似數(shù) x 的相的相對(duì)誤差滿足對(duì)誤差滿足nraxe1015)(1nraxe105)(1 （2.1.4）則則 x 至少至少有有n位有效數(shù)字位有效數(shù)字. x = 0.a1a2an 10m （2.1.1）nraxe105)(1(2.13) 定理定理1 揭示了數(shù)據(jù)的有效位數(shù)與該數(shù)據(jù)近似值的揭示了數(shù)據(jù)的有效位數(shù)與該數(shù)據(jù)近似值的相對(duì)誤差之間關(guān)系相對(duì)誤差之間關(guān)系. 根據(jù)式（根據(jù)式（2.1.3），由于），由于a11，可知，一個(gè)具有可知，一個(gè)具有 n 位有效數(shù)字的近似數(shù)位有效數(shù)字的近似數(shù) x，其相對(duì)，其相對(duì)誤差滿足誤差滿足 這

12、說(shuō)明，這說(shuō)明，有效數(shù)位數(shù)與相對(duì)誤差的階碼相對(duì)應(yīng)有效數(shù)位數(shù)與相對(duì)誤差的階碼相對(duì)應(yīng)， x 的有效數(shù)字位數(shù)越多，相對(duì)誤差越小的有效數(shù)字位數(shù)越多，相對(duì)誤差越小. nrxe105)(因此，要使相對(duì)誤差限不超過(guò)因此，要使相對(duì)誤差限不超過(guò)0.1%，只須不等式，只須不等式 10 n 0. 001 成立即可成立即可. 此時(shí)，取此時(shí)，取 n=3 即可即可. 故當(dāng)故當(dāng) x 取取 3 位有效數(shù)字位有效數(shù)字.例例3 要使要使 的近似值的近似值 x 的相對(duì)誤差限不超過(guò)的相對(duì)誤差限不超過(guò)0. 1%，x 應(yīng)取幾位有效數(shù)字？應(yīng)取幾位有效數(shù)字？。30解解: 因因 的第一位數(shù)字為的第一位數(shù)字為5，所以近似數(shù)，所以近似數(shù) x 的第一

13、位的第一位數(shù)字?jǐn)?shù)字 a1=5，根據(jù)定理，根據(jù)定理1，當(dāng)，當(dāng) x 取取 n 位有效數(shù)字時(shí)，有位有效數(shù)字時(shí)，有30151010( )nnrexa 四、函數(shù)計(jì)算的誤差估計(jì)四、函數(shù)計(jì)算的誤差估計(jì)設(shè)一元函數(shù)設(shè)一元函數(shù) y= f(x)，自變量準(zhǔn)確值為，自變量準(zhǔn)確值為 x*，對(duì)應(yīng)的函，對(duì)應(yīng)的函數(shù)準(zhǔn)確值為數(shù)準(zhǔn)確值為 y*= f(x*)，自變量近似值，自變量近似值 x 的誤差為的誤差為 e(x)，誤差限為，誤差限為 (x)，函數(shù)近似值的誤差為，函數(shù)近似值的誤差為 e(y)，誤，誤差限為差限為 (y). 利用一元函數(shù)全微分，得利用一元函數(shù)全微分，得| |( )|yyfxxx 由此得函數(shù)計(jì)算誤差估計(jì)由此得函數(shù)計(jì)算誤

14、差估計(jì)()|() |()yfxx 當(dāng)當(dāng) y0 ，x0 時(shí)，有相對(duì)誤差估計(jì)時(shí)，有相對(duì)誤差估計(jì)|( )|( )( )|( )|rrxfxyxf x 五、算術(shù)運(yùn)算的誤差估計(jì)五、算術(shù)運(yùn)算的誤差估計(jì) 設(shè)兩個(gè)近似數(shù)設(shè)兩個(gè)近似數(shù) x1與與x2 的誤差限分別為的誤差限分別為 和和 ，則，則對(duì)這兩個(gè)數(shù)的加、減、乘、除運(yùn)算，可以利用對(duì)這兩個(gè)數(shù)的加、減、乘、除運(yùn)算，可以利用多元函數(shù)的誤多元函數(shù)的誤差估計(jì)差估計(jì)，得，得)(1x)(2x)()()(2121xxxx)(|)(|)(122121xxxxxx22122121|)(|)(|)(xxxxxxx例例 4 設(shè)設(shè) a = 2. 31，b = 1. 93，c = 2.

15、24 都是有三位有都是有三位有效數(shù)字的近似數(shù)，令效數(shù)字的近似數(shù)，令 p = a + bc，求，求 (p) 和和 r(p)，并判斷并判斷 p 有幾位有效數(shù)字有幾位有效數(shù)字. 解解 由于由于a，b，c都有三位有效數(shù)字，故都有三位有效數(shù)字，故 (a) = (b) = (c) = 0. 005 所以所以 (p)= (a) + (bc) (a) + b (c) + (b) c = 0. 005 + 1. 930. 005 + 2. 240. 005= 0. 02585 而而 p= 2. 31 + 1. 932. 24= 6. 6332 故故6332. 602585. 0|)()(pppr0. 0039

16、= 0. 39% 因因 (p) 0. 02585 0. 05 ，故，故 p 中只有兩位有效數(shù)字中只有兩位有效數(shù)字. 例例5 已測(cè)得某場(chǎng)地長(zhǎng)和寬分別為已測(cè)得某場(chǎng)地長(zhǎng)和寬分別為 x= 110m，y= 80m，已知已知 試求該場(chǎng)地面積的絕試求該場(chǎng)地面積的絕對(duì)誤差限和相對(duì)誤差限對(duì)誤差限和相對(duì)誤差限. 相對(duì)誤差限相對(duì)誤差限解解: 因面積因面積 S = xy ， ，故絕對(duì)誤差限，故絕對(duì)誤差限SSyxxy ，( ) | ( ) | ( )SSSxyxy = 800. 2 + 1100. 1= 27 （m2） 1108027|)(|)()(xySSSSr= 0. 0031= 0. 31%0 20 1( )=

17、. m, ( )= . m.xy 六、六、 數(shù)值計(jì)算中的一些基本原則數(shù)值計(jì)算中的一些基本原則為使誤差不增長(zhǎng)，有一些基本原則為使誤差不增長(zhǎng)，有一些基本原則.1避免絕對(duì)值小的數(shù)作除數(shù)避免絕對(duì)值小的數(shù)作除數(shù) 這一原則主要指盡量避免除數(shù)絕對(duì)值遠(yuǎn)遠(yuǎn)小于被這一原則主要指盡量避免除數(shù)絕對(duì)值遠(yuǎn)遠(yuǎn)小于被除數(shù)絕對(duì)值的除法除數(shù)絕對(duì)值的除法. 2避免兩個(gè)相近的數(shù)據(jù)相減避免兩個(gè)相近的數(shù)據(jù)相減 3要防止大數(shù)要防止大數(shù)“吃掉吃掉”小數(shù)小數(shù) 一個(gè)絕對(duì)值很大的數(shù)和一個(gè)絕對(duì)值很小的數(shù)直接一個(gè)絕對(duì)值很大的數(shù)和一個(gè)絕對(duì)值很小的數(shù)直接相加時(shí)，很可能發(fā)生所謂相加時(shí)，很可能發(fā)生所謂“大數(shù)吃小數(shù)大數(shù)吃小數(shù)”的現(xiàn)象，的現(xiàn)象，從而影響計(jì)算結(jié)果的

18、可靠性從而影響計(jì)算結(jié)果的可靠性. 這主要是計(jì)算機(jī)表示的這主要是計(jì)算機(jī)表示的數(shù)位數(shù)有限這一客觀現(xiàn)實(shí)引起的數(shù)位數(shù)有限這一客觀現(xiàn)實(shí)引起的. 4盡量減少計(jì)算工作量盡量減少計(jì)算工作量 在考慮算法時(shí)應(yīng)注意簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)在考慮算法時(shí)應(yīng)注意簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù). 計(jì)算機(jī)執(zhí)行一個(gè)算法所花費(fèi)的時(shí)間代價(jià)除了與問(wèn)題的計(jì)算機(jī)執(zhí)行一個(gè)算法所花費(fèi)的時(shí)間代價(jià)除了與問(wèn)題的規(guī)模大小有關(guān)外，規(guī)模大小有關(guān)外，主要依賴于計(jì)算過(guò)程中所用乘除法主要依賴于計(jì)算過(guò)程中所用乘除法次數(shù)的多少次數(shù)的多少，也就是計(jì)算工作量的大小，也就是計(jì)算工作量的大小. 計(jì)算工作量小計(jì)算工作量小的算法不僅節(jié)約運(yùn)行時(shí)間，而且使誤差積累小的算法不僅節(jié)約

19、運(yùn)行時(shí)間，而且使誤差積累小. 5選用數(shù)值穩(wěn)定性好的算法選用數(shù)值穩(wěn)定性好的算法 對(duì)同一個(gè)數(shù)學(xué)問(wèn)題，即使在數(shù)學(xué)公式已經(jīng)確定的對(duì)同一個(gè)數(shù)學(xué)問(wèn)題，即使在數(shù)學(xué)公式已經(jīng)確定的情況下，仍然可以設(shè)計(jì)出不同的算法情況下，仍然可以設(shè)計(jì)出不同的算法. 而不同的算法而不同的算法在執(zhí)行過(guò)程中對(duì)數(shù)據(jù)誤差的影響不一樣，在執(zhí)行過(guò)程中對(duì)數(shù)據(jù)誤差的影響不一樣，舍入誤差舍入誤差對(duì)計(jì)算結(jié)果影響不大的算法被稱為對(duì)計(jì)算結(jié)果影響不大的算法被稱為數(shù)值穩(wěn)定的算法數(shù)值穩(wěn)定的算法. 方程：方程： f(x)= 0如果如果 f(x) 是非線性函數(shù)，則稱為是非線性函數(shù)，則稱為非線性方程非線性方程, 其其中中f(x)是關(guān)于是關(guān)于x的一元函數(shù)的一元函數(shù).2

20、.2 非線性方程數(shù)值方法非線性方程數(shù)值方法 非線性方程的求解問(wèn)題是科學(xué)與工程計(jì)算中常非線性方程的求解問(wèn)題是科學(xué)與工程計(jì)算中常見(jiàn)的問(wèn)題之一見(jiàn)的問(wèn)題之一. 但對(duì)高于但對(duì)高于4次的代數(shù)方程，不存在次的代數(shù)方程，不存在通用的求根公式，而對(duì)超越方程一般很難直接求通用的求根公式，而對(duì)超越方程一般很難直接求出其準(zhǔn)確解出其準(zhǔn)確解. 所以，數(shù)值方法就是非常實(shí)用和有效的方法所以，數(shù)值方法就是非常實(shí)用和有效的方法. 其其中，中，迭代迭代技術(shù)是一種常用技術(shù)技術(shù)是一種常用技術(shù). 其思想其思想是對(duì)根的是對(duì)根的逐逐次逼近次逼近.一般地，若用計(jì)算機(jī)求解非解線性方程有下列兩步一般地，若用計(jì)算機(jī)求解非解線性方程有下列兩步:第一步

21、第一步 對(duì)方程的根進(jìn)行隔離對(duì)方程的根進(jìn)行隔離. 找出找出隔根區(qū)間隔根區(qū)間（區(qū)間內(nèi)只包含方程的一個(gè)根）（區(qū)間內(nèi)只包含方程的一個(gè)根）. 第二步第二步 利用利用迭代法計(jì)算迭代法計(jì)算滿足一定精度的根近似值滿足一定精度的根近似值. 在方程的隔根區(qū)間內(nèi)從給定的一個(gè)（或多個(gè)）出在方程的隔根區(qū)間內(nèi)從給定的一個(gè)（或多個(gè)）出發(fā)值發(fā)值x0，按某種方法產(chǎn)生一個(gè)序列，按某種方法產(chǎn)生一個(gè)序列 x0，x1，x2，xn，.此序列在某種條件下收斂于方程的根此序列在某種條件下收斂于方程的根 x*. 本節(jié)介紹非線性方程求根的本節(jié)介紹非線性方程求根的逐次逼近法逐次逼近法. 同時(shí)也同時(shí)也討論方法的討論方法的收斂性收斂性和和誤差估計(jì)誤差

22、估計(jì)等問(wèn)題等問(wèn)題. 二分法本質(zhì)上是一種二分法本質(zhì)上是一種區(qū)間迭代算法區(qū)間迭代算法，在迭代過(guò)程中，在迭代過(guò)程中不斷對(duì)隔根區(qū)間進(jìn)行壓縮，以區(qū)間中點(diǎn)逼近方程的根不斷對(duì)隔根區(qū)間進(jìn)行壓縮，以區(qū)間中點(diǎn)逼近方程的根. 它所涉及的理論是連續(xù)函數(shù)介值定理它所涉及的理論是連續(xù)函數(shù)介值定理: 定理定理1 設(shè)函數(shù)設(shè)函數(shù) f(x) 在區(qū)間在區(qū)間a，b上連續(xù)，且上連續(xù)，且f(a)f(b) 0，則則f(x)= 0 在區(qū)間在區(qū)間(a，b)內(nèi)至少有一個(gè)根內(nèi)至少有一個(gè)根. 一一、 二分法二分法方法方法 (設(shè)函數(shù)設(shè)函數(shù) f(x)滿足定理滿足定理1條件條件):1. 求區(qū)間求區(qū)間a，b的中點(diǎn)的中點(diǎn) x0 = a + (b a)/2=

23、(a + b )/22. 計(jì)算計(jì)算f(x0), 如果如果 f(x0)= 0, 則則 x0 是方程的解是方程的解; 否則繼續(xù)否則繼續(xù)3. 3. 如果如果 f(x0)f(a) 0，取，取 a1= a，b1= x0; 如果如果 f(x0)f(b) 0，取，取a1= x0，b1= b. 此時(shí)區(qū)間此時(shí)區(qū)間 a1，b1的長(zhǎng)度是的長(zhǎng)度是a，b的一半的一半,將其作將其作為新的為新的a，b區(qū)間，重復(fù)區(qū)間，重復(fù) 1-3 直到找到根或找到滿直到找到根或找到滿足精度要求的近似根足精度要求的近似根(隔根區(qū)間充分小時(shí)隔根區(qū)間充分小時(shí)). 說(shuō)明說(shuō)明 二分法計(jì)算過(guò)程中，設(shè)第二分法計(jì)算過(guò)程中，設(shè)第n區(qū)間為區(qū)間為an，bn，則，

24、則(1) bn an= (b a)/ 2n (2) n充分大時(shí)，可取充分大時(shí)，可取xn = (an + bn )/2為方程的解為方程的解x*的近似值的近似值, 且有如下且有如下收斂定理收斂定理 定理定理2 設(shè)設(shè)x*為方程為方程 f(x)= 0在區(qū)間在區(qū)間a，b內(nèi)的唯一根，內(nèi)的唯一根，f(x)滿足滿足 f(a)f(b)0使對(duì)任意的使對(duì)任意的x0N(x*)，xn=(xn-1) 產(chǎn)生的序列產(chǎn)生的序列 xn均均收斂于收斂于 x*，則稱，則稱迭代法局部收斂迭代法局部收斂. 1log2abn(*)21*nnabxx算法算法1（二分法二分法求解非線性方程算法）求解非線性方程算法）第四步：第四步：若若 |b

25、a| 1 則轉(zhuǎn)第二步；否則，輸出則轉(zhuǎn)第二步；否則，輸出 x0 結(jié)束結(jié)束.第一步：第一步：輸入誤差限輸入誤差限 0， 1，計(jì)算，計(jì)算 y1 f(a)，y2 f(b)；第二步：第二步：計(jì)算計(jì)算 x0 0.5(a+b)，y0f(x0)，若，若 |y0| 0，則輸，則輸 出出 x0，結(jié)束，結(jié)束. 否則轉(zhuǎn)第三步；否則轉(zhuǎn)第三步；第三步：第三步：若若 y0 y1 0，則置，則置 b x0，y2 y0；否則；否則 a x0， y1 y0，轉(zhuǎn)第四步；，轉(zhuǎn)第四步；例例1 用二分法求下列方程在區(qū)間用二分法求下列方程在區(qū)間0，1內(nèi)的一個(gè)根，要求內(nèi)的一個(gè)根，要求 誤差不超過(guò)誤差不超過(guò) 1/250)2sin(xex 所以

26、所以 f(x) 在區(qū)間在區(qū)間 0，1 上恰有一個(gè)根上恰有一個(gè)根. 計(jì)算結(jié)果如下表計(jì)算結(jié)果如下表. 解解: 令令)2sin()(xexfx, 計(jì)算得計(jì)算得(0)10,(1)0.63210,( )cos()022xxfffxe 取取 x4= 0.5 (0.4375 + 0.5) = 0.4688 作為作為 x* 的近似的近似值值. 誤差不超過(guò)誤差不超過(guò)1/ 25. 二、二、 牛頓（牛頓（Newton）迭代法）迭代法算法思想算法思想 將方程將方程 f(x)=0 中函數(shù)中函數(shù) f(x) 在根的附近在根的附近線性化線性化，以線性方程的解逼近非線性方程的解以線性方程的解逼近非線性方程的解 .理論依據(jù)理論依

27、據(jù) 設(shè)函數(shù)設(shè)函數(shù)f(x)在有根區(qū)間在有根區(qū)間a，b二次連續(xù)可微，二次連續(xù)可微，x0是根是根 x*的一個(gè)近似值，則的一個(gè)近似值，則 f(x) 在在 x0 處的泰勒展式為處的泰勒展式為 20000)(! 2)()()()(xxfxxxfxfxf 其中其中 在在 x 和和 x0之間之間.即即)()()(000 xxxfxfxf于是于是 f(x)=0 可近似轉(zhuǎn)換可近似轉(zhuǎn)換為為0)()(000 xxxfxf y = x e - x O y x x0 x1 x2 x3 迭代公式的推導(dǎo)迭代公式的推導(dǎo)設(shè)設(shè) f (x0) 0，其解記為，其解記為這是較這是較 x0 更靠近更靠近x* 的新的的新的近似值近似值. 一

28、般，在一般，在 xn 附近的附近的線性化方程為線性化方程為:設(shè)設(shè) f (xn) 0, 其解記為其解記為)()(0001xfxfxx 0)()( nnnxxxfxf1()()nnnnfxxxfx，n = 0，1， Newton迭代公式迭代公式 這就是這就是, 被稱為牛頓迭代法的計(jì)算格式被稱為牛頓迭代法的計(jì)算格式. 選一個(gè)選一個(gè)初始點(diǎn)初始點(diǎn) x0，由迭代公式便可得到迭代序列，由迭代公式便可得到迭代序列 x0，x1，xn，.例例3 用牛頓迭代法計(jì)算用牛頓迭代法計(jì)算 7 的平方根，記錄并分析計(jì)的平方根，記錄并分析計(jì)算過(guò)程中數(shù)據(jù)變化規(guī)律算過(guò)程中數(shù)據(jù)變化規(guī)律. 解解 設(shè)設(shè) ，得方程，得方程 x2 7 =

29、0. 利用牛頓迭代利用牛頓迭代法，得計(jì)算格式法，得計(jì)算格式7 xn= 0，1， 117()2nnnxxx， 取初始值為取初始值為 x0 = 2.5，迭代計(jì)算的數(shù)據(jù)結(jié)果見(jiàn)下表，迭代計(jì)算的數(shù)據(jù)結(jié)果見(jiàn)下表 由此可見(jiàn)，第五次迭代和第四次迭代數(shù)據(jù)的由此可見(jiàn)，第五次迭代和第四次迭代數(shù)據(jù)的15位數(shù)完位數(shù)完全相同，說(shuō)明數(shù)據(jù)全相同，說(shuō)明數(shù)據(jù)2.64575131106459 準(zhǔn)確到小數(shù)點(diǎn)后準(zhǔn)確到小數(shù)點(diǎn)后14位位. 而得到這樣的精度的數(shù)據(jù)只有而得到這樣的精度的數(shù)據(jù)只有4次迭代次迭代.對(duì)于牛頓迭代法對(duì)于牛頓迭代法, 迭代函數(shù)為迭代函數(shù)為)()()(xfxfxx 2)(/)()()(xfxfxfx 假定假定x* 是是

30、f(x)=0 的單根，即的單根，即f(x*)=0， f (x*) 0. 由由 ，利用泰勒展式知，牛頓迭代法在根，利用泰勒展式知，牛頓迭代法在根x*附近至少平方收斂附近至少平方收斂. 0)(* x定理定理3 假設(shè)在的某鄰域內(nèi)具有連續(xù)的二階導(dǎo)數(shù)，且設(shè)假設(shè)在的某鄰域內(nèi)具有連續(xù)的二階導(dǎo)數(shù)，且設(shè)f(x*)=0， f (x*) 0 ，則對(duì)充分靠近的初始值，則對(duì)充分靠近的初始值x0，牛頓，牛頓迭代法產(chǎn)生的序列迭代法產(chǎn)生的序列xn至少至少平方收斂平方收斂于于x*. 牛頓迭代法的缺陷牛頓迭代法的缺陷: 1. 可能發(fā)生被零除錯(cuò)誤可能發(fā)生被零除錯(cuò)誤 當(dāng)函數(shù)在它的零點(diǎn)附近，導(dǎo)函數(shù)的絕對(duì)值非常當(dāng)函數(shù)在它的零點(diǎn)附近，導(dǎo)函

31、數(shù)的絕對(duì)值非常 小時(shí)，運(yùn)算會(huì)出現(xiàn)被零除錯(cuò)誤；小時(shí)，運(yùn)算會(huì)出現(xiàn)被零除錯(cuò)誤；2. 可能出現(xiàn)死循環(huán)可能出現(xiàn)死循環(huán) 當(dāng)函數(shù)在它的零點(diǎn)有拐點(diǎn)時(shí)，可能會(huì)使迭代當(dāng)函數(shù)在它的零點(diǎn)有拐點(diǎn)時(shí)，可能會(huì)使迭代 陷入死陷入死 循環(huán)循環(huán). 下面是兩個(gè)牛頓迭代法不成功的下面是兩個(gè)牛頓迭代法不成功的反例反例例例4 用牛頓迭代法解方程用牛頓迭代法解方程 x e x =0. y = x e - x O y x x0 x1 x2 x3 同時(shí)可計(jì)算出當(dāng)自變量增大時(shí)函數(shù)同時(shí)可計(jì)算出當(dāng)自變量增大時(shí)函數(shù) f(x) 迅速趨近于零，迅速趨近于零，例如例如 f(x15)=0.0000000536. 算法有可能錯(cuò)誤地將算法有可能錯(cuò)誤地將 x15做

32、為做為根根.解解: 令令 f(x)= xe x ，f(x) 恒為正，在區(qū)間恒為正，在區(qū)間1，內(nèi)單內(nèi)單調(diào)遞減調(diào)遞減. 取取x0= 2，用牛頓迭代法計(jì)算得，用牛頓迭代法計(jì)算得x1= 4，x2= 5.33333，x15= 19.72354943，.發(fā)生被零除錯(cuò)誤發(fā)生被零除錯(cuò)誤例例5 用牛頓迭代法解方程用牛頓迭代法解方程 x3 x 3= 0. 解：解：對(duì)于對(duì)于 f(x)= x3 x 3 ，取，取x0= 0，用牛頓迭代法計(jì)，用牛頓迭代法計(jì) 算，得算，得x1= 3，x2= 1.9615，x3= 1.1472，x4= 0.0066，.數(shù)列中的數(shù)列中的項(xiàng)以四項(xiàng)項(xiàng)以四項(xiàng)為一個(gè)周為一個(gè)周期重復(fù)期重復(fù)(見(jiàn)見(jiàn)右圖右圖

33、)，算，算法將陷入法將陷入一種死循一種死循環(huán)中環(huán)中. x0 y x1 x2 x3 y=x3 x 3 x 定理定理4 4 （非局部收斂性定理）（非局部收斂性定理）給定方程給定方程 f(x)= 0，如，如果函數(shù)果函數(shù) f(x)C2a，b，且在，且在a，b滿足條件：滿足條件：（1）f(a) f(b) 0. 則方程則方程 f(x)= 0 在在a，b 上有唯一根上有唯一根 x*，且由初值，且由初值x0按牛頓迭代公式按牛頓迭代公式1()()nnnnf xxxfx ， n= 0, 1, 2, 求得的序列求得的序列 xn 二階收斂二階收斂于于x*. 收斂性要求初始點(diǎn)要取得合適，否則會(huì)導(dǎo)致錯(cuò)誤結(jié)果收斂性要求初始

34、點(diǎn)要取得合適，否則會(huì)導(dǎo)致錯(cuò)誤結(jié)果. 定理定理4的解釋的解釋: 1. 定理定理4 中條件（中條件（1）保證了根的存在；）保證了根的存在； 2. 條件（條件（2）要求）要求 f(x) 是單調(diào)函數(shù)，且是單調(diào)函數(shù)，且f(x)在在a，b上是上凸或下凸；上是上凸或下凸； 3. 條件（條件（3）取）取 x0a，b使使 f (x0)f ”(x0) 0 保證了保證了當(dāng)當(dāng) xna，b時(shí)，有時(shí)，有 xn+1a，b. 注記如下：注記如下：如果如果 f(x) 的二階導(dǎo)數(shù)的二階導(dǎo)數(shù)大于零，則函數(shù)圖形大于零，則函數(shù)圖形是下凸曲線，根據(jù)條是下凸曲線，根據(jù)條件（件（3），應(yīng)取牛頓迭），應(yīng)取牛頓迭代 的 初 始 點(diǎn) 使 得代 的

35、 初 始 點(diǎn) 使 得 f(x0)0（見(jiàn)右圖）（見(jiàn)右圖） y x O x0 x1 x2 如果如果 f(x) 的二階導(dǎo)數(shù)小于零，則函數(shù)圖形是上的二階導(dǎo)數(shù)小于零，則函數(shù)圖形是上凸曲線，根據(jù)條件（凸曲線，根據(jù)條件（3），應(yīng)取牛頓迭代的初始），應(yīng)取牛頓迭代的初始點(diǎn)使得點(diǎn)使得 f(x0)0, 當(dāng)當(dāng) 時(shí)時(shí), 由弦截法產(chǎn)生的序列由弦截法產(chǎn)生的序列 xn 收斂于收斂于 x*, 且且收斂收斂階至少為階至少為1.618. *,xxxx01 2.3 線性方程組的直接解法線性方程組的直接解法 用用 E1, E2, , En表示方程的行號(hào)表示方程的行號(hào), 則則 n 階線性方程組可階線性方程組可寫(xiě)成如下形式寫(xiě)成如下形式:寫(xiě)

36、為矩陣形式寫(xiě)為矩陣形式 Ax= b (2.3.2) (2.3.1)1111122112212222221122,nnnnnnnnnnnEa xa xa xbEa xa xa xbEa xa xa xb分別稱為方程組的分別稱為方程組的系數(shù)矩陣系數(shù)矩陣、右端向量右端向量和和解向量解向量. 1212(),( , ,),( ,)n nTnTnij n nnnAaRbb bbR xx xxR 線性方程組的數(shù)值解法分為線性方程組的數(shù)值解法分為和和迭代法迭代法兩兩類(lèi)類(lèi). 直接法在沒(méi)有舍入誤差的情況下直接法在沒(méi)有舍入誤差的情況下, 通過(guò)有限步計(jì)通過(guò)有限步計(jì)算求得方程組的準(zhǔn)確解算求得方程組的準(zhǔn)確解. 對(duì)于中、小

37、型方程組對(duì)于中、小型方程組 (n1000) 及某些大型的稀疏方程組非常實(shí)用及某些大型的稀疏方程組非常實(shí)用. 實(shí)際實(shí)際計(jì)算中計(jì)算中, 由于誤差的影響由于誤差的影響, 直接法只能求得方程組直接法只能求得方程組的近似解的近似解. 而迭代法則是建立迭代格式而迭代法則是建立迭代格式, 從初始向量出發(fā)從初始向量出發(fā), 產(chǎn)生向量序列產(chǎn)生向量序列, 逐次逼近方程組的準(zhǔn)確解逐次逼近方程組的準(zhǔn)確解. 對(duì)大型對(duì)大型方程組方程組, 常選用迭代法常選用迭代法. 求解方程組求解方程組 (2.3.1) 的的 Gram 法則法則是公式求解方法是公式求解方法. 對(duì)對(duì)一個(gè)一個(gè)n 階方程組階方程組, Gram 法則需要計(jì)算出包括法

38、則需要計(jì)算出包括A的行列式的行列式在內(nèi)的在內(nèi)的 (n+1) 個(gè)個(gè)n 階行列式階行列式, 而每一個(gè)行列式的計(jì)算需用而每一個(gè)行列式的計(jì)算需用n!(n-1)次乘法次乘法. 對(duì)于對(duì)于n=20的中等規(guī)模問(wèn)題的求解的中等規(guī)模問(wèn)題的求解, 也要耗也要耗費(fèi)巨大機(jī)時(shí)費(fèi)巨大機(jī)時(shí); 而作為一類(lèi)最基本的直接法而作為一類(lèi)最基本的直接法高斯消元高斯消元法法, 其計(jì)算工作量只有大約其計(jì)算工作量只有大約2n3/3次浮點(diǎn)數(shù)運(yùn)算次浮點(diǎn)數(shù)運(yùn)算.一、一、高斯消元法高斯消元法基本思想基本思想 將一般的線性方程組將一般的線性方程組 (2.3.1) 經(jīng)初等變換經(jīng)初等變換化為等價(jià)的化為等價(jià)的上三角形方程組上三角形方程組, 然后對(duì)上三角形方程

39、然后對(duì)上三角形方程組直接求解組直接求解. 1. 上三角方程組求解的回代過(guò)程上三角方程組求解的回代過(guò)程如下形式的線性方程組稱為上三角形方程組如下形式的線性方程組稱為上三角形方程組 1111221122222,.nnnnnnnna xa xa xbaxaxbaxb (2.3.3) 當(dāng)當(dāng) a11a22ann0 時(shí)時(shí),求解過(guò)程為求解過(guò)程為 從最后一個(gè)方程開(kāi)從最后一個(gè)方程開(kāi)始始, 逐個(gè)計(jì)算出未知元逐個(gè)計(jì)算出未知元 (稱為回代過(guò)程稱為回代過(guò)程) , 即即1/,/,(1,2,2,1).nnnnnkkkjjkkjkxbaxba xaknn 算法算法1第一步：輸入方程組系數(shù)矩陣和右端向量第一步：輸入方程組系數(shù)矩

40、陣和右端向量; 回代過(guò)程所用的乘除法次數(shù)總共為回代過(guò)程所用的乘除法次數(shù)總共為 n(n+1)/2第二步：第二步： ; /;1nnnnxbakn1第三步：第三步：,11()/kkk kkkn nkkxbaxa xa第四步：判斷第四步：判斷, 若若k 1, 則則k k-1, 轉(zhuǎn)第三步轉(zhuǎn)第三步, 否則否則, 轉(zhuǎn)第轉(zhuǎn)第 五步五步; 第五步：輸出第五步：輸出 , 結(jié)束結(jié)束. 12,nx xx二、高斯消元過(guò)程二、高斯消元過(guò)程基本思想基本思想 對(duì)方程組的增廣矩陣做行初等變換使其為對(duì)方程組的增廣矩陣做行初等變換使其為上上三角形方程組三角形方程組, 再再回代回代求出方程組的解求出方程組的解.例例1 用高斯消元法解

41、方程組用高斯消元法解方程組:1231231232346,3525,433032.xxxxxxxxx解解 Ei 表示增廣矩陣的第表示增廣矩陣的第 i 行行, 用用 Ei +Ej Ej , 表示第表示第 i 行乘數(shù)行乘數(shù) 加至第加至第 j 行行. 該方程組的增廣矩陣為該方程組的增廣矩陣為:2 3463 5254 3 30 32A b12213334,22EEEEEE(1)(1)234600.544032220Ab23330.5EEE(2)(2)234600.5440024Ab由回代求出方程組的解由回代求出方程組的解: x1 = 13 x2 = 8 x3 = 2已得到三角形方程組已得到三角形方程組

42、1232332346,0.544,24.xxxxxx 說(shuō)明說(shuō)明: 對(duì)于方程組對(duì)于方程組 (2.3.1), 將其轉(zhuǎn)化為等價(jià)的上三角將其轉(zhuǎn)化為等價(jià)的上三角形方程組的過(guò)程稱為形方程組的過(guò)程稱為消元過(guò)程消元過(guò)程. 算法算法2 (消元過(guò)程的算法消元過(guò)程的算法)設(shè)方程組設(shè)方程組 (2.3.1) 的增廣矩陣為的增廣矩陣為111211212222124 nnnnnnaaabaaabaaabA b第一步：輸入第一步：輸入 A=(aij)nn 和和 b=b1, , bnT, k0; 第二步：第二步：kk+1, i k; 第三步：第三步：ii+1, 計(jì)算計(jì)算 mik = aik / akk, bi bi mikbk

43、 , aij aij mik akj ( j = k+1, , n);如果如果 i n, 則轉(zhuǎn)第三步則轉(zhuǎn)第三步, 否則轉(zhuǎn)第四步否則轉(zhuǎn)第四步; 第四步：如果第四步：如果k 1 , 轉(zhuǎn)第五步轉(zhuǎn)第五步; 否則輸出否則輸出 f1, f2, , fn , 結(jié)束結(jié)束. 第四步：判斷第四步：判斷, 如果如果 kn , 轉(zhuǎn)第三步轉(zhuǎn)第三步; 否則否則, jn, 轉(zhuǎn)第五步轉(zhuǎn)第五步; 隨著計(jì)算技術(shù)的發(fā)展隨著計(jì)算技術(shù)的發(fā)展, 計(jì)算機(jī)的存儲(chǔ)量日益增大計(jì)算機(jī)的存儲(chǔ)量日益增大, 計(jì)算計(jì)算速度也迅速提高速度也迅速提高, 在計(jì)算機(jī)上可以求解的線性方程的在計(jì)算機(jī)上可以求解的線性方程的規(guī)模也越來(lái)越大規(guī)模也越來(lái)越大, 在實(shí)際應(yīng)用中在

44、實(shí)際應(yīng)用中, 常常遇到大型稀疏線常常遇到大型稀疏線性方程組的求解問(wèn)題性方程組的求解問(wèn)題, 因此尋求能保持稀疏性的有效因此尋求能保持稀疏性的有效算法就成為數(shù)值代數(shù)中的一個(gè)非常重要的課題算法就成為數(shù)值代數(shù)中的一個(gè)非常重要的課題. 而而迭迭代法代法就是其中之一就是其中之一.2.4 線性方程組的迭代解法線性方程組的迭代解法迭代法思想迭代法思想: 構(gòu)造收斂的向量序列構(gòu)造收斂的向量序列, 使該序列收斂于所使該序列收斂于所求解方程組的準(zhǔn)確解求解方程組的準(zhǔn)確解. 具體地具體地設(shè)方程組設(shè)方程組 Ax = b有唯一解有唯一解 x*, 將將 Ax = b 變形為等價(jià)的方變形為等價(jià)的方程組程組 x = Bx + f

45、由此建立迭代公式由此建立迭代公式 x (k + 1) = Bx (k) + f ( k = 0, 1, 2, ) . 給定初始向量給定初始向量 x (0) , 按此公式計(jì)算的近似解向量序列按此公式計(jì)算的近似解向量序列 x (k ) , 稱此方法為稱此方法為迭代法迭代法. 若對(duì)任意初值若對(duì)任意初值 x (0) , 當(dāng)?shù)?dāng)?shù)螖?shù)無(wú)限增加時(shí)次數(shù)無(wú)限增加時(shí), 序列序列 x (k ) 都有相同的極限都有相同的極限 x*, 即即 x* = Bx* + f ,則稱迭代法是收斂的則稱迭代法是收斂的, 否則稱為發(fā)散的否則稱為發(fā)散的. 迭代格式中的矩迭代格式中的矩陣陣B稱為迭代矩陣稱為迭代矩陣. ( )*li

46、mkkxx一、雅可比迭代和高斯一、雅可比迭代和高斯-賽德?tīng)柕惖聽(tīng)柕?迭代法適用于大型稀疏矩陣的線性方程組迭代法適用于大型稀疏矩陣的線性方程組, 為了介紹該為了介紹該迭代法的思想迭代法的思想, 考查下面三階方程的迭代計(jì)算過(guò)程考查下面三階方程的迭代計(jì)算過(guò)程. 例例1 已知已知12312312397,108,1513.xxxxxxxxx試用迭代法產(chǎn)生向量序列逐步逼近準(zhǔn)確解試用迭代法產(chǎn)生向量序列逐步逼近準(zhǔn)確解 ( 注注:方程組的方程組的準(zhǔn)確解為準(zhǔn)確解為 x* = 1, 1, 1T ) .解解 將原方程做等價(jià)變形將原方程做等價(jià)變形, 由第一個(gè)方程解出由第一個(gè)方程解出 x1, 由第二由第二個(gè)方程解出

47、個(gè)方程解出 x2, 由第三個(gè)方程解出由第三個(gè)方程解出 x3, 得如下方程組得如下方程組:由此建立迭代格式由此建立迭代格式取初始向量取初始向量 x(0) = 0, 0, 0T, 迭代情況如表迭代情況如表2-6所示所示.1232133121179991181010101113151515xxxxxxxxx(1)( )( )123(1)( )( )213(1)( )( )3121179991181010101113151515kkkkkkkkkxxxxxxxxx說(shuō)明說(shuō)明: 1. 表表2-6中第一列數(shù)據(jù)為第一次迭代的結(jié)果中第一列數(shù)據(jù)為第一次迭代的結(jié)果, 記記 為為 x(1); 以以 x(1) 為輸入數(shù)

48、據(jù)進(jìn)行第二次迭代為輸入數(shù)據(jù)進(jìn)行第二次迭代, 其結(jié)果為表中第其結(jié)果為表中第二列數(shù)據(jù)二列數(shù)據(jù), 記為記為 x(2) ; . 當(dāng)當(dāng) k = 4時(shí)時(shí), 得近似解得近似解 x(4) = 0.9987, 0.9988, 0.9991T. 2. 由上可知由上可知, 對(duì)給定的方程組對(duì)給定的方程組, 迭代法是利用迭代格式迭迭代法是利用迭代格式迭代計(jì)算出向量序列代計(jì)算出向量序列 x(1), x(2), , x(n), 逐步逼近方程組的準(zhǔn)確解逐步逼近方程組的準(zhǔn)確解. 例例1所用迭代法稱為所用迭代法稱為雅可比雅可比 (Jacobi) 迭代法迭代法. 表表 2-6一般地一般地, n 階線性代數(shù)方程階線性代數(shù)方程 Ax

49、= b (AR nn, bR n, xR n ) 可以寫(xiě)成如下形式可以寫(xiě)成如下形式:設(shè)設(shè) aii 0 ( i = 1, 2, , n), 由第由第i個(gè)方程解出個(gè)方程解出xi ( i = 1, 2, , n), 得到與原方程組等價(jià)的方程組得到與原方程組等價(jià)的方程組( i = 1, 2, , n).1nijjija xb1iijjij iiixa xba( i = 1, 2, , n).將將迭代格式迭代格式 (2.4.1) 推廣推廣, 有有(1)()1kkiijjijiiixa xba ( i = 1, 2, , n). (2.4.2)從而得到雅可比迭代法的矩陣形式從而得到雅可比迭代法的矩陣形式x

50、(k + 1) = BJ x(k ) + fJ , k = 1, 2, , n其中其中這就是雅可比迭代法的分量形式這就是雅可比迭代法的分量形式, 即即(1)( )( )( )11221331111(1)( )( )( )221 12332222(1)( )( )( )1 122,111(),1(),1().kkkknnkkkknnkkkknnnn nnnnnxa xa xa xbaxa xa xa xbaxa xa xaxba將原方程組系數(shù)矩陣將原方程組系數(shù)矩陣A中主對(duì)角元分裂中主對(duì)角元分裂, 設(shè)設(shè)A = D L U 其中其中, D =diag(a11, a22, , ann), aii0 (

51、 i = 1, 2, , n), 112111111122122222221200,0nnJJnnnnnnnnnaabaaaaabaaafaabaaaB12131212323132312300000,0000nnnnnnaaaaaaaaaaaa LU由于由于D 1 存在存在, 于是于是BJ = D 1(L + U) = D 1(D A ) = I D 1 A,fJ = D 1 b.稱稱 BJ = I D 1 A為為雅可比迭代矩陣雅可比迭代矩陣. 算法算法1 (Jacobi 迭代算法迭代算法) (1) 輸入輸入A, b, x(0), 維數(shù)維數(shù)n, 精度精度 , 最大容許迭代次數(shù)最大容許迭代次數(shù)N

52、; (2) 置置k=1; (3) 計(jì)算計(jì)算 ( i = 1, 2, , n); (0)11iiijjjiixba xa (4) 若若| x x(0) | , 輸出輸出x, 停機(jī)停機(jī); 否則轉(zhuǎn)否則轉(zhuǎn) (5) ; (5) 若若 kN, 則則 k k+1, xi (0) xi ( i = 1, 2, , n), 轉(zhuǎn)轉(zhuǎn) (3) ; 否則否則, 輸出失敗信息輸出失敗信息, 停機(jī)停機(jī). 高斯高斯-賽德?tīng)栙惖聽(tīng)?(Gauss-Seidel) 迭代法迭代法引入引入 將例將例1中的方程組及迭代格式中的方程組及迭代格式 (2.4.1) 做如下修改：做如下修改：盡量利用最新計(jì)算數(shù)據(jù)盡量利用最新計(jì)算數(shù)據(jù), 如計(jì)算如計(jì)

53、算 時(shí)時(shí), 由于已算出由于已算出 , 所以用所以用 , 而不用而不用 , 則迭代格式則迭代格式 (2.4.1) 變?yōu)樽優(yōu)?1)2kx(1)1kx( )1kx(1)1kx (2.4.3) (1)( )( )123(1)(1)( )213(1)(1)(1)3121179991181010101113151515kkkkkkkkkxxxxxxxxx取初始值取初始值x(0) = 0, 0, 0T, 迭代情況如下表所示迭代情況如下表所示 k = 4時(shí)時(shí), 滿足滿足 =5.557810 4. 43( )( )|xx 說(shuō)明說(shuō)明: 1. 我們稱迭代格式我們稱迭代格式 (2.4.3) 為解為解Ax = b的的高

54、斯高斯-賽德賽德?tīng)枲?(Gauss-Seidel) 迭代法迭代法. 2. 對(duì)一般對(duì)一般n階方程組階方程組Ax = b, aii 0 ( i = 1, 2, , n), 迭代格式迭代格式 (2.4.3) 就成為就成為這就是這就是Gauss-Seidel迭代法的分量形式迭代法的分量形式, 其其矩陣形式矩陣形式為為(1)( )( )( )11221331111(1)(1)( )( )22112332222(1)(1)(1)(1)1122,111(),1(),1().kkkknnkkkknnkkkknnnn nnnnnxa xa xa xbaxa xa xaxbaxa xaxaxba x(k+1) =

55、 D 1( L x(k+1) + U x(k ) + b ) = D 1 L x (k+1) + D 1 U x(k ) + D 1b.即即 ( i = 1, 2, , n). (2.4.4) 1111111()()()inkkkiijjijjijj iiixa xa xba )可改寫(xiě)為可改寫(xiě)為x( k + 1) = (D L) 1 U x(k ) + (D L) 1b = BG-S x(k) + fG-S ( k = 1, 2, , n)其中其中 BG-S = ( D L ) 1 U 稱為稱為Guss-Seidel迭代矩陣迭代矩陣. 計(jì)算實(shí)踐表明計(jì)算實(shí)踐表明, 對(duì)許多問(wèn)題對(duì)許多問(wèn)題 Gaus

56、s-Seidel 迭代法迭代法確實(shí)比確實(shí)比 Jacobi 迭代法收斂快迭代法收斂快, 但也有但也有Gauss-Seidel迭迭代比代比Jacobi迭代收斂慢的情況迭代收斂慢的情況, 甚至還有甚至還有Jacobi迭代迭代收斂收斂, 而而Gauss-Seidel迭代發(fā)散的情形迭代發(fā)散的情形. (1) 輸入輸入A, b, x(0), 維數(shù)維數(shù)n, 精度精度 , , 最大容許迭代次數(shù)最大容許迭代次數(shù)N; (2) 置置k=1; 算法算法2 (Gauss-Seidel迭代算法迭代算法) (3) 計(jì)算計(jì)算 ( i = 2, , n 1 )(0)11121jjjnxba xa 1(0)111iniiijjij

57、jjj iiixba xa xa 111;nnnijjnnxba xa (4) 若若| x x(0) | , 輸出輸出x, 停機(jī)停機(jī); 否則轉(zhuǎn)否則轉(zhuǎn) (5) ; (5) 若若kN, 則置則置k k+1, xi xi(0) ( i = 1, 2, , n), 轉(zhuǎn)轉(zhuǎn) (3) ; 否則否則, 輸出失敗信息輸出失敗信息, 停機(jī)停機(jī). 定理定理1 1 迭代法迭代法 (2.4.4) 收斂的充分必要條件是迭代矩陣的收斂的充分必要條件是迭代矩陣的譜半徑譜半徑(B) 1.收斂定理收斂定理 定理定理2 若若 |B| 1, 則對(duì)于迭代格式則對(duì)于迭代格式 x(k+1) = B x(k) + f , k = 0, 1, 2, , 有有*( )( )(1)|1 |kkkBxxxxB (2.4.5) *( )(1)(0)|1|kBxxxxB (2.4.6) 其中其中x*為方程組為方程組 Ax = b 的精確解的精確解. | | 為矩陣的算子范數(shù)為矩陣的算子范數(shù),有有 111|max|,|max|,nijjinijijBbBb 2,|Fiji jBb 定理定理3 若若A x = b的系數(shù)矩陣的系數(shù)矩陣A為為嚴(yán)格對(duì)角占優(yōu)嚴(yán)格對(duì)角