3.2.2 矩阵的doolittle分解

3.2.2矩阵的doolittle分解定理3.12,0detkkADAn的顺序主子式阶方阵若1,2,...,1,knALUALU则的分解式存在且惟一L是单位下三角矩阵U一个上三角矩阵Gauss消元法的消元过程实际上是对线性代数方程组进行一系列初等行变换的过程。由线性代数知识知，线性代数方程组的初等变换相当于对其增广矩阵实行初等行变换，也即相当于增广矩阵左边乘以一个初等矩阵。,0)(knnijDaAn的顺序主子式阶方阵若1,2,...,knALUALU则由前面的分析可知，的分解存在且惟一，即111111..........................................knkkkknnnknnaaaAaaaaaa111.........1...............1knnklll(1)(1)(1)1111()()()........................knkkkkknnnnaaaaaaLU111.........1...............1rnnrlll1111........................rnrrrnnnuuuuuu111111..........................................rnrrrrnnnrnnaaaAaaaaaa也可以直接用比较法导出矩阵A的LU分解的计算公式。上式可记为1,jAa根据原理的第一行元素矩阵的乘法为111,2,...,jjaujn(,...,)rjArajrn的第行元素主对角线以右元素为rkkjrkrjula11,2,...,rn,...,jrn比较第1行比较第r行1,111.........1...............1rnnrlll1111........................rnrrrnnnuuuuuu111111..........................................rnrrrrnnnrnnaaaAaaaaaa同样，由(1,...,)irArairn可知的第列元素主对角线以下元素为rkkrikirula11,2,...,1rn1,...,irn1111,1,ularii时显然2,3,...,in比较第r列综合以上分析，有111,2,...,jjaujn因此可以推导出ju1ja11,2,...,jnU的第一行1111ualii2,3,...,inL的第一列111rrjrkkjrjkaluurrirrkkrikirulula11------(1)------(2)11112,3,...,iialuinrkkrikirula11,2,...,1rn1,...,irnrkkjrkrjula11,2,...,rn,...,jrn思考11rkkjrkrjrjulau1,2,...,rn,...,jrnU的第r行rrrkkrikiriruulal111,2,...,1rn1,...,irnL的第r列------(3)------(4)称上述(1)~(4)式所表示的分解过程为矩阵A的Doolittle分解(1)~(4).ADoolittleALULUALULUCrout的分解中为单位下三角阵,为上三角阵。如果将中的表示为下三角阵，表示为单位上三角阵,则称之为请找出类似于式的解，表达式分function[l,u]=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);fork=2:nforj=k:nu(k,j)=A(k,j)-l(k,1:k-1)*u(1:k-1,j);endu(k,k:n)=A(k,k:n)-l(k,1:k-1)*u(1:k-1,k:n);fori=k+1:nl(i,k)=(A(i,k)-l(i,1:k-1)*u(1:k-1,k))/u(k,k);endl(k+1:n,k)=(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...............1nnnlLlllll1112131,22232,1,11,............nnnnnnnnuuuuuuuUuuu:Lyb由上一节三角形方程组的知识，不难得到的解11by11rjjrjrrylby2,3,...,rn12122ylbyUxyAxb因此再由的解便得到的解:nnnnuyxrrnrjjrjrruxuyx11,2,...,2,1rnn213132123111...............1nnnlLlllll1112131,22232,1,11,............nnnnnnnnuuuuuuuUuuu上述解线性方程组的方法称为直接三角分解法的Doolittle分解例3.2.1用Doolittle分解求解方程组1391444321131243301024321xxxx72510解ju1ja11111ualii下面再用Doolittle分解方法求解14131211uuuu30102Tlll4131211T25.05.112423220uuu5.812110Tll423210T11/611/310343300uu11/211/300Tl43100T910044000u400011rkkjrkrjrjulaurrrkkrikiriruulal111391444321131243301024321xxxx72510210031.50.5211128.53/116/113/112/1194得解,bLy1234TyyyyT1611/1720101111rjjrjrrylbyby得解,yUxTxxxx4321T4321nnnnuyxrrnrjjrjrruxuyx1Doolittle分解在计算机上实现是比较容易的但如果按上述流程运算仍需要较大的存储空间:,,,,,AbxLUy都需要单独的存储空间,(1)~(4)ijijlu而从的计算过程式可知11(1)jjUuaj求出的第一行后的存储位置即不再需要的存储位置即不再需要后的第一列求出)2(11ialLii的存储位置即不再需要后行的第求出)(rjaurUrjrj的存储位置即不再需要后列的第求出)1(rialrLirir因此可按下列方法存储数据:(),1,2,...,rjrjaujrrn(1),1,2,...,1iriralirrn有如下特点：时解三角形方程组同样,,bLy的存储位置即不再需要后求出11by的存储位置即不再需要后求出)2(ibyii,1,2,...,iibyin空出的存储位置的存储可以使用因此)1(ibyii直接三角分解的Doolittle分解可以用以下过程表示:432144434241343332312423222114131211bbbbaaaaaaaaaaaaaaaa4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaa存储单元(位置)4321444342413433323124232221141312111bbbyaaalaaalaaaluuuur4321444342413433323124232221141312112bbyyaallaalluuuluuuur4321444342413433323124232221141312113byyyallluulluuuluuuur4321444342413433323124232221141312114yyyyullluulluuuluuuuryUL,,可知从上式最后一个矩阵中yUx然后解线性方程组Doolittle分解的紧凑格式Doolittle分解的结果与Gauss消元法所得结果完全一样，但却避免了中间过程。11(),1,2,1...,.ijijikkjjjUuijAaLlUuUuajn的元素等于矩阵的对应元素减去一个内积，内积每一项是左边的同行元素与上边的同列元素的乘积。的第一行元素注1111()U/,2,3,...,.jijiiijkkijjLljiAauLlUuLlaujn的元素等于矩阵的对应元素减去一个内积，再除以与它同列的的对角元素，内积每一项是左边的同行元素与上边的同列元素的乘积。的第一列元素注2byU可将右端向量放于紧凑格式的最后一注3列，使得的计算按中元素一样处理。ULLU无论计算的元还是计算的元，内积所含和的元应该事先注4按一行一列、二行二列算出，所以计算过程可...的次序进行。定理3.2.3设矩阵A非奇异，当且仅当矩阵A的所有顺序主子式全非零时，其Doolittle分解式存在，且分解是惟一的。下面给出Doolittle分解存在惟一的一个充要条件31Doolittle().3On分解的加法与乘法的计算量均为注5例3.2.2用紧凑格式的Doolittle分解求解方程组解4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaaA7251013914443211312433010272510139142432211312423301021rju1ja11111ualii11rkkjrkrjrjulaurrrkkrikiriruulal111111rjjrjrrylbyby102100335412132122342214913772201013911624311321217121123301022r11rkkjrkrjrjulaurrrkkrikiriruulal11711172010139116211211311321217121123301023r1111rjjrjrrylbyby21003103172011122217133211