第2章 計算方法

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

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

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

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

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

6、生產(chǎn)中允許參數(shù)有一定誤差，由此將零件分成生產(chǎn)中允許參數(shù)有一定誤差，由此將零件分成 A，B，C 三個等級，等級由相對誤差限決定，三個等級，等級由相對誤差限決定，A等為等為1%，B 等為等為5%，C 等為等為10%. 試確定三個等級的零試確定三個等級的零件參數(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ù)相對誤差限定義根據(jù)相對誤差限定義將三個相對誤差限分別代入，得將三個相對誤差限分別代入，得|rxxx 有有 )1 ()1 (rrxxx例例2

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

8、是某一位上的絕對誤差限是某一位上的半個單位的半個單位，該位到，該位到 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，兩個數(shù)可表示為兩個數(shù)可表示為 0. 3120710 2 ，0. 293704810 3 注注: 浮點數(shù)在計算機程序中常用浮點數(shù)在計算機程序中常用 em 代替

9、代替 10m 。 實數(shù)的實數(shù)的浮點表示法浮點表示法: 0.a1a2an 10m 其中第一部分其中第一部分0.a1a2an是是尾數(shù)部尾數(shù)部 且a1非零非零,第二部分第二部分10m是是定位部定位部，用來確定小數(shù)點的位置用來確定小數(shù)點的位置. 例如例如 0. 31207e 2 ，0. 2937048e + 3表示規(guī)格化浮點數(shù)表示規(guī)格化浮點數(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ī)格化浮點數(shù)規(guī)格化浮點數(shù)形式形式 x = 0.a1a2an 10m （2.1.1）其中，其中，a1，a2，an 都是都是0 9 中的任一整數(shù)，中的任一整數(shù)，且且 a1 0. 若若 x 的絕對誤差滿足：的絕對誤差滿足： （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ù)，其表達式為式（達式為式（2.

11、1.1）. 則它的則它的相對誤差滿足相對誤差滿足 （2.1.3）反之，若近似數(shù)反之，若近似數(shù) x 的相的相對誤差滿足對誤差滿足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ù)近似值的相對誤差之間關(guān)系相對誤差之間關(guān)系. 根據(jù)式（根據(jù)式（2.1.3），由于），由于a11，可知，一個具有可知，一個具有 n 位有效數(shù)字的近似數(shù)位有效數(shù)字的近似數(shù) x，其相對，其相對誤差滿足誤差滿足 這

12、說明，這說明，有效數(shù)位數(shù)與相對誤差的階碼相對應(yīng)有效數(shù)位數(shù)與相對誤差的階碼相對應(yīng)， x 的有效數(shù)字位數(shù)越多，相對誤差越小的有效數(shù)字位數(shù)越多，相對誤差越小. nrxe105)(因此，要使相對誤差限不超過因此，要使相對誤差限不超過0.1%，只須不等式，只須不等式 10 n 0. 001 成立即可成立即可. 此時，取此時，取 n=3 即可即可. 故當(dāng)故當(dāng) x 取取 3 位有效數(shù)字位有效數(shù)字.例例3 要使要使 的近似值的近似值 x 的相對誤差限不超過的相對誤差限不超過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ù)字時，有30151010( )nnrexa 四、函數(shù)計算的誤差估計四、函數(shù)計算的誤差估計設(shè)一元函數(shù)設(shè)一元函數(shù) y= f(x)，自變量準(zhǔn)確值為，自變量準(zhǔn)確值為 x*，對應(yīng)的函，對應(yīng)的函數(shù)準(zhǔn)確值為數(shù)準(zhǔn)確值為 y*= f(x*)，自變量近似值，自變量近似值 x 的誤差為的誤差為 e(x)，誤差限為，誤差限為 (x)，函數(shù)近似值的誤差為，函數(shù)近似值的誤差為 e(y)，誤，誤差限為差限為 (y). 利用一元函數(shù)全微分，得利用一元函數(shù)全微分，得| |( )|yyfxxx 由此得函數(shù)計算誤差估計由此得函數(shù)計算誤

