【正文】 ??? ? ? ?D U0 0A LU LD U??A symmetric and positive definite , 0 , 0t n tA A and x R x Ax? ? ? ? ?0 , 1 , ,iD i n??單位下三角 diagonal 單位上三角 西安電子科技大學理學院 主講 : 王衛(wèi)衛(wèi) ? ?00 ()tt t tA LD U U D L??單位下三角 上三角 0A L DU??單位下三角 上三角 0 tUL?LU分解的唯一性 tA L D L?1122D D D?? ? ? ?1 1 1 12 2 2 2 ttLD D L LD LD??1 2L LD?tLL?Cholesky factorization 121112122212nnuuDu???????????西安電子科技大學理學院 主講 : 王衛(wèi)衛(wèi) 用直接分解法確定 的元素的遞推公式 L11 11 21 121 22 22 212nnn n nn nnl l l ll l l lAl l l l? ? ? ?? ? ? ?? ? ? ??? ? ? ?? ? ? ?? ? ? ?? ? ? ?Obviously, if j i, then lij=0 Else ji 11 1 1jnni j i k k j i k j k i k j k i j j jk k ka l l l l l l l l?? ? ?? ? ? ?? ? ?if k j, then ljk=0 ? ?? ?12111jjj jj jkkjij ij ik jk jjkl a l i jl a l l l i j?????? ? ???????? ? ?????????西安電子科技大學理學院 主講 : 王衛(wèi)衛(wèi) Given Ax=b, where A is symmetric and positive definite, what does Cholesky factorization to do with solution of Ax=b A x b?tA LL?tL L x b?tL x y?tL y bL x y? ?? ??三角方程組，易于求解 1, , , 1ni i j i j i ijix y l y l i n????? ? ??????11, 1 , ,ii i i j j i ijy b l y l i n????? ? ??????對系數(shù)矩陣為對稱正定的線性方程組，先對 A作Chloesky分解，然后將方程組化成兩個三角方程組求解的方法稱為解線性方程組的平方根法，計算量是n3/6,是 Gauss法的一半，只要存儲下半個三角即可 西安電子科技大學理學院 主講 : 王衛(wèi)衛(wèi) Example 5 用平方根法解方程組 1234 2 2 102 2 3 52 3 14 4xxx?? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?solution A 對稱正定 2 5 21 1 0 21 2 3 3 1L y x? ? ? ? ? ?? ? ? ? ? ?? ? ?? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?西安電子科技大學理學院 主講 : 王衛(wèi)衛(wèi) diagonal 改進的平方根法 — 避 免平方根法中的開方運算 tA L D L?單位下三角 1 21 121 2 2121 11 11 1nnn n nd llld lAl l d? ? ? ? ??? ? ? ? ??? ? ? ? ???? ? ? ? ??? ? ? ? ??? ? ? ? ??? ? ? ?Obviously, if j i, then lij=0 and ljj=1。西安電子科技大學理學院 主講 : 王衛(wèi)衛(wèi) 第七章 線性方程組的直接解法 /* Direct methods for the solution of linear systems */ 線性方程組： 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? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?矩陣形式 西安電子科技大學理學院 主講 : 王衛(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 線性方程組由增廣矩陣唯一確定 Ab????西安電子科技大學理學院 主講 : 王衛(wèi)衛(wèi) 通過某種迭代系統(tǒng)（公式）求得近似解，優(yōu)點：編程簡單 缺點：存在收斂性和收斂速度問題 !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èi)衛(wèi) Gaussian elimination 通過初等變換將原方程組化成三角方程租來求解 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? ? ? ?? ? ? ??? ? ? ?? ? ? ?? ? ? ?回代求解 西安電子科技大學理學院 主講 : 王衛(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 ? 西安電子科技大學理學院 主講 : 王衛(wèi)衛(wèi) 初等行變換 ,相當于左乘初等行變換矩陣 ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ?? ?? ?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???????????????????????