第三章線性代數(shù)方程組的解法序本章主要討論n階線性代數(shù)方程組的解法。其矩陣形式為其中非奇異陣（即）未知向量右端向量（常數(shù)向量）由克拉默（Cramer）法則知，上述方程組有唯一解，其解為：1第三章線性代數(shù)方程組的解法序本章主要討論n階線性代數(shù)方程但是這種計算方法在實際應用中對于高階方程組卻不能用，如果用每秒計算一億次的計算機計算也要算30多萬年，因此，行之有效的方程組的數(shù)值解法在數(shù)值計算中有著十分重要的地位。計算機上解線性方程組的數(shù)值方法大致可分為兩種：直接法（精確解法）：迭代法：在沒有舍入誤差的條件下，經(jīng)過有限次四則運算而求得方程組的精確解的方法。通過某種極限過程去逐次逼近方程組的精確解的方法。例如當n=20時，計算量為是因為用此法解上方程組需計算n+1個n階行列式，每個行列式的展開式有n！項，每一項又是n個元素的乘積，不難算出，計算一個n階方程組的解需做乘除法次，這2但是這種計算方法在實際應用中對于高階方程組卻不能用，如果用每§1高斯消元法與選主元技巧一、高斯消元法1、三角形方程組定義系數(shù)矩陣是三角形矩陣的方程組，例如當時，方程組有唯一解.求解過程可采用逆推方式，稱之為回代過程（消元過程）。2、高斯消元法（順序消元法）通過依次消元，把所求線性方程組（*）的求解問題轉(zhuǎn)化為三角形方程組的求解。特點：3§1高斯消元法與選主元技巧一、高斯消元法1、三角形方程組例1用高斯消去法解方程組解（消元過程用增廣矩陣的行初等變換來表示）第一次消元第二次消元然后回代，解得：推至一般，對線性代數(shù)方程組（*），記4例1用高斯消去法解方程組解（消元過程用增廣矩陣的行初等變換來⑴消元過程①當時，記將增廣矩陣的第i行加上第一行的倍（即）得其中這樣，就得到了一個與原方程組同解的方程組5⑴消元過程①當時，記將增廣矩②當時，再對進行消元，又得其中這樣，就得到了一個與原方程組同解的方程組6②當時，再對③重復以上過程，在完成第次消元后，當時，記得將的第i行加上第k行的倍（即）其中第k次消元為：7③重復以上過程，在完成第次消元后，當④如此作下去，當時，經(jīng)過次消元后，就把原方程組轉(zhuǎn)化為同解的三角形方程組即⑵回代過程把上式自下向上回代，即得方程組的解。綜上所述，有定理1若約化主元素則方程組可通過高斯消去法約化為三角形方程組（**）求解,計算公式如下:這種解方程組的方法稱為高斯消元法。8④如此作下去，當99⑵回代求解⑴消元計算對依次計算：10⑵回代求解⑴消元計算對注由上面公式可得，整個高斯消元法的消元過程中，乘法運算次數(shù)為：除法運算次數(shù)為：回代過程中，乘法運算次數(shù)為：除法運算次數(shù)為：故用高斯消去法求解一個n階線性代數(shù)方程組共需做的乘、除法總數(shù)為：11注由上面公式可得，整個高斯消元法的消元過程中，乘法運算次數(shù)為二、列主元消元法序高斯消去法是按照原方程組中給定的方程以及未知元的排列順序依次進行消元的，故又稱順序消元法，①若第k步中主元素則消元過程就無法進行；②即使把它作除數(shù)，就可能造成誤差的嚴重擴散，使解的精確度受到嚴重影響，從而造成結(jié)果嚴重失真。例2解方程組用順序消元法解(用具有舍入的4位浮點數(shù)進行計算)，第一次消元消元過程：但若其絕對值相對較小(此時稱為小主元),兩個問題：但在消元中將遇到12二、列主元消元法序高斯消去法是按照原方程組中給定的方程以及未回代求解：得顯然答案是錯誤的，如果選用2.000作為約化主元素（即先交換兩個方程的位置），然后再進行消元，則有交換兩行第一次消元再回代求解，則得由此，這種消元法稱為主元消元法。按選取主元素的方法不同，主元素消去法可分為以下幾種：作除數(shù)，從而帶入了大的誤差。原因是相對較小的小主元在每次消元前，應選取絕對值盡可能大的元素作為約化主元素，13回代求解：得顯然答案是錯誤的，如果選用2.000作為約化主元完全主元消元法：在方程組的系數(shù)矩陣的某一行中，選擇絕對值最大的元素作為主元素的消元法。在方程組的系數(shù)矩陣的某一列中，選擇絕對值最大的元素作為主元素的消元法。列主元素消元法最為常用，其應用的步驟一般為：第一步，在方程組的增廣矩陣第一列的n個元素中選取絕對值最大的一個作為主元素，并把此元素所在的行與第一行交換位置，再在增廣矩陣的第二列的后個元素中選取絕對值最大的一個作為主元素，并把此元素所在的行與第二行交換位置；行主元消元法：列主元消元法：在方程組的系數(shù)矩陣的所有元素中，選擇絕對值最大的元素作為主元素的消元法。第一次消元后得增廣矩陣第二步，14完全主元消元法：在方程組的系數(shù)矩陣的某一行中，選擇絕對值最大依次進行下去，經(jīng)過步選主元與消元，就得到一個與原方程等價的三角形方程組，再進行回代求解。例3分別用順序消去法和列主元素消去法解方程組：解①順序消去法第一次消元15依次進行下去，經(jīng)過步選主元與消元，就得到一第二次消元回代求解，得②列主元素消去法交換兩行第一次消元交換兩行16第二次消元回代求解，得②列主元素消去法交換兩行第一次消元交第二次消元回代求解，得列主元素方法在解決一般線性方程組中有廣泛的應用.17第二次消元回代求解，得列主元素方法在解決一般線性方程組中有廣§2三角分解法一、矩陣的三角分解1.

