數(shù)值分析03線性方程組求解

§1線性方程組Grammer法則：需要乘除法次數(shù)：N＝(n+1)n!(n-1)+n第三章線性方程組的解法當(dāng)n>100，特別是某些偏微分方程數(shù)值求解過程中出現(xiàn)的方程組常選用迭代解法。相關(guān)理論包括：迭代的收斂性、收斂速度問題、誤差估計(jì)。常用的迭代法是：Jacobi迭代法；Gauss－Seidel迭代法。數(shù)值解法1、直接解法在不考慮舍入誤差的情況下，經(jīng)有限步四則運(yùn)算求得精確解。當(dāng)n<100及某些大型稀疏方程組、帶型方程組常選用直接解法。Gauss消去法的啟示。最基本的直接解法是Gauss消去法，其他重要的直接解法全都受到2、迭代解法基于一定迭代格式，產(chǎn)生逼近方程組精確解的近似序列。利用方程組的初等變換解方程組：（1）某一個(gè)方程兩端同乘以非零常數(shù)k；（2）某一個(gè)方程加上另一個(gè)方程的k倍；（3）互換方程組中兩個(gè)方程的位置。顯然，經(jīng)過初等變換后的方程組與原方程組同解。或者說初等變換不會(huì)改變方程組的解。例如：解方程組對(duì)得到的三角形方程組回代求解:x4=1,x3=0,x2=2,x1=-1上述過程實(shí)際上等價(jià)于對(duì)方程組的增廣矩陣實(shí)施相同的初等變換，從而將復(fù)雜方程組化為簡單的三角方程組進(jìn)行求解。這就是Gauss順序消去法的來源?！?Gauss消去法GaussianElimination一、基本思想主要包括兩個(gè)過程：消元過程和回代過程。例：用Gauss消去法求解線性方程組：利用方程組的初等變換（矩陣的初等變換）將復(fù)雜的線性方程組化為三角方程組upper-triangularmatrix

