第2章線(xiàn)性方程組求解的數(shù)值方法課件

第二章線(xiàn)性方程組求解的數(shù)值方法1.高斯消元法2.矩陣分解法3.向量范數(shù)與矩陣范數(shù)4.迭代法求解5.方程組的病態(tài)問(wèn)題與誤差分析主要內(nèi)容：第二章線(xiàn)性方程組求解的數(shù)值方法1.高斯消元法主要內(nèi)容：第二章線(xiàn)性方程組求解的數(shù)值方法理解各種線(xiàn)性方程組數(shù)值求解；掌握求解方法和解的誤差分析方法；能編程實(shí)現(xiàn)求解算法。 特別強(qiáng)調(diào)：遇到問(wèn)題養(yǎng)成用計(jì)算機(jī)編程求解的習(xí)慣，不要習(xí)慣性的用筆算，而這是國(guó)內(nèi)外學(xué)生的一個(gè)主要差距。教學(xué)要求：第二章線(xiàn)性方程組求解的數(shù)值方法理解各種線(xiàn)性方程組數(shù)值求解；在自然科學(xué)和工程技術(shù)中，有很多問(wèn)題的解決都需要用到線(xiàn)性方程組的求解。因此，求解線(xiàn)性方程組的問(wèn)題是一個(gè)在科學(xué)技術(shù)中常見(jiàn)的普遍問(wèn)題。解線(xiàn)性方程組的數(shù)值解法：有直接法和迭代法兩類(lèi)。直接法：計(jì)算過(guò)程沒(méi)有舍入誤差，經(jīng)過(guò)有限次四則運(yùn)算可求得方程組得精確解。（實(shí)際計(jì)算有舍入誤差）高斯消元法，矩陣分解法迭代法：核心是迭代求解的收斂條件和收斂速度。雅可比（Jacobi）迭代，高斯-賽德?tīng)枺℅auss-Seidel）迭代在自然科學(xué)和工程技術(shù)中，有很多問(wèn)題的解決都需要用到線(xiàn)基本思想方法：由行初等變換將系數(shù)矩陣約化為三角矩陣；用回代的方法求解方程組。例1

用消去法（高斯消元法）解方程組高斯消元法是求解方程組的古典方法。(2.1)§3.1高斯消元法基本思想方法：由行初等變換將系數(shù)矩陣約化為三角例1用消去結(jié)論：整個(gè)計(jì)算過(guò)程可分為兩部分：（1）消元：把原方程組轉(zhuǎn)化為系數(shù)矩陣為上三角矩陣的方程組；（2）回代：由系數(shù)矩陣為上三角矩陣的方程組求解（2）回代求解，得：解：（1）消元：結(jié)論：整個(gè)計(jì)算過(guò)程可分為兩部分：（2）回代求解，得：解：（1對(duì)于一般情形：n階線(xiàn)性方程組的高斯消元法對(duì)于一般情形：n階線(xiàn)性方程組的高斯消元法若記增廣矩陣（2.2）若記增廣矩陣（2.2）（1）第1步(k=1)，一般形式的高斯消元法：設(shè)，首先對(duì)行計(jì)算乘數(shù)對(duì)增廣矩陣

進(jìn)行行初等變換：(即用乘以2.2式的第1個(gè)方程，加到第i個(gè)方程上，消去2.2式的第二個(gè)方程直到第n個(gè)方程中的未知數(shù))(代表第i行)（1）第1步(k=1)，一般形式的高斯消元法：設(shè)得到與原方程組等價(jià)的方程組。記為（2）一般第k步消元()設(shè)已完成上述消元過(guò)程第1步，第2步，…，第k-1步，且

得到與原方程組等價(jià)的方程組其中：設(shè)，計(jì)算乘數(shù)其中：設(shè)，計(jì)算乘數(shù)(即用乘以2.2式的第k個(gè)方程，加到第i個(gè)方程上，消去2.2式的第k+1個(gè)方程直到第n個(gè)方程中的未知數(shù))那么第k步消元操作即：(3)繼續(xù)這一過(guò)程，直到完成第n-1次消元，最后我們得到與原方程組等價(jià)的三角形方程組(2.3)消元過(guò)程結(jié)束(即用乘以2.2式的第k個(gè)方程，加到第i個(gè)方求解三角形方程組2.3，得到求解公式這個(gè)過(guò)程稱(chēng)為回代過(guò)程。求解三角形方程組2.3，得到求解公式這個(gè)過(guò)程稱(chēng)為回代過(guò)程。例題：考慮方程組Gauss消去法中每步用來(lái)消去其他元素的

稱(chēng)為該步的主元素。Gauss消去法作為數(shù)值方法，主元素的選擇是否會(huì)影響計(jì)算的結(jié)果呢？則該方程的精確解為而采用(，1)作為主元素，利用高斯消去法得到的解為顯然結(jié)果是錯(cuò)誤的。例題：考慮方程組Gauss消去法中每步用來(lái)消去

錯(cuò)誤在哪個(gè)地方呢？原因是我們?cè)谙獣r(shí)，利用了小主元，使得約化后的方程組元素?cái)?shù)量級(jí)大大增長(zhǎng)，再經(jīng)舍入，而計(jì)算機(jī)的有效位數(shù)有限，造成消元后的三角形方程組就不準(zhǔn)確了。

結(jié)論：在消元過(guò)程中可能出現(xiàn)主元素為零的情況，這時(shí)消去法將無(wú)法進(jìn)行；即使不為零，在主元素很小時(shí)，用其做除數(shù)，也會(huì)導(dǎo)致其他元素?cái)?shù)量級(jí)的嚴(yán)重增長(zhǎng)和舍入誤差的擴(kuò)散，最后也使得計(jì)算解不可靠。

