方程组直接三角分解法

第四章方程组的直接解法4.2直接三角分解法4.2.3平方根法4.2.1一般矩阵的直接三角分解法4.2.2三对角方程组的追赶法第四章方程组的直接解法4.2直接三角分解法4.2.1一般矩阵的直接三角分解法本节讨论矩阵A的三角分解法的直接计算以及直接利用A的三角分解式来求解方程组。1.不选主元的三角分解法),(),(),(ijijijuUlLaA设A=LU，记其中L为单位下三角阵，U为上三角阵。我们可直接给出L和U的元素的计算公式。由A的第1行和第1列可计算出U的第1行和L的第1列，即（4.2.1）（4.2.2）如果U的第1至k-1列和L的第1至k-1列已经算出，则由,,,1,,1nkkjulakrrjkrkj111111,1,2,,,,2,3,,.jjkkuajnalknu第四章方程组的直接解法可得U的第k行元素同理，由ukj=akj-,j=k,k+1,···,n。（4.2.3）11krrjkrulakj=,i=k+1,k+2,···,n,krrkirul1可得L的第k列元素交替使用（4.2.3）和（4.2.4），就能逐次计算出U（按行）和L（按列）的全部元素，而且可以把它们存放在矩阵A对应的位置上（L的对角线元素不必存放）。这就完成了A的LU分解。krrkirul1lik=(aik-)/ukk,i=k+1,k+2,···,n。由（4.2.1）-（4.2.4）求得L和U后，解方程组Ax=b接化接为求解LUx=b，若记Ux=y，则有Ly=b。于是可分两部解方程组LUx=b，只要琢次向前代入的方法即可求得y。第二步求解Ux=y，只要琢次第四章方程组的直接解法用向后回代的方法即可求得x。设x=（x1，x2，···xn)T,y=（y1,y2,···yn)T,b=（b1，b2，···bn)T,则有计算公式1111,...,2,1,yirririiniylbybniriiririinnnnniuxuyxuy1n1,...,2,1,//x（4.2.5）（4.2.6）以上解方程组的计算与顺序Gauss消去法相当。如果有一系列方程组，其系数距阵都是相同的，右端向量b不同，则只须进行一次LU分解计算。上述解方程的方法称为LU分解法，也称Doolittle方法。例4.5用LU分解法求解第四章方程组的直接解法551631011411014211264321xxxx解由（4.2.1）-（4.2.4）计算可得741911091037313231039101615161314126,1111u由（4.2.5）计算得由（4.2.6）计算得Ty=(6,3,23/5,-191/74) Tx=(1,-1,1,-1)第四章方程组的直接解法2.列选主元的三角分解法设从A=A（1）开始已完成k-1步分解计算，U的元素（按行）和L的元素（按列）存放在A的位置，得到)()(1,21)()(1,,11,1322222111211knnknkknnnkknkkkkknkkknnaalllaaluuluuluuuA～该矩阵与顺序Gauss消去法中得到的A（k）是不同的，这种存储方式的形式称为紧凑形式。第四章方程组的直接解法当i=k时，si对应于（4.2.3）中的ukk，它可能不宜在（4.2.4）作除法。当i=k+1,k=2,….n，si对应于（4.2.4）中的分子。记,maxinikikssnkkiulasrkkrirkiki,,1,,11)(现做第k行计算，令),()(~)(kkbA交换的第i行与第行的位置，但每个位置上仍用原记号。然后仍按（4.2.3）计算，算出U的第k行。的计算可用这就算出了L的第k行。nkkjukj,,2,1,iklkinkkissiki,...,2,1,以上分解过程经过n-1步，可得PA=LU，因为b也参加换行计算，所以在其位置上得到Pb。最后再分两步求解方程组LUx=Pb，即求解Ly=Pb和Ux=y。第四章方程组的直接解法例4.6用列选主元的三角分解法解182014252513321321xxx39/21639/7213/53/13/143/43/133/220513),()3()3(~bA由此知,18253/214323/120513),()2()2(~bA由于s2=5/3s3=13/3,，所以第二步分解计算前要进行交换，分解计算结果为解第一步用列选主元后的分解计算结果第四章方程组的直接解法113/53/113/21L,39/723/43/13513,U0011000101223IIp由于方车程组的右端参与了消元计算，所以Ly=Pb的解为y=b（3）=（20，14/3，216/39）T。解Ux=y得x=（1，2，3）T4.2.2三对角方程组的追赶法设有方程组Ax=d,其中d=(d1d2,…dn)T,系数矩阵A是三对角形矩阵(4.2.7)nnnnnbacbacbacbA111211第四章方程组的直接解法nnnuccucuUlllL1221132,1111如果A满足Gauss消去发的条件,可用LU分解发求解.并且,L和U有如下形式(4.2.8)利用(4.2.7)和(4.2.7)可得由此可求得L和U的所有元素.。解原方程组Ax=b可分为两步Ly=d和Ux=y,计算公式为niclbuniualbuiiiiiii,...3,2,,...3,2,/1111(4.2.9)第四章方程组的直接解法1,...2,1,/)(/,...3,2,1111nniuxcyxuyxniyldydyiiiiinnniiii(4.2.10)称为(4.2.9)、(4.2.10)和(4.2.11)为求解三对角形方程组的追赶法,又称为Thomas算法。追赶发能实现的条件是ui≠0，i=1,2,…,n.。下面给出追赶发一个的充分条件。niucii,2,1,10niabuabiiiii,...2,1,定理4.6设三对角矩阵A有(4.2.7)的表达式,且满足则A非奇异,且有110,0,,0,2,3,...nniiiiibcbabacacin第四章方程组的直接解法iiiiiiiiiiabucabclbu111iicu1/,0iiiucu.另一方面,有利用条件可得到,故,111cbu1/,0111iiucuiiiiiiiiiiabucabclbu111证用归纳法。对i=1,有现设,我们有所以因为detA=u1u2…un，所以detA≠0。定理得证。在定理4.6的条件下，追赶法可以进行计算，并且计算过程的中间变量有界，不会产生大的变化，可以有效计算出结果。在定理4.6的条件下，要求ai和ci非零。若有某个ai（或ci）为零，则三对角方程组可以化为两个低阶的非耦和的方程组。第四章方程组的直接解法例4.7用追赶发求解三对角方程组Ax=d，其中解由(4.2.9)得231,4114414dA追赶法公式简单，计算量和存储量都很小。整过求解过程仅须5n-4次乘除和3（n-1）次加减法运算，仅需4个一为数组存储系数矩阵的元素和右端向量，，可分别存放在表示系数矩阵元素的数组和右段向量的位置。iliuix由(4.2.10)和(4.2.11)得733.3175.314,12667.0125.01UL第四章方程组的直接解法,111221111nnnnnnbaccbacbaacbA对另一类方程组，在周期样条插值等为题遇到的循环三对角方程组Ax=d，其中TTXy)7679.0,0714.1,5179.0(,)8668.2,25.3,1(我们也可用三对角分解的方法。从矩阵零元素的位置不难验证L和U可写成下面的形式：,111112132nnlllLnnnnucucucuU111222111由此不难得到L和U的元素的计算公式，这里不在介绍。第四章方程组的直接解法当A为对称正定矩阵时，对A可直接作LU分解。由（4.1.8）式可得下面的定理。定理4.7设A∈Rn×n，A=AT且A的顺序主子式Di≠0（I=1,2,…,n），则存在唯一的单位下三角阵和三角阵，使A=LDLT定理4.8设A∈Rn×n，当A为对称正定矩阵，则存在唯一的对角元素为正的下三角阵L，使A=LLT4.2.3平方根法),,,(2121nddddiagD证由（4.7）定理可知A=L1DLT1，其中L1为单位下三角阵，D=diag(d1,d2…dn)。若令U=DLT1，则A=L1U为A的Dolittle分解U的对角元即为D的对角元。因此A的顺序主子式Dm=d1d2…dm，m=1，2，…n。因为A正定，所以Di0,i=1，2，…n。由此推出dvi0，i=1，2，…n。记第四章方程组的直接解法令，则有由分解式的唯一性可得（4.2.3）分解式的唯一性。定理得证。称（4.2.13）式为矩阵A的Cholesky分解。利用A的Cholesky分解式来求解方程组Ax=b的方法称为Cholesky方法或平方根法，这是因为计算过程含开方运算。211LLLTTTLLDLDLLDDLA))((211211121211TDLL11nnnnllllllL21222111设A=（aij），由式（4.2.13）可得njjillllajjijjkjkikij,2,1,11第四章方程组的直接解法这样，可以从j=1直到j=n逐列算出L的元素,再求解下三角方程组Ly=b和上三角方程组LTx=y。计算公式为1,,2,1,/)(,/,,3,2,/)(,/1111111nnilllyxlyxnilllbylbyiinkkkiiinnnniijkkikii按逐列计算L的元素的计算步骤,设第1列至第j-1列已经计算得到,则有njjilllallaljjjkjkikijijjkjkjjjj,,2,1,/,1121112（4.2.15）（4.2.14）第四章方程组的直接解法解不难验证系数矩阵是对称正定的，按（4.2.14）和（4.2.15）依次计算得.25.15.375.2,5.075.225.4,64221321321xxxxxxxxx例4.8用平方根法求解15.15.025.02L由（4.2.14）可得由此推出，所以平方根法的中间量得以控制。不必选主元。,12jkjkjjlajkljkaljjjk,,2,1,平方根法的原理基于矩阵的LU分解,所以它也是Gauss消去法的变形.但由于利用了矩阵正定的性质,减少了计算量。平方根法的乘除法运算次数为(n3+9n2+2)/6,加减法次数为(n3+6n2-7n)/6。另外还有n次开方运算，其所含乘除法和加减法次数可分别看成n的常数倍。平方根