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

1、線性方程組的直接解法,概述 高斯消去法 矩陣分解及其在解線性方程組中的應(yīng)用 矩陣的條件數(shù)和方程組的性態(tài),September 8, 2020,2,1.1 數(shù)值解法的必要性,求：,的解 的值，根據(jù)克萊姆(Gramer)法則可 表示為兩個(gè)行列式之比：,1 概述,September 8, 2020,3,如： ,若用每秒萬(wàn)億次（1012）浮點(diǎn)乘法運(yùn)算的計(jì)算機(jī)（當(dāng)前國(guó)內(nèi)運(yùn)算速度最快）全天工作，完成這些計(jì)算約需30年。若使用一般的個(gè)人電腦，每秒完成十億次（109）浮點(diǎn)乘法運(yùn)算，則完成這些計(jì)算約需3萬(wàn)年。,計(jì)算一個(gè) 階行列式需要做 個(gè)乘法，求解上述方程共做 次乘除法。,研究數(shù)值方法的必要性,September

2、 8, 2020,4,1、直接法： 只包含有限次四則運(yùn)算。假定在計(jì)算過(guò)程中不產(chǎn)生舍入誤差，計(jì)算結(jié)果是原方程組的精確解。,2、迭代法： 基于一定的遞推公式建立逼近方程組近似解的序列。收斂性是其前提，然后還有收斂速度以及誤差估計(jì)等問(wèn)題。,Remark：由于運(yùn)算過(guò)程中舍入誤差的確存在，實(shí)際上直接方法得到的解也是方程組的近似解。,1.2 線性代數(shù)方程組的解法分類,September 8, 2020,5,設(shè)有線性方程組,為非奇異矩陣.,或?qū)憺榫仃囆问?，其中,2 高斯消去法,September 8, 2020,6,2.1 高斯順序消去法,若 令 ,用 乘 第一個(gè)方程加到第 個(gè)方程 ，并保留第一式，得,S

3、tep1：,September 8, 2020,7,Gauss順序消去法（續(xù)）,乘除法運(yùn)算次數(shù),Step2:,September 8, 2020,8,Gauss順序消去法,記為,（續(xù)2）,乘除法運(yùn)算次數(shù),September 8, 2020,9,設(shè)為,第k-1步消元完成后，有,（續(xù)3）,Step k：,September 8, 2020,10,Step K,（續(xù)4）,(i,j=k+1,n),（i=k+1,n）,乘除法運(yùn)算次數(shù),September 8, 2020,11,做完n-1步，原方程可化為同解的上三角方程組。,Gauss順序消去法,（續(xù)5）,回代過(guò)程：,（i=n-1,n-2,2，1）,回代乘

4、除運(yùn)算次數(shù)：,September 8, 2020,12,在Gauss順序消去法的消去過(guò)程中，若將右端列向量視為方程組A的第n1列，直接對(duì)該增廣矩陣A進(jìn)行行初等變換，將其變換為上三角矩陣，從而回代求解得原方程組的解。,計(jì)算量,Gauss順序消去法消去過(guò)程所需的乘除運(yùn)算次數(shù)為,總的乘除運(yùn)算次數(shù)：,取n20，則N3060,September 8, 2020,13,在消去過(guò)程中采用Gauss-Jordan消去法，即將方程組化為對(duì)角形方程組，進(jìn)而化為單位陣，則右端列向量就化為方程組的解向量。 該方法不需回代過(guò)程，但總的計(jì)算量為 n3/2+n2-n/2， 比Gauss順序消去法有所增加。,GaussJor

5、dan消去法,September 8, 2020,14,消去過(guò)程能夠?qū)嵤┑臈l件是 回代過(guò)程條件增加條件,命題1,定義,Gauss順序消去法的消元條件,September 8, 2020,15,高斯順序消去法僅對(duì)原增廣矩陣作行初等變換，故,命題證明,September 8, 2020,16,續(xù),定理2： 若系數(shù)矩陣A的各階順序主子式均不為零則可以用高斯順序消去法求解方程組A X=b。,定理1：高斯順序消去法求解方程組A X=b的消元過(guò)程能夠?qū)嵤┑某湟獥l件是系數(shù)矩陣A的前n-1個(gè)順序主子式均不為零。,September 8, 2020,17,用Gauss順序消去法求解線性方程組的條件強(qiáng)于解的存在唯

