線性代數(shù)方程組的解法詳解演示文稿當(dāng)前第1頁\共有59頁\編于星期二\12點(diǎn)（優(yōu)選）線性代數(shù)方程組的解法當(dāng)前第2頁\共有59頁\編于星期二\12點(diǎn)考慮上三角形方程組的計(jì)算公式為：當(dāng)前第3頁\共有59頁\編于星期二\12點(diǎn)兩種算法的工作量(加減乘除運(yùn)算次數(shù)之和)均為當(dāng)前第4頁\共有59頁\編于星期二\12點(diǎn)三角分解法的基本思想:記方程組可化為下面兩個(gè)易求解的三角方程組設(shè)已知方程組系數(shù)矩陣的三角分解為其中,為下三角矩陣,為上三角矩陣.當(dāng)前第5頁\共有59頁\編于星期二\12點(diǎn)二、高斯消去法設(shè)給定矩陣當(dāng)前第6頁\共有59頁\編于星期二\12點(diǎn)forforforGauss消去法的消元過程算法endendend當(dāng)前第7頁\共有59頁\編于星期二\12點(diǎn)LU分解求A的LU分解（L是下三角矩陣，U是上三角矩陣）當(dāng)前第8頁\共有59頁\編于星期二\12點(diǎn)LU分解性質(zhì)1

設(shè)向量且則存在唯一的下三角陣,滿足證明：尋找滿足條件的初等下三角陣記當(dāng)前第9頁\共有59頁\編于星期二\12點(diǎn)寫成分量形式：唯一確定性質(zhì)2

當(dāng)前第10頁\共有59頁\編于星期二\12點(diǎn)性質(zhì)3當(dāng)前第11頁\共有59頁\編于星期二\12點(diǎn)性質(zhì)4若記,則有當(dāng)前第12頁\共有59頁\編于星期二\12點(diǎn)即單位下三角陣可以分解為一系列初等下三角陣的乘積當(dāng)前第13頁\共有59頁\編于星期二\12點(diǎn)三、三角分解的計(jì)算Gauss消去法設(shè)給定矩陣取Gauss變換矩陣則有當(dāng)前第14頁\共有59頁\編于星期二\12點(diǎn)再取Gauss變換矩陣其中當(dāng)前第15頁\共有59頁\編于星期二\12點(diǎn)設(shè)給定階矩陣記Gauss消去法的矩陣表示令Step1：如果高斯變換當(dāng)前第16頁\共有59頁\編于星期二\12點(diǎn)取其中記當(dāng)前第17頁\共有59頁\編于星期二\12點(diǎn)類似地，對(duì)中的部分重復(fù)以上做法當(dāng)前第18頁\共有59頁\編于星期二\12點(diǎn)Stepk：第k步消元過程的計(jì)算公式整個(gè)消元過程的矩陣表示上三角矩陣計(jì)算當(dāng)前第19頁\共有59頁\編于星期二\12點(diǎn)當(dāng)前第20頁\共有59頁\編于星期二\12點(diǎn)forforforGauss消去法的消元過程算法endendend當(dāng)前第21頁\共有59頁\編于星期二\12點(diǎn)經(jīng)過n-1次消元，并將存放在矩陣零元素位置當(dāng)前第22頁\共有59頁\編于星期二\12點(diǎn)LU分解的計(jì)算過程:Step1Step2Step3Step4Step5Step6Step2n-1Step2(n-1)先計(jì)算的行再計(jì)算的列依次交替進(jìn)行對(duì)方程組求解,只要得到了系數(shù)矩陣的三角分解形式,再利用前代算法和回代算法解兩個(gè)三角方程組即得.當(dāng)前第23頁\共有59頁\編于星期二\12點(diǎn)例1：用Gauss消去法求解下列方程組解：系數(shù)矩陣當(dāng)前第24頁\共有59頁\編于星期二\12點(diǎn)當(dāng)前第25頁\共有59頁\編于星期二\12點(diǎn)（Gauss消去法的實(shí)現(xiàn)條件）全不為零的充要條件是的各階順序主子式都不等于零，即證明：歸納法證明(對(duì)k歸納)當(dāng)前第26頁\共有59頁\編于星期二\12點(diǎn)設(shè)直到k-1成立,只要證明非零時(shí)，非零的充要條件是即可。在歸納假設(shè)下，Gauss消去法可進(jìn)行到第k-1步其中是對(duì)角元為的上三角矩陣矩陣的k階主子式是上三角的當(dāng)前第27頁\共有59頁\編于星期二\12點(diǎn)均為單位下三角矩陣其中因此，若矩陣的各階順序主子式均不為零，可以采用Gauss消元法進(jìn)行三角分解。結(jié)論得證當(dāng)前第28頁\共有59頁\編于星期二\12點(diǎn)若的順序主子式

