3.2.2矩阵的doolittle分解ppt课件

1、3.2.2 矩阵的矩阵的doolittle分解分解定理3.12 ,0detkkADAn的顺序主子式阶方阵若1,2,.,1,knALUALU则的分解式存在且惟一L是单位下三角矩阵U一个上三角矩阵 Gauss消元法的消元过程实际上是对线性代数方程消元法的消元过程实际上是对线性代数方程组进行一系列初等行变换的过程。由线性代数知识知，组进行一系列初等行变换的过程。由线性代数知识知，线性代数方程组的初等变换相当于对其增广矩阵实行线性代数方程组的初等变换相当于对其增广矩阵实行初等行变换，也即相当于增广矩阵左边乘以一个初等初等行变换，也即相当于增广矩阵左边乘以一个初等矩阵。矩阵。,0)(knnijDaAn的

2、顺序主子式阶方阵若1,2,.,knALUALU则由前面的分析可知， 的分解存在且惟一，即111111.knkkkknnnknnaaaAaaaaaa111.1. 1knnklll(1)(1)(1)1111( )( )( ).knkkkkknnnnaaaaaaLU111. .1. . 1rnnrlll1111.rnrrrnnnuuuuuu111111.rnrrrrnnnrnnaaaAaaaaaa也可以直接用比较法导出矩阵A的LU分解的计算公式。上式可记为1,jAa根据原理的第一行元素矩阵的乘法为111,2,.,jjaujn(,., )rjArajrn的第 行元素主对角线以右元素为rkkjrkrju

3、la11,2,.,rn,.,jrn比较第1行比较第r行1,111.1.1rnnrlll1111.rnrrrnnnuuuuuu111111.rnrrrrnnnrnnaaaAaaaaaa同样，由(1,., )irArairn可知 的第 列元素主对角线以下元素为rkkrikirula11,2,.,1rn1,.,irn1111,1,ularii 时显然2,3,.,in比较第r列综合以上分析，有111,2,.,jjaujn因此可以推导出ju1ja11,2,.,jnU的第一行1111ualii2,3,.,inL的第一列111rrjrkkjrjkal uurrirrkkrikirulula11-(1)-(2

4、)11 112,3,.,iial uinrkkrikirula11,2,.,1rn1,.,irnrkkjrkrjula11,2,.,rn,.,jrn思索11rkkjrkrjrjulau1,2,.,rn,.,jrnU的第r行rrrkkrikiriruulal111,2,.,1rn1,.,irnL的第r列-(3)-(4)称上述(1) (4)式所表示的分解过程为矩阵A的Doolittle分解(1) (4).ADoolittleALULUALULUCrout的分解中为单位下三角阵,为上三角阵。如果将中的表示为下三角阵，表示为单位上三角阵, 则称之为请找出类似于式的解，表达式分function l,u=

5、lu_Doolittle1(A)% 求可逆矩阵的LU分解% A为可逆矩阵，l为单位下三角矩阵，u为上三角矩阵n=length(A);u=zeros(n);l=eye(n);u(1,:)=A(1,:);l(2:n,1)=A(2:n,1)/u(1,1);for k=2:n for j=k:n u(k,j)=A(k,j)-l(k,1:k-1)*u(1:k-1,j); end u(k,k:n)=A(k,k:n)-l(k,1:k-1)*u(1:k-1,k:n); for i=k+1:n l(i,k)=(A(i,k)-l(i,1:k-1)*u(1:k-1,k)/u(k,k); end l(k+1:n,k)

6、=(A(k+1:n,k)-l(k+1:n,1:k-1)*u(1:k-1,k)/u(k,k);end对于线性方程组bAx 系数矩阵非奇异，经过Doolittle分解后LUA 线性方程组可化为下面两个三角形方程组bLy yUx 为中间未知量向量y213132123111.1nnnlLlllll1112131,22232,1,11,.nnnnnnnnuuuuuuuUuuu:Lyb由上一节三角形方程组的知识，不难得到的解11by 11rjjrjrrylby2,3,.,rn12122ylbyUxyAxb因此再由的解便得到的解:nnnnuyx rrnrjjrjrruxuyx11,2,.,2,1rnn213

7、132123111.1nnnlLlllll1112131,22232,1,11,.nnnnnnnnuuuuuuuUuuu上述解线性方程组的方法称为直接三角分解法的 Doolittle分解例例3.2.1 用用Doolittle分解求解方程组分解求解方程组1391444321131243301024321xxxx72510解解ju1ja11111ualii下面再用Doolittle分解方法求解14131211uuuu30102Tlll4131211T25 . 05 . 112423220uuu5 . 812110Tll423210T11/611/310343300uu11/211/300Tl431

8、00T910044000u400011rkkjrkrjrjulaurrrkkrikiriruulal111391444321131243301024321xxxx72510210031.50.521112 8.53/116/113/1 1 2/1 194得解,bLy 1234TyyyyT1611/1720101111rjjrjrrylbyby得解, yUx Txxxx4321T4321nnnnuyx rrnrjjrjrruxuyx1Doolittle分解在计算机上实现是比较容易的但如果按上述流程运算仍需要较大的存储空间:, , , ,A b x L U y 都需要单独的存储空间,(1) (4)

9、ijijl u而从的计算过程式可知11(1)jjUuaj 求出 的第一行后的存储位置即不再需要的存储位置即不再需要后的第一列求出)2(11ialLii的存储位置即不再需要后行的第求出)(rjaurUrjrj的存储位置即不再需要后列的第求出)1( rialrLirir因此可按下列方法存储数据:(),1,2,.,rjrjaujr rn(1),1,2,.,1iriralirrn有如下特点：时解三角形方程组同样,bLy 的存储位置即不再需要后求出11by的存储位置即不再需要后求出)2( ibyii,1,2,.,iibyin空出的存储位置的存储可以使用因此)1( ibyii直接三角分解的Doolittl

10、e分解可以用以下过程表示:432144434241343332312423222114131211bbbbaaaaaaaaaaaaaaaa4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaa存储单元(位置)4321444342413433323124232221141312111bbbyaaalaaalaaaluuuur4321444342413433323124232221141312112bbyyaallaalluuuluuuur4321444342413433323124232221141312113byyyallluu

11、lluuuluuuur4321444342413433323124232221141312114yyyyullluulluuuluuuuryUL,可知从上式最后一个矩阵中yUx 然后解线性方程组Doolittle分解的紧凑格式Doolittle分解的结果与Gauss消元法所得结果完全一样，但却避免了中间过程。11(),1,2,1., .ijijikkjjjUuijAaLlUuUuajn的元素等于矩阵 的对应元素减去一个内积，内积每一项是左边的同行元素与上边的同列元素的乘积。的第一行元素注1111()U/,2,3,., .jijiiijkk ijjLljiAauLlUuLlaujn的元素等于矩阵

12、 的对应元素减去一个内积，再除以与它同列的的对角元素，内积每一项是左边 的同行元素与上边的同列元素的乘积。的第一列元素注2byU可将右端向量 放于紧凑格式的最后一注3列，使得的计算按中元素一样处理。ULLU无论计算的元还是计算 的元，内积所含 和的元应该事先注4按一行一列、二行二列算出，所以计算过程可.的次序进行。定理3.2.3 设矩阵A非奇异，当且仅当矩阵A的所有顺序主子式全非零时，其Doolittle分解式存在，且分解是惟一的。 下面给出Doolittle分解存在惟一的一个充要条件31Doolittle().3O n分解的加法与乘法的计算量均为注5例例3.2.2 用紧凑格式的用紧凑格式的D

13、oolittle分解求解方程组分解求解方程组解解4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaaA7251013914443211312433010272510139142432211312423301021rju1ja11111ualii11rkkjrkrjrjulaurrrkkrikiriruulal111111rjjrjrrylbyby102100335412132122342214913772201013911624311321217121123301022r11rkkjrkrjrjulaurrrkkrikirir

14、uulal11711172010139116211211311321217121123301023r1111rjjrjrrylbyby21003103172011122217133211211111162913711410210033172011122213321721111111162941611r Lx12100331711122221332321111116429411Ux y 解4321xxxxx4321所以yU例例3.2.3 用用Doolittle分解求解方程组分解求解方程组9189271845045901269274591354321xxxx12168解解直接利用Doolittle

15、分解的紧凑格式算得918927121391890218154152/391LUyUxy回代求解方程组得：(1/9,1/9,1/9,1/9)Tx 123Doolittle12314 2521831520 xxx 用分解求例3.解.方4程2Doolittle 123142141035247212314014,10 .002472 (1,2,3) .TUyUxyx直接利用分解的紧凑格式算得因此得解求解 列选主元Doolittle分解11rkkjrkrjrjulaurrrkkrikiriruulal11在Doolittle分解(包括紧凑格式)中，会反复用到公式( )rrrrruGaussa显然相当于法

16、的顺序主元rruDoolittle仍然称为分解的顺序主元仍有可能是小主元做除数为此，也要考虑在算法中加入选取列主元111211112121222212221212.1.1.1nnnnnnnnnnnnaaaluuaaalluaaalllCrout,A CroutDoolittleTTTTTTALUAU LULA分解等价于，其中为单位下三角矩阵， 为上三角矩阵即对矩阵 作分解等价于对矩阵 作分解。Uby在解方程组时，可将右端向量 放入的最后一列，使得 的计算按 中元素一紧凑格式样处理。LUDoolittle在计算时，应，即第k步分解时先算 的第k列，后注先算 的第k行，与分解的计算次序恰算列后算行

17、好相反。 Crout 分解L为下三角矩阵，U为单位上三角矩阵三、三、 Cholesky分解与平方根法分解与平方根法 对称正定矩阵的三角分解Cholesky分解）det0,1,2,.,kAAkn且 的顺序主子式为对称正定矩阵阶矩阵若AnAAAT,0)det(则)(分解或分解可以进行因此DoolittleLUA工程实际计算中，线性方程组的系数矩阵常常具有对称正定性，即其各阶顺序主子式及全部特征值均大于零。矩阵的这一特性使它的三角分解也有更简单的形式，从而导平方根法出一些特改进殊的解法，如与的平方根法。111213122232333.nnnnnuuuuuuuUuuu112233.nnuuuu1311

18、211111123222221,1,11.1.11nnnnnnuuuuuuuuuuuu DRALU因此ALDR可以证明这种分解是唯一的可以证明这种分解是唯一的设存在另外的一个分解设存在另外的一个分解111AL D R111L D RLDR那么那么111111L LDRRD单位单位下三下三角角单位单位下三下三角角上三上三角角上三上三角角所以：所以：111,LL RR DD又因为：又因为：TAAALDR即即TTLDRR DL所以：所以：TLR1122(,.,)nnDdiag uuu21122(,.,)nndiaguuu即即TALDL1122TALD D L那么：那么：令：令：12LLD12( )T

19、TLD L综合以上分析,为对称正定矩阵阶矩阵若An则有( )TAL LTLLA 为了方便我们记：为了方便我们记：定理定理3.2.3 (Cholesky分解分解)使得正数的下三角阵元全是则一定存在一个主对角为对称正定矩阵设, , LATLLA 且该分解式唯一这种关于对称正定矩阵的分解称为Cholesky分解1111.rrrnnrnnlLlllll111111.rnrrrrnnnrnnaaaAaaaaaa设jiijaa irarArL列元素的第考察列已求出的第假设,111111.rrrnnrnnllllll111111.rnrrrrnnnrnnaaaaaaaaa1111.rnrrnrnnlllll

20、l111111al l212111all1111iial l1,2,.,in可以求出的第一列元素1ilL1rrrrkrkkall2112rrrkrkll1ririkrkkal l11rikrkirrrkl ll l,1,.,ir rn-(6)-(7)-(8)的元素的计算公式式可得由L)8()6(1111al1111lalii2,3,.,in112rkrkrrrrlal2,.,rn11ririkrkkirrral lll1,.,irn)9(1111iial l1ririkrkkall11rikrkirrrklll l316ACholesky()DoolittleCroutO n对称正定矩阵 的分

21、解的加法与乘法的计算量均为，约为分解或分解的一半，但需作注n次开方运算。ijijijlal放的储存地址可以用来存求出后当在计算机上运算时从公式中可以看出, 对称正定线性方程组的解法bAx 线性方程组阶对称正定矩阵为其中nA使得的下三角阵则存在主对角元为正数, LTLLA -(10)-(11)因而线性方程组(10)可化为两个三角形方程组L ybyxLTbxLLT)(-(12)-(13)例例3.2.7用平方根法解对称正定方程组12367597138105869xxx解解A先分解系数矩阵6757 13 8586A分解TLLL66765629174132925rrrkrkikirirrkrkrrrriilllallallalal1111211111111,bLy 其次解1111lby 692212122lylby62969*710174329101111lby iiikkikiilylby113321333lylbykkk9109),(bL29251741365629676即Tyyyy),(321T)2910,1743,69(yxLT最后解nnnnlyx iinikkkii