解決方法：對(duì)一般的矩陣來(lái)說(shuō)，最好每一步選取系數(shù)矩陣（或消元后的低階矩陣）的該列中絕對(duì)值最大的元素作為主元素，以使高斯消去法具有較好的數(shù)字穩(wěn)定性。(高斯列主元素消去法)錯(cuò)誤在哪個(gè)地方呢？結(jié)論：在消元過(guò)程中可能出現(xiàn)主元素為零的1.列主元法第一列中絕對(duì)值最大是10，取10為主元n階方程組第k輪消元時(shí)，選第k列的后(n-k+1)個(gè)元素中絕對(duì)值最大作主元。1.列主元法第一列中絕對(duì)值最大是10，取10為主元n階方程x3=6.2/6.2=1x2=(2.5-5x3)/2.5=-1x1=(7+7x2-0x3)/10=0x1=0x2=-1x3=1第二列的后兩個(gè)數(shù)中選出主元2.5x3=6.2/6.2=1x2=(2.5-5x3)/2.5=-2完全主元素消去法整個(gè)矩陣中絕對(duì)值最大是10，取10為主元n階方程組第k輪消元時(shí)，選消元后元素中絕對(duì)值最大作主元。2完全主元素消去法整個(gè)矩陣中絕對(duì)值最大是10，取10為主元x1=0x2=-1x3=1方框中6最大，交換行列，交換列的時(shí)候要做記錄（即x3和x2交換了位置）：x1=0方框中6最大，交換行列，交換列的時(shí)候要做記錄（即x3完全主元素消除法與列主元素消除法的優(yōu)缺點(diǎn)比較：優(yōu)點(diǎn)：數(shù)值更加穩(wěn)定；缺點(diǎn)：計(jì)算量大；完全主元素消除法與列主元素消除法的優(yōu)缺點(diǎn)比較：優(yōu)點(diǎn)：對(duì)矩陣A實(shí)行初等行變換相當(dāng)于用初等矩陣左乘A，于是對(duì)(2.2)做第一次消元后，化為化為，即，其中

§3.1

矩陣的三角分解LU分解對(duì)矩陣A實(shí)行初等行變換相當(dāng)于用初等矩陣左乘A，于第k步的初等矩陣為并且重復(fù)這一過(guò)程，最后得到將上三角矩陣記為U，則第k步的初等矩陣為并且重復(fù)這一過(guò)程，最后得到將上三角矩陣將上三角矩陣記為U，則，其中則，L為單位下三角矩陣。高斯消去法實(shí)質(zhì)上是產(chǎn)生了一個(gè)將A分解為兩個(gè)三角形矩陣相乘的因式分解。如果A是非奇異陣，則LU分解是唯一的，否則分解不唯一。將上三角矩陣記為U，則消元法：消元法與三角分解法間的關(guān)系：

三角分解法：討論消元法：消元法與三角分解法間的關(guān)系：三角分解法：討論直接三角分解法解線(xiàn)性方程組（）的具體流程：1.2.計(jì)算U的第r行，L的第r列元素r=2,3,…,n3.(一)LU分解直接三角分解法解線(xiàn)性方程組（）的再求解Ly=b,Ux=y計(jì)算公式：(二)x的計(jì)算再求解Ly=b,Ux=y計(jì)算公式：(二)x的計(jì)算例

用直接三角分解法解方程組

解:(一)矩陣LU分解(1)故：例用直接三角分解法解方程組(2)經(jīng)計(jì)算：(2)經(jīng)計(jì)算：(二)求解x：從而(二)求解x：從而§3.2矩陣的Cholesky分解對(duì)稱(chēng)正定矩陣A：AT=A,A的各階順序主子式大于零.前面指出非奇異的矩陣可以有三角分解，當(dāng)A是某些特殊矩陣時(shí)，它的LU分解會(huì)有更加簡(jiǎn)潔的形式。A的LU分解(2.4)§3.2矩陣的Cholesky分解對(duì)稱(chēng)正定矩陣A：uii

>0(i=1,···,n)由于A是對(duì)稱(chēng)正定的，則有將U進(jìn)一步分解：uii>0(i=1,···,n)由于A是對(duì)稱(chēng)正定的，則根據(jù)A的對(duì)稱(chēng)性：故：由分解的唯一性知：故：其中P為上三角矩陣，這種對(duì)稱(chēng)正定矩陣的分解稱(chēng)為Cholesky分解。在Matlab中函數(shù)“chol”給出對(duì)稱(chēng)正定矩陣的Cholesky分解。根據(jù)A的對(duì)稱(chēng)性：故：由分解的唯一性知：故：其中P為上三角矩陣經(jīng)過(guò)n步可直接求得思路:(1)分解對(duì)稱(chēng)正定矩陣設(shè)n階對(duì)稱(chēng)正定矩陣A有分解,先用待定系數(shù)法求L的元素Cholesky分解的具體步驟(平方根法)：(2)分解求解方程組經(jīng)過(guò)n步可直接求得思路:設(shè)n階對(duì)稱(chēng)正定矩陣A有分解Cholesky方法具體計(jì)算公式：分解計(jì)算：

求解：

Cholesky方法具體計(jì)算公式：分解計(jì)算：求解：§

3.3向量范數(shù)與矩陣范數(shù)向量、矩陣與線(xiàn)性方程組有著密切的關(guān)系，向量、矩陣范數(shù)是解方程組以及研究與探討方程組本身性質(zhì)的工具。一、向量范數(shù)的定義定義范數(shù)為其中的，最常用的范數(shù)是，以及§3.3向量范數(shù)與矩陣范數(shù)向量、矩陣與線(xiàn)性方程組有著密切容易證明向量范數(shù)滿(mǎn)足如下性質(zhì)：(1)如果，則；而且，當(dāng)且僅當(dāng)(2)對(duì)任何的數(shù)c，都有(3)范數(shù)也稱(chēng)為2-范數(shù)或Euclidean函數(shù)；范數(shù)也稱(chēng)為-范數(shù)或一致范數(shù)。在Matlab中用函數(shù)用來(lái)計(jì)算向量x的范數(shù)。由性質(zhì)(3),還容易得到：容易證明向量范數(shù)滿(mǎn)足如下性質(zhì)：范數(shù)也稱(chēng)為2-范數(shù)或二矩陣范數(shù)的定義在向量范數(shù)的基礎(chǔ)上可以進(jìn)一步定義矩陣范數(shù)如果上式中的向量范數(shù)取為范數(shù)，則可以證明定義出的矩陣范數(shù)（稱(chēng)為矩陣范數(shù)或者列范數(shù)）為如果向量范數(shù)取為2-范數(shù)，則其中（模），稱(chēng)為矩陣B的譜半徑。(為B的任意特征值。)二矩陣范數(shù)的定義在向量范數(shù)的基礎(chǔ)上可以進(jìn)一步定義矩陣范數(shù)類(lèi)似地，Matlab函數(shù)norm(A,p)給出矩陣p=1,2或范數(shù)

如果向量范數(shù)取為，則可以證明定義出的矩陣范數(shù)（稱(chēng)為矩陣的范數(shù)或者行范數(shù)）為

容易證明矩陣范數(shù)滿(mǎn)足如下性質(zhì)：(1)如果，則；而且，而且僅當(dāng)(2)對(duì)任何的數(shù)

，

(3)

(4)而且由矩陣范數(shù)的定義還有稱(chēng)之為矩陣范數(shù)與相應(yīng)的向量范數(shù)是相容的。類(lèi)似地，Matlab函數(shù)norm(A,p)給出矩陣p38§3.4古典迭代法的構(gòu)造求解線(xiàn)性代數(shù)方程組的方法中小規(guī)模問(wèn)題直接法迭代法