6、一性條件,斯順序消去法能進(jìn)行下去，但 或相對(duì)于,比較小時(shí)，計(jì)算產(chǎn)生的舍入誤差將導(dǎo)致計(jì)算結(jié)果誤差急劇增大，計(jì)算解與真解相差甚遠(yuǎn)，即該方法不穩(wěn)定。,Gauss順序消去法的不足,小主元是不穩(wěn)定的根源，需要采用“選主元”技術(shù)，即選取絕對(duì)值較大的元素作為主元。,September 8, 2020,18,2.2 選主元的高斯消去法,列主元消去法,在第一列中選取絕對(duì)值最大的元素,設(shè) = 調(diào)換第一行與第p行，這時(shí)的,再執(zhí)行消去法的第一步,就是原來(lái)的 ,然后,September 8, 2020,19,再考慮 右下角矩陣，在第二列選取絕對(duì)值最大的元素作為主元素,將其所在行與第二行交換，消元。依此類推直至將方程組化

7、成上三角方程組，再進(jìn)行回代就可求得解。,列主元消去法（續(xù)）,優(yōu)點(diǎn)：只要系數(shù)矩陣非奇異，消元過(guò)程就能進(jìn)行，并且主元相對(duì)較大，方法穩(wěn)定好。,September 8, 2020,20,在系數(shù)矩陣中選取絕對(duì)值最大的元素作為主元素，如,然后交換增廣矩陣的第一行與第i1行，第一列與第j1列，這時(shí),全主元消去法,實(shí)施第一次消元。,September 8, 2020,21,換把主元素移到,再消元。,消元結(jié)束后回代求解。,再考慮 右下角系數(shù)矩陣，選取絕對(duì)值最大的元素作為主元素,經(jīng)過(guò)行對(duì)換和列對(duì),的位置,全主元消去法（續(xù)）,September 8, 2020,22,評(píng)注1：全主元消去法每一步所選取的主元的絕對(duì)值不

8、低于列主元消去法的同一步所選主元的絕對(duì)值，因而計(jì)算結(jié)果更加可靠。,評(píng)注2：全主元消去法每一步選主元要花費(fèi)更多的機(jī)時(shí)，并且對(duì)增廣矩陣做了列交換，從而未知量的次序發(fā)生了變化，對(duì)編程帶來(lái)了麻煩。而列主元消去法的計(jì)算結(jié)果已比較可靠，故實(shí)用中常用列主元消去法。,特點(diǎn),September 8, 2020,23,3.1 Gauss順序消去法的矩陣形式,設(shè)方程組Ax=b的系數(shù)矩陣各階順序主子式均不為零,3 矩陣三角分解法,定義符號(hào)：,September 8, 2020,24,3.1 Gauss順序消去法的矩陣表示,September 8, 2020,25,Gauss順序消去法的矩陣表示,（續(xù)）,L是一系列單位

9、下三角矩陣逆的乘積，U是上三角陣,引理：?jiǎn)挝幌氯蔷仃噷?duì)求逆和乘積是封閉的。,L也是單位下三角陣,September 8, 2020,26,A=LU,Gauss順序消去法的矩陣表示,（續(xù)2）,September 8, 2020,27,定義1.設(shè)A為n階矩陣（n 2）,稱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è)順序主子

10、式不為零，則A有唯一的Doolittle(Crout)分解。,3.2 矩陣的三角分解,September 8, 2020,28,證明1,對(duì)Doolittle分解進(jìn)行證明。存在性：,A的順序主子式 ，根據(jù)Gauss順序消去法的消元過(guò)程有 記 得A=LU。,A=LU的唯一性證明:,三角分解條件,設(shè)A有兩個(gè)Doolittle分解 為單位下三角矩陣, 為上三角矩陣。,將矩陣進(jìn)行分塊如下：,September 8, 2020,29,矩陣的三角分解條件,證明續(xù),唯一性得證,September 8, 2020,30,存在性：,Crout分解證明,September 8, 2020,31,唯一性可類似Doolittle分解的方法可證。,Remark：實(shí)際中對(duì)A進(jìn)行三角分解并不是按上述過(guò)程進(jìn)行的，而是直接使用矩陣乘法得到。（下面以Doolittle型三角分解為例。）,Crout分解證明續(xù),September 8,