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

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