大規(guī)模，超大規(guī)模問(wèn)題

古典方法現(xiàn)代方法38§3.4古典迭代法的構(gòu)造求解線(xiàn)性代數(shù)方程組的方法中39線(xiàn)性方程組的一般形式為：如果是非奇異的，則上式有唯一解。我們將通過(guò)一個(gè)具體線(xiàn)性方程組的例子來(lái)講解迭代法。?。杭淳€(xiàn)性方程組為：方程的精確解(直接法計(jì)算)39線(xiàn)性方程組的一般形式為：如果是非奇異的，則40如果對(duì)該方程組進(jìn)行變形，將變量分別從三個(gè)方程中分離出來(lái)：(1)令初值40如果對(duì)該方程組進(jìn)行變形，將變量所以(1)式可以表示為迭代形式：所以我們可以得到一個(gè)向量的序列，只要該序列當(dāng)時(shí)有極限，那么這個(gè)極限就是該線(xiàn)性方程組的解。上面這種迭代求解線(xiàn)性方程組的方法稱(chēng)為Jacobi迭代法。所以(1)式可以表示為迭代形式：所以我們可以得到一個(gè)向量的序考慮線(xiàn)性方程組的一般形式：其中矩陣A為n×n階方陣，則方程的分量形式為：改寫(xiě)成：考慮線(xiàn)性方程組的一般形式：其中矩陣A為n×n階方陣，則方程的從而得到迭代公式：上面式子就是一般形式的Jacobi迭代法，也可也記做：從而得到迭代公式：上面式子就是一般形式的Jacobi迭代法，在Jacobi迭代法中充分利用新值，可得到下面迭代：上面這種迭代方法也叫做Gauss-Seidel迭代，也可以記為：在Jacobi迭代法中充分利用新值，可得到下面迭代：上面這種方程組的精確解為x*=(1,1,1)T.解Jacobi迭代法計(jì)算公式為取初始向量x(0)=(0,0,0)T,迭代可得例1：利用Jacobi法和Gauss-Seidel法求解線(xiàn)性方程組方程組的精確解為x*=(1,1,1)T.解Jackx1(k)x2(k)x3(k)‖x(k)-x*‖0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636可見(jiàn),迭代序列逐次收斂于方程組的解,而且迭代7次得到精確到小數(shù)點(diǎn)后兩位的近似解.計(jì)算結(jié)果列表如下:kx1(k)x2(k)x3(k)‖x(k)-x*‖0000Gauss-Seidel迭代法的計(jì)算公式為:同樣取初始向量x(0)=(0,0,0)T,計(jì)算結(jié)果為

由計(jì)算結(jié)果可見(jiàn),Gauss-Seidel迭代法收斂較快.取精確到小數(shù)點(diǎn)后兩位的近似解,Gauss-Seidel迭代法只需迭代3次,而Jacobi迭代法需要迭代7次.kx1(k)x2(k)x3(k)‖x(k)-x*‖012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956Gauss-Seidel迭代法的計(jì)算公式為:同樣取初始向量x為了進(jìn)一步研究,從矩陣角度來(lái)討論上述迭代法.

對(duì)線(xiàn)性方程組Ax=b,記D=diag(a11,a22,…,ann)則有A=D-L-U于是線(xiàn)性方程組Ax=b可寫(xiě)成

(D-L-U)x=b等價(jià)于

Dx=(L+U)x+b或x=D-1(L+U)x+D-1b

為了進(jìn)一步研究,從矩陣角度來(lái)討論上述迭代法.對(duì)線(xiàn)性方程組由此建立Jacobi迭代法迭代公式

x(k+1)=D-1(L+U)x(k)+D-1bk=0,1,2,…或?qū)懗?/p>

x(k+1)=Bx(k)+fk=0,1,2,…其中由此建立Jacobi迭代法迭代公式或?qū)懗善渲兴訥auss-Seidel迭代法可以寫(xiě)成其中Gauss-Seidel迭代法迭代公式為寫(xiě)成矩陣形式為：所以Gauss-Seidel迭代法可以寫(xiě)成其中Gauss-S§3.5迭代法的分析構(gòu)造迭代法的途徑可以有很多，那么是不是所有的方法都能收斂呢？收斂速度的快慢與什么有關(guān)系呢？它的精確解為例：§3.5迭代法的分析構(gòu)造迭代法的途徑kx1(k)x2(k)x3(k)‖x(k)-x*‖0123401416.792.8168104.7-41.4-52.4-254.30-1.74.56-151-238.211342.41521680可見(jiàn),并不是所有的方程組都收斂，即使收斂對(duì)于不同的方法(例如Jacobi與Gauss-Seidel)收斂速度也是不同的.計(jì)算結(jié)果列表如下:kx1(k)x2(k)x3(k)‖x(k)-x*‖0000設(shè)是矩陣B任意一個(gè)特征值，是相應(yīng)的特征向量，即再假設(shè)為任意的向量范數(shù)及與之相融的矩陣范數(shù)，則有：首先引入幾個(gè)定義、引理：所以對(duì)矩陣B任意一個(gè)特征值，都有記，稱(chēng)之為矩陣B的譜半徑，則設(shè)是矩陣B任意一個(gè)特征值，先引入兩個(gè)引理（詳細(xì)證明見(jiàn)附錄）：引理3.1矩陣，則的充分必要條件是引理3.2矩陣，若，則是非奇異的。先引入兩個(gè)引理（詳細(xì)證明見(jiàn)附錄）：引理3.1矩陣

定理3.1

