3.2.2矩阵的doolittle分解经典实用

《3.2.2矩阵的doolittle分解经典实用》由会员分享，可在线阅读，更多相关《3.2.2矩阵的doolittle分解经典实用（35页珍藏版）》请在装配图网上搜索。

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

2、增广矩阵左边乘以一个初等左边乘以一个初等矩阵矩阵。3.2.2 矩阵的doolittle分解111. .1. . 1rnnrlll1111.rnrrrnnnuuuuuu111111.rnrrrrnnnrnnaaaAaaaaaa也可以直接用比较法导出矩阵A的LU分解的计算公式。上式可记为1,jAa根据原理的第一行元素矩阵的乘法为111,2,.,jjaujn(,., )rjArajrn的第 行元素主对角线以右元素为rkkjrkrjula11,2,.,rn,.,jrn比较第1行比较第r行3.2.2 矩阵的doolittle分解1,111.1.1rnnrlll1111.rnrrrnnnuuuuuu111

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

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

5、olittle1(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)=(A(k

6、+1:n,k)-l(k+1:n,1:k-1)*u(1:k-1,k)/u(k,k);end3.2.2 矩阵的doolittle分解对于线性方程组bAx 系数矩阵非奇异，经过Doolittle分解后LUA 线性方程组可化为下面两个三角形方程组bLy yUx 为中间未知量向量y213132123111.1nnnlLlllll1112131,22232,1,11,.nnnnnnnnuuuuuuuUuuu3.2.2 矩阵的doolittle分解上述解线性方程组的方法称为直接三角分解法的 Doolittle分解例例3.2.1 用Doolittle分解求解方程组13914443211312433010243

7、21xxxx72510解解ju1ja11111ualii下面再用Doolittle分解方法求解14131211uuuu30102Tlll4131211T25 . 05 . 113.2.2 矩阵的doolittle分解得解, yUx Txxxx4321T4321nnnnuyx rrnrjjrjrruxuyx1Doolittle分解在计算机上实现是比较容易的但如果按上述流程运算仍需要较大的存储空间:, , , ,A b x L U y 都需要单独的存储空间,(1) (4)ijijl u而从的计算过程式可知11(1)jjUuaj 求出 的第一行后的存储位置即不再需要3.2.2 矩阵的doolittl

8、e分解的存储位置即不再需要后的第一列求出)2(11ialLii的存储位置即不再需要后行的第求出)(rjaurUrjrj的存储位置即不再需要后列的第求出)1( rialrLirir因此可按下列方法存储数据:(),1,2,.,rjrjaujr rn(1),1,2,.,1iriralirrn有如下特点：时解三角形方程组同样,bLy 的存储位置即不再需要后求出11by3.2.2 矩阵的doolittle分解的存储位置即不再需要后求出)2( ibyii,1,2,.,iibyin空出的存储位置的存储可以使用因此)1( ibyii直接三角分解的Doolittle分解可以用以下过程表示:43214443424

9、1343332312423222114131211bbbbaaaaaaaaaaaaaaaa4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaa存储单元(位置)3.2.2 矩阵的doolittle分解4321444342413433323124232221141312111bbbyaaalaaalaaaluuuur4321444342413433323124232221141312112bbyyaallaalluuuluuuur4321444342413433323124232221141312113byyyallluulluu

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

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

12、解的加法与乘法的计算量均为注53.2.2 矩阵的doolittle分解例例3.2.2 用紧凑格式的Doolittle分解求解方程组解解4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaaA7251013914443211312433010272510139142432211312423301021rju1ja11111ualii11rkkjrkrjrjulaurrrkkrikiriruulal111111rjjrjrrylbyby3.2.2 矩阵的doolittle分解21003103172011122217133211211

13、111162913711410210033172011122213321721111111162941611r Lx12100331711122221332321111116429411Ux y 解4321xxxxx4321所以yU3.2.2 矩阵的doolittle分解例例3.2.3 用Doolittle分解求解方程组9189271845045901269274591354321xxxx12168解解直接利用Doolittle分解的紧凑格式算得918927121391890218154152/391LUyUxy回代求解方程组得：(1/9,1/9,1/9,1/9)Tx 3.2.2 矩阵的doo

14、little分解 列选主元列选主元Doolittle分解分解11rkkjrkrjrjulaurrrkkrikiriruulal11在Doolittle分解(包括紧凑格式)中，会反复用到公式( )rrrrruGaussa显然相当于法的顺序主元rruDoolittle仍然称为分解的顺序主元仍有可能是小主元做除数为此，也要考虑在算法中加入选取列主元3.2.2 矩阵的doolittle分解111211112121222212221212.1.1.1nnnnnnnnnnnnaaaluuaaalluaaalllCrout,A CroutDoolittleTTTTTTALUAU LULA分解等价于，其中为单

15、位下三角矩阵， 为上三角矩阵即对矩阵 作分解等价于对矩阵 作分解。Uby在解方程组时，可将右端向量 放入的最后一列，使得 的计算按 中元素一紧凑格式样处理。LUDoolittle在计算时，应，即第k步分解时先算 的第k列，后注先算 的第k行，与分解的计算次序恰算列后算行好相反。 Crout 分解分解L为下三角矩阵，U为单位上三角矩阵3.2.2 矩阵的doolittle分解三、三、 Cholesky分解与平方根法分解与平方根法 对称正定矩阵的三角分解（对称正定矩阵的三角分解（Cholesky分解）分解）det0,1,2,.,kAAkn且 的顺序主子式为对称正定矩阵阶矩阵若AnAAAT,0)det