。通過回代求得原方程組的解。解：消元：得到同解方程組：回代backwardsubstitution求解得：Gauss消去法的一般過程記方程組初始增廣矩陣為第一步消元設(shè)利用把第一列對(duì)角線下方元素全消為0為此，令然后用下面的n-1行元素減去第一行對(duì)應(yīng)位置元素的倍，將變化后的各位置元素表示為則有Gauss消去法的一般過程記方程組初始增廣矩陣為假設(shè)經(jīng)過k-1步消元后，增廣矩陣變?yōu)榈趉步消元：設(shè)以第k行為基礎(chǔ)，將下方元素全消為0，為此需要計(jì)算消元因子然后，以第i行減去第k行的得經(jīng)過n-1步消元后，增廣矩陣化為回代即可求得解在Gauss消去法的消元過程中，為了計(jì)算消元因子，需要用到除法運(yùn)算，為了避免絕對(duì)值較小的數(shù)作除數(shù)以及溢出現(xiàn)象。在每一步消元之前先選主元，并將主元所在行與對(duì)角線所在行交換，再進(jìn)行消元過程。若某一步主元的絕對(duì)值小于事先給定的閾值，則求解結(jié)果會(huì)嚴(yán)重失真，此時(shí)終止計(jì)算，并輸出計(jì)算失敗的信息。二、相關(guān)理論Th1：若A為n階非奇異矩陣，則可通過Gauss消去法及互換兩行的初等變換，將方程組化為三角方程組。Th2：若A的所有順序主子式均不為零，則可通過Gauss消去法（無需交換兩行的初等變換）將方程組化為三角方程組。Gauss消去法的乘除法次數(shù)：三、Gauss列主元消去法(PartialPivotingormaximalcolumnpivoting)例：用Gauss列主元消去法求下面解線性方程組的解解：得到同解線性方程組：回代解得：§3矩陣分解及其在解方程組中的應(yīng)用一、LU分解法(Doolittle分解Crout分解)Th：設(shè)A是非奇異矩陣，則A可分解為一個(gè)單位下三角和一個(gè)上三角矩陣的乘積。即：其中則：L與U中各元素的確定：利用矩陣乘法：令二、Cholesky分解法Th：若A為對(duì)稱正定矩陣，則A可分解為下三角矩陣，D為對(duì)角陣，即其中L為單位進(jìn)一步地有：從而用差分方法解二階常微分方程的邊值問題，熱傳導(dǎo)及三次樣條插值函數(shù)的求解等問題中常會(huì)遇到下邊嚴(yán)格對(duì)角占優(yōu)的三對(duì)角線形方程組的求解問題。三、追趕法（適用于三對(duì)角方程組）嚴(yán)格對(duì)角占優(yōu)矩陣若則稱矩陣A是嚴(yán)格行對(duì)角占優(yōu)陣，也稱為強(qiáng)對(duì)角占優(yōu)。類似地可定義嚴(yán)格列對(duì)角占優(yōu)陣。嚴(yán)格行（列）對(duì)角占優(yōu)簡稱嚴(yán)格對(duì)角占優(yōu)陣。系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)的三對(duì)角方程組（帶型方程組）的解法：追趕法追：方程組化為如下的等價(jià)方程組共需要乘除法次數(shù)：＝4n－2趕（回代）：需要乘除法次數(shù)：n-1追趕法乘除法總次數(shù)：（4n－2）＋（n－1）＝5n－3Th：若三對(duì)角矩陣滿足：則方程組Ax＝b的解存在且唯一，且追趕法是數(shù)值穩(wěn)定的?！?向量范數(shù)與矩陣范數(shù)一、向量范數(shù)1、向量范數(shù)的定義Def：若對(duì)任意向量與之對(duì)應(yīng)，且這種對(duì)應(yīng)關(guān)系滿足下面的條件都存在一個(gè)實(shí)數(shù)（1）并且當(dāng)且僅當(dāng)x=0時(shí)，上式取等號(hào)（非負(fù)性）；（2）（齊次性）；（3）（三角不等式）；則稱上的一個(gè)向量范數(shù)。是