對(duì)任意的和任意的初始向量，迭代法收斂的充分必要條件是證明：必要性設(shè)迭代法產(chǎn)生的序列收斂，記是該序列的極限點(diǎn)，所以滿(mǎn)足又由迭代關(guān)系，可以得到定理3.1對(duì)任意的由的任意性，知：由引理3.1知：充分性由及引理2知（即）有唯一解，記為類(lèi)似于必要性的證明，得到再由第一步知，故由的任意性，知：由引理3.1知定理3.1給出了迭代收斂的充要條件，但不宜計(jì)算，所以在實(shí)際使用中通常并不好用。由知，只要對(duì)某種相容的矩陣范數(shù)有那么當(dāng)然，所以這常常是實(shí)際中很有效的收斂判別準(zhǔn)則。嚴(yán)格對(duì)角占優(yōu)矩陣：考慮，設(shè)，當(dāng)時(shí)的矩陣。定理3.1給出了迭代收斂的充要條件，但定理3.2如果A是嚴(yán)格對(duì)角占優(yōu)的矩陣，則它一定非奇異。由于A是對(duì)角占優(yōu)矩陣，所以，故矩陣是可逆的?？紤]定理3.2如果A是嚴(yán)格對(duì)角占優(yōu)的矩陣，則它一定非奇異。由矩陣的范數(shù)為由A是對(duì)角占優(yōu)矩陣，得由引理3.2知是非奇異的，又由于是非奇異的，所以A是非奇異的。得證！引理3.2矩陣，若，則是非奇異的。矩陣的范數(shù)為由A是對(duì)角定理3.3系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)的線(xiàn)性代數(shù)方程組，它的Jacobi迭代法和Gauss-Seidel迭代都是收斂的。證明：Jacobi方法的迭代矩陣為由定理3.2中的證明知，嚴(yán)格對(duì)角占優(yōu)矩陣滿(mǎn)足：再由定理3.1，得Jacobi迭代法收斂。(a)Jocobi的證明<1定理3.3系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)的線(xiàn)性代數(shù)方程組再考慮Gauss-Seidel方法，其迭代矩陣為用反證法，假設(shè)Gauss-Seidel迭代不收斂，則由定理3.1知：所以存在模大于1的特征值.設(shè)有，使得行列式：(b)Gauss-Seidel的證明再考慮Gauss-Seidel方法，其迭代矩陣為用反證法，假故，只有才能使得成立。由于A是對(duì)角占優(yōu)的，所以矩陣也是對(duì)角占優(yōu)的，那么該矩陣一定非奇異，這與上面該矩陣的行列式等于0矛盾。由于可逆，所以得證！故，只有由于A是對(duì)角占優(yōu)的，所以矩陣定理3.4若迭代矩陣B滿(mǎn)足，則迭代生成的序列滿(mǎn)足收斂速度問(wèn)題其中表示精確解。證明：先證明(b),然后證明(a)定理3.4若迭代矩陣B滿(mǎn)足，則迭代而所以故，本頁(yè)第一個(gè)式子可寫(xiě)為而所以故，本頁(yè)第一個(gè)式子可寫(xiě)為由于，故(b)得證顯然對(duì)于任意的正整數(shù)p，都有那么在本頁(yè)第一個(gè)式子中反復(fù)利用上式就可以得到(a)(a)得證由于，故(b)得證顯然對(duì)于任意的正整數(shù)給出的關(guān)系可以作為計(jì)算終止的判別準(zhǔn)則。即只要和已足夠接近，表明與便已足夠靠近。定理3.4(a)給出的是迭代收斂速度的一個(gè)估計(jì)。顯然越接近0，生成序列收斂得越快。定理3.14(b)定理3.4的討論給出的關(guān)系可以作為計(jì)算終止的判別準(zhǔn)則。即只要§3.6超松弛迭代(SOR)及分塊迭代方法對(duì)于給定的迭代法，每步迭代所需的工作量是確定的。如果迭代法收斂速度緩慢，則需要比較多的迭代次數(shù)，由此導(dǎo)致算法工作量太大而失去使用價(jià)值，因此各種迭代法的加速技術(shù)具有重要意義。假設(shè)是已經(jīng)得到的迭代值，以為初值進(jìn)行一步Gauss-Seidel迭代得：§3.6超松弛迭代(SOR)及分塊迭代方法將這一迭代值與的值組合作為新一步的迭代值其中為待定的參數(shù)，寫(xiě)成矩陣形式為：這時(shí)迭代矩陣：將這一迭代值與的值組合作為新一步的迭代值其中新的迭代每步的計(jì)算代價(jià)與Gauss-Seidel方法相差無(wú)幾，如果能取得恰當(dāng)?shù)闹?，使新?gòu)造的方法比Gauss-Seidel方法收斂得更快，松弛就起到了加速的作用。在實(shí)際上真正使用的值通常的范圍為，被統(tǒng)稱(chēng)為超松弛方法，簡(jiǎn)稱(chēng)SOR(SuccessiveOver-Relaxation)方法。上面的這個(gè)方法就叫做松弛方法，它可以視為Gauss-Seidel方法的加速。顯然時(shí)，上面這個(gè)方法就是Gauss-Seidel方法。新的迭代每步的計(jì)算代價(jià)與Gauss-Seidel方法定理3.5SOR方法收斂的必要條件是：證明：假設(shè)SOR方法收斂，所以設(shè)為的特征值，則另一方面，經(jīng)過(guò)計(jì)算不難得到故，結(jié)論得證。定理3.5SOR方法收斂的必要條件是：證明：假設(shè)SOR方分塊矩陣以及分塊迭代方法在許多實(shí)際應(yīng)用中，矩陣可以寫(xiě)成如下分塊的形式：其中是階的方陣，而且據(jù)此可以構(gòu)造分塊形式的迭代法，考慮其中分塊矩陣以及分塊迭代方法在許多實(shí)際應(yīng)用中，矩陣可以寫(xiě)成如下分求解方程組，分塊的Jacobi迭代法為：分塊的Gauss-Seidel迭代法為：求解方程組，分塊的Jacobi分塊的超松弛迭代法(BSOR)為分塊的超松弛迭代法(BSOR)為§

3.7線(xiàn)性方程組的條件數(shù)對(duì)于線(xiàn)性方程組如果解x關(guān)于問(wèn)題（即矩陣A和向量b）的“微小”變化(來(lái)源可能是模型誤差或數(shù)據(jù)上的誤差，也可能是數(shù)值計(jì)算中的舍入誤差)不敏感，那么這個(gè)問(wèn)題即是一個(gè)“好”問(wèn)題，反之就是“壞”問(wèn)題或者病態(tài)的問(wèn)題。關(guān)于病態(tài)的例子，我們?cè)诘谝徽轮幸呀?jīng)包含了一個(gè)，這一章主要用范數(shù)作為工具來(lái)分析線(xiàn)性方程組的好壞。§3.7線(xiàn)性方程組的條件數(shù)對(duì)于線(xiàn)性方程組例

