研究生数值分析直接三角分解法.ppt

三角分解法也是直接法，基本思想是： 将系数矩阵A分解为两个三角形矩阵L和U的乘积A=LU ，将方程组AX=b的求解问题归结为两个三角形方程组 LY=b与UX=Y的求解问题。,即：先由LY=b求出Y ，然后由UX=Y求出X ，从而获得AX=b的解。,2 直接三角分解法,(1) A为一般稠密（零元素占很小比例）矩阵的杜利特尔(Doolittlr)和克劳特(Crout)分解法；,(2) A为三对角的追赶法。,把一个n阶矩阵A分解成两个三角形矩阵相乘的形式称为矩阵的三角分解。,1 Doolittle分解法和Crout 分解法,A=LU，其中L为下三角阵，U为上三角阵。,若U为单位上三角阵(对角元都是1的上三角阵), L为单位下三角阵,则称为克劳特(Crout)分解。,矩阵三角分解的常见形式是：,作为特例，若L为单位下三角阵(对角元都是1的下三角阵), U为上三角阵，则称为杜利特尔(Doolittle)分解；,下面分析实现矩阵杜利特尔(Doolittle)分解和克劳特(Crout)分解的条件,讨论这些分解的唯一性。,定理2 (矩阵三角分解基本定理),则存在唯一的杜利特尔分解A=LU，其中L 为单位下三角阵，U 为非奇异上三角阵。,设 。若A的顺序主子式,还可以证明存在唯一的克劳特Crout分解,这里L为非奇异下三角阵，U为单位上三角阵。,如果A是一般非奇异阵，由列主消元法，A适当行交换后，可使A的各阶顺序主子式 ， 从而实现杜利特尔Doolittle或克劳特Crout分解。,设方程组AX=b的系数矩阵的各阶顺序主子式,，则存在唯一杜利特尔分解,，其中,杜利特尔Doolittle分解法,下面介绍直接根据A的元素计算L、U元素的分解方法,由矩阵乘法规则与相等条件,第一步求U的第一行元素和L的第一列元素,第二步求U的第二行元素和L的第二列元素,对那些明确是1或是0的元素不再求。,导出计算 或 的公式。,利用 在上述计算过程中，,第一步计算由 得,第二步计算由 得,（1）,由 得,由 得,（2）,例如,第k步计算U的第k行L的第k列元素的公式为：,在我们利用杜利特尔矩阵分解解线性方程组AX=b时,只要实现矩阵分解A=LU,依次解三角形方程组LY=b与UX=Y即可。,（3）,（4）,（6）,（5）,计算公式：,杜利特尔矩阵分解 求解线性方程组的过程为:,10 实现A=LU分解，即,(a)按计算公式(1),(2)依次计算U的第1行元素 与L的第1列元素,(b) 对k+2,3,n 按计算公式(3),(4)依次计算U的第k行元素 与L的第k列元素,20 求解三角形方程组LY=b，即按计算公式(5)依次计算,30 求解三角形方程组UX=Y，即按计算公式(6)依次计算,为便于记忆，我们给出L、U分解紧凑格式:,在解方程组时,对于右端项b也可不必经过中间过程而按紧凑格式的方法直接得出y，因为Ly=b ，所以,它与公式（3）相似。若将b作为增广矩阵的最后一列元素,那么对增广矩阵作LU分解, b也作相应运算,仍在最后一列,则分解后的最后一列即为y 。 于是,例3：将方程组,解：增广矩阵为,的系数矩阵作LU分解，并求方程组的解。,LU分解的紧凑格式为,所以系数矩阵的三角分解为,等价的三角方程组为,用回代法解得,4 追赶法求解三对角线性方程组,在样条函数的计算、微分方程数值求解中常遇到如下形式的线性代数方程组：,其中方程组AX=f 的系数矩阵A的元素满足条件：,且,（1）,根据系数矩阵A的特点，设,其中 为待定系数。比较A与LU对应的元素，有,（2）,由（1）和（2）可以看出,因此有,由,有,一般地，用归纳法可以证明,因此我们从关系式（2）解出待定系数为,（3）,由以上推导过程知，方程组AX=f 有唯一解,由（3）式可得计算 的递推公式,（4）,只要计算出 ，其它待定系数 与 均可通过已知数 与 表示。,上述解方程组 AX=f 的过程归纳为：,10 实现A=LU分解,按递推公式(4)计算,20 求解方程组 LY=f ,相应的递推公式是,（5）,30 求解方程组 UX=Y ,相应的递推公式是,（6）,计算 及 的过程,称为追的过程，计算方程组的解 的过程称为赶的过程，因此上述方法称为追赶法。,例4：用追赶法解方程组,解：按递推公式（4）计算 得,按递推公式（5）计算,得