研究生数值分析直接三角分解法PPT课件

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