14、差估計()|() |()yfxx 當(dāng)當(dāng) y0 ，x0 時，有相對誤差估計時，有相對誤差估計|( )|( )( )|( )|rrxfxyxf x 五、算術(shù)運算的誤差估計五、算術(shù)運算的誤差估計 設(shè)兩個近似數(shù)設(shè)兩個近似數(shù) x1與與x2 的誤差限分別為的誤差限分別為 和和 ，則，則對這兩個數(shù)的加、減、乘、除運算，可以利用對這兩個數(shù)的加、減、乘、除運算，可以利用多元函數(shù)的誤多元函數(shù)的誤差估計差估計，得，得)(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 已測得某場地長和寬分別為已測得某場地長和寬分別為 x= 110m，y= 80m，已知已知 試求該場地面積的絕試求該場地面積的絕對誤差限和相對誤差限對誤差限和相對誤差限. 相對誤差限相對誤差限解解: 因面積因面積 S = xy ， ，故絕對誤差限，故絕對誤差限SSyxxy ，( ) | ( ) | ( )SSSxyxy = 800. 2 + 1100. 1= 27 （m2） 1108027|)(|)()(xySSSSr= 0. 0031= 0. 31%0 20 1( )=

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

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

19、運行時間，而且使誤差積累小. 5選用數(shù)值穩(wěn)定性好的算法選用數(shù)值穩(wěn)定性好的算法 對同一個數(shù)學(xué)問題，即使在數(shù)學(xué)公式已經(jīng)確定的對同一個數(shù)學(xué)問題，即使在數(shù)學(xué)公式已經(jīng)確定的情況下，仍然可以設(shè)計出不同的算法情況下，仍然可以設(shè)計出不同的算法. 而不同的算法而不同的算法在執(zhí)行過程中對數(shù)據(jù)誤差的影響不一樣，在執(zhí)行過程中對數(shù)據(jù)誤差的影響不一樣，舍入誤差舍入誤差對計算結(jié)果影響不大的算法被稱為對計算結(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ù)值方法 非線性方程的求解問題是科學(xué)與工程計算中常非線性方程的求解問題是科學(xué)與工程計算中常見的問題之一見的問題之一. 但對高于但對高于4次的代數(shù)方程，不存在次的代數(shù)方程，不存在通用的求根公式，而對超越方程一般很難直接求通用的求根公式，而對超越方程一般很難直接求出其準(zhǔn)確解出其準(zhǔn)確解. 所以，數(shù)值方法就是非常實用和有效的方法所以，數(shù)值方法就是非常實用和有效的方法. 其其中，中，迭代迭代技術(shù)是一種常用技術(shù)技術(shù)是一種常用技術(shù). 其思想其思想是對根的是對根的逐逐次逼近次逼近.一般地，若用計算機求解非解線性方程有下列兩步一般地，若用計算機求解非解線性方程有下列兩步:第一步

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

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

23、(a + b )/22. 計算計算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. 此時區(qū)間此時區(qū)間 a1，b1的長度是的長度是a，b的一半的一半,將其作將其作為新的為新的a，b區(qū)間，重復(fù)區(qū)間，重復(fù) 1-3 直到找到根或找到滿直到找到根或找到滿足精度要求的近似根足精度要求的近似根(隔根區(qū)間充分小時隔根區(qū)間充分小時). 說明說明 二分法計算過程中，設(shè)第二分法計算過程中，設(shè)第n區(qū)間為區(qū)間為an，bn，則，

24、則(1) bn an= (b a)/ 2n (2) n充分大時，可取充分大時，可取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使對任意的使對任意的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，計算，計算 y1 f(a)，y2 f(b)；第二步：第二步：計算計算 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)的一個根，要求內(nèi)的一個根，要求 誤差不超過誤差不超過 1/250)2sin(xex 所以

26、所以 f(x) 在區(qū)間在區(qū)間 0，1 上恰有一個根上恰有一個根. 計算結(jié)果如下表計算結(jié)果如下表. 解解: 令令)2sin()(xexfx, 計算得計算得(0)10,(1)0.63210,( )cos()022xxfffxe 取取 x4= 0.5 (0.4375 + 0.5) = 0.4688 作為作為 x* 的近似的近似值值. 誤差不超過誤差不超過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*的一個近似值，則的一個近似值，則 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迭代公式迭代公式 這就是這就是, 被稱為牛頓迭代法的計算格式被稱為牛頓迭代法的計算格式. 選一個選一個初始點初始點 x0，由迭代公式便可得到迭代序列，由迭代公式便可得到迭代序列 x0，x1，xn，.例例3 用牛頓迭代法計算用牛頓迭代法計算 7 的平方根，記錄并分析計的平方根，記錄并分析計算過程中數(shù)據(jù)變化規(guī)律算過程中數(shù)據(jù)變化規(guī)律. 解解 設(shè)設(shè) ，得方程，得方程 x2 7 =

29、0. 利用牛頓迭代利用牛頓迭代法，得計算格式法，得計算格式7 xn= 0，1， 117()2nnnxxx， 取初始值為取初始值為 x0 = 2.5，迭代計算的數(shù)據(jù)結(jié)果見下表，迭代計算的數(shù)據(jù)結(jié)果見下表 由此可見，第五次迭代和第四次迭代數(shù)據(jù)的由此可見，第五次迭代和第四次迭代數(shù)據(jù)的15位數(shù)完位數(shù)完全相同，說明數(shù)據(jù)全相同，說明數(shù)據(jù)2.64575131106459 準(zhǔn)確到小數(shù)點后準(zhǔn)確到小數(shù)點后14位位. 而得到這樣的精度的數(shù)據(jù)只有而得到這樣的精度的數(shù)據(jù)只有4次迭代次迭代.對于牛頓迭代法對于牛頓迭代法, 迭代函數(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 ，則對充分靠近的初始值，則對充分靠近的初始值x0，牛頓，牛頓迭代法產(chǎn)生的序列迭代法產(chǎn)生的序列xn至少至少平方收斂平方收斂于于x*. 牛頓迭代法的缺陷牛頓迭代法的缺陷: 1. 可能發(fā)生被零除錯誤可能發(fā)生被零除錯誤 當(dāng)函數(shù)在它的零點附近，導(dǎo)函數(shù)的絕對值非常當(dāng)函數(shù)在它的零點附近，導(dǎo)函

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

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

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*. 收斂性要求初始點要取得合適，否則會導(dǎo)致錯誤結(jié)果收斂性要求初始

34、點要取得合適，否則會導(dǎo)致錯誤結(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時，有時，有 xn+1a，b. 注記如下：注記如下：如果如果 f(x) 的二階導(dǎo)數(shù)的二階導(dǎo)數(shù)大于零，則函數(shù)圖形大于零，則函數(shù)圖形是下凸曲線，根據(jù)條是下凸曲線，根據(jù)條件（件（3），應(yīng)取牛頓迭），應(yīng)取牛頓迭代 的 初 始 點 使 得代 的

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

36、為矩陣形式寫為矩陣形式 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ù)值解法分為和和迭代法迭代法兩兩類類. 直接法在沒有舍入誤差的情況下直接法在沒有舍入誤差的情況下, 通過有限步計通過有限步計算求得方程組的準(zhǔn)確解算求得方程組的準(zhǔn)確解. 對于中、小

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

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

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

40、陣和右端向量; 回代過程所用的乘除法次數(shù)總共為回代過程所用的乘除法次數(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二、高斯消元過程二、高斯消元過程基本思想基本思想 對方程組的增廣矩陣做行初等變換使其為對方程組的增廣矩陣做行初等變換使其為上上三角形方程組三角形方程組, 再再回代回代求出方程組的解求出方程組的解.例例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 說明說明: 對于方程組對于方程組 (2.3.1), 將其轉(zhuǎn)化為等價的上三角將其轉(zhuǎn)化為等價的上三角形方程組的過程稱為形方程組的過程稱為消元過程消元過程. 算法算法2 (消元過程的算法消元過程的算法)設(shè)方程組設(shè)方程組 (2.3.1) 的增廣矩陣為的增廣矩陣為111211212222124 nnnnnnaaabaaabaaabA b第一步：輸入第一步：輸入 A=(aij)nn 和和 b=b1, , bnT, k0; 第二步：第二步：kk+1, i k; 第三步：第三步：ii+1, 計算計算 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)第五步; 隨著計算技術(shù)的發(fā)展隨著計算技術(shù)的發(fā)展, 計算機的存儲量日益增大計算機的存儲量日益增大, 計算計算速度也迅速提高速度也迅速提高, 在計算機上可以求解的線性方程的在計算機上可以求解的線性方程的規(guī)模也越來越大規(guī)模也越來越大, 在實際應(yīng)用中在

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

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

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

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

48、據(jù)進行第二次迭代為輸入數(shù)據(jù)進行第二次迭代, 其結(jié)果為表中第其結(jié)果為表中第二列數(shù)據(jù)二列數(shù)據(jù), 記為記為 x(2) ; . 當(dāng)當(dāng) k = 4時時, 得近似解得近似解 x(4) = 0.9987, 0.9988, 0.9991T. 2. 由上可知由上可知, 對給定的方程組對給定的方程組, 迭代法是利用迭代格式迭迭代法是利用迭代格式迭代計算出向量序列代計算出向量序列 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 ) 可以寫成如下形式可以寫成如下形式:設(shè)設(shè) aii 0 ( i = 1, 2, , n), 由第由第i個方程解出個方程解出xi ( i = 1, 2, , n), 得到與原方程組等價的方程組得到與原方程組等價的方程組( 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中主對角元分裂中主對角元分裂, 設(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) 計算計算 ( i = 1, 2, , n); (0)11iiijjjiixba xa (4) 若若| x x(0) | , 輸出輸出x, 停機停機; 否則轉(zhuǎn)否則轉(zhuǎn) (5) ; (5) 若若 kN, 則則 k k+1, xi (0) xi ( i = 1, 2, , n), 轉(zhuǎn)轉(zhuǎn) (3) ; 否則否則, 輸出失敗信息輸出失敗信息, 停機停機. 高斯高斯-賽德爾賽德爾 (Gauss-Seidel) 迭代法迭代法引入引入 將例將例1中的方程組及迭代格式中的方程組及迭代格式 (2.4.1) 做如下修改：做如下修改：盡量利用最新計算數(shù)據(jù)盡量利用最新計算數(shù)據(jù), 如計算如計

53、算 時時, 由于已算出由于已算出 , 所以用所以用 , 而不用而不用 , 則迭代格式則迭代格式 (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時時, 滿足滿足 =5.557810 4. 43( )( )|xx 說明說明: 1. 我們稱迭代格式我們稱迭代格式 (2.4.3) 為解為解Ax = b的的高

54、斯高斯-賽德賽德爾爾 (Gauss-Seidel) 迭代法迭代法. 2. 對一般對一般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 )可改寫為可改寫為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迭代矩陣迭代矩陣. 計算實踐表明計算實踐表明, 對許多問題對許多問題 Gaus

56、s-Seidel 迭代法迭代法確實比確實比 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) 計算計算 ( i = 2, , n 1 )(0)11121jjjnxba xa 1(0)111iniiijjij

57、jjj iiixba xa xa 111;nnnijjnnxba xa (4) 若若| x x(0) | , 輸出輸出x, 停機停機; 否則轉(zhuǎn)否則轉(zhuǎn) (5) ; (5) 若若kN, 則置則置k k+1, xi xi(0) ( i = 1, 2, , n), 轉(zhuǎn)轉(zhuǎn) (3) ; 否則否則, 輸出失敗信息輸出失敗信息, 停機停機. 定理定理1 1 迭代法迭代法 (2.4.4) 收斂的充分必要條件是迭代矩陣的收斂的充分必要條件是迭代矩陣的譜半徑譜半徑(B) 1.收斂定理收斂定理 定理定理2 若若 |B| 1, 則對于迭代格式則對于迭代格式 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)格對角占優(yōu)嚴(yán)格對角