第二章 解线性方程组的直接法 2.4 直接三角分解法§ 2.4 直接三角分解法§ 一 、 基本的三角分解法 (Doolittle法 ) ,0)( ≠= × knnij DaAn 的顺序主子式阶方阵若 nk ,,2,1 L= 即存在且唯一分解的则由上节可知 ,, LUALUA = ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? = nnnkn knkkk nk aaa aaa aaa A LL MOMM LL MMOM LL 1 1 1111 ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? = 1 1 1 1 1 LL OMM L OM nkn k mm m ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? )( )()( )1( 1 )1( 1 )1( 11 n nn k kn k kk nk a aa aaa MO L MMO LL LU= ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? = 1 1 1 1 1 LL OMM L OM nrn r ll l ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? nn rnrr nr u uu uuu MO L MMO LL 1111 ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? = nnnrn rnrrr nr aaa aaa aaa A LL MOMM LL MMOM LL 1 1 1111 上式可记为 为的第一行元素根据矩阵的乘法原理 jaA 1, njua jj ,,2,111 L== 为素行元素主对角线以右元的第 ),,( nrjarA rj L= ∑ = = r k kjrkrj ula 1 nr ,,2,1 L= nrj ,,L= ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? = + 1 1 1 1 1,1 LL OMM L OM nrn r ll l ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? nn rnrr nr u uu uuu MO L MMO LL 1111 ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? = nnnrn rnrrr nr aaa aaa aaa A LL MOMM LL MMOM LL 1 1 1111 同样 ,由 为素列元素主对角线以下元的第可知 ),,1( nriarA ir L+= ∑ = = r k krikir ula 1 1,,2,1 ?= nr L nri ,,1 L+= 1111,1, ular ii == 时显然 ni ,,3,2 L= 综合以上分析 ,有 njua jj ,,2,111 L== ∑ = = r k kjrkrj ula 1 nr ,,2,1 L= nrj ,,L= ∑ = = r k krikir ula 1 1,,2,1 ?= nr L nri ,,1 L+= 1111 ula ii = ni ,,3,2 L= 因此可以推导出 ju1 ja1= nj ,,2,1 L= U的第一行 11 1 1 u al i i = ni ,,3,2 L= L的第一列 rj r k kjrkrj uula ?+= ∑ ? = 1 1 1 rrir r k krikir ulula += ∑ ? = 1 1 ------(1) ------(2) ∑? = ?= 1 1 r k kjrkrjrj ulau nr ,,2,1 L= nrj ,,L= U的第 r行 rr r k krikir ir u ula l ∑? = ? = 1 1 1,,2,1 ?= nr L nri ,,1 L+= L的第 r列 ------(3) ------(4) 称上述 (1) ~ (4)式所表示的分解过程为 Doolittle分解 .)4(~)1(, ,, 式的表达式请找出类似于解 分则称之为表示为单位上三角阵角阵 表示为下三中的为上三角阵 ， 如果将 为单位下三角阵中分解的 CroutU LLUA ULLUADoolittleA = =思考 对于线性方程组 bAx = 系数矩阵非奇异 ,经过 Doolittle分解后 LUA = 线性方程组可化为下面两个三角形方程组 bLy = yUx = 为中间未知量向量y ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? = 1 1 1 1 321 3231 21 L OMMM nnn lll ll l L ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? = ??? nn nnnn n n u uu uuu uuuu U ,11,1 ,22322 ,1131211 MO L L :, 的解不难得到的知识由第一节三角形方程组 bLy = 11 by = ∑? = ?= 1 1 r j jrjrr ylby nr ,,3,2 L= 12122 ylby ?= 的解的解便得到因此再由 bAxyUx == nn n n u yx = rr n rj jrjr r u xuy x ∑ += ? = 1 1,2,,2,1 L??= nnr ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? = 1 1 1 1 321 3231 21 L OMMM nnn lll ll l L ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ??? nn nnnn n n u uu uuu uuuu ,11,1 ,22322 ,1131211 MO L L ju1 ja1= 11 1 1 u al i i = 上述解线性方程组的方法称为 直接三角分解法的 Doolittle法 例 1. 用 Doolittle法解方程组 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? 139144 4321 131243 30102 ?? ? ? ? ? ?? ? ? ? ? 4 3 2 1 x x x x ? ? ? ? ? ? ? ? ? ? ? ? ?= 7 2 5 10 解 : 由 Doolittle分解 ( )14131211 uuuu ( )30102 ?= ( )Tlll 4131211 ( )T25.05.11 ?= ( )2423220 uuu ( )5.812110 ?= ( )Tll 423210 ( )T11/611/310 ??= ( )343300 uu ( )11/211/300 ??= ( )Tl43100 ( )T9100 ?= ( )44000 u ( )4000 ?= 得解 ,bLy = ( )Tyyyy 4321 ( )T1611/172010 ??= ∑? = ?= 1 1 r k kjrkrjrj ulau rr r k krikir ir u ula l ∑? = ? = 1 1 得解 ,yUx = ( )Txxxx 4321 ( )T4321= nn n n u yx = rr n rj jrjr r u xuy x ∑ += ? = 1 Doolittle法在计算机上实现是比较容易的 但如果按上述流程运算仍需要较大的存储空间 : 都需要单独的存储空间yULxbA ,,,,, 式可知的计算过程而从 )4(~)1(, ijij ul 的存储位置即不再需要后的第一行求出 )1(11 ≥jauU jj 的存储位置即不再需要后的第一列求出 )2(11 ≥ialL ii 的存储位置即不再需要后行的第求出 )( rjaurU rjrj ≥ 的存储位置即不再需要后列的第求出 )1( +≥ rialrL irir 因此可按下列方法存储数据 : nrrjua rjrj ,,2,1),( L=≥? 1,,2,1),1( ?=+≥? nrrila irir L 有如下特点 ：时解三角形方程组同样 ,, bLy = 的存储位置即不再需要后求出 11 by 的存储位置即不再需要后求出 )2( ≥iby ii niyb ii ,,2,1, L=? 空出的存储位置的存储可以使用因此 )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 存储单元 (位置 ) ?? ? ? ? ? ? ?? ? ? ? ? ? →? = 4 3 2 1 44434241 34333231 24232221 14131211 1 b b b y aaal aaal aaal uuuu r ?? ? ? ? ? ? ?? ? ? ? ? ? →? = 4 3 2 1 44434241 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法 例 2. 用紧凑格式的 Doolittle法解方程组 (例 1) 解 : ? ? ? ? ? ? ? ? ? ? ? ? = 45 35 25 15 44434241 34333231 24232221 14131211 a a a a aaaa aaaa aaaa aaaa A ?? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ??? ? = 7 2 5 10 139144 4321 131243 30102 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? →? = 7 2 5 10 139142 43221 1312423 30102 1r ju 1 ja 1= 11 1 1 u al i i = ∑? = ?= 1 1 r k kjrkrjrj ulau rr r k krikir ir u ula l ∑? = ? = 1 1 ?? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ?? ?? ? →? = 7 2 20 10 1391162 4311321 2 171211 2 3 30102 2r ∑? = ?= 1 1 r k kjrkrjrj ulau rr r k krikir ir u ula l ∑? = ? = 1 1 ?? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ??? ??? ?? ? →? = 7 11 17 20 10 1391162 11 2 11 3 11 3 2 1 2 171211 2 3 30102 3r ?? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ??? ??? ?? ? →? = 16 11 17 20 10 491162 11 2 11 3 11 3 2 1 2 171211 2 3 30102 4r L x U ?? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ??? ??? ?? ? →? = 4 3 2 1 491162 11 2 11 3 11 3 2 1 2 171211 2 3 30102 yUx解 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 4 3 2 1 x x x x x ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 4 3 2 1 所以 y 二 、 列主元 Doolittle分解 ∑? = ?= 1 1 r k kjrkrjrj ulau rr r k krikir ir u ula l ∑? = ? = 1 1 在 Doolittle法 (包括紧凑格式 )中 ,会反复用到公式 )(r rrrr aGaussu 法的顺序主元相当于显然 法的顺序主元为仍然称 Doolittleurr 仍有可能为小 主元做除数 为此 ,我们也要考虑在算法中加入选取列主元 我们下面介绍紧凑格式的 Doolittle列 主元法 然后分解 并进行换行 者作为 最大将 , , || 11 1 uai →???? ? ? ? ? ? ? ? ? ? ? 45 35 25 15 44434241 34333231 24232221 14131211 a a a a aaaa aaaa aaaa aaaa ? ? ? ? ? ? ? ? ? ? ? ? 4 3 2 1 44434241 34333231 24232221 14131211 b b b y aaal aaal aaal uuuu ? ? ? ? ? ? ? ? ? ? ? ? 4 3 2 1 44434241 34333231 24232221 14131211 b b y y aall aall uuul uuuu 大作主元不一定绝对值最由于 12212222 ulau ?= 4,3,2,1212 =→? iSula iii因此比较 然后分解最大的行与第二行交换将 ,)4,3,2(|| =iSi 分解换行 , →?? 符号因换行只代 表存储位置 ,与原 数值可能有差异 依此类推 列主元 Doolittle法步骤 : 第一步 : ||max||, 11 1 iniiii SSaS ≤≤ == 设比较 公式分解然后按行交换将第一行与第 Doolittlei ,1 ||max||, 1 1 iniri r k krikiri SSulaS r ≤≤ ? = =?= ∑ 设比较 公式分解然后按行交换行与第将第 Doolittleir r , :步第 r :步第 n 而直接分解故不需选主元因为只有 ,,1 1 ∑? = ?= n k knnknnn ulaS rrr Su =则 rr i ir u Sl =也交换与同时 rir SS 例 3. 用列主元 Doolittle法解线性方程组 ?? ? ? ? ?? ? ? ? = ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ? ? ? 1 4 1 294 642 311 3 2 1 x x x 解 : ?? ? ? ? ?? ? ? ? ? ? ? 1 4 1 294 642 311 *4 2 1 1 3 2 1 = = = = S S S r 31 rr ? ?? ? ? ? ?? ? ? ? ? ? ? 1 4 1 311 642 294 分解 ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? 1 4 1 3141 6421 294 4 5 2 1 2 3 2 = = = S S r 32 rr ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? 4 1 1 6421 3141 294 rirr Su = rr i ir u Sl = 分解 ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? 4 4 3 1 65221 2 5 4 5 4 1 294 3=r 分解 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 5 164 3 1 45221 2 5 4 5 4 1 294 y yUx =解 回代 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 5 4 1 5 12 45221 2 5 4 5 4 1 294 x ?? ? ? ? ? ? ?? ? ? ? ? ? = 3 2 1 x x x x ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? = 5 4 1 5 12 所以原 方程组 的解为 试用列主元 Doolittle法解矩阵方程 BAX = ?? ? ? ? ? ?? ? ? ? ? = nnnn n n aaa aaa aaa A L MMM L L 21 22221 11211 ?? ? ? ? ? ?? ? ? ? ? = nmnn m m xxx xxx xxx X L MMM L L 21 22221 11211 ?? ? ? ? ? ?? ? ? ? ? = nmnn m m bbb bbb bbb B L MMM L L 21 22221 11211 并设计自然语言的算法