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

線性方程組的直接解法,概述高斯消去法矩陣分解及其在解線性方程組中的應(yīng)用矩陣的條件數(shù)和方程組的性態(tài),December16,2019,yfnie,2,1.1數(shù)值解法的必要性,求：,的解的值，根據(jù)克萊姆(Gramer)法則可表示為兩個行列式之比：,1概述,December16,2019,yfnie,3,如：,若用每秒萬億次（1012）浮點(diǎn)乘法運(yùn)算的計算機(jī)（當(dāng)前國內(nèi)運(yùn)算速度最快）全天工作，完成這些計算約需30年。若使用一般的個人電腦，每秒完成十億次（109）浮點(diǎn)乘法運(yùn)算，則完成這些計算約需3萬年。,計算一個階行列式需要做個乘法，求解上述方程共做次乘除法。,研究數(shù)值方法的必要性,December16,2019,yfnie,4,1、直接法：只包含有限次四則運(yùn)算。假定在計算過程中不產(chǎn)生舍入誤差，計算結(jié)果是原方程組的精確解。,2、迭代法：基于一定的遞推公式建立逼近方程組近似解的序列。收斂性是其前提，然后還有收斂速度以及誤差估計等問題。,Remark：由于運(yùn)算過程中舍入誤差的確存在，實(shí)際上直接方法得到的解也是方程組的近似解。,1.2線性代數(shù)方程組的解法分類,December16,2019,yfnie,5,設(shè)有線性方程組,為非奇異矩陣.,或?qū)憺榫仃囆问?，其?2高斯消去法,December16,2019,yfnie,6,2.1高斯順序消去法,若令,用乘第一個方程加到第個方程，并保留第一式，得,Step1：,December16,2019,yfnie,7,Gauss順序消去法（續(xù)）,乘除法運(yùn)算次數(shù),Step2:,December16,2019,yfnie,8,Gauss順序消去法,記為,（續(xù)2）,乘除法運(yùn)算次數(shù),December16,2019,yfnie,9,設(shè)為,第k-1步消元完成后，有,（續(xù)3）,Stepk：,December16,2019,yfnie,10,StepK,（續(xù)4）,(i,j=k+1,n),（i=k+1,n）,乘除法運(yùn)算次數(shù),December16,2019,yfnie,11,做完n-1步，原方程可化為同解的上三角方程組。,Gauss順序消去法,（續(xù)5）,回代過程：,（i=n-1,n-2,2，1）,回代乘除運(yùn)算次數(shù)：,December16,2019,yfnie,12,在Gauss順序消去法的消去過程中，若將右端列向量視為方程組A的第n1列，直接對該增廣矩陣A進(jìn)行行初等變換，將其變換為上三角矩陣，從而回代求解得原方程組的解。,計算量,Gauss順序消去法消去過程所需的乘除運(yùn)算次數(shù)為,總的乘除運(yùn)算次數(shù)：,取n20，則N3060,December16,2019,yfnie,13,在消去過程中采用Gauss-Jordan消去法，即將方程組化為對角形方程組，進(jìn)而化為單位陣，則右端列向量就化為方程組的解向量。該方法不需回代過程，但總的計算量為n3/2+n2-n/2，比Gauss順序消去法有所增加。,GaussJordan消去法,December16,2019,yfnie,14,消去過程能夠?qū)嵤┑臈l件是回代過程條件增加條件,命題1,定義,Gauss順序消去法的消元條件,December16,2019,yfnie,15,高斯順序消去法僅對原增廣矩陣作行初等變換，故,命題證明,December16,2019,yfnie,16,續(xù),定理2：若系數(shù)矩陣A的各階順序主子式均不為零則可以用高斯順序消去法求解方程組AX=b。,定理1：高斯順序消去法求解方程組AX=b的消元過程能夠?qū)嵤┑某湟獥l件是系數(shù)矩陣A的前n-1個順序主子式均不為零。,December16,2019,yfnie,17,用Gauss順序消去法求解線性方程組的條件強(qiáng)于解的存在唯一性條件,斯順序消去法能進(jìn)行下去，但或相對于,比較小時，計算產(chǎn)生的舍入誤差將導(dǎo)致計算結(jié)果誤差急劇增大，計算解與真解相差甚遠(yuǎn)，即該方法不穩(wěn)定。,Gauss順序消去法的不足,小主元是不穩(wěn)定的根源，需要采用“選主元”技術(shù)，即選取絕對值較大的元素作為主元。,December16,2019,yfnie,18,2.2選主元的高斯消去法,列主元消去法,在第一列中選取絕對值最大的元素,設(shè)=調(diào)換第一行與第p行，這時的,再執(zhí)行消去法的第一步,就是原來的,然后,December16,2019,yfnie,19,再考慮右下角矩陣，在第二列選取絕對值最大的元素作為主元素,將其所在行與第二行交換，消元。依此類推直至將方程組化成上三角方程組，再進(jìn)行回代就可求得解。,列主元消去法（續(xù)）,優(yōu)點(diǎn)：只要系數(shù)矩陣非奇異，消元過程就能進(jìn)行，并且主元相對較大，方法穩(wěn)定好。,December16,2019,yfnie,20,在系數(shù)矩陣中選取絕對值最大的元素作為主元素，如,然后交換增廣矩陣的第一行與第i1行，第一列與第j1列，這時,全主元消去法,實(shí)施第一次消元。,December16,2019,yfnie,21,換把主元素移到,再消元。,消元結(jié)束后回代求解。,再考慮右下角系數(shù)矩陣，選取絕對值最大的元素作為主元素,經(jīng)過行對換和列對,的位置,全主元消去法（續(xù)）,December16,2019,yfnie,22,評注1：全主元消去法每一步所選取的主元的絕對值不低于列主元消去法的同一步所選主元的絕對值，因而計算結(jié)果更加可靠。,評注2：全主元消去法每一步選主元要花費(fèi)更多的機(jī)時，并且對增廣矩陣做了列交換，從而未知量的次序發(fā)生了變化，對編程帶來了麻煩。而列主元消去法的計算結(jié)果已比較可靠，故實(shí)用中常用列主元消去法。,特點(diǎn),December16,2019,yfnie,23,3.1Gauss順序消去法的矩陣形式,設(shè)方程組Ax=b的系數(shù)矩陣各階順序主子式均不為零,3矩陣三角分解法,定義符號：,December16,2019,yfnie,24,3.1Gauss順序消去法的矩陣表示,December16,2019,yfnie,25,Gauss順序消去法的矩陣表示,（續(xù)）,L是一系列單位下三角矩陣逆的乘積，U是上三角陣,引理：單位下三角矩陣對求逆和乘積是封閉的。,L也是單位下三角陣,December16,2019,yfnie,26,A=LU,Gauss順序消去法的矩陣表示,（續(xù)2）,December16,2019,yfnie,27,定義1.設(shè)A為n階矩陣（n2）,稱A=LU為矩陣的三角分解，其中L是下三角矩陣，U是上三角矩陣。,定義2.如果L是單位下三角矩陣，U是上三角矩陣，則稱三角分解A=LU為Doolittle分解；如果L是下三角矩陣，U是單位上三角矩陣，則稱A=LU為Crout分解。高斯順序消去法對應(yīng)A的Doolittle分解。,定理3：設(shè)A為n階(n>1)矩陣，若A的前n1個順序主子式不為零，則A有唯一的Doolittle(Crout)分解。,3.2矩陣的三角分解,December16,2019,yfnie,28,證明1,對Doolittle分解進(jìn)行證明。存在性：,A的順序主子式，根據(jù)Gauss順序消去法的消元過程有記得A=LU。,A=LU的唯一性證明:,三角分解條件,設(shè)A有兩個Doolittle分解為單位下三角矩陣,為上三角矩陣。,將矩陣進(jìn)行分塊如下：,December16,2019,yfnie,29,矩陣的三角分解條件,證明續(xù),唯一性得證,December16,2019,yfnie,30,存在性：,Crout分解證明,December16,2019,yfnie,31,唯一性可類似Doolittle分解的方法可證。,Remark：實(shí)際中對A進(jìn)行三角分解并不是按上述過程進(jìn)行的，而是直接使用矩陣乘法得到。（下面以Doolittle型三角分解為例。）,Crout分解證明續(xù),December16,2019,yfnie,32,設(shè)A=LU,Step1：比較第一行元素,比較第一列元素：,直接三角分解法,三角分解（2）,Step2：比較第二行元素,比較第二列的元素：,December16,2019,yfnie,34,設(shè)U的前k-1行以及L的前k-1列已求出。,比較第k行元素,直接三角分解法,Stepk：,續(xù),續(xù)2,比較第k列元素,緊湊格式,