§4 直接三角分解法 一、教学设计1．教学内容：Doolittle 分解法、Crout 分解法，紧凑格式的Doolittle 分解法、部分选主元的Doolittle 分解法。

2．重点难点：紧凑格式的Doolittle 分解法、部分选主元的Doolittle 分解法。

3．教学目标：了解直接三角分解法的基本思想，掌握基本三角分解法及其各种变形。

4．教学方法：讲授与讨论。

二、教学过程在上节中我们用矩阵初等变换来分析Gauss 消去法，得到了重要的矩阵LU 分解定理（定理 3.1，3.2）。

由此我们将得到Gauss 消去法的变形：直接三角分解法。

直接三角分解法的基本想法是，一旦实现了矩阵A 的LU 分解，那么求解方程组b x =A 的问题就等价于求解两个三角形方程组 （1）b y =L ，求y ； （2）y x =U ，求x 。

而这两个三角形方程组的求解是容易的。

下面我们先给出这两个三角形方程组的求解公式；然后研究在LU A =或LU PA =时，U L ,的元素与A 的元素之间的直接关系。

4－0 三角形线性方程组的解法 设⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=nn n n l l l l l l L21222111， 11121222n n nn u u u u u U u ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦则b y =L 为下三角形方程组，它的第i 个方程为),2,1(11,22111n i b y l y l y l y l y l ii ii i i i i i ij j ij ==++++=--=∑假定0≠ii l ，按n y y y ,,,21 的顺序解得：⎪⎪⎩⎪⎪⎨⎧=+-==∑-=),,3,2(/111111n i l b y l y l b y ii i i j j ij i上三角形方程组y x =U 的第i 个方程为),2,1(11,n i y x u x u x u x u in in i i i i ii nij j ij ==+++=++=∑假定0≠ii u ，按121,,,,x x x x n n -的顺序求解得：⎪⎪⎩⎪⎪⎨⎧--=+-==∑+=)1,2,,2,1(/1n n i u y x u x u y x ii i n i j j ij i nnn n4－1 基本的三角分解法设矩阵n n ij a A ⨯=)(的各阶顺序主子式均不为零，由定理3.1，A 有LU 分解如下⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡nn nrn n rn rrr r n rn ra a a a a a a a a a a a a a a a 2121222221111211 LU u u u u u u u u u u l l l l l l nn rn rrn r n r nrn n r r =⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡= 22221112112121211111比较等式两边的第1行上的相应元素，得U 的第1行元素：),,2,1(11n i a u i i == （4.4）比较等式两边的第1列上的相应元素（从第2开始），得L 的第1列元素：),,3,2(1111n i u a l i i ==（4.5） 比较等式两边的第2行上的相应元素（从第2开始），得i i i u u l a 21212+=故得U 的第2行元素：),,3,2(12122n i u l a u i i i =-=比较等式两边的第2列上的相应元素（从第3开始），得2222121i i i a u l u l =+，得L 的第2列元素：),,4,3(2212122n i u u l a l i i i =-=假设已求得U 的第1至1-r 行，L 的第1至1-r 列，比较等式两边的第r 行上的相应元素（从第r 开始），得rnrn n r r r n r n r r r r r r r r r r r r r rrrr r r r r r r r r a u u l u l u l a u u l u l u l a u u l u l u l =++++=++++=++++--+++--++--,11,22111,1,1,11,1,221,11,11,2211即),,1,(11n r r i a u u l riri r k ki rk +==+∑-=故得U 的第r 行元素：),,3,2;,,1,(11n r n r r i u l a u r k ki rk ri ri =+=-=∑-= （4.6）比较等式两边的第r 列上的相应元素（从第1+r 开始），得nrrr nr r r r n r n r n r r rr r r r r r r r r r r r r rr r r r r r r r r r r a u l u l u l u l a u l u l u l u l a u l u l u l u l =++++=++++=++++--++--+++++--+++,11,2211,2,2,11,222,211,2,1,1,11,122,111,1即),,2,1(,11n r r i a u l u l ir rr ir r k kr ik ++==+∑-=故得L 的第r 列元素：)1,,3,2;,,2,1(,11-=++=-=∑-=n r n r r i u u l a l rrr k krik ir ir （4.7）称由（4.4）－（4.7）式所表示的矩阵分解为Doolittle 分解。

它的计算顺序为：U 的第1行→L 的第1列→U 的第2行→L 的第2列→…→U 的第r 行→L 的第r 列→…→U 的第1-n 行→L 的第1-n 列→U 的第n 行。

(r 从1到n 循环即可！)实现了系数矩阵A 的Doolittle 分解后，求解方程组b x =A 的问题就等价于求解两个三角形方程组（1）b y =L ，求y ；（2）y x =U ，求x 。

利用4－0节有关结论，立得Doolittle 分解相应的求解公式为：⎪⎩⎪⎨⎧=-==∑-=),,3,2(1111n r y l b y b y r i i ri r r ⎪⎪⎩⎪⎪⎨⎧--=-==∑+=)1,2,,2,1(/1 n n r u x u y x u y x rr n r i i ri r r nnn n 类似地，可以推导Crout 分解的计算公式：),,2,1;,,1,(11n r n r r i u l a l r k kr ik ir ir =+=-=∑-=)1,,2,1;,,1(11-=+=-=∑-=n r n r i l u l a u rrr k kirk ri ri它的计算顺序为：L 的第1列→U 的第1行→L 的第2列→U 的第2行→…→L 的第r 列→U 的第r 行→…→L 的第1-n 列→U 的第1-n 行→L 的第n 行Crout 分解相应的求解公式为：⎪⎪⎩⎪⎪⎨⎧=-==∑-=),,3,2(/111111n r l y l b y l b y rr r i i ri r r ⎪⎩⎪⎨⎧--=-==∑+=)1,2,,2,1(1 n n r x u y x y x nr i i ri r r n n小结：Doolittle 分解计算：A ＝LU 1．计算U 的第1行元素： ),,2,1(11n i a u i i ==如果011=u ，则计算停止。

2．计算L 的第1列元素：),,3,2(1111n i u a l i i ==3．对于n r ,,3,2 =（1）计算U 的第r 行元素：),,1,(11n r r i u l a u r k ki rk ri ri +=-=∑-=如果0=rr u ，则计算停止。

（2）计算L 的第r 列元素：),,2,1(,11n r r i u u l a l rrr k krik ir ir ++=-=∑-=4．求解计算：y x b y ==U L ,⎪⎩⎪⎨⎧=-==∑-=),,3,2(1111n r y l b y b y r i iri r r⎪⎪⎩⎪⎪⎨⎧--=-==∑+=)1,,2,1(/1n n r u x u y x u y x rrnr i iri r r nn n n例：用Doolittle 法解方程组⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡-=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------725101391444321131243301024321x x x x 直接利用公式计算，从中总结 Doolittle 分解的计算规律（图示中还可清楚地看到存贮情况）： Gauss 消去法逐步对A 施加变换，逐步获得L ，U ，而Doolittle 分解公式则集中了前r-1次变换，一次性付诸实施。

U 的第1行与L 的第1列：⎥⎥⎥⎥⎦⎤⎢⎢⎣nn nn a a a a 2222U的第2行与L的第2列：⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡nn nin n i l l l u 2112111⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎣nn nin n in iin i n ia a a l a a u u u u212222211 U的第3行与L 的第3列：⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡nn ni n n n in iii i i n in i n ia a a l l a a a l l a a a l l u u u u l u u u u u 321321333332312223222111131211⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎣nn nin n n in iin in i n ia a a l l a a u u u u u u 321332211 U的第r 行与L 的第r 列（1,,3,2-=n r ）：⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎣---nn ninrr n n in iirn rin r i r n ia a a l l a a u u u u1,1,1,111最后计算U 的第n 行（实际上只有一个元素nn u ）。

注意在计算U 和解y b 看作A 的第1+n 列，它们遵循着相同的规则。

事实上，由y b L LU A ==,，得),(),(1b y A L U -=，据此，我们可得到紧凑格式的Doolittle 分解：即将上述分解过程处理的对象由A 改为增广矩阵),(b A ，用同样的方法处理第1+n 列，从而在获得系数矩阵的Doolittle 分解U L ,的同时，存放在增广矩阵第1+n 列中的元素就是y 。

(注意此时在公式（4.4）（4.6）中计算ri u 时，i 应到1+n 为止，编程计算时，应注意所有y x ,,,U L 的元素都存贮在增广矩阵中)紧凑格式的Doolittle 分解的算法设计： 小结：分解计算：A ＝LU 1．对于n r ,,3,2,1 =（1）计算U 的第r 行元素：)1,,1,(1111++=-=-=←∑∑-=-=n r r i a a a u l a u a r k ki rk ri r k ki rk ri ri ri如果0=rr a ，则计算停止。