【正文】 西安電子科技大學(xué)理學(xué)院 主講 : 王衛(wèi)衛(wèi) 第七章 線(xiàn)性方程組的直接解法 /* Direct methods for the solution of linear systems */ 線(xiàn)性方程組： 11 1 12 2 1 121 1 22 2 2 21 1 2 2nnnnn n nn n na x a x a x ba x a x a x ba x a x a x b? ? ? ???? ? ? ????? ? ? ? ??11 12 1 1 121 22 2 2 212nnn n nn n na a a x ba a a x ba a a x b? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?矩陣形式 西安電子科技大學(xué)理學(xué)院 主講 : 王衛(wèi)衛(wèi) Homogeneous term Coefficient matrix A x b?or 11 12 1 1 121 22 2 2 212,nnn n nn n na a a x ba a a x bA x ba a a x b? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?Unknown variables 線(xiàn)性方程組由增廣矩陣唯一確定 Ab????西安電子科技大學(xué)理學(xué)院 主講 : 王衛(wèi)衛(wèi) 通過(guò)某種迭代系統(tǒng)（公式）求得近似解，優(yōu)點(diǎn)：編程簡(jiǎn)單 缺點(diǎn)：存在收斂性和收斂速度問(wèn)題 !0solut i on A? ? ?How to get the solution？ Coefficient matrix A 低階稠密陣 高階稀疏陣 small dense matrix large sparse matrix Direct methods Iteration methods Gaussian elimination 列 /行 /完全主元素 (pivoting)消去法 GaussJordan elimination Square root/improved square root methods 追趕法 Jaccobi iteration GaussSidel iteration SOR Existence and uniqueness of the solution？ ii Dx D?Cramer rule: Computation cost: (n+1)! 上萬(wàn)階，零元素很多，非零元素很少 非零元素較多，零元素較少 經(jīng)過(guò)有限步算術(shù)運(yùn)算直接求得精確解（在沒(méi)有舍入誤差的情況下），但實(shí)際上機(jī)器總存在舍入誤差，因此求得的是近似解 ? 西安電子科技大學(xué)理學(xué)院 主講 : 王衛(wèi)衛(wèi) Gaussian elimination 通過(guò)初等變換將原方程組化成三角方程租來(lái)求解 1 2 3231 2 36 ( 1 )4 5 ( 2 )2 2 1 ( 3 )x x xxxx x x? ? ??? ???? ? ? ??1231 1 1 64 1 52 2 1 1xxx? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?2*(1)+(3) 1 2 323236 ( 1 )4 5 ( 2)4 11 ( 3 )x x xxxxx? ? ??? ???? ? ? ? ??1231 1 1 64 1 54 1 11xxx? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ?? ? ?? ? ? ? ? ?(2)+(3) 1 2 32336 ( 1 )4 5 ( 2)2 6 ( 3 )x x xxxx? ? ??? ???? ? ? ??1231 1 1 64 1 526xxx? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?123123xxx? ? ? ?? ? ? ??? ? ? ?? ? ? ?? ? ? ?回代求解 西安電子科技大學(xué)理學(xué)院 主講 : 王衛(wèi)衛(wèi) Step 1. Denote Ax=b as (1 ) (1 )A x b?( 1 ) ( 1 ) ( 1 ) ( 1 )( ) ( ) , ( ) ( )ij ij i iA a a A b b b b? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ?? ?? ?1 1 1 111 12 1 111 1 1 1221 22 2 21 1 1 112nnnn n nn na a a bxxa a a bxa a a b? ? ? ???? ? ? ???? ? ? ????? ? ? ???? ? ? ???? ? ? ?????? ? ? ?Suppose (1)11 0a ?let ( 1 ) ( 1 )1 1 11iil a a?li1*(1)+(i), i=2,…, n ? ? ? ? ? ?? ? ? ?? ? ? ?? ?? ?? ?1 1 1 111 12 1 112 2 2222 2 22 2 22nnnn nn na a a bxxa a bxa a b? ? ? ???? ? ? ???? ? ? ????? ? ? ???? ? ? ???? ? ? ?????? ? ? ?( 2 ) ( 2 )A x b?General procedure of Gaussian elimimation ? 西安電子科技大學(xué)理學(xué)院 主講 : 王衛(wèi)衛(wèi) 初等行變換 ,相當(dāng)于左乘初等行變換矩陣 ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ?? ?? ?1 1 1 111 12 1 11 1 1 111 21 22 2 21 1 1 112nnn n nn na a a ba a a bAba a a b?????? ?????????li1* row 1+ row i, i=2,…, n formulae ? ? ? ? ? ?? ? ? ? ? ?2 1 1112 1 111, , 2 , ..., 2 , ...,ij ij i ji i ia a l a i j nb b l b i n? ? ? ?? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ?? ?? ?? ?1 1 1 111 12 1 12 2 222 22 2 22 2 2200nnn nn na a a ba a bAba a b?????? ???????Directly replace with 0 Leave alone Need to be updated ? ? ? ? ? ? ? ?2 2 1 11A b L A b? ? ? ??? ? ? ?Convenient in using Matlab,Mathmatica,Maple 1121110111... 10111... 0101nilllL???????????????????????????????????????????????????11, 2 , .. .,101i inl?????? ??????第 i行第 1列 西安電子科技大學(xué)理學(xué)院 主講 : 王衛(wèi)衛(wèi) Step k. After k1 eliminations, we have ( ) ( )kkA x b?? ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ?? ?? ?? ?? ?1 1 1 1 111 12 1 1 112 2 2 222 2 2 2 2knknk k kkk k k n kk k knnk nn na a a a bxa a a x bxa a bxa a b? ? ? ???? ? ? ???? ? ? ???? ? ? ???? ? ? ????? ? ? ???? ? ? ???? ? ? ???? ? ? ?????? ? ? ?? ? ? ?let Suppose () 0kkka ? ( ) ( )kkik ik k kl a a?lik*(k)+(i), i=k+1,…, n ? ? ? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ?? ?? ?? ?? ?? ?1 1 1 111 12 1 112 2 222 2 2211 1 111 1 1 111nnk k k kkk k k k k n kk k kkk k k n kkknnn na a a bxa a bxxa a a bxa a bxab?? ? ??? ? ? ???? ? ? ???? ? ? ???? ? ? ???? ? ? ???? ? ? ???? ? ? ????? ? ? ???? ? ? ???? ? ? ???? ? ? ???? ? ? ???? ? ? ?? ? ? ?( 1 ) ( 1 )kkA x b???西安電子科技大學(xué)理學(xué)院 主講 : 王衛(wèi)衛(wèi) lik* row k+ row i, i=k+1,…, n ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ?? ?? ?? ?? ?1 1 1 1 111 12 1 1 12 2 2 222 2 2 2knknkkk k kk k k n kk k knk nn na a a a ba a a bAba a ba a b???????? ???????初等行變換 ,相當(dāng)于左乘初等行變換矩陣 Leave alone Need to be updated ? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ?? ?? ?? ?? ?? ?1 1 1 111 12 1 12 2 222 2 21111 1 11 1 1 11 1 11nnkk k k k kk k k k k n kk k kk k k n kk k knk nn na a a ba a bAb a a a ba a ba a b???? ? ?? ? ? ?? ? ?????????? ?????????Directly replace with 0 第 i行第 k列 1111ikl???????????????formulae ? ? ? ? ? ?? ? ? ? ? ?( ) ( )11, 1 , .. ., , 1 , .. ., 1 , .. .,kkik ik k kk k kij ij ik k jk k ki i ik kl a a i k n