設(shè)有方程組已知系數(shù)測(cè)量數(shù)據(jù)待求數(shù)據(jù)其中A為，若測(cè)量數(shù)據(jù)為準(zhǔn)確數(shù)據(jù)，即，那么很容易計(jì)算如果測(cè)量數(shù)據(jù)不夠精確，即測(cè)量數(shù)據(jù)僅保留了2位有效數(shù)字，即，計(jì)算結(jié)果為例設(shè)有方程組已知系數(shù)測(cè)量數(shù)據(jù)待求數(shù)據(jù)其中A為如果測(cè)量數(shù)據(jù)和系數(shù)矩陣的數(shù)據(jù)都僅保留了2位有效數(shù)字，即，則計(jì)算結(jié)果為以上問(wèn)題稱(chēng)為病態(tài)的問(wèn)題，病態(tài)是問(wèn)題本身固有的。如果測(cè)量數(shù)據(jù)和系數(shù)矩陣的數(shù)據(jù)都僅保留了2位有效數(shù)字，即，則計(jì)(1)考慮由于右端的擾動(dòng)所引起的解的變化，已知兩式相減得利用范數(shù)關(guān)系可以得到：綜合上述兩式有：(1)考慮由于右端的擾動(dòng)所引起的解的變化，已知兩式相減得利這個(gè)式子給出了右端的擾動(dòng)可能引起解擾動(dòng)的上界，顯然越小，方程右端的變化引起解的變化就越小。(2)考慮由于矩陣A有擾動(dòng)時(shí)所引起的解的變化可以得到：其中利用了這個(gè)式子給出了右端的擾動(dòng)可能引起解擾動(dòng)的上界，顯然經(jīng)過(guò)整理可以得到(3)考慮更一般的情形所引起的解的變化假設(shè)滿(mǎn)足如下的特殊形式：又Tylor展開(kāi)，可以寫(xiě)成經(jīng)過(guò)整理可以得到(3)考慮更一般的情形所引起的解的變化假設(shè)對(duì)求導(dǎo)得令，并考慮到，則記，從而有對(duì)從上面三種情況可見(jiàn)，問(wèn)題擾動(dòng)所引起解的擾動(dòng)是被同一個(gè)因子控制的定義3.1設(shè)A為可逆矩陣，是與某種向量范數(shù)相容的矩陣范數(shù)，稱(chēng)為線(xiàn)性方程組相應(yīng)于該矩陣范數(shù)的條件數(shù)。由前面的分析可見(jiàn)，條件數(shù)大的就是病態(tài)的矩陣，反之是良態(tài)的矩陣。求解線(xiàn)性方程時(shí)了解它的條件數(shù)大小是必要的，它可以幫助你判斷所得數(shù)值解的可信性及模型的合理性。在Matlab中可以用cond（A）來(lái)計(jì)算條件數(shù)或者用rcond(A)來(lái)估計(jì)其量級(jí)的倒數(shù)。從上面三種情況可見(jiàn)，問(wèn)題擾動(dòng)所引起解的擾動(dòng)是被同一設(shè)，則，即對(duì)于該函數(shù)，誤差會(huì)被放大n倍。二、病態(tài)問(wèn)題與條件數(shù)（針對(duì)問(wèn)題本身）定義：輸入數(shù)據(jù)的微小變動(dòng)導(dǎo)致輸出數(shù)據(jù)的較大誤差，就被稱(chēng)為病態(tài)問(wèn)題。衡量是否病態(tài)的標(biāo)準(zhǔn)：條件數(shù)對(duì)于函數(shù)值計(jì)算問(wèn)題，條件數(shù)定義為：不同的問(wèn)題，條件數(shù)具體定義不同。一般情況下，條件數(shù)大于10，就認(rèn)為問(wèn)題病態(tài)。通過(guò)構(gòu)造特殊算法來(lái)解決設(shè)，則，即對(duì)于該函數(shù)，誤條件數(shù)的重要性質(zhì)：定理3.6

(a)對(duì)任意的非奇異矩陣A，cond(A)是由任意的矩陣范數(shù)定義的條件數(shù)，則(b)如果Q是正交矩陣，則對(duì)于任意的非奇異矩陣A，都有其中條件數(shù)的重要性質(zhì)：定理3.6(b)如果Q是正交證明：(a)中的各條性質(zhì)是顯然的，例如，對(duì)任意的非奇異矩陣A，有(b)由于Q是正交矩陣，所以

另外，證明：(a)中的各條性質(zhì)是顯然的，例如，對(duì)任意的非奇第二章線(xiàn)性方程組求解的數(shù)值方法1.高斯消元法2.矩陣分解法3.向量范數(shù)與矩陣范數(shù)4.迭代法求解5.方程組的病態(tài)問(wèn)題與誤差分析主要內(nèi)容：第二章線(xiàn)性方程組求解的數(shù)值方法1.高斯消元法主要內(nèi)容：第二章線(xiàn)性方程組求解的數(shù)值方法理解各種線(xiàn)性方程組數(shù)值求解；掌握求解方法和解的誤差分析方法；能編程實(shí)現(xiàn)求解算法。 特別強(qiáng)調(diào)：遇到問(wèn)題養(yǎng)成用計(jì)算機(jī)編程求解的習(xí)慣，不要習(xí)慣性的用筆算，而這是國(guó)內(nèi)外學(xué)生的一個(gè)主要差距。教學(xué)要求：第二章線(xiàn)性方程組求解的數(shù)值方法理解各種線(xiàn)性方程組數(shù)值求解；在自然科學(xué)和工程技術(shù)中，有很多問(wèn)題的解決都需要用到線(xiàn)性方程組的求解。因此，求解線(xiàn)性方程組的問(wèn)題是一個(gè)在科學(xué)技術(shù)中常見(jiàn)的普遍問(wèn)題。解線(xiàn)性方程組的數(shù)值解法：有直接法和迭代法兩類(lèi)。直接法：計(jì)算過(guò)程沒(méi)有舍入誤差，經(jīng)過(guò)有限次四則運(yùn)算可求得方程組得精確解。（實(shí)際計(jì)算有舍入誤差）高斯消元法，矩陣分解法迭代法：核心是迭代求解的收斂條件和收斂速度。雅可比（Jacobi）迭代，高斯-賽德?tīng)枺℅auss-Seidel）迭代在自然科學(xué)和工程技術(shù)中，有很多問(wèn)題的解決都需要用到線(xiàn)基本思想方法：由行初等變換將系數(shù)矩陣約化為三角矩陣；用回代的方法求解方程組。例1

用消去法（高斯消元法）解方程組高斯消元法是求解方程組的古典方法。(2.1)§3.1高斯消元法基本思想方法：由行初等變換將系數(shù)矩陣約化為三角例1用消去結(jié)論：整個(gè)計(jì)算過(guò)程可分為兩部分：（1）消元：把原方程組轉(zhuǎn)化為系數(shù)矩陣為上三角矩陣的方程組；（2）回代：由系數(shù)矩陣為上三角矩陣的方程組求解（2）回代求解，得：解：（1）消元：結(jié)論：整個(gè)計(jì)算過(guò)程可分為兩部分：（2）回代求解，得：解：（1對(duì)于一般情形：n階線(xiàn)性方程組的高斯消元法對(duì)于一般情形：n階線(xiàn)性方程組的高斯消元法若記增廣矩陣（2.2）若記增廣矩陣（2.2）（1）第1步(k=1)，一般形式的高斯消元法：設(shè)，首先對(duì)行計(jì)算乘數(shù)對(duì)增廣矩陣