定義把一個n階矩陣A分解成兩個三角形矩陣乘積的形式稱為三角分解。三角分解的常用形式為：其中：L為下三角陣，U為上三角陣。若L為單位下三角陣（對角元素都是1），U為上三角陣，則三角分解稱為杜利特爾（Doolittle）分解。若L為下三角陣，U為單位上三角陣（對角元素都是1），則三角分解稱為克勞特（Crout）分解。18§2三角分解法一、矩陣的三角分解1.定義把一個n階2.矩陣的三角分解基本定理定理2設n階矩陣若A的順序主子式即則存在唯一的杜利特爾（Doolittle）分解其中：L為單位下三角陣，U為非奇異的上三角陣。192.矩陣的三角分解基本定理定理2設n階矩陣若A的順序2020212122222323242425252626注在定理的條件下，也存在唯一的克勞特分解其中：L為非奇異的下三角陣，U為單位上三角陣。（見習題3）二、杜利特爾（Doolittle）分解法（直接三角分解法）設方程組的系數(shù)矩陣的各階順序主子式都不等于零，即由定理2，有存在唯一的杜利特爾（Doolittle）分解：記為27注在定理的條件下，也存在唯一的克勞特分解其中：L為非奇異的下在A中元素已知的前提下，由矩陣的乘法原理，可直接求出矩陣L和U中的各元素，第一步，第二步，求U的第一行元素和L的第一列元素。顯有由求U的第二行元素和L的第二列元素。由由依次計算下去，設U的前行和L的前列已經(jīng)求出，下面導出求U的第k行和L的第k列的元素的公式：方法如下：28在A中元素已知的前提下，由矩陣的乘法原理，可直接求出矩陣L和用L的第k行乘以U的第i（）列,有即用L的第i（）行乘以U的第k列,有即所以，有29用L的第k行乘以U的第i（）列,有即用L的注杜利特爾（Doolittle）分解的計算特點為：以上計算方法稱為杜利特爾（Doolittle）分解。U的元素按行求，L的元素按列求；先求U的第k行元素，再求L的第k列元素，U和L一行一列逐步交叉計算，即按下圖逐框計算：每次計算出的L、U的元素放入A的相應位置上即可。這種記錄方法稱為緊湊格式。30注杜利特爾（Doolittle）分解的計算特點為：以上計算方令則解即等價于求解計算公式如下：價于當把A杜利特爾分解后，即有則方程組就等31令則解即等價于求解計算公式如下：綜上，用杜利特爾分解解方程組的方法如下：⑴對A實現(xiàn)杜利特爾分解：①先計算U的第一行元素，再計算L的第一列元素：②當時，求U的第k行和L的第k列的元素：⑵解三角形方程組計算出⑶解三角形方程組計算出32綜上，用杜利特爾分解解方程組的方例4用杜利特爾分解解方程組其中解由得由得由得當k=2時，33例4用杜利特爾分解解方程組其中解由得由得由得當k=2時，33由得當k=3時，所以，有由由34由得當k=3時，所以，有由由34三、解三對角方程組的追趕法1、三對角方程組形如的方程組稱之為三對角線方程組，簡記為其中A稱為三對角矩陣。2、三對角矩陣的三角分解根據(jù)A的特點，A分解后有以下形式：35三、解三對角方程組的追趕法1、三對角方程組形如的方程組稱之為3636由矩陣乘法原理，可直接求出L和U中的各元素，方法如下：用L的第i行乘以U的第i-1

