《现代数值计算》课件5.3 直接三角分解方法

1、5.3 直接三角分解法5.3.3 平方根法5.3.1 一般矩阵的直接三角分解法5.3.2 三对角方程组的追赶法5.3 直接三角分解法5.3.1 一般矩阵的直接三角分解法三角分解的紧凑形式 将高斯消去法改写为紧凑形式，可以直接从矩阵A的元素得到计算L、U元素的递推公式，而不需任何中间步骤，这就是所谓直接三角分解法. 一旦实现了矩阵A的LU分解，那么求解Ax=b的问题就等价于求解两个三角形方程组 (1)Ly=b，求y； (2)Ux=y，求x 1.不选主元的三角分解法 设A为非奇异矩阵，且有分解式A=LU，其中L为单位下三角阵，U为上三角阵，即如果U的第1至k-1列和L的第1至k-1列已经算出，则由

2、可得U的第k行元素同理，由ukj =akj ,j =k,k+1, ,n。 （5.3.3） akj = ,i=k+1,k+2,n, （5.3.1）（5.3.2）由A的第1行和第1列可计算出U的第1行和L的第1列，即可得L的第k列元素交替使用（5.3.3）和 （5.3.4），就能逐次计算出U（按行）和L（按列）的全部元素，而且可以把它们存放在矩阵A对应的位置上（L的对角线元素不必存放）。这就完成了A的LU分解。 lik=(aik )/ ukk ,i =k+1,k+2, ,n。 由（5.3.1）- （5.3.4）求得L和U后，解方程组Ax=b 化为求解LUx=b，若记Ux=y，则有Ly=b。于是可分

3、两部解方程组LUx=b，只要逐次向前代入的方法即可求得y。第二步求解Ux=y，只要逐次用向后回代的方法即可求得x。设 x=（x1 ，x2， xn) T, y=（y1, y2, yn) T, b= (b1 ，b2， bn) T, 则有计算公式（5.3.4）（5.3.5）（5.3.6） 以上解方程组的计算与顺序Gauss消去法相当。如果有一系列方程组，其系数矩阵都是相同的，右端向量b不同，则只须进行一次LU分解计算。上述解方程的方法称为LU分解法，也称杜利特尔(Doolittle)方法。 解 由LU分解的紧凑格式（5.3.1）-（ 5.3.4 ）计算可得例5.5 用LU分解法求解解下三角方程组 L

4、y = b，即解(单位)上三角方程组 Ux= y，即二 Crout分解（） 设A为非奇异矩阵，A还有一种分解式A=LU，其中L为下三角阵，U为单位上三角阵，即 先计算L的第一列，再计算U的第一行，其余类此。得到以下公式， 实现 A=LU，则 Ax=b 可以化为 LUx=b。令 Ux=y，则 Ly=b。 由 Ly=b解出 yi: 再由 Ux=y 解出 xi: 例5.5用Crout分解求解方程组：解 设 A=LU，即解下三角方程组 Ly = b，即解(单位)上三角方程组 Ux= y，即在数值求解常微分方程边值问题、热传导方程和建立三次样条函数时，都会要解三对角方程组：AX=b5.3.2 三对角方程

5、组的追赶法并且满足条件(i)保证方程组不能降阶，条件(ii)保证三角分解可做到底。(5.3.7)下面讨论三角分解(1)如果A满足Gauss消去法的条件,可用LU (Doolittle)分解法求解. 并且, L和U有如下形式(5.3.8)按乘法展开 (5.3.9)计算次序为 而解原方程组Ax=b可分为两步Ly=d和Ux=y,计算公式为称这一过程为“追”的过程. (5.3.10)(5.3.11)称为(5.3.9)、(5.3.10)和(5.3.11)为求解三对角形方程组的追赶法,又称为Thomas算法。追赶法求解 Ax=f 仅需5n-4次乘除运算。工作量较小。追赶法能实现的条件是ui0，i=1,2,

6、n.下面给出追赶法的一个充分条件。定理5.6 设三对角矩阵A有(5.3.7)的表达式,且满足则A非奇异,且有(2)*如果A满足Gauss消去法的条件,也可用LU (Crout)分解法求解. 并且, L和U有如下形式(5.3.8*)按乘法展开 则可计算 计算次序为 (5.3.9*)(5.3.10*)而解原方程组Ax=b可分为两步Ly=d和Ux=y,计算公式为称这一过程为“追”的过程. 由此可依次求得L和U的所有元素.(5.3.11*)例 用追赶法求解三对角线性方程组AX=b，其中作Doolitle分解解作Crout分解解练习 用追赶法求解三对角方程组- Crout 分解 解 由Ly=f 解出y又

7、由Ux=y解出x 5.3.3 平方根法 工程实际计算中,线性方程组的系数矩阵常常具有对称正定性.(5.3.12)总结上述讨论有2.若A为对称正定矩阵, det(Ak)0,(k=1,2,n), （5.3.13）记 于是对角阵D还可分解称（5.3.13）式为矩阵A的乔累斯基(Cholesky)分解。利用A的Cholesky分解式来求解方程组Ax=b的方法称为Cholesky方法或平方根法，这是因为计算过程含开方运算。 下面我们用直接分解方法来确定计算L元素的递推公式。因为 其中lii0(i=1,2,n)由矩阵乘法及ljk=0(当jk),得于是得到解对称正定方程组Ax=b的平方根法计算公式：（5.3

8、.15）（5.3.14）对于 j=1,2,n, 按逐列计算L的元素的计算步骤,设第1列至第j-1列已经计算得到,则有 平方根法的原理基于矩阵的LU分解,所以它也是Gauss消去法的变形.但由于利用了矩阵正定的性质,减少了计算量。平方根法的乘除法运算次数为(n3+9n2+2)/6,加减法次数为(n3+6n2-7n)/6 。另外还有n次开方运算，其所含乘除法和加减法次数可分别看成n的常数倍。平方根需n3 /6次乘除法，与Gauss消去法相比减少了一半。3. 求解Ax=b，即求解两个三角形方程组 (1)Ly=b，求y； （2）LTx=y，求x 解 不难验证系数矩阵是对称正定的，按（5.3.14）和（5.3.15）依次计算得 例5.6 用平方根法求解解Ly=(6, -0.5, 1.25)T ,得y=(3, 0.5, -1) T ，再解LTx=y可以得到x=(2,1,-1)T 。 （5.3.14）则可避免开方根运算，称为改进的平方根法。 它既适合于求接对称正定方程组，也适合于求解A对称且其顺序主子式全不为零的方程组。分解式的计算公式为(j=1,2,n) 如果对矩阵采用定理4.7的（5.3.12）分解式， 即其中j=1时，求和部分为零。这样求解方程组Ax=b化为求解Ly=b和LTx=D-1y.4.改进的平方根法解Ly=b得y=(6,1,