《应用数值分析》课件数值分析5.4线性方程组的数值解法.pptx

1、第第5章章 线性方程组的数值解法线性方程组的数值解法5.2 方程组的性态与条件数-基本的高斯消元法5.3 高斯消元法高斯列主元消去法高斯 若当消去法矩阵的三角分解5.4 基于矩阵三角分解的方法 平方根法和改进的平方根法追赶法（三对角矩阵）-SOR雅可比迭代法5.5 雅可比迭代法和高斯 赛德尔迭代法高斯 赛德尔迭代法5.6 逐次超松弛迭代法（）直接法迭代法5.1 引言5.4 基于矩阵三角分解的方法基于矩阵三角分解的方法5.4.1 矩阵的三角分解矩阵的三角分解第第1步消元步消元其中其中 211311111.1nlLll2111311111.1nlLll第第2步消元步消元2322111.1nLll1

2、2322111.1nLll其中其中 一般第一般第K 步消元步消元 其中其中 1,11.11kkkn kLll11,11.11kkkn kLll111()121111()121nnnnAL LLAbL LLb)()()3(3)3(3)3(33)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11.000.00.0.)(nnnnnnnnbabaabaaabaaaabA(n)(n),LUxb7 )()3(3)3(33)2(2)2(23)2(2211312113213231211111)(nnnnnnnnnnnijaaaaaaaaaallllllLUaA条件:.0,0,0)

