線性代數(shù)方程組的解法詳解演示文稿

線性代數(shù)方程組的解法詳解演示文稿目前一頁\總數(shù)五十九頁\編于八點（優(yōu)選）線性代數(shù)方程組的解法目前二頁\總數(shù)五十九頁\編于八點考慮上三角形方程組的計算公式為：目前三頁\總數(shù)五十九頁\編于八點兩種算法的工作量(加減乘除運算次數(shù)之和)均為目前四頁\總數(shù)五十九頁\編于八點三角分解法的基本思想:記方程組可化為下面兩個易求解的三角方程組設(shè)已知方程組系數(shù)矩陣的三角分解為其中,為下三角矩陣,為上三角矩陣.目前五頁\總數(shù)五十九頁\編于八點二、高斯消去法設(shè)給定矩陣目前六頁\總數(shù)五十九頁\編于八點forforforGauss消去法的消元過程算法endendend目前七頁\總數(shù)五十九頁\編于八點LU分解求A的LU分解（L是下三角矩陣，U是上三角矩陣）目前八頁\總數(shù)五十九頁\編于八點LU分解性質(zhì)1

設(shè)向量且則存在唯一的下三角陣,滿足證明：尋找滿足條件的初等下三角陣記目前九頁\總數(shù)五十九頁\編于八點寫成分量形式：唯一確定性質(zhì)2

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

均非奇異,則存在唯一的單位下三角陣和上三角陣,滿足（矩陣三角分解的一個充分條件)證明可參照定理3.1.1.目前二十九頁\總數(shù)五十九頁\編于八點給定矩陣，如果滿足：且時，則稱為上半帶寬為，下半帶寬為的帶狀矩陣，稱為帶狀方程組；如果，則稱為的半帶寬，并稱之為等帶寬方程組；為的總帶寬。四、其他的三角分解如果矩陣可以分解為一個單位下三角陣和一個上三角陣的乘積，即，則稱此分解為Doolittle分解;如果矩陣可以分解一個下三角陣和單位上三角陣

的乘積,則稱此分解為Crout分解.目前三十頁\總數(shù)五十九頁\編于八點例如上半帶寬為2，下半帶寬為1總帶寬為3目前三十一頁\總數(shù)五十九頁\編于八點半帶寬為t的等帶狀矩陣的一般形式:目前三十二頁\總數(shù)五十九頁\編于八點（保帶狀結(jié)構(gòu)定理）設(shè)為上半帶寬為，下半帶寬為的帶狀矩陣，且其順序主子式，則

有唯一的三角分解，其中是下半帶寬為的單位下三角陣，是上半帶寬為的上三角陣。證明可根據(jù)前面講過的三角分解公式保帶狀結(jié)構(gòu)定理說明：矩陣的三角分解中，和帶外元素為零，因此不必計算，且不必參加求和運算目前三十三頁\總數(shù)五十九頁\編于八點三對角線性方程組的三對角算法（追趕法）三對角線性方程組其中目前三十四頁\總數(shù)五十九頁\編于八點根據(jù)保帶狀結(jié)構(gòu)定理，系數(shù)矩陣可作如下三角分解：目前三十五頁\總數(shù)五十九頁\編于八點三對角矩陣分解的計算公式：目前三十六頁\總數(shù)五十九頁\編于八點方程組求解的計算公式：

解方程組

解方程組“追”的過程“趕”的過程目前三十七頁\總數(shù)五十九頁\編于八點追趕法實現(xiàn)的一個充分條件(補充)設(shè)為前述三對角矩陣，且滿足下列條件：

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

選取主元的方法中計算量太大;

選取主元的過程中用到列變換,需要記錄交換信息.目前五十五頁\總數(shù)五十九頁\編于八點設(shè)，則存在排列矩陣

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

算法:

Gauss列主元消