研究生数值分析(8).ppt

《研究生数值分析(8).ppt》由会员分享，可在线阅读，更多相关《研究生数值分析(8).ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 三角分解法也是直接法，基本思想是：三角分解法也是直接法，基本思想是：将系数矩阵将系数矩阵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、；(2)A为三对角的追赶法。为三对角的追赶法。把一个把一个n阶矩阵阶矩阵A分解成两个三角形矩阵相分解成两个三角形矩阵相乘的形式称为矩阵的三角分解。乘的形式称为矩阵的三角分解。1 Doolittle分解法和分解法和Crout 分解法分解法A=LU，其中，其中L为下三角阵，为下三角阵，U为上三角阵。为上三角阵。若若U为单位上三角阵为单位上三角阵(对角元都是对角元都是1 1的上三角阵的上三角阵),L L为单位下三角阵为单位下三角阵,则称为则称为克劳特克劳特(Crout)分解分解。矩阵三角分解的常见形式是：矩阵三角分解的常见形式是：作为特例，若作为特例，若L为单位下三角阵为单位下三角阵(对角元都是对角

3、元都是1 1的下三角阵的下三角阵),U为上三角阵，则称为为上三角阵，则称为杜利特尔杜利特尔(Doolittle)分解分解；下面分析实现矩阵杜利特尔下面分析实现矩阵杜利特尔(Doolittle)分解和克分解和克劳特劳特(Crout)分解的条件分解的条件,讨论这些分解的唯一性。讨论这些分解的唯一性。定理定理2 (2 (矩阵三角分解基本定矩阵三角分解基本定 理理)则存在唯一的杜利特尔分解则存在唯一的杜利特尔分解A=LU，其中，其中L 为单位下三角阵，为单位下三角阵，U 为非奇异上三角阵。为非奇异上三角阵。设设 。若。若A的顺序的顺序主子式主子式 还可以证明存在唯一的克劳特还可以证明存在唯一的克劳特C

4、rout分解分解这里这里L为非奇异下三角阵，为非奇异下三角阵，U为单位上三角阵。为单位上三角阵。如果如果A是一般非奇异阵，由列主消元法，是一般非奇异阵，由列主消元法，A适当适当行交换后，行交换后，可使可使A的各阶顺序主子式的各阶顺序主子式 ，从而实现杜利特尔从而实现杜利特尔Doolittle或克劳特或克劳特Crout分解。分解。设方程组设方程组AX=b的系数矩阵的各阶顺序主子式的系数矩阵的各阶顺序主子式，则存在唯一杜利特尔分解，则存在唯一杜利特尔分解，其中，其中 杜利特尔杜利特尔Doolittle分解法分解法下面介绍直接根据下面介绍直接根据A的元素计算的元素计算L、U元素的分解方法元素的分解方

5、法由矩阵乘法规则与相等条件由矩阵乘法规则与相等条件,第一步第一步求求U的第一行元素和的第一行元素和L的第一列元素的第一列元素第二步第二步求求U的第二行元素和的第二行元素和L的第二列元素的第二列元素.对那些明确是对那些明确是1或是或是0的元素不再求。的元素不再求。导出计算导出计算 或或 的公式。的公式。利用利用 在上述计算过程中，在上述计算过程中，第一步第一步计算由计算由 得得第二步第二步计算计算由由 得得（1）由由 得得由由 得得（2）例如例如第第k步计算步计算U的第的第k行行L的第的第k列元素的公式为：列元素的公式为：在我们利用杜利特尔矩阵分解解线性方程组在我们利用杜利特尔矩阵分解解线性方程

6、组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，即按计算公即按计算公式式

7、(5)依次计算依次计算30 求解三角形方程组求解三角形方程组UX=Y，即按计算公即按计算公式式(6)依次计算依次计算为便于记忆，我们给出为便于记忆，我们给出L、U分解紧凑格式分解紧凑格式:在解方程组时在解方程组时,对于右端项对于右端项b也可不必经也可不必经过中间过程过中间过程而按紧凑格式的方法直接得出而按紧凑格式的方法直接得出y，因为因为Ly=b，所以，所以 它与公式（它与公式（3）相似。若将）相似。若将b作为增广矩阵的最作为增广矩阵的最后一列元素后一列元素,那么对增广矩阵作那么对增广矩阵作LU分解分解,b也作相应也作相应运算运算,仍在最后一列仍在最后一列,则分解后的最后一列即为则分解后的最后

8、一列即为y。于是于是 例例3：将方程组：将方程组解：增广矩阵为解：增广矩阵为的系数矩阵作的系数矩阵作LU分解，并求方程组的解。分解，并求方程组的解。LU分解的紧凑格式为分解的紧凑格式为所以系数矩阵所以系数矩阵的三角分解为的三角分解为等价的三角方程组为等价的三角方程组为用回代法解得用回代法解得 4 追赶法求解三对角线性方程组追赶法求解三对角线性方程组 在样条函数的计算、微分方程数值求在样条函数的计算、微分方程数值求解中常遇到如下形式的线性代数方程组：解中常遇到如下形式的线性代数方程组：其中方程组其中方程组AX=f 的系数矩阵的系数矩阵A的元素满足条件：的元素满足条件：且且（1）根据系数矩阵根据系

9、数矩阵A的特点，设的特点，设其中其中 为待定系数。比较为待定系数。比较A与与LU对应对应的元素，有的元素，有（2）由（由（1）和（）和（2）可以看出）可以看出因此有因此有 由由 有有 一般地，用归纳法可以证明一般地，用归纳法可以证明因此我们从关系式（因此我们从关系式（2）解出待定系数为）解出待定系数为（3）由以上推导过程知，方程组由以上推导过程知，方程组AX=f 有唯一解有唯一解由（由（3）式可得计算）式可得计算 的递推公式的递推公式（4）只要计算出只要计算出 ，其它待定系数，其它待定系数 与与 均可均可通过已知数通过已知数 与与 表示。表示。上述解方程组上述解方程组 AX=f 的过程归纳为：

10、的过程归纳为：10 实现实现A=LU分解分解,按递推公式按递推公式(4)计算计算20 求解方程组求解方程组 LY=f ,相应的递推公式是相应的递推公式是（5）30 求解方程组求解方程组 UX=Y ,相应的递推公式是相应的递推公式是 （6）计算计算 及及 的过程的过程称为追的过程，计算方程组的解称为追的过程，计算方程组的解 的过程的过程称为赶的过程，因此上述方法称为追赶法。称为赶的过程，因此上述方法称为追赶法。例例4：用追赶法解方程组：用追赶法解方程组解：按递推公式（解：按递推公式（4）计算）计算 得得按递推公式（按递推公式（5）计算）计算得得按递推公式（按递推公式（6）计算）计算 得得 用追赶法解方程组用追赶法解方程组 AX=f 仅需仅需 5n-4 次乘除次乘除法运算法运算,计算过程稳定。计算过程稳定。练习：练习：1、利用、利用LU分解求解四元线性方程组分解求解四元线性方程组AX=b，其中其中2、用追赶法求方程组的解、用追赶法求方程组的解