進(jìn)行行初等變換：(即用乘以2.2式的第1個(gè)方程，加到第i個(gè)方程上，消去2.2式的第二個(gè)方程直到第n個(gè)方程中的未知數(shù))(代表第i行)（1）第1步(k=1)，一般形式的高斯消元法：設(shè)得到與原方程組等價(jià)的方程組。記為（2）一般第k步消元()設(shè)已完成上述消元過(guò)程第1步，第2步，…，第k-1步，且

得到與原方程組等價(jià)的方程組其中：設(shè)，計(jì)算乘數(shù)其中：設(shè)，計(jì)算乘數(shù)(即用乘以2.2式的第k個(gè)方程，加到第i個(gè)方程上，消去2.2式的第k+1個(gè)方程直到第n個(gè)方程中的未知數(shù))那么第k步消元操作即：(3)繼續(xù)這一過(guò)程，直到完成第n-1次消元，最后我們得到與原方程組等價(jià)的三角形方程組(2.3)消元過(guò)程結(jié)束(即用乘以2.2式的第k個(gè)方程，加到第i個(gè)方求解三角形方程組2.3，得到求解公式這個(gè)過(guò)程稱(chēng)為回代過(guò)程。求解三角形方程組2.3，得到求解公式這個(gè)過(guò)程稱(chēng)為回代過(guò)程。例題：考慮方程組Gauss消去法中每步用來(lái)消去其他元素的

稱(chēng)為該步的主元素。Gauss消去法作為數(shù)值方法，主元素的選擇是否會(huì)影響計(jì)算的結(jié)果呢？則該方程的精確解為而采用(，1)作為主元素，利用高斯消去法得到的解為顯然結(jié)果是錯(cuò)誤的。例題：考慮方程組Gauss消去法中每步用來(lái)消去

錯(cuò)誤在哪個(gè)地方呢？原因是我們?cè)谙獣r(shí)，利用了小主元，使得約化后的方程組元素?cái)?shù)量級(jí)大大增長(zhǎng)，再經(jīng)舍入，而計(jì)算機(jī)的有效位數(shù)有限，造成消元后的三角形方程組就不準(zhǔn)確了。

結(jié)論：在消元過(guò)程中可能出現(xiàn)主元素為零的情況，這時(shí)消去法將無(wú)法進(jìn)行；即使不為零，在主元素很小時(shí)，用其做除數(shù)，也會(huì)導(dǎo)致其他元素?cái)?shù)量級(jí)的嚴(yán)重增長(zhǎng)和舍入誤差的擴(kuò)散，最后也使得計(jì)算解不可靠。

解決方法：對(duì)一般的矩陣來(lái)說(shuō)，最好每一步選取系數(shù)矩陣（或消元后的低階矩陣）的該列中絕對(duì)值最大的元素作為主元素，以使高斯消去法具有較好的數(shù)字穩(wěn)定性。(高斯列主元素消去法)錯(cuò)誤在哪個(gè)地方呢？結(jié)論：在消元過(guò)程中可能出現(xiàn)主元素為零的1.列主元法第一列中絕對(duì)值最大是10，取10為主元n階方程組第k輪消元時(shí)，選第k列的后(n-k+1)個(gè)元素中絕對(duì)值最大作主元。1.列主元法第一列中絕對(duì)值最大是10，取10為主元n階方程x3=6.2/6.2=1x2=(2.5-5x3)/2.5=-1x1=(7+7x2-0x3)/10=0x1=0x2=-1x3=1第二列的后兩個(gè)數(shù)中選出主元2.5x3=6.2/6.2=1x2=(2.5-5x3)/2.5=-2完全主元素消去法整個(gè)矩陣中絕對(duì)值最大是10，取10為主元n階方程組第k輪消元時(shí)，選消元后元素中絕對(duì)值最大作主元。2完全主元素消去法整個(gè)矩陣中絕對(duì)值最大是10，取10為主元x1=0x2=-1x3=1方框中6最大，交換行列，交換列的時(shí)候要做記錄（即x3和x2交換了位置）：x1=0方框中6最大，交換行列，交換列的時(shí)候要做記錄（即x3完全主元素消除法與列主元素消除法的優(yōu)缺點(diǎn)比較：優(yōu)點(diǎn)：數(shù)值更加穩(wěn)定；缺點(diǎn)：計(jì)算量大；完全主元素消除法與列主元素消除法的優(yōu)缺點(diǎn)比較：優(yōu)點(diǎn)：對(duì)矩陣A實(shí)行初等行變換相當(dāng)于用初等矩陣左乘A，于是對(duì)(2.2)做第一次消元后，化為化為，即，其中

§3.1

矩陣的三角分解LU分解對(duì)矩陣A實(shí)行初等行變換相當(dāng)于用初等矩陣左乘A，于第k步的初等矩陣為并且重復(fù)這一過(guò)程，最后得到將上三角矩陣記為U，則第k步的初等矩陣為并且重復(fù)這一過(guò)程，最后得到將上三角矩陣將上三角矩陣記為U，則，其中則，L為單位下三角矩陣。高斯消去法實(shí)質(zhì)上是產(chǎn)生了一個(gè)將A分解為兩個(gè)三角形矩陣相乘的因式分解。如果A是非奇異陣，則LU分解是唯一的，否則分解不唯一。將上三角矩陣記為U，則消元法：消元法與三角分解法間的關(guān)系：

三角分解法：討論消元法：消元法與三角分解法間的關(guān)系：三角分解法：討論直接三角分解法解線(xiàn)性方程組（）的具體流程：1.2.計(jì)算U的第r行，L的第r列元素r=2,3,…,n3.(一)LU分解直接三角分解法解線(xiàn)性方程組（）的再求解Ly=b,Ux=y計(jì)算公式：(二)x的計(jì)算再求解Ly=b,Ux=y計(jì)算公式：(二)x的計(jì)算例

用直接三角分解法解方程組

解:(一)矩陣LU分解(1)故：例用直接三角分解法解方程組(2)經(jīng)計(jì)算：(2)經(jīng)計(jì)算：(二)求解x：從而(二)求解x：從而§3.2矩陣的Cholesky分解對(duì)稱(chēng)正定矩陣A：AT=A,A的各階順序主子式大于零.前面指出非奇異的矩陣可以有三角分解，當(dāng)A是某些特殊矩陣時(shí)，它的LU分解會(huì)有更加簡(jiǎn)潔的形式。A的LU分解(2.4)§3.2矩陣的Cholesky分解對(duì)稱(chēng)正定矩陣A：uii