由條件（3）可推出不等式：由向量范數(shù)導(dǎo)出的兩個(gè)向量之間的距離設(shè)x，y是n維向量空間中的兩個(gè)點(diǎn)，則它們之間的距離可定義為2、常用的向量范數(shù)（1）1－范數(shù)（2）2－范數(shù)（3）無窮范數(shù)（4）p－范數(shù)前三種范數(shù)是p－范數(shù)中p分別取1，2，以及趨于無窮的特例。以無窮范數(shù)為例，驗(yàn)證其滿足向量范數(shù)定義中的三條性質(zhì)；證明：3、向量序列的斂散性Def：設(shè)為中一向量序列，其中是一個(gè)固定向量。若則稱向量序列收斂于向量記為4、向量范數(shù)的連續(xù)性Th：設(shè)非負(fù)函數(shù)為上任一向量范數(shù)，則是分量的連續(xù)函數(shù)。5、向量范數(shù)的等價(jià)性（相容性）Th：設(shè)與是任意兩個(gè)向量范數(shù)，則一定存在兩個(gè)常數(shù)（與x無關(guān)）使得對(duì)一切x均成立。這一性質(zhì)稱為向量范數(shù)的等價(jià)性。向量范數(shù)等價(jià)性的意義在于：不影響向量序列的收斂性，進(jìn)而不會(huì)破壞空間的完備性。利用該定理，不難證明如下有關(guān)向量序列收斂的充分必要條件Th：6、向量范數(shù)在評(píng)價(jià)方程組近似解的效果中應(yīng)用設(shè)分別表示方程組的近似解與準(zhǔn)確解，則分別表示近似解與準(zhǔn)確解之間的絕對(duì)誤差與相對(duì)誤差。二、矩陣范數(shù)1、矩陣范數(shù)的定義Def：如果矩陣的某個(gè)實(shí)值函數(shù)滿足：（1）時(shí)，上式取等號(hào)（非負(fù)性）；并且當(dāng)且僅當(dāng)（3）（三角不等式）；（4）（2）（齊次性）則稱是矩陣A的范數(shù)。2、矩陣范數(shù)與向量范數(shù)的相容性Def：對(duì)于給定的向量范數(shù)和矩陣范數(shù)，如果對(duì)于任一個(gè)向量和任一個(gè)矩陣不等式恒成立，則稱所給的向量范數(shù)和矩陣范數(shù)是相容的。3、常用的矩陣范數(shù)（1）行范數(shù)（2）列范數(shù)（3）譜范數(shù)其中表示矩陣的最大特征值（的絕對(duì)值）。（4）F（Frobenius）－范數(shù)例：設(shè)計(jì)算矩陣的行范數(shù)、列范數(shù)、譜范數(shù)分別與向量的無窮范數(shù)、1范數(shù)、2范數(shù)相容4、譜半徑Def：設(shè)的特征值為則稱為矩陣A的譜半徑。Th：Th：若是對(duì)稱矩陣，則Th：若則為非奇異矩陣，且§5方程組的性態(tài)和條件數(shù)引例考察如下三個(gè)方程組的解若方程組Ax＝b的系數(shù)矩陣A與右端列向量b的微小擾動(dòng)將引起解產(chǎn)生巨大變化，則稱此方程組為病態(tài)方程組，否則稱為良態(tài)方程組。對(duì)于病態(tài)方程組，無論用多么穩(wěn)定的算法求解，一旦計(jì)算中產(chǎn)生了誤差就將使解面目全非，這種方程組的性態(tài)是很壞的。于是，在求解方程組之前，就有必要考慮這樣的問題：如何衡量方程組的病態(tài)程度？一、矩陣的條件數(shù)考慮下面的問題：設(shè)A是非奇異矩陣，并且Ax＝b的準(zhǔn)確解為x，當(dāng)右端向量b有一個(gè)小的擾動(dòng)，相應(yīng)解的擾動(dòng)記為即有：分析與之間的關(guān)系。即，解的相對(duì)誤差與右端列向量相對(duì)擾動(dòng)之間的關(guān)系。這說明了常數(shù)項(xiàng)b的相對(duì)誤差在解中可能放大倍若Ax＝b中的系數(shù)矩陣A有一個(gè)小的擾動(dòng)且當(dāng)時(shí)，可以證明此時(shí)受擾解的相對(duì)誤差滿足：若系數(shù)矩陣與右端向量分別有微小擾動(dòng)時(shí)，擾動(dòng)解的相對(duì)誤差為：為矩陣A的條件數(shù)。它刻畫了矩陣的“病態(tài)”程度。Def：設(shè)A為非奇異矩陣，稱矩陣的條件數(shù)與所用的范數(shù)有關(guān)，常用的條件數(shù)主要有：特別的，當(dāng)A為對(duì)稱矩陣時(shí)，有這里分別表示矩陣A的絕對(duì)值最大和最小的特征值。條件數(shù)的性質(zhì)（1）對(duì)任何非奇異矩陣A，都有（2）設(shè)A為非奇異矩陣且常數(shù)則有（3）設(shè)A為正交矩陣，則（4）若A為非奇異矩陣，R為正交矩陣，則有注：一般判斷矩陣是否病態(tài)，并不計(jì)算A1，而由經(jīng)驗(yàn)得出。

行列式很大或很?。ㄈ缒承┬?、列近似相關(guān)）；

元素間相差大數(shù)量級(jí)，且無規(guī)則；

主元消去過程中出現(xiàn)小主元；