16、(则)(分解或分解可以进行因此DoolittleLUA工程实际计算中，线性方程组的系数矩阵常常具有对称正定性，即其各阶顺序主子式及全部特征值均大于零。矩阵的这一特性使它的三角分解也有更简单的形式，从而导平方根法出一些特改进殊的解法，如与的平方根法。3.2.2 矩阵的doolittle分解因此ALDR可以证明这种分解是唯一的可以证明这种分解是唯一的设存在另外的一个分解设存在另外的一个分解111AL D R111L D RLDR则则111111L LDRRD单位单位下三下三角角单位单位下三下三角角上三上三角角上三上三角角所以：所以：111,LL RR DD3.2.2 矩阵的doolittle分解又

17、因为：又因为：TAAALDR即即TTLDRR DL所以：所以：TLR1122(,.,)nnDdiag uuu21122(,.,)nndiaguuu即即TALDL1122TALD D L则：则：令：令：12LLD12( )TTLD L3.2.2 矩阵的doolittle分解综合以上分析,为对称正定矩阵阶矩阵若An则有( )TAL LTLLA 为了方便我们记：为了方便我们记：定理定理3.2.3 (Cholesky分解)使得正数的下三角阵元全是则一定存在一个主对角为对称正定矩阵设, , LATLLA 且该分解式唯一这种关于对称正定矩阵的分解称为Cholesky分解3.2.2 矩阵的doolittle

18、分解irarArL列元素的第考察列已求出的第假设,111111.rrrnnrnnllllll111111.rnrrrrnnnrnnaaaaaaaaa1111.rnrrnrnnllllll111111al l212111all1111iial l1,2,.,in可以求出的第一列元素1ilL1rrrrkrkkall2112rrrkrkll1ririkrkkal l11rikrkirrrkl ll l,1,.,ir rn-(6)-(7)-(8)3.2.2 矩阵的doolittle分解 对称正定线性方程组的解法对称正定线性方程组的解法bAx 线性方程组阶对称正定矩阵为其中nA使得的下三角阵则存在主对角

19、元为正数, LTLLA -(10)-(11)因而线性方程组(10)可化为两个三角形方程组L ybyxLTbxLLT)(-(12)-(13)3.2.2 矩阵的doolittle分解例例3.2.7用平方根法解对称正定方程组12367597138105869xxx解解A先分解系数矩阵6757 13 8586A分解TLLL66765629174132925rrrkrkikirirrkrkrrrriilllallallalal1111211111111,3.2.2 矩阵的doolittle分解即Tyyyy),(321T)2910,1743,69(yxLT最后解nnnnlyx iinikkkiiilxly

20、x13333lyx 1132111lxlyxkkk22233222lxlyx11Txxxx),(321所以原方程组的解为T)2 , 1, 1(),(yLT2910174369292517413629656763.2.2 矩阵的doolittle分解 平方根法的数值稳定性平方根法的数值稳定性用平方根法求解对称正定方程组时不需选取主元TLLA 由可知1rrrrkrkkallrkrkl12因此2|rkrrlarkl中间量 是完全可以控制的，因而舍入误差积累不会有明显增长，也就是可以控制的。1,2,.,rn1,2,.,kr平方根法是数值稳定的3.2.2 矩阵的doolittle分解3.2.6 解三对角

21、方程组的追赶法解三对角方程组的追赶法11222111.nnnnnbcabcabcab12.nxxx12.nddd3.2.2 矩阵的doolittle分解(2) | | ,0,iiiiibaca c2,.,1;in(3) | | 0.nnba.A称为的三对角占优角矩阵对11(1) | | 0;bc如果矩阵A满足,det0AA非奇异即0det,kAkA即阶顺序主子式非零的任意因此分解进行可以将所以LUA,分解为为上三角阵时为单位下三角阵DoolittleUL,分解为为单位上三角阵时为下三角阵CroutUL,3.2.2 矩阵的doolittle分解以下先以gauss消元法导出三对角方程组的解法112

22、22111.nnnnnbcabcabcab12.nxxx12.nddd3.2.2 矩阵的doolittle分解设经过经过n-1消元以后消元以后11122211111.11nnnnnxquxquxquxq111111111/()2,3,.1()/()2,3,.iiiiiiiiiiiiucbqdbucbu ainqdq abu ain3.2.2 矩阵的doolittle分解再依次回代回去就可以求解了：再依次回代回去就可以求解了：11,2.1nniiiixqxqu xinn此课件下载可自行编辑修改，供参考！此课件下载可自行编辑修改，供参考！感谢你的支持，我们会努力做得更好！感谢你的支持，我们会努力做得更好！