均非奇異,則存在唯一的單位下三角陣和上三角陣,滿足（矩陣三角分解的一個(gè)充分條件)證明可參照定理3.1.1.當(dāng)前第29頁\共有59頁\編于星期二\12點(diǎn)給定矩陣，如果滿足：且時(shí)，則稱為上半帶寬為，下半帶寬為的帶狀矩陣，稱為帶狀方程組；如果，則稱為的半帶寬，并稱之為等帶寬方程組；為的總帶寬。四、其他的三角分解如果矩陣可以分解為一個(gè)單位下三角陣和一個(gè)上三角陣的乘積，即，則稱此分解為Doolittle分解;如果矩陣可以分解一個(gè)下三角陣和單位上三角陣

的乘積,則稱此分解為Crout分解.當(dāng)前第30頁\共有59頁\編于星期二\12點(diǎn)例如上半帶寬為2，下半帶寬為1總帶寬為3當(dāng)前第31頁\共有59頁\編于星期二\12點(diǎn)半帶寬為t的等帶狀矩陣的一般形式:當(dāng)前第32頁\共有59頁\編于星期二\12點(diǎn)（保帶狀結(jié)構(gòu)定理）設(shè)為上半帶寬為，下半帶寬為的帶狀矩陣，且其順序主子式，則

有唯一的三角分解，其中是下半帶寬為的單位下三角陣，是上半帶寬為的上三角陣。證明可根據(jù)前面講過的三角分解公式保帶狀結(jié)構(gòu)定理說明：矩陣的三角分解中，和帶外元素為零，因此不必計(jì)算，且不必參加求和運(yùn)算當(dāng)前第33頁\共有59頁\編于星期二\12點(diǎn)三對(duì)角線性方程組的三對(duì)角算法（追趕法）三對(duì)角線性方程組其中當(dāng)前第34頁\共有59頁\編于星期二\12點(diǎn)根據(jù)保帶狀結(jié)構(gòu)定理，系數(shù)矩陣可作如下三角分解：當(dāng)前第35頁\共有59頁\編于星期二\12點(diǎn)三對(duì)角矩陣分解的計(jì)算公式：當(dāng)前第36頁\共有59頁\編于星期二\12點(diǎn)方程組求解的計(jì)算公式：

解方程組

解方程組“追”的過程“趕”的過程當(dāng)前第37頁\共有59頁\編于星期二\12點(diǎn)追趕法實(shí)現(xiàn)的一個(gè)充分條件(補(bǔ)充)設(shè)為前述三對(duì)角矩陣，且滿足下列條件：