特征值相差大數(shù)量級(jí)。二、近似解與殘向量之間的關(guān)系考慮下面的問題：設(shè)是方程組Ax＝b的近似解，自然想到將代入到原方程組中，考察方程組左右兩邊誤差大小，據(jù)此評(píng)價(jià)近似效果。一般來說代入后兩邊差距越小，近似效果越好。定義：稱為近似解的殘向量問題：當(dāng)殘向量較小時(shí)，能否說明就是一個(gè)較好的近似解？分析下面一個(gè)具體問題方程組準(zhǔn)確解為兩個(gè)近似解考察近似效果及殘向量大小Th：設(shè)A非奇異，x是方程組Ax=b的準(zhǔn)確解，是其近似解則，證明：§6線性方程組的迭代解法一、迭代法的一般步驟例如:依據(jù)兩種不同改寫方式，構(gòu)造迭代格式，考察迭代矩陣如：令，則事實(shí)上，方程組總是可以改寫為我們所需要的等價(jià)形式的二、迭代法的收斂性與誤差估計(jì)Th1：收斂的充分條件與誤差估計(jì)設(shè)是方程組的準(zhǔn)確解，若則迭代格式對(duì)任意初值均收斂，且有幾點(diǎn)說明：（1）該定理只能用于判別迭代收斂，不能說明發(fā)散（2）解方程組的迭代法如果收斂，對(duì)初值的選取沒有要求，這是與方程求根的迭代法不同的（3）該定理給出了估計(jì)截?cái)嗾`差的兩種方法，在實(shí)際應(yīng)用中常用下面的方法控制迭代終止Th2：迭代法收斂的充分必要條件迭代格式收斂的充分必要條件是事實(shí)上這一停機(jī)準(zhǔn)則并不可靠，僅在q小于等于0.5時(shí)才能保證解的精度滿足要求，q>0.5時(shí)有更復(fù)雜的停機(jī)準(zhǔn)則，參閱宋永忠.解線性方程組的迭代法的停機(jī)準(zhǔn)則和誤差界.計(jì)算數(shù)學(xué)，1992(1):27~32三、Jacobi迭代法1、Jacobi迭代格式根據(jù)方程組中第i個(gè)方程，將未知量表示出來。用其余的未知量構(gòu)造迭代格式：將上面的格式寫成矩陣乘法的形式，等價(jià)與下面的矩陣方程其中，L，D，U分別是原方程組Ax=b中系數(shù)矩陣A的對(duì)角線下方元素、對(duì)角線元素、對(duì)角線上方元素構(gòu)成的矩陣，即可見，Jacobi迭代法中的迭代矩陣為2、Jacobi迭代法的收斂性判定Jacobi迭代法收斂的充分必要條件是：而Jacobi迭代法中迭代矩陣的譜半徑可以按照下面的公式計(jì)算這是因?yàn)槔河肑acobi迭代法求解下列方程組，并驗(yàn)證收斂性；取初值x=（1，1，1）T，給出迭代兩步后的方程組的近似解解：迭代格式收斂性所以Jacobi迭代法收斂。準(zhǔn)確解（1，2，3）四、Gauss－Seidel迭代法1、基本思想與迭代格式在Jacobi迭代法中，注意到計(jì)算時(shí)，從一直到都已經(jīng)計(jì)算好，然而Jacobi迭代法并沒有利用這些最新的近似值進(jìn)行下一步的計(jì)算，仍用第k步的各個(gè)x進(jìn)行迭代。為此，我們對(duì)Jacobi迭代格式進(jìn)行如下修改：一旦有未知量最新的近似值，下面就用最新結(jié)果進(jìn)行迭代，這樣可能使收斂速度加快，同時(shí)節(jié)省存儲(chǔ)空間將上面的方程組寫成矩陣乘法形式：Gauss－Seidel迭代法的迭代矩陣為：2、Gauss－Seidel迭代法的收斂性判定Gauss－Seidel迭代法收斂的充分必要條件是：例：用Gauss－Seidel迭代法求解下列方程組，并驗(yàn)證收斂性；取初值x=(1,1,1)T，給出迭代兩步的結(jié)果解：迭代格式收斂性：所以Gauss-Seidel