線性方程組直接解法.ppt

第三章,線性方程組直接解法,第三章目錄,1.Gauus消元法2.主元素法2.1引入主元素法的必要性2.2列主元素法2.3全主元素法2.4解三對角方程組的追趕法3.矩陣分解法3.1Gauss消去法的矩陣形式3.2矩陣的三角分解3.3直接三角分解法4.平方根法與改進的平方根法5.矩陣求逆6.方程組的性態(tài)和條件數(shù),設(shè)n階線性方程組：,其矩陣形式為：,Ax=b(2-2),其中：,在科學(xué)研究和工程技術(shù)中所提出的計算問題中，線性方程組的求解問題是基本的，常見的，很多問題如插值函數(shù)，最小二乘數(shù)據(jù)擬合，構(gòu)造求解微分方程的差分格式等，都包含了解線性方程組問題，因此，線性方程組的解法在數(shù)值計算中占有較重要的地位。,求解Ax=b，曾經(jīng)學(xué)過高斯（Gauss）消元法，克萊姆（Cramer）法則，矩陣變換法等，但已遠遠滿足不了實際運算的需要，主要體現(xiàn)兩個方面：一是運算的快速和準確，其次是方程組的個數(shù)增大時的計算問題。如何建立能在計算機上可以實現(xiàn)的有效而實用的解法，具有極其重要的意義，我們也曾指出過，Cramer法則在理論上是絕對正確的，但當n較大時，在實際計算中卻不能用。,如果線性方程組Ax=b的系數(shù)行列式不為零，即det(A)0，則該方程組有唯一解。,線性方程組的數(shù)值解法,解線性方程組的數(shù)值方法大致分為兩類：,請注意：由于在計算中某些數(shù)據(jù)實際上只能用有限位小數(shù)，即不可避免地存在著舍入誤差的影響，因而即使是準確解法，也只能求到近似解。直接法在求解中小型線性方程組（100個），特別是系數(shù)矩陣為稠密型時，是常用的、非常好的方法。,直接法：指假設(shè)計算過程中不產(chǎn)生含入誤差，經(jīng)過有限步四則運算可求得方程組準確解的方法。,2.迭代法：從給定的方程組的一個近似值出發(fā)，構(gòu)造某種算法逐步將其準確化，一般不能在有限步內(nèi)得到準確解。,這一章介紹計算機上常用的直接法，它們都是以Gauss消元法為基本方法，即先將線性方程組化為等價的三角形方程組，然后求解。,1Gauss消元法,Gauss消元法是最基本的一種方法，下例說明其基本思想:,例1,解線性方程組：,解：消去x1，進行第一次消元：首先找乘數(shù)，以-12乘第一個方程加到第二個方程，以18乘第一個方程加到第三個方程上可得同解方程組：,例1（續(xù)）,上述Gauss消元法的基本思想是：先逐次消去變量，將方程組化成同解的上三角形方程組，此過程稱為消元過程。然后按方程相反順序求解上三角形方程組，得到原方程組的解，此過程稱為回代過程。,再消一次元得：,二次消元后將方程化為倒三角形式，然后進行回代容易解出：x3=3,x2=2,x1=1。,我們的目的，是要總結(jié)歸納出一般情況下的n階線性方程組的消元公式和回代求解公式，從而得到求解n階線性方程組的能順利在計算機上實現(xiàn)的行之有效的算法。,為能更清楚地得到算法，下面以4階線性方程組為例總結(jié)求解步驟，并且很容易地可推廣至一般的n階線性方程組。,可以檢查，分別以li1乘第一個方程加到第i個方程上可以完成第一次消元，得同解方程組：,變化以后的方程組系數(shù)及右邊的常數(shù)項可總結(jié)出如下的計算公式：,Gauss消元法的基本步驟3（4階）,以方程組中第i個方程減去第二個方程乘li2(i=3,4)，完成第二次消元。,上標為3的系數(shù)和右端項可由下面公式計算：,第三步：消元（4階方程組需進行3次消元）將上述A(3)X=b(3)中最后一個方程中的x3消為零：,然后可回代求解：由于A(4)為上三角形，所以可按變量的逆序逐步回代求原方程組的解：,上述消元、回代求解過程很容易推廣到一般的n階線性方程組。,經(jīng)過上述消元步驟，得到同解的上三角形方程組：A(4)x=b(4),Gauss消元法的消元過程1、2（n階）,一般地，設(shè)n階方程組：,消元過程為：,第k步消元后同解方程組中上標為k+1的元素的計算公式見下屏,照此消元下去，完成n1次消元后，可將原方程組化成同解的上三角形方程組如下：,Gauss消元法的回代過程（n階）,回代過程：逐步回代求得原方程組的解,Gauss消元法的計算量,由于在計算機中作乘除運算量所需時間遠大于作加減運算所需時間，故只考慮作乘除運算量。由消元法步驟知，第k次消元需作nk次除法，作(nk)(nk+1)次乘法，故消元過程中乘除法運算量為：,所以Gauss消去法的乘除法總運算量為：,Gauss法與Cramer法則的計算量比較,Gauss消元法的乘除法總運算量為：,與我們曾經(jīng)介紹的Cramer法則的乘除法總運算量(n21)n!+n相比，由下表可知：當階數(shù)越高時，Gauss消元法所需乘除法次數(shù)比Cramer法則要少得多：,Gauss消元法的優(yōu)缺點：,但其計算過程中，要求akk(k)（稱為主元素）均不為零，因而適用范圍小，只適用于從1到n1階順序主子式均不為零的矩陣A，計算實踐還表明，Gauss消元法的數(shù)值穩(wěn)定性差，當出現(xiàn)小主元素時，會嚴重影響計算結(jié)果的精度，甚至導(dǎo)出錯誤的結(jié)果。,Gauss消元法簡單易行。,2主元素法,2.1引入主元素的必要性對線性方程組AX=b，若其系數(shù)行列式det(A)0，則該方程組有唯一解，但是這一條件不能保證所有主元素都不等于零，只要某一主元素等于零，就不能用Gauss消元法求解該方程組，即使所有主元素不等于零，但某一主元素的絕對值很小時，Gauss消元法也是不適用的。如下例：,例2,例2（續(xù)1）,解：為減小誤差，計算過程中保留3位有效數(shù)字。按Gauss消元法步驟：,第一次消元后得同解方程組：,第二次消元后得同解方程組,回代得解，x3=2.02，x2=2.40，x1=5.80。容易驗證，方程組（3-8）的準確解為：x1=2.60，x2=1.00，x3=2.0。,顯然兩種結(jié)果相差很大。,若在解方程組前，先交換方程的次序，如將（2-8）交換一行與三行改寫成如下所示：,再用Gauss消元法，順序消元后得同解方程組：,回代得解：x3=2.00，x2=1.00，x1=2.60與準確解相同。,例2（續(xù)2）,例2兩種解法的誤差分析,在例2中，對(2-8)的方程進行順序消元時，主元a(1)11=0.50，a(2)22=0.100都比較小，以它們作除數(shù)就增長了舍入誤差,而導(dǎo)致計算結(jié)果不準確。,產(chǎn)生上述現(xiàn)象的原因在于舍入誤差，當|a(k)kk|很小時，進行第k次消元，要用|a(k)kk|作除數(shù)，這樣就可能增大舍入誤差造成溢出停機，或者導(dǎo)致錯誤的結(jié)果。,為了在計算過程中，抑制舍入誤差的增長，應(yīng)盡量避免小主元的出現(xiàn)。如例2的第二種解法,通過交換方程次序，選取絕對值大的元素作主元基于這種思想而導(dǎo)出主元素法。,2.2列主元素法,為簡便起見，對方程組（2-1），用其增廣矩陣：,表示，并直接在增廣矩陣上進行運算。,列主元素法的具體步驟如下：,列主元素法,如此經(jīng)過n1步，增廣矩陣（2-9）被化成上三角形，然后由回代過程求解。在上述過程中，主元是按列選取的，故稱為列主元法。例2中的第二種解法就是按列主元法進行的。,2.3全主元素法,經(jīng)過nk次消元后，得到與方程組（2-1）同解的上三角形方程組，再由回代過程求解。,例6,計算過程保留三位小數(shù)。,2.4解三對角方程組的追趕法,在很多問題中，需要解如下形式的三對角方程組：,三對角方程組的系數(shù)矩陣為三對角陣，對于這種特殊而又簡單的方程組，用前面介紹的方法求解由于有大量的零元素既占內(nèi)存又浪費計算時間，顯然很不經(jīng)濟。充分注意到三對角方程組的特點，根據(jù)順序消元的思想導(dǎo)出一個簡便的算法追趕法。,首先進行順序消元，且每步將主元系數(shù)化為1，將方程組化為：,其中系數(shù)按下式計算：,然后回代求解，得：,上述追趕法能進行到底。,追趕法舉例,用追趕法解下列三對角方程組：,例4,解：首先將方程組化為（先追）：,然后回代（趕）求解：x5=0，x4=30/7，x3=6/7，x2=12/7，x1=0,可以看出，追趕法本質(zhì)上還是順序消元法，但由于計算過程中只涉及系數(shù)矩陣的非零元，因此大大節(jié)約了計算機內(nèi)存與計算量，按乘除法次數(shù)進行比較，Gauss消元法約為n3/3，全主元法為n3/2，而追趕法僅為5n-3次，可見追趕法是求解三對角方程組的非常好的方法。,3矩陣分解法,如果用矩陣形式表示，Gauss消元法的消元過程是對方程組（2-1）的增廣矩陣（A、b）進行一系列的初等行變換，將系數(shù)矩陣A化成上三角矩陣的過程，也等價于用一串初等變換陣去左乘增廣矩陣，因此，消元過程可以通過矩陣運算來實現(xiàn)。,緊接下屏：,3.1Gauss消元法的矩陣形式,事實上，Gauss消元法的第一次消元相當于用初等矩陣：,第二次消元相當于用初等矩陣：,第k次消元相當于用初等矩陣：,Gauss消元法的矩陣形式,經(jīng)過n1步消元后得到：,因為Lk(k=1,2,n1)均為非奇異陣，故它們的逆矩陣存在。容易求出：,這說明：在的條件下，消元過程實際上是把系數(shù)矩陣A分解成單位下三角陣與上三角矩陣的乘積的過程。,Gauss消元法的矩陣形式（續(xù)）,杜利特爾（Doolittle）分解LU分解,事實上，只要A滿足一定條件，由上述結(jié)論，它一定可以分解成兩個三角形矩陣的乘積，即：A=LU。,上述分解稱為杜利特爾（Doolittle）分解，也稱為LU分解，當系數(shù)矩陣完成三角分解后，對于求解方程組：Ax=b。,消元過程相當于分解A=LU及求解三角形方程組Ly=b，回代過程則是求解另一個三角形方程組Ux=y，因此，解線性方程組問題可轉(zhuǎn)化為矩陣的三角分解問題。,其中：L為單位下三角矩陣，,U為上三角矩陣：,3.2矩陣的三角分解,正如Gauss消元法要在一定條件下才能進行到底一樣，矩陣A也必須滿足一定條件才能進行三角分解。,設(shè)A為n階方陣，若A的順序主子式Ai(i=1,2,n)均不為零,則矩陣A存在唯一的Doolittle分解。,定理2.1,下面討論如何對A進行LU分解：（1行1列）,由于兩個矩陣相等就是它們的對應(yīng)元素都相等，因此通過比較A與LU的對應(yīng)元素，即可得到直接計算L、U的元素的公式：A=LU即：,緊接下屏：,對A進行LU分解,由矩陣乘法規(guī)則及比較（2-11）兩端的元素，得：,即可由（2-12）求出U的第一行，L的第一列。,下面討論一般情況，即：U的第i行，L的第j列：,一般情況下，可由：,對A進行LU分解（r行r列）,計算過程應(yīng)按U第1行、L第1列（第1框），U第2行、L第2列（第2框），的順序,具體分解步驟見下屏：,得到計算uij和lij的公式：,對A進行LU分解的具體步驟,1.計算U的第1行，L的第1列，亦稱為計算第1框；,2.計算U的第r行，L的第r列（r=2,n），即第r框：,矩陣A的LU分解舉例,解：按分解公式（2-13），一框一框分解，每框計算時先行后列：,所以：,例5,3.3直接三角分解法,若線性方程組Ax=b的系數(shù)矩陣A完成三角分解，A=LU，那么解方程組Ax=b等價于求解兩個三角形方程組Ly=b，Ux=y，即由：,再由：,可解得：,直接三角分解法（續(xù)）,容易看出，式（2-14）與式（2-13）的運算規(guī)律相同，或者由：,解線性方程組舉例,例6,解：按表2-3計算：,三角分解法的幾點說明,1、用三角分解法求線性方程的乘除法運算量也是n3/3數(shù)量級。由于在求出uij,lij和yi后，aij和bi無需保留，故上機計算時，可把L，U和y存在A，b所占的單元，回代時x取代y，整個計算過程中不需要增加新的存貯單元。,3、完成A=LU分解后可以較容易地求出行列式|A|的值：,2、從三角分解法的推導(dǎo)及例中可以看出，系數(shù)矩陣的三角分解與右端項無關(guān)。因而在計算多個系數(shù)矩陣為A而右端不同的線性方程組系時，用三角分解法更為簡便（如可用于求逆矩陣）。,三角分解法的幾點說明（續(xù)）,6、分解法的優(yōu)點除上述2、3外，還有：a.可求解A2z=b,因為算A2計算量大，可用,b.可根據(jù)A的形狀設(shè)計算法，當A為大型稀疏，且非零元素有規(guī)律如帶狀，三對角等，作分解時能充分利用A的特點，L，U能保持A的原狀，即L與A的下三角相同，U與A的上三角形狀相同。,4、三角分解法一般也可采用選主元的技術(shù)，以使算法更具數(shù)值穩(wěn)定性。,5、也可以把矩陣A分解成一個下三角矩陣與一個單位上三角矩陣的乘積，矩陣的這種分解稱為克勞特（Crout）分解。,解線性方程組舉例,例：下述矩陣能否分解為LU（其中L為單位下三角陣，U為上三角陣）？若能分解，那么分解是否惟一？,4平方根法與改進的平方根法,對稱正定矩陣概念：,工程實際問題的計算中，線性方程組的系數(shù)矩陣常常具有對稱正定性，即其各階順序主子式及全部特征值均大于零。矩陣的這一特性使它的三角分解也有更簡單的形式，從而導(dǎo)出一些特殊的解法。,5.A的所有順序主子式均為正數(shù)，即det(Ak)>0,k=1,2,n)。,4.A的所有特征值>0；,3.A的對角線元素aii>0(i=1,2,n)；,2.A是非奇異陣，且A1也是對稱正定陣；,1.A的所有順序主子矩陣Ak(k=1,2,n)也是對稱正定陣；,若A為對稱正定矩陣，則：,4.1平方根法,定理2.2,證明：首先A可直接作LU分解，記為A=LU1，,其中：,定理2.2（續(xù)）,其中U0是單位上三角陣，則由A的對稱性可得：,再由唯一性得U0=LT，所以A=LDLT，并且這種分解是唯一的，又由于U1的對角線元素Ukk就是Gauss消元法的主元素：,由于LD1/2是下三角陣，因此有推論：,Choleskg分解1,推論,若A是對稱正定矩陣，則存在唯一的主對角線元素都為正的下三角陣L，使得：A=LLT,矩陣的這種分解稱為Choleskg分解。用比較法可以導(dǎo)出L的計算公式。設(shè)：,比較A與LLT的相應(yīng)元素，即由A=LLT可得：,計算順序按列進行。,因此：,Choleskg分解2,當完成矩陣A的Cholesky分解后，求解方程組AX=b就轉(zhuǎn)化求：,求解對稱正定線性方程組的方法稱為平方根法，也稱為Cholesky分解法，這種方法無需選主元，計算過程也是穩(wěn)定的。由于A的對稱性，平方根法的乘除運算量為n3/6數(shù)量級，約為直接分解法的一半。上機計算時，所需存貯單元也少，只要存貯A的下三角部分和右端項b，計算中L存放于A的存貯單元，y,x存放在b的存貯單元。平方根法的不足之處在于需作n次開方運算。,它們的解分別為：,平方根法舉例,用平方根法解對稱正定方程組：,例7,解：先分解系數(shù)矩陣A，只對A的下三角部分運算即可，所以只存放A的下三角部分：,4.2改進的平方根法,由定理2.2，對稱正定矩陣A又可以作如下分解：,其中，L是單位下三角陣，D是對角陣，U=DLT。,由于U=DLT，即：,比較兩邊的對應(yīng)元素可得：,的三角分解可得：,改進的平方根法說明,基于上述LDLT分解的方法稱為改進的平方根法，其乘除運算量與Cholesky分解相當，且避免了開方運算。計算順序按先行后列逐層分解計算；對稱正定陣A完成A=LDLT=LU分解后，求解方程組：Ax=b，就轉(zhuǎn)化為求解：,并且由于求y和求U的最后一列的算法完全相同，所以可將y視為U的最后一列進行計算。,按上述算法，當A為對稱正定陣時，單位下三角陣L的元素不必按緊湊格式方法去求解，而只需在求得U的第k行元素后，以它們?nèi)コ評kk即得相應(yīng)的L的第k列元素，這樣就大大減少了計算量。,改進的平方根法舉例,用改進的平方根法求解方程組：,例8,改進平方根法由于對矩陣A無正定要求（只要ukk0），(k=1,2,n)即可，而正定要求ukk>0(k=1,2,n)，因此是求解對稱方程組常用的方法。,