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

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

設(shè)向量且則存在唯一的下三角陣,滿足證明：尋找滿足條件的初等下三角陣記現(xiàn)在是9頁\一共有59頁\編輯于星期三寫成分量形式：唯一確定性質(zhì)2

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

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

的乘積,則稱此分解為Crout分解.現(xiàn)在是30頁\一共有59頁\編輯于星期三例如上半帶寬為2，下半帶寬為1總帶寬為3現(xiàn)在是31頁\一共有59頁\編輯于星期三半帶寬為t的等帶狀矩陣的一般形式:現(xiàn)在是32頁\一共有59頁\編輯于星期三（保帶狀結(jié)構(gòu)定理）設(shè)為上半帶寬為，下半帶寬為的帶狀矩陣，且其順序主子式，則

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

解方程組

解方程組“追”的過程“趕”的過程現(xiàn)在是37頁\一共有59頁\編輯于星期三追趕法實(shí)現(xiàn)的一個(gè)充分條件(補(bǔ)充)設(shè)為前述三對角矩陣，且滿足下列條件：

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

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

選取主元的過程中用到列變換,需要記錄交換信息.現(xiàn)在是55頁\一共有59頁\編輯于星期三設(shè)，則存在排列矩陣

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

算法:

Gauss