解三对角方程组的追赶法

1第二章解线性方程组的直接方法)232(11111213433323232221212111nnnnnnnnnnnndxbxadxcxbxadxcxbxadxcxbxadxcxb2.3.4解三对角方程组的追赶法在数值计算中，如三次样条插值或用差分方法解常微分方程边值问题，常常会遇到求解以下形式的方程组2第二章解线性方程组的直接方法,AxdnnnnbacbcbacbacbA113332221100如果用矩阵形式简记为其中系数矩阵称为三对角方程组.是一种特殊的稀疏矩阵.它的非零元素集中分布在主对角线及其相邻两条对角线上，称为三对角矩阵.方程(2-23)(2-24)p53第二章解线性方程组的直接方法100111211nllL),,3(01nili)2(23)2(232)2(22dxaxaGauss消去法用于三对角方程组时过程可以大大简化.具体地说，第一次消元只要对第2个方程进行，也就是矩阵其中,第一次消元后，第2个方程变成4第二章解线性方程组的直接方法2L),,4(02niliUL、231111nlOLlOl因而在第二次消元时只要对第3个方程进行消元，即是单位下二对角阵中.因此类推可以得出,三对角矩阵作三角分解时,矩阵的形式也比较简单，其中5第二章解线性方程组的直接方法nnurruruU12211000)()1,,3,2(0011nniiiiiabnicacabcb定理2.2设矩阵（2-24）满足下列条件：是上二对角阵.p26第二章解线性方程组的直接方法10101132nlllLUAnnuccucu1221100)1,,2,1(nici其中则它可以分解为为矩阵（2-24）中所给出,且分解是唯一的.(2-25)nnnnbacbcbacbacbA11333222110011bu1iiialu1iiiibclu7第二章解线性方程组的直接方法11bu)1,,2,1(0niui11ub[证明]将式(2-25)右端按乘法规则展开,并与A进行比较,得如果，则由上式可得（2-26）1iiiibclu1iiialu(2,3,,)in(2,3,,)in1iiiiubcl1iiilaup118第二章解线性方程组的直接方法1knnnkkkkkkbaccbacucuA111111)(00按Gauss消去法步骤易得，经过次消元后,方程组（2-23）的系数矩阵变成9第二章解线性方程组的直接方法),,2(11nkuacbukkkkk011bu11222,,bcbac121212bbbabc12221caubu其中由A满足条件（*），显然有又因为从而有于是1212cabc12121bbcab12121bbcab121bcb2c10第二章解线性方程组的直接方法02u)2(A0iu(1,2,,).indLyyUxdLy11,yd故且矩阵仍满足条件（*）.依次类推可得出因此由式(2-26)唯一地确定了L和U当矩阵（2-24）按式（2-26）可化为求解方程组和解得（2-27）122310000100001000001nnylyLylyl计算进行三角分解后,求解方程组（2-23）(2,3,,)kn1,kkkkydly11第二章解线性方程组的直接方法,Uxy,nnnyxu再解得方程组（2-23）的解:(2-28)按上述过程求解三对角方程称为追赶法,式（2-26）和式（2-27）结合称为“追”的过程,相当于Gauss消去法中的消元过程.式(2-28)称为“赶”的过程,相当于回代过程.111222100nnnucxucxUxycxu(1,2,,1)knn1(),kkkkkxycxup8712第二章解线性方程组的直接方法21111(,,),(,,),(,,),(,,),nnnnaaabbbcccdddnni,,3,2)(1iiiilaba2．对1.输入算法2.2)(1iiiiiubacb)(1iiiiiyddad13第二章解线性方程组的直接方法)(.3nnnnxdbd)()(1,,2,11iiiiiixdbdcdnnixd5．输出4.对,停机.追赶法的基本思想与Gauss消去法及三角分解法相同,只是由于系数中出现了大量的零，计算中可将它们撇开,从而使得计算公式简化，也大大地减少计算量.其乘除运算量为45n14第二章解线性方程组的直接方法§2.4平方根法与改进的平方根法A,LTLLAL的对角元素皆为正数。工程实际问题的计算中，线性方程组的系数矩阵常常具有对称正定性，矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法。2.4.1平方根法（Cholesky分解法）定理2.3设是对称正定矩阵,则存在唯一的非奇异下三角阵使得（2-29）且15第二章解线性方程组的直接方法ULA~L~U11(,,),nnDdiaguuPDPLA~ATTTAPDL[证明]因为A由定理2.1,矩阵A其中角矩阵,且为单位下三角矩阵。则为上三角阵，令因为对称正定,其各阶顺序主子式大于零,存在Doolitle分解，即为单位上三对称，故有1,PDUALDP16第二章解线性方程组的直接方法,TPLTAPDP,xA11()TTTxDxxPAPxDD),,(~11nnuudiagD由Doolitle分解的唯一性，得对任意非零向量于是由即正定，所以的对角元素均为正数。令即是正定的1,yPx11()TPxAPxTyAy0TTTAPDLALDP17第二章解线性方程组的直接方法TTAPDDPTPDL)~(,GLTTGGLLA111()()TTTTLGLLLG其中唯一性。假设存在非奇异下三角阵则为非奇异下三角阵,且对角元素皆为正数.元素皆为正数，且使得其对角于是有11()TTLGGG1LG()TDPDPTLLTAPDP18第二章解线性方程组的直接方法1)(TTGLGL111TTL(G)LGLG因为是上三角阵，即，与假设矛盾。上式必得是下三角阵,故由L11212212000nnnnlllLlll矩阵的这种分解称为Cholesky分解。用比较法可以导出设的计算公式.TLLAp14I20第二章解线性方程组的直接方法ATLL11221()(1,2,,)kkkkkkjjlalkn010.j),,3(),,3,2(222111nillnillii比较与这里规定计算顺序是按列进行，即的相应元素，可得（2-30）1112111112112122221222221212000000nnnnnnnnnnnnnnaaallllaaallllaaallll1221kkkkjkkjall11()/(1,,)kikikijkjkkjlalllikn21第二章解线性方程组的直接方法bAx,Lyb11()/(1,2,,)(231)kkkkjjkkjyblylkn当矩阵A完成Cholesky分解后，求解方程组就转化为依次求解方程组它们的解分别为1()/(,1,,1)(232)nkkjkjkkjkxylxlknnTLxy即111121222212000,nnnnnnlybllyblllyb112111122222000nnnnnnlllxyllxylxyTLLA22第二章解线性方程组的直接方法63nLCholesky分解法。这种方法无需选主元，计算过程也是单元也少，只要存贮A的下三角部分和右端项b中存放在A的存贮单元，y,x存放在b但这种方法在求L时需作n了计算量.求解线性方程组的上述方法称为平方根法，也称为稳定的.由于A的对称性,平方根法的乘除运算量为数量级，约是Gauss消去法的一半.上机计算时,所需存贮,计算的存贮单元.次开方运算，这样又增加23第二章解线性方程组的直接方法123121332352233127xxxxxxx[解]显然系数矩阵是正定矩阵,设例用平方根法解线性方程组1111213121222232313233333230022000301200llllAllllllll1111213121222232313233333230022000301200llllAllllllll113,l212111/lal313111/3/3,lal122222221()lal3232312122()/lalll122233333132()lall111212223132333005037lyllyllly解得由112131112232223333000lllxyllxylxy由解得31,3x21,2x11x15,3y21,6y313y1242(2),332(02)/6312(1236)32/3,25第二章解线性方程组的直接方法(TLDLTLDLALD2112100101nnlLll),,(1ndddiagD2.4.2改进的平方根法其中为单位下三角矩阵，为对角阵.记定理2.3的证明过程表明，对称正定矩阵A又可以做如下分解：法)26第二章解线性方程组的直接方法1211212212100110011001TnnnnnALDLdllldllld注意到1,jjl由比较法得1()()nTkkkjjkjaLDL1kkjjkjjldl121kjkjkjdld121kkkkkjjjdald21kjkjjdl0,jkljk27第二章解线性方程组的直接方法1211212212100110011001TnnnnnALDLdllldllld1,0,jjjklljk1()()nTikijjkjaLDL1kijjkjjldl11kijjkjikkkkjldlldl11(1)(,,)kikikijjkjkjlaldldikn28第二章解线性方程组的直接方法TLDL由比较法可以导出分解的计算公式：nk,,2,1121kkkkkjjjdald32211),,3(),,3,2(dnildnildii对（2-33）计算顺序如下：11()(1,,)kikikijjkjkj