>0(i=1,···,n)由于A是對(duì)稱(chēng)正定的，則有將U進(jìn)一步分解：uii>0(i=1,···,n)由于A是對(duì)稱(chēng)正定的，則根據(jù)A的對(duì)稱(chēng)性：故：由分解的唯一性知：故：其中P為上三角矩陣，這種對(duì)稱(chēng)正定矩陣的分解稱(chēng)為Cholesky分解。在Matlab中函數(shù)“chol”給出對(duì)稱(chēng)正定矩陣的Cholesky分解。根據(jù)A的對(duì)稱(chēng)性：故：由分解的唯一性知：故：其中P為上三角矩陣經(jīng)過(guò)n步可直接求得思路:(1)分解對(duì)稱(chēng)正定矩陣設(shè)n階對(duì)稱(chēng)正定矩陣A有分解,先用待定系數(shù)法求L的元素Cholesky分解的具體步驟(平方根法)：(2)分解求解方程組經(jīng)過(guò)n步可直接求得思路:設(shè)n階對(duì)稱(chēng)正定矩陣A有分解Cholesky方法具體計(jì)算公式：分解計(jì)算：

求解：

Cholesky方法具體計(jì)算公式：分解計(jì)算：求解：§

3.3向量范數(shù)與矩陣范數(shù)向量、矩陣與線(xiàn)性方程組有著密切的關(guān)系，向量、矩陣范數(shù)是解方程組以及研究與探討方程組本身性質(zhì)的工具。一、向量范數(shù)的定義定義范數(shù)為其中的，最常用的范數(shù)是，以及§3.3向量范數(shù)與矩陣范數(shù)向量、矩陣與線(xiàn)性方程組有著密切容易證明向量范數(shù)滿(mǎn)足如下性質(zhì)：(1)如果，則；而且，當(dāng)且僅當(dāng)(2)對(duì)任何的數(shù)c，都有(3)范數(shù)也稱(chēng)為2-范數(shù)或Euclidean函數(shù)；范數(shù)也稱(chēng)為-范數(shù)或一致范數(shù)。在Matlab中用函數(shù)用來(lái)計(jì)算向量x的范數(shù)。由性質(zhì)(3),還容易得到：容易證明向量范數(shù)滿(mǎn)足如下性質(zhì)：范數(shù)也稱(chēng)為2-范數(shù)或二矩陣范數(shù)的定義在向量范數(shù)的基礎(chǔ)上可以進(jìn)一步定義矩陣范數(shù)如果上式中的向量范數(shù)取為范數(shù)，則可以證明定義出的矩陣范數(shù)（稱(chēng)為矩陣范數(shù)或者列范數(shù)）為如果向量范數(shù)取為2-范數(shù)，則其中（模），稱(chēng)為矩陣B的譜半徑。(為B的任意特征值。)二矩陣范數(shù)的定義在向量范數(shù)的基礎(chǔ)上可以進(jìn)一步定義矩陣范數(shù)類(lèi)似地，Matlab函數(shù)norm(A,p)給出矩陣p=1,2或范數(shù)

如果向量范數(shù)取為，則可以證明定義出的矩陣范數(shù)（稱(chēng)為矩陣的范數(shù)或者行范數(shù)）為

容易證明矩陣范數(shù)滿(mǎn)足如下性質(zhì)：(1)如果，則；而且，而且僅當(dāng)(2)對(duì)任何的數(shù)

，

(3)

(4)而且由矩陣范數(shù)的定義還有稱(chēng)之為矩陣范數(shù)與相應(yīng)的向量范數(shù)是相容的。類(lèi)似地，Matlab函數(shù)norm(A,p)給出矩陣p122§3.4古典迭代法的構(gòu)造求解線(xiàn)性代數(shù)方程組的方法中小規(guī)模問(wèn)題直接法迭代法

大規(guī)模，超大規(guī)模問(wèn)題

古典方法現(xiàn)代方法38§3.4古典迭代法的構(gòu)造求解線(xiàn)性代數(shù)方程組的方法中123線(xiàn)性方程組的一般形式為：如果是非奇異的，則上式有唯一解。我們將通過(guò)一個(gè)具體線(xiàn)性方程組的例子來(lái)講解迭代法。?。杭淳€(xiàn)性方程組為：方程的精確解(直接法計(jì)算)39線(xiàn)性方程組的一般形式為：如果是非奇異的，則124如果對(duì)該方程組進(jìn)行變形，將變量分別從三個(gè)方程中分離出來(lái)：(1)令初值40如果對(duì)該方程組進(jìn)行變形，將變量所以(1)式可以表示為迭代形式：所以我們可以得到一個(gè)向量的序列，只要該序列當(dāng)時(shí)有極限，那么這個(gè)極限就是該線(xiàn)性方程組的解。上面這種迭代求解線(xiàn)性方程組的方法稱(chēng)為Jacobi迭代法。所以(1)式可以表示為迭代形式：所以我們可以得到一個(gè)向量的序考慮線(xiàn)性方程組的一般形式：其中矩陣A為n×n階方陣，則方程的分量形式為：改寫(xiě)成：考慮線(xiàn)性方程組的一般形式：其中矩陣A為n×n階方陣，則方程的從而得到迭代公式：上面式子就是一般形式的Jacobi迭代法，也可也記做：從而得到迭代公式：上面式子就是一般形式的Jacobi迭代法，在Jacobi迭代法中充分利用新值，可得到下面迭代：上面這種迭代方法也叫做Gauss-Seidel迭代，也可以記為：在Jacobi迭代法中充分利用新值，可得到下面迭代：上面這種方程組的精確解為x*=(1,1,1)T.解Jacobi迭代法計(jì)算公式為取初始向量x(0)=(0,0,0)T,迭代可得例1：利用Jacobi法和Gauss-Seidel法求解線(xiàn)性方程組方程組的精確解為x*=(1,1,1)T.解Jackx1(k)x2(k)x3(k)‖x(k)-x*‖0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636可見(jiàn),迭代序列逐次收斂于方程組的解,而且迭代7次得到精確到小數(shù)點(diǎn)后兩位的近似解.計(jì)算結(jié)果列表如下:kx1(k)x2(k)x3(k)‖x(k)-x*‖0000Gauss-Seidel迭代法的計(jì)算公式為:同樣取初始向量x(0)=(0,0,0)T,計(jì)算結(jié)果為

由計(jì)算結(jié)果可見(jiàn),Gauss-Seidel迭代法收斂較快.取精確到小數(shù)點(diǎn)后兩位的近似解,Gauss-Seidel迭代法只需迭代3次,而Jacobi迭代法需要迭代7次.kx1(k)x2(k)x3(k)‖x(k)-x*‖012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956Gauss-Seidel迭代法的計(jì)算公式為:同樣取初始向量x為了進(jìn)一步研究,從矩陣角度來(lái)討論上述迭代法.

對(duì)線(xiàn)性方程組Ax=b,記D=diag(a11,a22,…,ann)則有A=D-L-U于是線(xiàn)性方程組Ax=b可寫(xiě)成

