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

《線性方程組的直接解法.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《線性方程組的直接解法.ppt（36頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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