列用L的第一行乘以U的第一、二列用L的第i行乘以U的第i列用L的第i行乘以U的第i+1列由此，有再由和求出即可完成A的三角分解。37由矩陣乘法原理，可直接求出L和U中的各元素，方法如下：用L的⑴對A實現(xiàn)三角分解：遞推公式為：⑵解方程組計算3、解三對角方程組的步驟（解方程組的追趕法）：由和與38⑴對A實現(xiàn)三角分解：遞推公式為得遞推公式為：⑶解方程組計算得遞推公式為：由39得遞推公式為：⑶解方程組計算得遞推公式為：由39例1用追趕法解方程組解由公式得40例1用追趕法解方程組解由得40由得由得41由得由得41§3向量與矩陣的范數(shù)一、向量的范數(shù)設向量（n維空間），⑴非負性：⑵齊次性：⑶三角不等式：對一切向量X，都有且對任意的實數(shù)與向量X，都有對任何向量X與Y，都有定義若存在X的某一實數(shù)值函數(shù)記為滿足則稱為n維空間上X的范數(shù)（?；蜷L度）。42§3向量與矩陣的范數(shù)一、向量的范數(shù)設向量（n維空間），設向量有向量X的“1”范數(shù)：向量X的“2”范數(shù)：理論上滿足以上三條的向量的范數(shù)多種多樣，常用的有以下三種：向量X的范數(shù)：解例2設向量求43設向量有向量X的“1”范數(shù)：向量X的“2”范數(shù)：理論上滿證例3證明其中（習題三.9⑴）即44證例3證明其中（習題三.9⑴）即44二、矩陣的范數(shù)設矩陣⑴非負性：且定義1若存在A的某一實數(shù)值函數(shù)記為滿足⑵齊次性：對任意的實數(shù)，都有⑶三角不等式：對都有⑷矩陣乘法不等式：對都有則稱為n維空間上A的的范數(shù)（?；蜷L度）。定義2若對于給定的向量范數(shù)和矩陣范數(shù)滿足成立，則稱和是相容的(或稱向量和矩陣的范數(shù)具有相容性).45二、矩陣的范數(shù)設矩陣⑴非負性：且定義1若存在A的某一實數(shù)定義3設向量矩陣對于給定的一種向量范數(shù)相應的定義一個矩陣A的實值函數(shù)為矩陣A的范數(shù)，并稱為矩陣A的算子范數(shù)。（可以證明滿足定義1中的四條，此不證）。設矩陣其常用的算子范數(shù)有以下三種：矩陣A的“1”范數(shù)：又稱為列?；蛄蟹稊?shù)各列元素的絕對值的和的最大者46定義3設向量矩陣對于給定的一種向量范數(shù)相應的定義一個矩陣A的矩陣A的范數(shù)：矩陣A的“2”范數(shù)：又稱為譜模或譜范數(shù)其中是矩陣的最大的特征值，即矩陣的特征方程的解（即的特征值）中的最大者。例4設矩陣求矩陣的范數(shù)各行元素的絕對值的和的最大者又稱為行模或行范數(shù)47矩陣A的范數(shù)：矩陣A的“2”范數(shù)：解根據(jù)定義，有的特征方程為得48解根據(jù)定義，有的特征方程為得48§4迭代法一、迭代法及其有關(guān)概念對于給定的方程組其中A為n階非奇異陣，b為n元非零向量，即將其轉(zhuǎn)化為等價的方程組從事先給定的某一初始向量出發(fā)，通過依次迭代計算就得到一個由向量構(gòu)成的序列其中設方程組的精確解為49§4迭代法一、迭代法及其有關(guān)概念對于給定的方程組其中A為若即即所得的向量序列收斂于方程組的解向量，則對于給定的允許誤差，只要k適當大，就可作為方程組的滿足精度要求的近似解，這就是求方程組的滿足精度要求的近似解的迭代法，也稱為求方程組的滿足精度要求的近似解的一階線性定常迭代法。其中B迭代矩陣迭代公式或迭代過程迭代序列若迭代序列收斂，則稱迭代法收斂，否則稱迭代法發(fā)散。顯然，迭代法的等價形式是不唯一的，因此用迭代法解方程組的一個重要問題是討論其收斂性。以下討論三種迭代法：雅可比（Jacobi）迭代法、高斯—賽德爾（Gauss-Seidel）迭代法超松弛迭代法（簡稱SOR迭代）50若即即所得的向量序列收斂于方程組的解向量，則對于給定的允許誤二、雅可比（

