3.2.2 矩阵的doolittle分解[优教课堂]

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

2、。 2课堂教育 ,0)( knnij DaAn的顺序主子式阶方阵若1,2,.,kn ALUALU则由前面的分析可知， 的分解存在且惟一，即 1111 1 1 . . . . . kn kkkkn nnknn aaa Aaaa aaa 1 1 1 . .1 . . 1 k nnk l ll (1)(1)(1) 1111 ( )( ) ( ) . . . . kn kk kkkn n nn aaa aa a LU 3课堂教育 1 1 1 . . .1 . . . 1 r nnr l ll 1111 . . . . rn rrrn nn uuu uu u 1111 1 1 . . . . . rn

3、rrrrn nnrnn aaa Aaaa aaa 也可以直接用比较法导出矩阵A的LU分解的计算公式。 上式可记为 1 , j Aa根据原理的第一行元素矩阵的乘法为 11 1,2,., jj aujn (,., ) rj Arajrn的第 行元素主对角线以右元素为 r k kjrkrj ula 11,2,.,rn ,.,jrn 比较第1行 比较第r行 4课堂教育 1,1 1 1 . .1 . .1 r nnr l ll 1111 . . . . rn rrrn nn uuu uu u 1111 1 1 . . . . . rn rrrrn nnrnn aaa Aaaa aaa 同样，由 (1,.

4、, ) ir Arairn可知 的第 列元素主对角线以下元素为 r k krikir ula 11,2,.,1rn 1,.,irn 1111 ,1,ular ii 时显然2,3,.,in 比较第r列 5课堂教育 综合以上分析，有 11 1,2,., jj aujn 因此可以推导出 j u1 j a11,2,.,jn U的第一行 11 1 1 u a l i i 2,3,.,inL的第一列 1 1 1 r rjrkkjrj k al uu rrir r k krikir ulula 1 1 -(1) -(2) 11 11 2,3,., ii al uin r k krikir ula 11,2,

5、.,1rn 1,.,irn r k kjrkrj ula 11,2,.,rn ,.,jrn 6课堂教育 思考 1 1 r k kjrkrjrj ulau 1,2,.,rn ,.,jrn U的第r行 rr r k krikir ir u ula l 1 1 1,2,.,1rn 1,.,irn L的第r列 -(3) -(4) 称上述(1) (4)式所表示的分解过程为矩阵A的 Doolittle分解 (1) (4) . ADoolittleALUL UALUL U Crout 的分解中为单位下三角 阵,为上三角阵。如果将中的表 示为下三角阵，表示为单位上三角阵, 则 称之为请找出类似于 式的 解，

6、表达式 分 7课堂教育 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); 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)*