3、1(11)2(2211 nnnaaa,2,1111niaalii .2,1,)()(nknikaalkkkkikik :L:U矩阵矩阵A经经Gauss消元法后得到的上三角矩阵消元法后得到的上三角矩阵.Gauss Gauss消元法的矩阵表示消元法的矩阵表示11121222.nnnnuuuuuuU2131321231111nnnlLlllll:,.由高斯消去法知 在给定条件下 分解证是存在的明.仅证唯一性（反证）11ALULU110nDAL UL U11,L U L U都可逆1111UUL L上三角阵上三角阵单位下三角单位下三角I11,UULL21313211161116111604150,2 0

4、4151 04152211041110026 lll求矩阵求矩阵 的的LU分解。分解。1472583610A 1100210301L 取取变换变换矩阵矩阵则有则有11470360611L A2100010021L 再取再取变换变换矩阵矩阵21147036001L L AU1112100210321LL L 例例解：解：100147210036321001A nnnnnnnnuuuuuuuuuullllllA3332232211312113213231211111 DoolittleDoolittle分解中分解中 LULU 元素的求解次序元素的求解次序111212122212nnnnnnuuul

5、uullu111212122212nnnnnnaaaaaaAaaa A=LU A=LU 三角分解三角分解的的紧凑格式紧凑格式1511u1 irlrru1 jru1 1 rrl1ilirl1rlrjurruju1ru121l12u22u),2,1(nj),3,2(ni),1,(nrrj ),1(nri 对对r=2,3,n,jjau11 1111ualii)(112211jrrrjrjrrjrjulululau rrrrirririiriruulululal)(112211 矩阵三角分解的紧凑格式矩阵三角分解的紧凑格式 例例5 用直接三角分解法即用直接三角分解法即Doolittle分解法解解 .2

6、01814513252321321xxx解解,11111au,21/2/112121 ual,122512212222ulau,21212au,31313au31/3/113131ual,432213212323ulau,51/)231(/)(2212313232uulal.24)4()5(335233213313333ululau2400410321153012001A.LU从而从而求解求解 ,)20,18,14(TyL,)72,10,14(TxU,)72,10,14(Ty得得求解求解.)3,2,1(Tx得得111211112121222212221212111112121121212222

7、221122111()()()()()()()()()存储形式nnnnnnnnnnnnnnnnnnnnnnnnaaauuuaaaluuaaalluauauaualauaualalau :)/:1111(1iijijikkjkjijijikkjjjkjinijnual ulal uu旧旧元元素素减减去去左左边边行行与与顶顶上上列列向向量量的的点点积积；计计算算行行不不用用除除法法，计计算算列列要要除除以以主主对对角角元元素素。18)2()2()3()4()7()7()4()2()5(解解223224 122 3227 1327 232)1(4 6123)1(5 LUA 6001303221210

8、12001223477245求的解例6：分ALU1020010112210102ALU=11020011011212101012，解解24423312624124211练习1：求的分解ALU244224423363331262105024121942112295A13121011922152442363509LU21练练2 用直接三角分解法解用直接三角分解法解 223291076824312321xxx)2()1()3()4()2()8()7()6()10(解解21 3224 326 4)1(22 2328 14)1(37 32)1(3310 LUA 30024031211301200122

9、22329113121321yyy 9149321yyy 9149324312321321yyyxxx 321321xxx 先求先求Ly=b 得得 y 再求再求 Ux=y 得得x:,A因为的各阶顺序主子式都不证等于零明4.3.1,A由定理知可惟一分解为111212122212111nnnnnnuuuluuAllu0(1,2,)iiuin且5.4.2 平方根法和改进的平方根法平方根法和改进的平方根法0(1,2,)iiuin因为，U所以可进一步分解为11211111122222111nnnnuuuuuuuUuu1DU1,.DU为对角矩阵为单位上三角阵11ALDUL DU故A 对称1TTTTAAU

10、D L1TTU DL1()TTUDLLU分解唯一1TLUTALDL上三角上三角阵阵单位下单位下三角三角实对称正定矩阵的平方根法实对称正定矩阵的平方根法:,A由的对称性和定理5.3证.3知明111,TLDAL DL必存在惟一的单位下三角矩阵和对角阵使得A正定1,2,iiDdin的对角元素都是正数121,2,iiDdin用表示对角元素为的对角阵11112222111111()()TTTAL DLL DD LL DL D则有121LL D令，为主对角线元素都是正数的下三角矩阵，TALL则得30 333222312111333231222111333231222111llllllllllllaaaaa

11、aA对称对称00 A为为3阶对称正定阵阶对称正定阵,A=L LT,怎样求怎样求L?2332322313222312131112222212111211llllllllllllll对称对称1131311121211111 ,lallalal 322232213122222221 ,allllall 33233232231 alll:column1st:column2nd:column3rd22213132322212222/)(,lllallal 2322313333llal 31例例 对下列矩阵进行对下列矩阵进行Cholesky分解分解,241111 al,1112121 lal,311313

12、1 lal,1111al,112121lal,113131lal,2212222lal ,2231213232lllal .2322313333llal 22565172624A,41172212222 lal,24/8)(2221313232 lllal349222322313333 llal 323041002LTLLA 32 A为为n阶对称正定阵阶对称正定阵,A=L LT 21l11l22l1nl2nl2kl1klkklnklnnl L L中元素的求解次序中元素的求解次序 依次求依次求L的第一列的第一列,第二列第二列,第第n列列.1 2(;,)iklik kn 元素元素A仍然存放在矩阵仍

13、然存放在矩阵 的相应位置上的相应位置上1112111112112122221222221212nnnnnnnnnnnnnnaaallllaaallllaaallll34 求求 L 的第一列的第一列 求求 L 的第二列的第二列对称正定阵对称正定阵A=L LT,求求L的计算公式的计算公式1111al),3,2(/1111nilalii 2212222lal ),3()(2221122nilllaliii )(212221 kkkkkkkklllal,ki 对对kkkkkikikiikiklllllllal)(112211 设已求得设已求得 L 的前的前k1列列,现求现求L 的第的第 k 列列(k=

14、3,n)：用平方根法求解下面对称例8正定方程组12342210223523144xxx解：2222311112121113131112222222132313333132213222212,21,214(1)(2)211,3(1),12123lalal lllaallalllllla 112211111(),()(:)jjjjjjkkjijijikjkkjjlallal lijnl2L=1112312342210223523144xxx4222211,223111223141233即TALL5,03221 解得再解，得TLybyL xyx2L=1112338 60230219122956312

15、69 Acolumn1st112121/lal 431231 /l13341 /l1111al column2nd22222221all 1)2(5222 l3222322131allll 11/)2)(4 9(32 l4222422141allll 01/)2)1)(2(42 l例例9 求求 的的Cholesky分解分解.3911 l23621 /l113131/lal 114141/lal 解解 L1423 011 39column4th44244243242241allll 1)2()0()1(6 22244 lcolumn3rd33233232231alll 2)1()4(212233

16、 l43433342324131allllll 22/)1)(0()4)(1(0(43 l解解 6023021912295631269 A L1423 011 221121212,nnndldAlld只需要存储下三角部分111111111111111jinjjiijinnnjdlllldAllddll 1,0()jjjklljk111)（jnijikk jkikk jkijjkkal d ll d ll dij11121111()(,:)()jijijikk jkkjiiiiikkklal d lij jiddal difij 对称正定阵的对称正定阵的LDLT分解中分解中L,D的计算的计算公式

17、公式111121111()(,:)()jijijikk jkkjiiiiikkklal d lij jiddal difij1111(1,2,1);/(1,2,1);(*1)jijijikjkkijijjiiiiik ikktat ljiltdjidat l(1,2,1);ijijjtl dji(避免重复计算，便于编程避免重复计算，便于编程)对称正定阵的对称正定阵的LDLT分解中分解中L,D的计算的计算公式公式23nt2nt1nt32t31t21t1dStep12dStep23dStep321l31l1nl32l2nl3nlndStepn 333231222111aaaaaaA对对称称 332

18、312211dlldld 33323122211aaaatd 3332312211attdld 3332312211aaadld储存比消去法节省一半，但比平方根法多用一个单元内存储存比消去法节省一半，但比平方根法多用一个单元内存1111(1,2,1);/(1,2,1);(*1)jijijik jkkijijjiiiiik ikktat ljiltdjidat lt 对称正定阵的对称正定阵的LDLT分解分解紧凑格式及存储紧凑格式及存储AxbTALDLTLDL xbTDL xyTLybDL xy1111;(*2)(2,).iiiikkkybybl yin1/;(*3)/(1,2,1).nnnnii

19、ikikk ixydxydl xin 对称正定阵的对称正定阵的LDLT分解分解求方程组求方程组 （改进平方根法）改进平方根法）;1,1111 adi,1,22121 ati;2,1/212122212121 ltaddtl,1,1,3213132323131 ltatati;3,5.0/,1/323231313332323213131 ltltaddtldtl 15.01111L 321D12311141328.12 4.512xxx 例例10 用用LDLT解方程组解方程组解解12311141328.12 4.512xxx 例例10 用用LDLT解方程组解方程组 128415.01111321

20、yyy 644321yyy 64415.01111321321xxx 211321xxx11 120 5.311312 4.5 或紧凑格式或紧凑格式111212122212111nnnnnnuuuluuAllu11211111122222111nnnnuuuuuuuUuu1TLU1DU49 对称正定阵的对称正定阵的LDLT分解本质上是对分解本质上是对A作作Doolittle分解分解,即即LU分解分解.LDLT分解中的 D 即LU分解中的U的对角部分LDLT分解中的 L 即LU分解中的L50 对称正定矩阵对称正定矩阵A的的LU分解分解,计算量可以计算量可以节省一半节省一半),2,1(11njau

21、jj ),2(1111niuulii 求求U的第的第1行行 求求L的第的第1列列 对称正定阵的对称正定阵的LDLT分解中分解中L,D的计算的计算 先对对称正定阵先对对称正定阵A作作LU分解分解51),1(nkiuulkkkiik )()()1()1(2211njkulululaujkkkjkjkkjkj 求求U的第的第k行行 (k=2,3,n)求求L的第的第k列列 (k=2,3,n)对称正定阵的对称正定阵的LDLT分解中分解中L,D的计算的计算节省了计算量 nnuuuD2211 求求D5.4.3 三对角线性方程组的三对角线性方程组的追赶法追赶法1111222223333311111nnnnnn

22、nnnbcxfabcxfabcxfabcxfabxf定义：形如的线性方程组称为三对角线性方程组，其系数矩阵为三对角矩阵。56 4433322211bacbacbacb122bal 443332)2(2110bacbacbcb122)2(2clbb )2(233bal 443)3(32)2(21100bacbcbcb233)3(3clbb )3(344bal )4(43)3(32)2(211000bcbcbcb344)4(4clbb 例例 四阶三对角矩阵的三角分解（四阶三对角矩阵的三角分解（Gauss消去法）消去法）57 )4(43)3(32)2(211000bcbcbcb 1111432lll

23、 4433322211bacbacbacb例例 四阶三对角矩阵的三角分解四阶三对角矩阵的三角分解单位下二对角阵单位下二对角阵上二对角阵上二对角阵 nnnnnbacbacbacb11122211 nnnucucuculll13221132111159 nnnnnbacbacbacb11122211 nnnucucuculll132211321111 三对角矩阵三角分解中三对角矩阵三角分解中LULU的求解次序的求解次序nniiullululu 1322160 nnnnnbacbacbacb11122211 nnnucucuculll13221132111111bu 122ual 1222clbu

24、对对 k=3,n 1 kkkual1 kkkkclbu 三对角矩阵三角分解中三对角矩阵三角分解中LU LU 的求解的求解 右端用矩阵乘法展开右端用矩阵乘法展开,比较两边元素得比较两边元素得追赶法追赶法LyfUxyAxfLUxf111,2,iiiiyfyfl yin1,1,1nnniiiiixyuxyc xuin追追的过程的过程:n-1赶的过程赶的过程:2n-1111122,n,niiiiiiiubaliuubl ci11112222223333111111111 nnnnnnnnnbcucabclucabclucabcluab乘除运算量乘除运算量 2n2 系数矩阵为系数矩阵为严格对角占优阵严格

25、对角占优阵时时,追赶法数值稳定追赶法数值稳定计算过程中撇开系数中大量的零计算过程中撇开系数中大量的零,使计算公式大大简化使计算公式大大简化,减少了计算量减少了计算量.追赶法总的乘除运算量追赶法总的乘除运算量 5n4.1111iiiiiiiclbuualbu线性方线性方程组的程组的直接法直接法小结小结()Gauss 0kkka是，消去法列主元消去法否全主元消去法LU 0iDA分解法顺序主子式，若 是三对角矩阵，追赶法 A对称正定，平方根法0 iDA，改进平方根法对称(正定)三角分解的计算过程三角分解的计算过程11u12u13u1nuStep121l31l1nlStep222u23u2nuStep332l2nlStep433u3nuStep53nlStep6nnuStep2n-1Step2(n-1)依次依次交替交替进行进行再计算再计算 的的列列L先计算先计算 的的行行U存储存储杜利特尔分解杜利特尔分解/*Doolittle Factorization*/：对方程组求解对方程组求解,只要得到了系数矩阵的三角分解形式只要得到了系数矩阵的三角分解形式,再利用再利用前代前代算法和算法和回代回代算法解两个三角方程组即得算法解两个三角方程组即得.