Jacobi

）迭代法對于方程組：其中A非奇異，且將其改寫成等價形式即51二、雅可比（Jacobi）迭代法對于方程組：其中A非奇異構(gòu)造相應的迭代公式:即52構(gòu)造相應的迭代公式:即52從事先給定的某一初始向量出發(fā)，就得到一個由向量構(gòu)成的序列其中若則對于給定的允許誤差，只要k適當大，就可作為方程組的滿足精度要求的近似解。這種求方程組的的近似解的方法稱為雅可比（Jacobi）迭代法。例5用雅可比迭代法解方程組取解等價形式為53從事先給定的某一初始向量出發(fā)，就得到一個由向量構(gòu)成的序列其迭代公式為逐次迭代，結(jié)果如下表：1.99972.0004…1.66672.500.99981.0005…0.83331.66670109…210k取54迭代公式為逐次迭代，結(jié)果如下表：1.99972.0004…1為方便討論迭代法的斂散性，將系數(shù)矩陣A寫成其中則方程組可寫成所以，有因為所以D可逆，所以，有所以，得雅可比迭代法的矩陣形式的迭代公式：其中稱為雅可比迭代矩陣，55為方便討論迭代法的斂散性，將系數(shù)矩陣A寫成其中則方程組三、高斯—賽德爾迭代法把雅可比迭代公式進行改進，即即這種迭代法就稱為高斯—賽德爾迭代法。56三、高斯—賽德爾迭代法把雅可比迭代公式進行改進，即即這種迭代所以高斯—賽德爾迭代法的矩陣形式的迭代公式為：其中稱為高斯—賽德爾迭代矩陣，類似于雅可比迭代法，把方程組寫成有例6用高斯—賽德爾迭代法解方程組取解等價形式為57所以高斯—賽德爾迭代法的矩陣形式的迭代公式為：其中稱為高斯—逐次迭代，結(jié)果如下表：取2.99992.99912.99382.95392.68401.99991.99891.99231.94451.5600.99970.99780.98430.88040.30543210k需要指出的是，方程組的等價形式是不唯一的，因此得到的雅可比迭代公式和高斯—賽德爾迭代公式也不是唯一的，因此用迭代法解方程組的一個重要問題是討論其收斂性。對應的高斯—賽德爾迭代公式為：58逐次迭代，結(jié)果如下表：取2.99992.99912.9938四、迭代法的收斂條件與誤差估計定義矩陣的所有特征值的模（絕對值）的最大值稱為矩陣A的譜半徑，記為即定理4矩陣A的譜半徑不超過A的任何一種算子范數(shù)證設為A的任一特征值，X為對應于的A的特征向量，即此即說明A的任一特征值的模都不超過所以59四、迭代法的收斂條件與誤差估計定義矩陣定理5若迭代過程中迭代矩陣B的某種算子范數(shù)則⑴對任意的初始向量該迭代過程都收斂于所給方程的唯一解⑵⑶證60定理5若迭代過程中迭代矩陣B的某種算子范數(shù)則⑴對任意的初始6161注①本定理說明了迭代矩陣只要有一個算子范數(shù)小于1，那么對應的迭代公式一定收斂。②式(2)、⑶給出了迭代過程中的誤差估計式。對于雅可比迭代法和高斯—賽德爾迭代法，下面再給出判定其收斂的更為方便的方法。62注①本定理說明了迭代矩陣只要有一個算子范數(shù)小于1，那么對定理6若方程組的系數(shù)矩陣按行嚴格對角占優(yōu)，即或按列嚴格對角占優(yōu)，即如既按行嚴格對角占優(yōu)又按行嚴格對角占優(yōu)則方程組有唯一解，且對任意的初始向量雅可比迭代法和高斯—賽德爾迭代法都收斂。63定理6若方程組的系數(shù)矩陣定理7若方程組的系數(shù)矩陣為對稱正定矩陣，則對任意的初始向量高斯—賽德爾迭代法收斂。對稱陣A正定的充要條件是：所有特征值都正；或者各階順序主子式都為正，如注定理5、6、7都是迭代法的充分條件，不滿足定理條件的迭代法不一定不收斂。定理8迭代過程對任意的初始向量都收斂的充要條件是迭代矩陣的譜半徑；且當時，迭代矩陣的譜半徑越小，收斂速度越快。64定理7若方程組的系數(shù)矩陣例7考察用雅可比迭代法和高斯—賽德爾迭代法解方程組時的收斂性，其中解65例7考察用雅可比迭代法和高斯—賽德爾迭代法解方程組時的收斂性由即得所以同理，得所以由定理8知，用雅可比迭代法求解，迭代過程收斂；用高斯—賽德爾迭代法求解，迭代過程發(fā)散。66由即得所以同理，得所以由定理8知，用雅可比迭代法求解，迭代過五、逐次超松弛迭代法（SOR迭代法）SOR迭代法是高斯—賽德爾迭代法一種改進。高斯—賽德爾迭代法為即67五、逐次超松弛迭代法（SOR迭代法）SOR迭代法是高斯—賽德把高斯—賽德爾迭代公式改寫成：進而改寫成：就有可能通過適當?shù)倪x擇因子的值，以期使迭代過程收斂速度更快，這種迭代法稱為逐次超松弛迭代法（簡稱為SOR迭代法），其中，松弛因子。68把高斯—賽德爾迭代公式改寫成：進而改寫成：就有可能通過適當?shù)腟OR迭代法的矩陣形式為：其中稱為逐次超松弛迭代矩陣，顯然，當時，SOR迭代法就是高斯—賽德爾迭代法。除了利用定理5、定理8判定SOR迭代法的收斂性之外，還有以下定理：定理9設方程組的系數(shù)矩陣的主對角線上的元素則用SOR法求解時，若SOR法收斂，則證69SOR迭代法的矩陣形式為：其中稱為逐次超松弛迭代矩陣，顯然，定理10設方程組的系數(shù)矩陣是對稱正定矩陣，且則對任意初始向量SOR法收斂。70定理10設方程組的系數(shù)矩陣解例8用SOR迭代法求解方程組取迭代公式為計算如下：-1.000003…-0.4952594-0.2224321-0.202109801.000001…0.69482600.42309390.884588301.999998…2.5661402.3216693.65020…3210k取71解例8用SOR迭代法求解方程組取迭代公式為計算如下：-1.0§5方程組的狀態(tài)(與解的迭代改善)一、方程組的狀態(tài)與矩陣的條件數(shù)用計算方法解方程組時，有時其結(jié)果是不準確的。原因可能有兩個：其一是采取的方法不合理；其二是所給的方程組本身有問題。對于有問題的方程組，采取再好的計算方法求解也是毫無意義的。因此，在解方程組之前，需要討論方程組本身的“好”與“壞”的問題，即方程組的“狀態(tài)”問題。例9其解為：其解為：其解為：72§5方程組的狀態(tài)(與解的迭代改善)一、方程組的狀態(tài)與矩陣上例說明，有些方程組，即使系數(shù)矩陣和右端常數(shù)項有微小變化（稱有一個小小的擾動），它們的解變化卻很大，這樣的方程組很難求得其較精確的解。象這樣系數(shù)矩陣和右端常數(shù)項有微小擾動就能引起解的巨大變化的方程組稱之為“病態(tài)”方程組，其系數(shù)矩陣稱為“病態(tài)”矩陣