7、u(1:k-1,k)/u(k,k); end l(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 8课堂教育 对于线性方程组 bAx 系数矩阵非奇异，经过Doolittle分解后LUA 线性方程组可化为下面两个三角形方程组 bLy yUx 为中间未知量向量y 21 3132 123 1 1 1 . .1 nnn l Lll lll 1112131, 22232, 1,11, . . . n n nnnn nn uuuu uuu U uu u 9课堂教育 :Lyb由上一节三角形方程组的知识，不难得到的解 11 by 1 1 r

8、 j jrjrr ylby 2,3,.,rn 12122 ylby UxyAxb因此再由的解便得到的解: nn n n u y x rr n rj jrjr r u xuy x 1 1,2,.,2,1rnn 21 3132 123 1 1 1 . .1 nnn l Lll lll 1112131, 22232, 1,11, . . . n n nnnn nn uuuu uuu U uu u 10课堂教育 上述解线性方程组的方法称为 直接三角分解法的 Doolittle分解 例例3.2.1 用Doolittle分解求解方程组 139144 4321 131243 30102 4 3 2 1 x

9、x x x 7 2 5 10 解解 j u 1j a1 11 1 1 u a l i i 下面再用Doolittle分解方法求解 14131211 uuuu30102 T lll 413121 1 T 25 . 05 . 11 11课堂教育 242322 0uuu5 . 812110 T ll 4232 10 T 11/611/310 3433 00uu11/211/300 T l43100 T 9100 44 000u 4000 1 1 r k kjrkrjrj ulau rr r k krikir ir u ula l 1 1 139144 4321 131243 30102 4 3 2

10、1 x x x x 7 2 5 10 21003 1.5 0.5 2 11128.5 3/11 6/11 3/1 1 2/1 1 94 得解,bLy 1234 T yyyy T 1611/172010 1 1 11 r j jrjrr ylby by 12课堂教育 得解, yUx T xxxx 4321 T 4321 nn n n u y x rr n rj jrjr r u xuy x 1 Doolittle分解在计算机上实现是比较容易的 但如果按上述流程运算仍需要较大的存储空间: , , , ,A b x L U y 都需要单独的存储空间 ,(1) (4) ijij l u而从的计算过程式

11、可知 11 (1) jj Uuaj 求出 的第一行后的存储位置即不再需要 13课堂教育 的存储位置即不再需要后的第一列求出)2( 11 ialL ii 的存储位置即不再需要后行的第求出)(rjaurU rjrj 的存储位置即不再需要后列的第求出)1( rialrL irir 因此可按下列方法存储数据: (),1,2,., rjrj aujr rn (1),1,2,.,1 irir alirrn 有如下特点：时解三角形方程组同样,bLy 的存储位置即不再需要后求出 11 by 14课堂教育 的存储位置即不再需要后求出)2( iby ii ,1,2,., ii byin 空出的存储位置的存储可以使

12、用因此)1( iby ii 直接三角分解的Doolittle分解可以用以下过程表示: 4 3 2 1 44434241 34333231 24232221 14131211 b b b b aaaa aaaa aaaa aaaa 45 35 25 15 44434241 34333231 24232221 14131211 a a a a aaaa aaaa aaaa aaaa 存储单元(位置) 15课堂教育 4 3 2 1 44434241 34333231 24232221 14131211 1 b b b y aaal aaal aaal uuuu r 4 3 2 1 44434241

13、34333231 24232221 14131211 2 b b y y aall aall uuul uuuu r 4 3 2 1 44434241 34333231 24232221 14131211 3 b y y y alll uull uuul uuuu r 4 3 2 1 44434241 34333231 24232221 14131211 4 y y y y ulll uull uuul uuuu r yUL,可知从上式最后一个矩阵中 yUx 然后解线性方程组 Doolittle分解 的紧凑格式 16课堂教育 Doolittle分解的结果与Gauss消元法所得结果完全 一样，但

14、却避免了中间过程。 11 () ,1,2, 1 ., . ijij ik kj jj UuijAa Ll Uu Uuajn 的元素等于矩阵 的对应元素减去 一个内积，内积每一项是左边的同行元素与上 边的同列元素的乘积。 的第一行元素 注 1111 () U /,2,3,., . jiji ii jk k i jj LljiAa u LlU u Llaujn 的元素等于矩阵 的对应元素减去 一个内积，再除以与它同列的的对角元素，内 积每一项是左边 的同行元素与上边的同列元素 的乘积。 的第一列元素 注2 17课堂教育 b yU 可将右端向量 放于紧凑格式的最后一注3列， 使得的计算按中元素一样处

15、理。 ULLU无论计算 的元还是计算 的元，内积所含 和 的 元应该事先 注4 按一行一列、二行二列 算出，所以计算过程可 .的次序进行。 定理3.2.3 设矩阵A非奇异，当且仅当矩阵A的所有 顺序主子式全非零时，其Doolittle分解式存在，且 分解是惟一的。 下面给出Doolittle分解存在惟一的一个充要条件 3 1 Doolittle(). 3 O n分解的加法与乘法的计算量均为注5 18课堂教育 例例3.2.2 用紧凑格式的Doolittle分解求解方程组 解解 45 35 25 15 44434241 34333231 24232221 14131211 a a a a aaaa

16、 aaaa aaaa aaaa A 7 2 5 10 139144 4321 131243 30102 7 2 5 10 139142 432 2 1 13124 2 3 30102 1r j u 1j a 1 11 1 1 u a l i i 1 1 r k kjrkrjrj ulau rr r k krikir ir u ula l 1 1 1 1 11 r j jrjrr ylby by 19课堂教育 10 21003 3 541213 2 1 2 234 2 214913 7 7 2 20 10 139 11 6 2 43 11 3 2 1 2 17 1211 2 3 30102 2r

17、 1 1 r k kjrkrjrj ulau rr r k krikir ir u ula l 1 1 7 11 17 20 10 139 11 6 2 11 2 11 3 11 3 2 1 2 17 1211 2 3 30102 3r 1 1 11 r j jrjrr ylby by 20课堂教育 2100310 317 201112 22 171332 112111111 6 2913 7 11 4 10 21003 317 201112 22 1332 17 2111111 11 6 294 16 11 r L x 1 21003 317 11122 22 1332 3 2111111

18、6 4294 11 Ux y 解 4 3 2 1 x x x x x 4 3 2 1 所以 y U 21课堂教育 例例3.2.3 用Doolittle分解求解方程组 918927 1845045 901269 27459135 4 3 2 1 x x x x1 2 16 8 解解直接利用Doolittle分解的紧凑格式算得 9189271 2 1 3 91890 2 1 815415 2/391 L U y Uxy回代求解方程组得：(1/9,1/9,1/9,1/9)Tx 22课堂教育 1 2 3 Doolittle 12314 25218 31520 x x x 用分解求例3.解.方4程2 D

19、oolittle 12314 21410 352472 12314 014,10 . 002472 (1,2,3) . T Uy Uxyx 直接利用分解的紧凑格式算得 因此 得 解 求解 23课堂教育 列选主元列选主元Doolittle分解分解 1 1 r k kjrkrjrj ulau rr r k krikir ir u ula l 1 1 在Doolittle分解(包括紧凑格式)中，会反复用到公式 ( )r rrrr uGaussa显然相当于法的顺序主元 rr uDoolittle仍然称为分解的顺序主元 仍有可能是小 主元做除数 为此，也要考虑在算法中加入选取列主元 24课堂教育 111

20、2111121 2122221222 1212 .1. .1. . .1 nn nn nnnnnnnn aaaluu aaallu aaalll Crout ,A CroutDoolittle TTTTT T ALUAU LUL A 分解等价于，其中为单位下三角矩阵， 为 上三角矩阵即对矩阵 作分解等价于对矩阵 作分解。 U by在解方程组时，可将右端向量 放入的最后一列，使得 的 计算按 中元素一 紧凑格式 样处理。 L UDoolittle 在计算时，应，即第k步分解时先算 的第k列， 后 注先 算 的第k行，与分解的计算次序恰 算列后算行 好相反。 Crout 分解分解 L为下三角矩阵，

21、U为单位上三角矩阵 25课堂教育 三、三、 Cholesky分解与平方根法分解与平方根法 对称正定矩阵的三角分解（对称正定矩阵的三角分解（Cholesky分解分解） det0,1,2,., k AAkn且 的顺序主子式 为对称正定矩阵阶矩阵若An AAA T ,0)det(则 )(分解或分解可以进行因此DoolittleLUA 工程实际计算中，线性方程组的系数矩阵常常具有对 称正定性，即其各阶顺序主子式及全部特征值均大于零。 矩阵的这一特性使它的三角分解也有更简单的形式，从而 导平方根法出一些特改进殊的解法，如与的平方根法。 26课堂教育 1112131 22232 333 . . . . n

22、 n n nn uuuu uuu Uuu u 11 22 33 . nn u u u u 13112 111111 232 2222 1, 1,1 1. 1. . 1 1 n n nn nn uuu uuu uu uu u u DR ALU 27课堂教育 因此 ALDR 可以证明这种分解是唯一的可以证明这种分解是唯一的 设存在另外的一个分解设存在另外的一个分解 111 AL D R 111 L D RLDR则则 111 111 L LDRRD 单位单位 下三下三 角角 单位单位 下三下三 角角 上三上三 角角 上三上三 角角 所以：所以： 111 ,LL RR DD 28课堂教育 又因为：又因

23、为： T AA ALDR 即即 TT LDRR DL 所以：所以： T LR 1122 (,.,) nn Ddiag uuu 2 1122 (,.,) nn diaguuu 即即 T ALDL 11 22 T ALD D L 则：则： 令：令： 1 2 LLD 1 2 ( )T T LD L 29课堂教育 综合以上分析, 为对称正定矩阵阶矩阵若An 则有 ( )TAL L T LLA 为了方便我们记：为了方便我们记： 定理定理3.2.3 (Cholesky分解) 使得正数的下三角阵 元全是则一定存在一个主对角为对称正定矩阵设 , , L A T LLA 且该分解式唯一 这种关于对称正定矩阵的分

24、解称为Cholesky分解 30课堂教育 11 1 1 . . . . rrr nnrnn l Lll lll 1111 1 1 . . . . . rn rrrrn nnrnn aaa Aaaa aaa 设 jiij aa 31课堂教育 ir arArL列元素的第考察列已求出的第假设,11 11 1 1 . . . . rrr nnrnn l ll lll 1111 1 1 . . . . . rn rrrrn nnrnn aaa aaa aaa 1111 . . . . rn rrnr nn lll ll l 111111 al l 212111 all 1111ii al l 1,2,.

25、,in 可以求出的第一列元素 1i lL 1 r rrrkrk k all 2 1 1 2 rr r k rk ll 1 r irikrk k al l 1 1 r ikrkirrr k l ll l ,1,.,ir rn -(6) -(7) -(8) 32课堂教育 的元素的计算公式式可得由L)8()6( 1111 al 11 1 1 l a l i i 2,3,.,in 1 1 2 r k rkrrrr lal 2,.,rn 1 1 r irikrk k ir rr al l l l 1,.,irn )9( 1111ii al l 1 r irikrk k all 1 1 r ikrkirr

26、r k lll l 3 1 6 ACholesky() DoolittleCrout O n对称正定矩阵 的分解的加法与乘法的计算量均为， 约为分解或分解的一半，但需作 注 n次开方运算。 ijijij lal放的储存地址可以用来存求出后当 在计算机上运算时从公式中可以看出 , , 33课堂教育 对称正定线性方程组的解法对称正定线性方程组的解法 bAx 线性方程组 阶对称正定矩阵为其中nA 使得的下三角阵则存在主对角元为正数, L T LLA -(10) -(11) 因而线性方程组(10)可化为两个三角形方程组 L yb yxL T bxLL T )( -(12) -(13) 34课堂教育 例

27、例3.2.7用平方根法解对称正定方程组 1 2 3 6759 713810 5869 x x x 解解 A先分解系数矩阵 675 7 13 8 586 A 分解 T LL L 6 6 7 6 5 6 29 174 13 29 25 rr r k rkikir ir r k rkrrrr i i l lla l lal l a lal 1 1 1 1 2 11 1 11111 , 35课堂教育 bLy 其次解 11 1 1 l b y 6 9 22 1212 2 l ylb y 6 29 6 9*7 10 174 3 29 10 11 1 1 l b y ii i k kiki i l ylb y 1 1 33 2 1 33 3 l ylb y k kk 9 10 9 ),(bL 29 25 174 13 6 5 6 29 6 7 6 36课堂教育 即 T yyyy),( 321 T ) 29 10 , 174 3 , 6 9 ( yxL T 最后解 nn n n l y x ii n ik kkii i l xly x 1 33 3 3 l y x 11 3 2 11