第二节矩阵三角分解法 一、Doolittle分解法 二、平方根法 1、平方根法 2、LDL分解法 三、追赶法
第二节 矩阵三角分解法 一、 Doolittle 分解法 二、平方根法 1、 平方根法 2、 LDLT 分解法 三、追赶法
一、Doolittle分解法 设矩阵A存在LU分解，即有 12 12 12 an an2 比较两端的第一行，有 41y=a j=1,2,…,n
设矩阵A存在LU分解，即有 11 12 1 11 12 1 21 22 2 21 22 2 1 2 1 2 1 0` 0 1 0 0 1 0 0 n n n n n n nn n n nn a a a u u u a a a l u u a a a l l u = 比较两端的第一行，有 u a 1 1 j j = j n =1,2, , 一、 Doolittle 分解法
比较两端的第一列，有 11=a1/41 i=2,3,,n 再比较两端第二行的其余元素得 42,=a2,-24. j=2,3,…,n 再比较两端第二列的其余元素得 2=(a2-li42)/u2 i=2,3,…,n
比较两端的第一列，有 1 1 11 / i i l a u = i n = 2,3, , . 再比较两端第二行的其余元素得 2 2 21 1 , j j j u a l u = − j n = 2,3, , . 再比较两端第二列的其余元素得 2 2 1 12 22 ( )/ , 2,3, , i i i l a l u u i n = − =
从上面的计算过程，不难归纳出一般的计算公式 j=1,2,,n (21) aa/ /4, i=2,3,…,n 再对k=2,3,…,n 计算 =w-1u j=k,k+1,…,n (22） 6=a2 i=k+l,…,n
从上面的计算过程，不难归纳出一般的计算公式 1 1 , j n =1,2, , 1 1 11 , j j i i u a a l u = = i n = 2,3, , . (2.1) 再对 k n = 2,3, , 计算 1 , 1 1 1 ( ) , k kj kj ks sj s k ik ik is sk kk s u a l u l a l u u − = − = = − = − (2.2) j k k n = + , 1, , i k n = +1,
同时，由Y=b,按上边顺序依次求得： =b,=b-∑1y k=2,3,…,n 2.3) 这个分解过程叫做Doolitt 2 分解，用这种方 法求解方程组所需要的计算量和用Gass消元法 计算需要的计算量基本相同，但这种方法把对系 数矩阵的计算和对右端项的计算分开了，这就使
同时，由 LY b = ，按上边顺序依次求得： 1 1 1 1 , , k k k ks s s y b y b l y − = = = − k n = 2,3, , . (2.3) 这个分解过程叫做 Doolittle 分解，用这种方 法求解方程组所需要的计算量和用 Gauss 消元法 计算需要的计算量基本相同，但这种方法把 对系 数矩阵的计算和对右端项的计算分开了，这就使
我们在计算系数矩阵相同而右端项不同的一系 列方程组时变得特别方便。 与此类似，如果A存在LU分解，则有 A-LU=LDU=LU 其中，D是以4为对角元素的对角矩阵， 0是单位上三角矩阵，立=LD是下三角矩阵， 和Doolittle分解一样，我们可以依次得矩阵i 和0的元素1和u,,从而将矩阵A分解为 A=i0这样的分解称为Crou分解
我们在计算系数矩阵相同而右端项不同的一系 列方程组时变得特别方便。 与此类似，如果A存在LU分解，则有 A LU LDU LU = = = (2.4) 其中， 是以 为对角元素的对角矩阵， 是单位上三角矩阵， 是下三角矩阵， 和 分解一样,我们可以依次得矩阵 和 的元素 和 ， 从而将矩阵A分解为 A LU = Crout D ii u U L LD = Doolittle L U ik l ukj 这样的分解称为 分解
例2 用LU分解求解方程组 卧日 7 和 18 2 X, 解容易验证系数矩阵A的顺序主子式全不为零， 故A存在唯一的LU分解，由(2.1)得 411=2,412=2,413=3 12,=421/41=4/2=2,131=-2/2=-1
例2 用 LU 分解求解方程组 1 2 3 2 2 3 3 4 7 7 1 2 4 5 7 x x x = − − 和 1 2 3 2 2 3 7 4 7 7 18 2 4 5 1 x x x = − 解 容易验证系数矩阵A的顺序主子式全不为零， 11 12 13 21 21 11 31 2, 2, 3 4 2 2, 2 2 1 u u u l a u l = = = = = = = − = − 故A存在唯一的 LU 分解，由 (2.1) 得
再由(2.2)可计算出 422=a2-21412=3,423=a23-21241 12=(a2-442)/422=6/3=2 433=a33-1i43-132423=5+3-2=6 对第一个方程组，由LY=b和(2.3)可求得 y=3y2=-5,y3=6 再由X=Y和(1.4)，求得解X x3=1,x2=-2,x=2
再由 (2.2) 可计算出 ( ) 22 22 21 12 23 23 21 13 32 32 31 12 22 33 33 31 13 32 23 3, 1 6 3 2 5 3 2 6 u a l u u a l u l a l u u u a l u l u = − = = − = = − = = = − − = + − = 对第一个方程组，由 LY b = 和 (2.3) 可求得 y y y 1 2 3 = = − = 3, 5, 6 再由 UX Y = 和 (1.4) ，求得解 X x x x 3 2 1 = = − = 1, 2, 2
对第二个方程组，由LY=b和(23)得 y=7,3=4,⅓=6 由X=Y和(1.4)得 x3=1,x2=1,x1=1
对第二个方程组，由 LY b = 和 (2.3) 得 y y y 1 2 3 = = = 7, 4, 6 由 UX Y = 和 (1.4) 得 3 2 1 x x x = = = 1, 1, 1
二、平方根法 求解对称正定方程组，在许多工程实际计算问 题中经常遇到，由于其本身的特点，使用前述的解 法是不利的，应该采用适合其特点的解法。这里介 绍的Cholesk分解法，其运算量和存储量较LU分解 法均节省一半左右，是目前在计算机上解这类问题 最有效的方法之一。设A为对称正定矩阵，则A的各 阶主子式均大于零，于是有如下三角分解 A=LU (3.1) 其中为下三角矩阵，0为单位上三角矩阵
二、平方根法 求解对称正定方程组，在许多工程实际计算问 题中经常遇到，由于其本身的特点，使用前述的解 法是不利的，应该采用适合其特点的解法。这里介 绍的 分解法，其运算量和存储量较LU分解 法均节省一半左右，是目前在计算机上解这类问题 最有效的方法之一。设A为对称正定矩阵，则A的各 阶主子式均大于零，于是有如下三角分解 Cholesky A LU = (3.1) 其中 L 为下三角矩阵， U 为单位上三角矩阵