解線性方程組的直接方法.ppt

《解線性方程組的直接方法.ppt》由會員分享，可在線閱讀，更多相關(guān)《解線性方程組的直接方法.ppt（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。

22三角分解法,2.2.1杜里特爾分解法求解線性代數(shù)議程組的三角分解法，起源于高斯消去法的矩陣形式。高斯消去法消去過程中，將變換后增廣矩陣的第k行-c倍加于第i行，相當(dāng)于左乘初等矩陳,它們都是單位下三角矩陣，即對角元全為1、對角線上方元素全為零的矩陣。因此不選主元的高斯消去法消去過程，實質(zhì)是增廣矩陳被左乘一系列倍加矩陣，變成上三角形矩陣，即,此式稱為高斯消去法的矩陣形式。由此顯然,這說明，高斯消去法的消去過程，實質(zhì)上是把系數(shù)矩陣分解為單位下三角矩陣與上三角矩陣的乘積，并且求解議程組的過程?；卮^程就是求解上三角形方程組,矩陣和也可直接算出。事實上，比較等式兩邊等行、第列元素可知,注意是單位下三角矩陣，便知,從而,同樣，因為上三角陣，知,可見,公式（2-2）和（2-3）就是計算和各元素的計算公式。實際計算時的對角元不必存放，和中肯定為零的元素也不必存放，因此的可共同存放在增廣矩陣的位置：,此時公式（2-2）、（2-3）表明，或都是原始矩陣對應(yīng)元素，減去同行左邊的元素與同列上邊的元素乘積；只是對的元素，然后需除以的對角元。計算順序，通常先算的第行，再算的第列；也可先算的第列，再算的第行，如圖21所示：,圖21計算順序,例21分解，并解方程組，其中,解按計算公式（2-2）和（2-3）,詳細(xì)計算過程如下（下文不再寫出）：,從而,回代（解方程組），得,分解且為單位下三角陣、為上三角陣，稱為杜里特爾Dolittlse)分解。利用杜里特爾分解求解方程組或，相當(dāng)于解兩個三角形方程組,解下三角方程組可以在分解時同時完成（如例21），也可獨立完成。這是因為，把寫成分量形式，就是,由此可見，,用杜里特爾分解求解方程組（2-1），所需乘除次數(shù)與高斯消去法完全一樣。其中分解需次，解需次，解需次，共計次。,它們都是單位下三角矩陣，即對角全為1、對角線上方元素全為零的矩陣。因此不選主元的高斯消去過程，實質(zhì)是增廣矩陣被左乘一系列倍加矩陣，變成上三角形矩陣,即此式稱為高斯消去法的矩陣形式。由此顯然注意是將單位矩陣,三角分解法常用于求解系數(shù)矩陣都是的若干方程式組,這是因為，一旦完成分解，只需再解個三角形方程組,解這種三角形方程組每組只需次乘除法，遠(yuǎn)比重復(fù)使用高斯消去法節(jié)省工作量。,為保證三角分解順序、穩(wěn)定進(jìn)行，與高斯消去法一樣，也可選,主元。常用列主元法。,.克洛特分解法,當(dāng)矩陣可作杜里特爾分解時,令為對角元構(gòu),成的對角陣,則,再算第行；或者先算第行，再算第列，如圖22所示?？寺逄胤纸夥ǖ挠梅斑\算量與杜里特爾分解法相同。例22用克洛特分解法求解方程組,解,得,解，得解。解畢。,為保證克洛特分解法順利、穩(wěn)定進(jìn)行，也可采用列主元法。求解步驟如下：,對做,計算結(jié)束時的第列就是解注意：例22中系數(shù)矩陣對稱：，此時就是各列除以對角元所得矩陣的轉(zhuǎn)置矩陣。一般來說對稱且可作克洛特分解，記的對角元構(gòu)成的對角陣為，各列除以對角元構(gòu)成的單位下三角矩陣為，則,可見，說明都是各列除以對角元所得矩陣的轉(zhuǎn)置矩陣；說明對稱矩陣可分解為或。因此可由直接求出，而不必再按公式（24）第二式重復(fù)計算。這樣分解可以節(jié)省次乘法，即節(jié)約大約一半的運算量。也可不存儲。,2.2.3追趕法追趕法適于求解對角方程組,這里,其實質(zhì)是高斯消去法、三角分解法的應(yīng)用。事實上，將作克特分解,則易知,回代得,。,按照這些公式次數(shù)求解的方法就稱追趕法，其中算稱追，回代稱趕，共需乘除法次數(shù)為，遠(yuǎn)比一般方程組的高斯消去法或三角分解法節(jié)省運算量。實際問題提出的三對角方程組往往嚴(yán)格對角占優(yōu)，因此不用選主元，就可保證順利、穩(wěn)定進(jìn)行。,2.2.4平方根法,平方根法適于求解對稱正定的方程組。此時的各階順序主子式，保證了主元大于零，保證了可作克特分解而且的對角元（也就是主元）全為正數(shù)。所以令，則,再記為，則上式表明。對稱正定矩陣可分解為，即下三角矩陣及其轉(zhuǎn)置矩陣的乘積，利用比較法可得元素計算公式：,利用這種分解方程組稱為平方根法或喬列斯基(cholesky)分解法。跟前種分解法一樣，求解下三角方程組可在分解的同時進(jìn)行。,例23用平方根法求解例22方程組。,解,故知,解,解畢,平方根法求解方程組，需做次乘除法和次開方，比考慮到對稱的克洛特分解法節(jié)省次乘除法但增加次開方。為避免開主，有人提出了改進(jìn)平方根法，不過它其實就是考慮到對稱的克洛特分解法，如2.2.2節(jié)最后一段所述。,