(D-L-U)x=b等價(jià)于

Dx=(L+U)x+b或x=D-1(L+U)x+D-1b

為了進(jìn)一步研究,從矩陣角度來(lái)討論上述迭代法.對(duì)線(xiàn)性方程組由此建立Jacobi迭代法迭代公式

x(k+1)=D-1(L+U)x(k)+D-1bk=0,1,2,…或?qū)懗?/p>

x(k+1)=Bx(k)+fk=0,1,2,…其中由此建立Jacobi迭代法迭代公式或?qū)懗善渲兴訥auss-Seidel迭代法可以寫(xiě)成其中Gauss-Seidel迭代法迭代公式為寫(xiě)成矩陣形式為：所以Gauss-Seidel迭代法可以寫(xiě)成其中Gauss-S§3.5迭代法的分析構(gòu)造迭代法的途徑可以有很多，那么是不是所有的方法都能收斂呢？收斂速度的快慢與什么有關(guān)系呢？它的精確解為例：§3.5迭代法的分析構(gòu)造迭代法的途徑kx1(k)x2(k)x3(k)‖x(k)-x*‖0123401416.792.8168104.7-41.4-52.4-254.30-1.74.56-151-238.211342.41521680可見(jiàn),并不是所有的方程組都收斂，即使收斂對(duì)于不同的方法(例如Jacobi與Gauss-Seidel)收斂速度也是不同的.計(jì)算結(jié)果列表如下:kx1(k)x2(k)x3(k)‖x(k)-x*‖0000設(shè)是矩陣B任意一個(gè)特征值，是相應(yīng)的特征向量，即再假設(shè)為任意的向量范數(shù)及與之相融的矩陣范數(shù)，則有：首先引入幾個(gè)定義、引理：所以對(duì)矩陣B任意一個(gè)特征值，都有記，稱(chēng)之為矩陣B的譜半徑，則設(shè)是矩陣B任意一個(gè)特征值，先引入兩個(gè)引理（詳細(xì)證明見(jiàn)附錄）：引理3.1矩陣，則的充分必要條件是引理3.2矩陣，若，則是非奇異的。先引入兩個(gè)引理（詳細(xì)證明見(jiàn)附錄）：引理3.1矩陣

定理3.1

對(duì)任意的和任意的初始向量，迭代法收斂的充分必要條件是證明：必要性設(shè)迭代法產(chǎn)生的序列收斂，記是該序列的極限點(diǎn)，所以滿(mǎn)足又由迭代關(guān)系，可以得到定理3.1對(duì)任意的由的任意性，知：由引理3.1知：充分性由及引理2知（即）有唯一解，記為類(lèi)似于必要性的證明，得到再由第一步知，故由的任意性，知：由引理3.1知定理3.1給出了迭代收斂的充要條件，但不宜計(jì)算，所以在實(shí)際使用中通常并不好用。由知，只要對(duì)某種相容的矩陣范數(shù)有那么當(dāng)然，所以這常常是實(shí)際中很有效的收斂判別準(zhǔn)則。嚴(yán)格對(duì)角占優(yōu)矩陣：考慮，設(shè)，當(dāng)時(shí)的矩陣。定理3.1給出了迭代收斂的充要條件，但定理3.2如果A是嚴(yán)格對(duì)角占優(yōu)的矩陣，則它一定非奇異。由于A是對(duì)角占優(yōu)矩陣，所以，故矩陣是可逆的?？紤]定理3.2如果A是嚴(yán)格對(duì)角占優(yōu)的矩陣，則它一定非奇異。由矩陣的范數(shù)為由A是對(duì)角占優(yōu)矩陣，得由引理3.2知是非奇異的，又由于是非奇異的，所以A是非奇異的。得證！引理3.2矩陣，若，則是非奇異的。矩陣的范數(shù)為由A是對(duì)角定理3.3系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)的線(xiàn)性代數(shù)方程組，它的Jacobi迭代法和Gauss-Seidel迭代都是收斂的。證明：Jacobi方法的迭代矩陣為由定理3.2中的證明知，嚴(yán)格對(duì)角占優(yōu)矩陣滿(mǎn)足：再由定理3.1，得Jacobi迭代法收斂。(a)Jocobi的證明<1定理3.3系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)的線(xiàn)性代數(shù)方程組再考慮Gauss-Seidel方法，其迭代矩陣為用反證法，假設(shè)Gauss-Seidel迭代不收斂，則由定理3.1知：所以存在模大于1的特征值.設(shè)有，使得行列式：(b)Gauss-Seidel的證明再考慮Gauss-Seidel方法，其迭代矩陣為用反證法，假故，只有才能使得成立。由于A是對(duì)角占優(yōu)的，所以矩陣也是對(duì)角占優(yōu)的，那么該矩陣一定非奇異，這與上面該矩陣的行列式等于0矛盾。由于可逆，所以得證！故，只有由于A是對(duì)角占優(yōu)的，所以矩陣定理3.4若迭代矩陣B滿(mǎn)足，則迭代生成的序列滿(mǎn)足收斂速度問(wèn)題其中表示精確解。證明：先證明(b),然后證明(a)定理3.4若迭代矩陣B滿(mǎn)足，則迭代而所以故，本頁(yè)第一個(gè)式子可寫(xiě)為而所以故，本頁(yè)第一個(gè)式子可寫(xiě)為由于，故(b)得證顯然對(duì)于任意的正整數(shù)p，都有那么在本頁(yè)第一個(gè)式子中反復(fù)利用上式就可以得到(a)(a)得證由于，故(b)得證顯然對(duì)于任意的正整數(shù)給出的關(guān)系可以作為計(jì)算終止的判別準(zhǔn)則。即只要和已足夠接近，表明與便已足夠靠近。定理3.4(a)給出的是迭代收斂速度的一個(gè)估計(jì)。顯然越接近0，生成序列收斂得越快。定理3.14(b)定理3.4的討論給出的關(guān)系可以作為計(jì)算終止的判別準(zhǔn)則。即只要§3.6超松弛迭代(SOR)及分塊迭代方法對(duì)于給定的迭代法，每步迭代所需的工作量是確定的。如果迭代法收斂速度緩慢，則需要比較多的迭代次數(shù)，由此導(dǎo)致算法工作量太大而失去使用價(jià)值，因此各種迭代法的加速技術(shù)具有重要意義。假設(shè)是已經(jīng)得到的迭代值，以為初值進(jìn)行一步Gauss-Seidel迭代得：§3.6超松弛迭代(SOR)及分塊迭代方法將這一迭代值與的值組合作為新一步的迭代值其中為待定的參數(shù)，寫(xiě)成矩陣形式為：這時(shí)迭代矩陣：將這一迭代值