則非奇異，且特殊情況：如果三對(duì)角矩陣為嚴(yán)格對(duì)角占優(yōu)矩陣，則可以采用追趕法求解。當(dāng)前第38頁\共有59頁\編于星期二\12點(diǎn)例2：用追趕法求解三對(duì)角方程組,其中:解：注意到本例并不滿足定理’的條件,但仍然可以利用追趕法來求解.因此,定理’的條件僅是充分條件.當(dāng)前第39頁\共有59頁\編于星期二\12點(diǎn)當(dāng)前第40頁\共有59頁\編于星期二\12點(diǎn)求解方程組求解方程組當(dāng)前第41頁\共有59頁\編于星期二\12點(diǎn)§3.2選主元三角分解選主元三角分解的思想三角分解過程中存在的問題Gauss消元法完成的條件是矩陣的各階順序主子式(n=1,2,…,n-1)均不為零.三角分解過程中的除法運(yùn)算要求分母不能太小,否則將可能產(chǎn)生不穩(wěn)定情況.選主元的目的就是為了完成消元且避免不穩(wěn)定情況的發(fā)生當(dāng)前第42頁\共有59頁\編于星期二\12點(diǎn)例3：在8位制計(jì)算機(jī)上解方程組要求用三角分解方法計(jì)算。8個(gè)解：小主元可能導(dǎo)致計(jì)算失敗當(dāng)前第43頁\共有59頁\編于星期二\12點(diǎn)交換方程組的兩行8個(gè)當(dāng)前第44頁\共有59頁\編于星期二\12點(diǎn)Gauss全主元三角分解法交換單位矩陣的第列(行)和第列(行)得到的矩(初等置換矩陣)陣,稱之為初等置換矩陣.列列當(dāng)前第45頁\共有59頁\編于星期二\12點(diǎn)Step1(k=1)：第1步選擇主元尋求和滿足然后交換矩陣的第行和行，第列和列設(shè)給定階矩陣記然后按照前面討論的方法進(jìn)行三角分解.用矩陣表示:其中,為初等置換矩陣.當(dāng)前第46頁\共有59頁\編于星期二\12點(diǎn)當(dāng)前第47頁\共有59頁\編于星期二\12點(diǎn)當(dāng)前第48頁\共有59頁\編于星期二\12點(diǎn)其中當(dāng)前第49頁\共有59頁\編于星期二\12點(diǎn)第1步選主元完成后的計(jì)算公式:第1步選主元完成后的實(shí)際編程計(jì)算公式:對(duì)中右下角的矩陣重復(fù)以上做法即可.Stepk：第k(k=1,2,…,n-1)步選擇主元尋求和滿足當(dāng)前第50頁\共有59頁\編于星期二\12點(diǎn)再按照前面討論的方法進(jìn)行三角分解.用矩陣表示整個(gè)過程:第k步選主元完成后的計(jì)算公式:然后交換矩陣的第行和行，第列和列當(dāng)前第51頁\共有59頁\編于星期二\12點(diǎn)設(shè)上述過程可以進(jìn)行到第r步終止,則有令則有結(jié)論:其中為上三角陣,為單位下三角陣,且它的第列對(duì)角線以下的元素是由構(gòu)成的Gauss向量做相應(yīng)的排列得到的,故的所有元素之模均不會(huì)超過1.結(jié)論具有什么意義?當(dāng)前第52頁\共有59頁\編于星期二\12點(diǎn)令證明：則有下面利用歸納法證明具有如下形式:其中是所有元素模均小于1的階單位下三角陣,是所有元素模均小于1的階矩陣,表示階單位矩陣.當(dāng)前第53頁\共有59頁\編于星期二\12點(diǎn)k=1時(shí)結(jié)論顯然成立.現(xiàn)假設(shè)對(duì)k-1上述結(jié)論成立,則其中是由交換了第1行和行得到的,且當(dāng)前第54頁\共有59頁\編于星期二\12點(diǎn)Gauss全主元三角分解法求解方程組設(shè)已經(jīng)得到三角分解式則原方程組等價(jià)于令則注意到的計(jì)算可在三角分解的過程中來完成Gauss全主元三角分解法存在的問題

選取主元的方法中計(jì)算量太大;

選取主元的過程中用到列變換,需要記錄交換信息.當(dāng)前第55頁\共有59頁\編于星期二\12點(diǎn)設(shè)，則存在排列矩陣

,以及單位下三角陣和上三角陣,使得而且的所有元素均滿足,的非零對(duì)角元的個(gè)數(shù)正好等于矩陣的秩.(排列矩陣)有限個(gè)初等置換矩陣的乘積稱之為排列矩陣.全主元Gauss消去法的算法見教材:算法3.2.1當(dāng)前第56頁\共有59頁\編于星期二\12點(diǎn)Gauss列主元三角分解法Gauss列主元三角分解法與全主元三角分解法的區(qū)別就是在消元過程中只作行變換,這樣即可以減少選擇主元時(shí)的邏輯計(jì)算量,又可以避免記錄交換信息.Stepk：第k(k=1,2,…,n-1)步選擇主元尋求滿足用矩陣表示整個(gè)過程:則有結(jié)論:當(dāng)前第57頁\共有59頁\編于星期二\12點(diǎn)Gauss列主元三角分解法求解方程組設(shè)已經(jīng)得到三角分解式則原方程組等價(jià)于令則注意到的計(jì)算仍在三角分解的過程中來完成教材中算法3.2.2為列主元Gauss消去法的算法當(dāng)前第58頁\共有59頁\編于星期二\12點(diǎn)

算法:

Ga