計(jì)算方法解線性方程組的直接法

1、計(jì)算方法 第一章解線性方程組的直接法,第一章解線性方程組的直接法,計(jì)算方法 第一章解線性方程組的直接法,求解Ax=b直接法是指在無(wú)舍入誤差存在的情況下,經(jīng)過有限步運(yùn)算即可求得精確解的算法,因此又稱精確法.因?yàn)樯崛胝`差的存在,精確解也是不精確的.直接法的典型代表是Gauss消元法,計(jì)算方法 第一章解線性方程組的直接法,,,消元過程,回代過程,計(jì)算方法 第一章解線性方程組的直接法,按照矩陣變換的觀點(diǎn)來描繪消元的過程,分別表示n維

2、實(shí)和復(fù)向量空間，用R n×n 表示n×n階實(shí)矩陣空間考慮線性方程組 Ax=b其中,計(jì)算方法 第一章解線性方程組的直接法,矩陣形式為,其增廣矩陣為,計(jì)算方法 第一章解線性方程組的直接法,第一步消元過程相當(dāng)于用矩陣G1左乘增廣矩陣，即,它可以記為　　　　　 其中　　　　　是將A中的第一列中的元素a11換成0而得到的列向量，

3、 是單位矩陣I的第一列所形成的列向量，1/2是a11的倒數(shù)。這種形式的矩陣稱為Gauss矩陣。,計(jì)算方法 第一章解線性方程組的直接法,同樣，若取Gauss矩陣為,則有,從上述討論看出，消元過程等價(jià)于將方程組的增廣矩陣依次左乘相應(yīng)的Gauss矩陣，將其化為上三角形式,計(jì)算方法 第一章解線性方程組的直接法,下面，按照上述思想推導(dǎo)消元法的一般算式對(duì)于一般的矩陣A=[aij]，設(shè)a11≠0，令

4、 構(gòu)造Gauss矩陣用G1左乘a1得從而G1(A,b)具有下列形式，其中,計(jì)算方法 第一章解線性方程組的直接法,一般地，如果已經(jīng)利用Gauss矩陣G1, …,Gk-1得到,則當(dāng) 時(shí),取,計(jì)算方法 第一章解線性方程組的直接法,計(jì)算方法 第一章解線性方程組的直接法,如此繼續(xù)下去,最后,當(dāng) 時(shí)得到,其中,上述過程結(jié)束后,方程組化成

5、了具有上三角系數(shù)矩陣的方程組,當(dāng)U非奇異，即uii≠0(i=1,2, …,n)時(shí)，方程組容易求解。,計(jì)算方法 第一章解線性方程組的直接法,Gauss消元法的計(jì)算量,回代過程所用的乘除法次數(shù):消元過程所用的乘除法次數(shù):計(jì)算A(k+1)和b(k+1)時(shí),需要計(jì)算(n-k)個(gè)lik和(n-k)(n-k+1)個(gè)元素 , 而計(jì)算每一個(gè)元素只需要用一次乘(除)法,所以第k步消元過程所用乘(除)法的次數(shù)為

6、(n-k)(n-k+2)這樣，n-1步消元過程及回代過程所需的乘除法次數(shù)的總和為,計(jì)算方法 第一章解線性方程組的直接法,Gauss消元法能夠進(jìn)行到底的條件,從上述消元過程可以看出:方程組Ax=b能夠按照自然順序?qū)⑾^程進(jìn)行到底的充要條件是,為了進(jìn)一步討論這個(gè)條件與矩陣A的關(guān)系，將下式中的A(k+1)寫成分塊形式,其中Ak是A(k+1)的k階順序主子矩陣,計(jì)算方法 第一章解線性方程組的直接法,由于可將Gauss矩陣寫成其中，

7、不難驗(yàn)證因而,計(jì)算方法 第一章解線性方程組的直接法,如果將A也寫成分塊形式,其中Akk為k階矩陣,則顯然有,由于Lk是單位下三角陣，其行列式det(Lk)=1, Ak是上三角陣，所以,計(jì)算方法 第一章解線性方程組的直接法,引理1.1　按自然順序消元過程得到的均不為零的充分必要條件是順序主子矩陣非奇異，并且由上述引理，當(dāng)k=n-1時(shí)得到下面的結(jié)果定理1.1　按自然順序消元過程可以實(shí)現(xiàn)的充分必要條件是A的順序主子矩陣　　

8、　　　均為非奇異矩陣.,計(jì)算方法 第一章解線性方程組的直接法,1.2　矩陣的LU分解,定理1.2（LU分解）設(shè)A的前n-1個(gè)順序主子矩陣非奇異，則存在單位下三角陣L及上三角陣U，使　　　　　　　　A＝LU　而且這樣的分解是唯一的。,計(jì)算方法 第一章解線性方程組的直接法,LU分解（Doolittle分解）,計(jì)算方法 第一章解線性方程組的直接法,Doolittle分解算法的程序語(yǔ)言表述,對(duì)于i=1,2,…,n(1)計(jì)算U的第i行k列元

9、素，即對(duì)于k=i,i+1, …,n,計(jì)算(2)計(jì)算L的第i列k行元素，即對(duì)于k=i+1, …,n,計(jì)算其計(jì)算順序?yàn)椤11, u12, …,u1n ; l21, l31, … , ln1; u22, u23, …, u2n; l32, l42, …, ln2; …存儲(chǔ)格式為,計(jì)算方法 第一章解線性方程組的直接法,1.3 選主元的消元法,按照定理1.2，按自然順序消元的各種算法，只有當(dāng)系數(shù)矩陣的順序主子矩陣非奇異時(shí)才能應(yīng)

10、用，也就是說只有當(dāng)　時(shí)才能應(yīng)用，但是在消元過程中可能出現(xiàn)　　　的情況，這時(shí)消元就無(wú)法進(jìn)行；即使　　　，但很小時(shí)，用其作除數(shù)，會(huì)導(dǎo)致其他元素?cái)?shù)量級(jí)的嚴(yán)重增長(zhǎng)和舍入誤差的擴(kuò)散，最后導(dǎo)致計(jì)算解不可靠。例：其精確解為,計(jì)算方法 第一章解線性方程組的直接法,主元素　在Gauss消元過程中，當(dāng)　　 時(shí)，可以進(jìn)行k步消元，則 稱為消元過程的主元素（主元），主元所在的方程為主方程。主元消去法　由于在線性方程中，交換方程和未知

11、數(shù)的順序不影響方程的解，所以主元和主方程是可以選擇的。除了特殊情形外，消元過程的每一步都應(yīng)當(dāng)選主元，這樣既可以保證主元素不為0，也可以保證算法的穩(wěn)定性，這種先選主元后進(jìn)行消元的過程稱為主元消去法,計(jì)算方法 第一章解線性方程組的直接法,主元消去法分類列選主元：在變換到第k步時(shí)，選擇 中絕對(duì)值最大者為主元，然后交換它與 所在方程的位置全選主元：在變換到第k步時(shí)，選擇 中絕對(duì)值最大者為主元，然后通過行、

12、列交換將它換到　　 所在的位置上 注：由于列交換改變了x的次序，應(yīng)對(duì)交換次序作一下記錄。,計(jì)算方法 第一章解線性方程組的直接法,第一章　解線性方程組的直接法,高斯消去法矩陣的三角分解法Doolittle(杜利特爾分解)Crout（克洛脫分解）LDU分解選主元消去法,計(jì)算方法 第一章解線性方程組的直接法,高斯消去法,消去過程回代過程,計(jì)算方法 第一章解線性方程組的直接法,1）列選主元：在變換到第k步時(shí)，選擇

13、 中絕對(duì)值最大者為主元，2）全選主元：在變換到第k步時(shí)，選擇 中絕對(duì)值最大者為主元,選主元消去法,計(jì)算方法 第一章解線性方程組的直接法,LU分解（Doolittle分解）,計(jì)算方法 第一章解線性方程組的直接法,LU分解,計(jì)算方法 第一章解線性方程組的直接法,引理1.1　按自然順序消元過程得到的均不為零的充分必要條件是順序主子矩陣非奇異，并且由上述引理，當(dāng)k=n-1時(shí)得到下面的結(jié)果定理1.1　按自然順序消元過

14、程可以實(shí)現(xiàn)的充分必要條件是A的順序主子矩陣　　　　　均為非奇異矩陣.,計(jì)算方法 第一章解線性方程組的直接法,1.2　矩陣的LU分解,定理1.2（LU分解）設(shè)A的前n-1個(gè)順序主子矩陣非奇異，則存在單位下三角陣L及上三角陣U，使　　　　　　　　A＝LU　而且這樣的分解是唯一的。注: 順序主子矩陣非奇異等價(jià)于順序主子式Di不為零.,計(jì)算方法 第一章解線性方程組的直接法,緒論,學(xué)習(xí)計(jì)算方法的必要性計(jì)算方法的主要內(nèi)容誤差的來源及有關(guān)

15、誤差的概念,計(jì)算方法 第一章解線性方程組的直接法,誤差,絕對(duì)誤差相對(duì)誤差,計(jì)算方法 第一章解線性方程組的直接法,有效數(shù)字,如果　　則說x*近似表示x準(zhǔn)確到第n位，并從第n位起直到最左邊的非零數(shù)字之間的一切數(shù)字都稱為有效數(shù)字，并把有效數(shù)字的位數(shù)稱為有效位數(shù)。如果　　　則說近似值x*具有n位有效數(shù)字，這里n為正整數(shù)，m為整數(shù)。,計(jì)算方法 第一章解線性方程組的直接法,定理,若近似值x*具有n位有效數(shù)字，則其相對(duì)誤差滿足