线性方程组的数值解法课件

6.5 矩阵三角分解法矩阵三角分解法 6.5.1 6.5.1 矩阵三角分解原理矩阵三角分解原理 应用高斯消去法解应用高斯消去法解 n 阶线性方程组阶线性方程组 Ax=b,经过经过 n 步消元之后步消元之后,得出一个等价的上三角型方程组得出一个等价的上三角型方程组A(n-1)x=b(n-1),对上三角形方程组用逐步回代就可以对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。求出解来。上述过程可通过矩阵分解来实现。将非奇异阵将非奇异阵 A 分解成一个下三角阵分解成一个下三角阵 L 和一个上和一个上三角阵三角阵 U 的乘积：的乘积：A=LU 称为对称为对矩阵矩阵 A A 的的三角分解三角分解，又称，又称LU分解分解。其中其中方程组方程组 Ax=b 的系数矩阵的系数矩阵 A 经过顺序消元逐经过顺序消元逐步化为上三角型步化为上三角型 A(n),相当于用一系列初等变相当于用一系列初等变换左乘换左乘A的结果。事实上，第的结果。事实上，第1列消元将列消元将A(0)=A化为化为A(1)，若令：，若令：则根据距阵左乘有则根据距阵左乘有 L1A(0)=A(1)第第2列消元将列消元将 A(1)化为化为 A(2)，若令：，若令：经计算可知经计算可知 L2A(1)=A(2),依此类推依此类推,一般有一般有LkA(k-1)=A(k)mi1=a(1)i1/a(1)11 i=2,3,n矩阵矩阵 经过消元化为上三角阵经过消元化为上三角阵 的过程的过程可表示为可表示为:是一类初等矩阵是一类初等矩阵,它们都是单位它们都是单位下三角阵，且其逆矩阵也是单位下三角阵下三角阵，且其逆矩阵也是单位下三角阵,只需将只需将 改为改为 ,就得到就得到 。即：。即：于是有：于是有：其中：其中：由此可见，在由此可见，在 的的条件下，高斯消去法实质上是将方程组的系数矩阵条件下，高斯消去法实质上是将方程组的系数矩阵A A分解为两个三角矩阵的乘积分解为两个三角矩阵的乘积 A=LUA=LU。这种把非奇异矩阵这种把非奇异矩阵 A A 分解成一个下三角矩阵分解成一个下三角矩阵 L L 和一个上三角矩阵和一个上三角矩阵 U U 的乘积称为的乘积称为矩阵的三角分解矩阵的三角分解，又称又称 LU LU 分解分解。显然，如果显然，如果 ,由行列由行列式的性质知，方程组系数矩阵式的性质知，方程组系数矩阵 A A 的前的前 n-1 n-1 个顺序个顺序主子矩阵主子矩阵 非奇异，即顺序非奇异，即顺序主子式不等于零，即：主子式不等于零，即：其中：其中：（A A的主子阵）的主子阵）反之反之,可用归纳法证明可用归纳法证明,如果如果 A A 的顺序主子式：的顺序主子式：则则 于是得到下述定理：于是得到下述定理：定理定理6.56.5 设设 ，如果，如果 A 顺序各阶主子式顺序各阶主子式 ,则则A可惟一地可惟一地 分解成一个单位下三角阵分解成一个单位下三角阵 L 和一个非奇异的和一个非奇异的 上三角阵上三角阵 U 的乘积。的乘积。证：证：由于由于A A各阶主子式不为零各阶主子式不为零,则消元过程能进行到底则消元过程能进行到底,前面已证明将方程组的系数矩阵前面已证明将方程组的系数矩阵 A A 用初等变换用初等变换 的方法分解成两个三角矩阵的乘积的方法分解成两个三角矩阵的乘积 A=LU A=LU 的过程。的过程。现仅证明分解的惟一性。现仅证明分解的惟一性。设设A A有两种有两种 LU LU 分解：分解：其中其中 为单位下三角阵，为单位下三角阵，为上三角阵为上三角阵 A A的行列式的行列式 均为非奇异矩阵均为非奇异矩阵,且有：且有：上式两边左边同乘上式两边左边同乘 ，右边同乘，右边同乘 得：得：上式左边为单位下三角阵上式左边为单位下三角阵,右边为上三角阵右边为上三角阵,故应为单故应为单位阵位阵,即：即：惟一性得证。惟一性得证。把把A分解成一个单位下三角阵分解成一个单位下三角阵 L 和一个和一个上三角阵上三角阵 U 的乘积称为的乘积称为杜利特尔杜利特尔（Doolittle）分解分解。其中：其中：若把若把A分解成一个下三角阵分解成一个下三角阵 L 和一个单位和一个单位上三角阵上三角阵 U 的乘积称为的乘积称为克克洛特洛特（Crout）分解，）分解，其中：其中：6.5.2 用三角分解法解方程组用三角分解法解方程组 求求解线性方程组解线性方程组 Ax=b 时时,先对非奇异矩阵先对非奇异矩阵 A 进行进行LU分解，使分解，使 A=LU，那么方程组就化为：，那么方程组就化为：LU x=b从而使问题转化为求解两个简单的三角方程组：从而使问题转化为求解两个简单的三角方程组：L y=b 求解求解 y U x=y 求解求解 x这就是求解线性方程组的这就是求解线性方程组的三角分解法的基本思想三角分解法的基本思想。下面只介绍下面只介绍杜利特尔（杜利特尔（Doolittle）分解法）分解法。设设 A=LU 为：为：由矩阵乘法规则：由矩阵乘法规则：由此可得由此可得 U 的第的第 1 行元素和行元素和 L 的第的第 1 列元素：列元素：再确定再确定 U 的第的第 k 行元素与行元素与 L 的第的第 k 列元素列元素,对于对于K=2,3,n，计算计算L L的第的第k列元素：列元素：（i,ji,j=k,k+1,=k,k+1,n,n）计算计算U的第的第k行元素：行元素：利用上述计算公式便可逐步求出利用上述计算公式便可逐步求出U与与L的各元素的各元素求解求解 Ly=b,即计算即计算:求解求解 Ux=y,即计算：即计算：显显然然,只只有有当当 时时,解解Ax=b的的直直接接三三角角分分解解法法计计算算才才能能完完成成。设设A为为非非奇奇异异矩矩阵阵,当当 时时计计算算将将被被中中断断或或者者当当 的的绝绝对对值值很很小小时时，按按分分解解公公式式计计算算可可能能引引起起舍舍入入误误差差的的积积累累，因因此此可可采采用用与与列列主主元元消消去去法法类类似似的的方方法法，对对矩矩阵阵进进行行行行交换，再实现矩阵的三角分解。交换，再实现矩阵的三角分解。用直接三角分解法解用直接三角分解法解Ax=b大约需要大约需要 次乘除法。次乘除法。例例6.8 用三角分解法解方程组：用三角分解法解方程组：解：解：设设 A=LU A=LU 为：为：例例6.8 用三角分解法解方程组：用三角分解法解方程组：求解求解 Ly=b 得：得：y=2，2，1T 求解求解 Ux=y 得：得：x=-1，0，1 T所以方程组的解为：所以方程组的解为：例例6.8 用三角分解法解方程组：用三角分解法解方程组：6.6 平方根法平方根法 工程实际计算中工程实际计算中,线性方程组的系数矩阵线性方程组的系数矩阵常常具有常常具有对称正定性对称正定性，其各阶顺序主子式及，其各阶顺序主子式及全部特征值均大于全部特征值均大于0。矩阵的这一特性使它的三角分解也有更矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法，如简单的形式，从而导出一些特殊的解法，如平方根法平方根法与与改进的平方根法改进的平方根法。定理定理6.66.6 设设A A是正定矩阵，则存在惟一的对角元素是正定矩阵，则存在惟一的对角元素 均为正数的下三角阵均为正数的下三角阵L L，使，使 A=LLA=LLT T证：证：因因 A A 是正定矩阵是正定矩阵,A,A的顺序主子式的顺序主子式 det(A Ai i)0,i=1,2,)0,i=1,2,n,n 因此存在惟一的分解因此存在惟一的分解 A=LU A=LU L是单位下三角阵是单位下三角阵,U是上三角阵是上三角阵,将将U再分解再分解:其中其中D为对角阵为对角阵,U0为单位上三角阵，于是为单位上三角阵，于是 A=L U=L D U0 又又 A=AT=U0TD LT由分解惟一性由分解惟一性,即得即得:U0T=L A=L D LT 记记 又因为又因为det(Ak)0,(k=1,2,n),故故于是对角阵于是对角阵D还可分解还可分解:其中其中 为下三角阵为下三角阵,令令L=LL=L1 1，定理得证。，定理得证。将将A=LLT展开，写成展开，写成:按矩阵乘法展开，可逐行求出分解矩阵按矩阵乘法展开，可逐行求出分解矩阵L L的元素，计的元素，计算公式是对于算公式是对于 i=1,2,i=1,2,n,n j=i+1,i+2,n j=i+1,i+2,n 这一方法称为这一方法称为平方根法平方根法,又称又称乔累斯基乔累斯基(Cholesky)分解分解,它所需要的乘除次数约它所需要的乘除次数约 为数量级为数量级,比比 LU分解节省近一半的工作量。分解节省近一半的工作量。例例6.96.9 用平方根法求解方程组用平方根法求解方程组 解解:因方程组系数矩阵对称正定因方程组系数矩阵对称正定,设设 A=A=,即：即：解解:例例6.96.9 用平方根法求解方程组用平方根法求解方程组 由由 解得解得:由由 Ly=b Ly=b 解得解得:例例6.96.9 用平方根法求解方程组用平方根法求解方程组 解解:由此例可以看出，平方根法解正定方程组的由此例可以看出，平方根法解正定方程组的缺点缺点是需要进行是需要进行开方运算开方运算。为避免开方运算，我们改用单。为避免开方运算，我们改用单位三角阵作为分解阵，即把对称正定矩阵位三角阵作为分解阵，即把对称正定矩阵A分解成分解成:的形式，其中的形式，其中:为对角阵，而为对角阵，而 是单位下三角阵是单位下三角阵,这里分解公式为这里分解公式为:据此可逐行计算据此可逐行计算 运用这种矩阵分解方法运用这种矩阵分解方法,方程组方程组 Ax=b 可归结为求可归结为求解两个上三角方程组解两个上三角方程组 即即:和和其计算公式分别为其计算公式分别为:和和 上述算法称为上述算法称为改进的平方根法改进的平方根法。这种方法总的计算量。这种方法总的计算量约为约为 ，即仅为高斯消去法计算量的一半。，即仅为高斯消去法计算量的一半。6.4 追赶法追赶法在数值计算中在数值计算中,有一种系数矩阵是三对角矩阵的方程组有一种系数矩阵是三对角矩阵的方程组:简记为简记为 Ax=fAx=f简记为简记为 Ax=f,AAx=f,A满足条件满足条件:（1 1）（2 2）（3 3）用归纳法可以证明，满足上述条件的三对角线性用归纳法可以证明，满足上述条件的三对角线性方程组的系数矩阵方程组的系数矩阵 A 非奇异，所以可以利用矩阵的直非奇异，所以可以利用矩阵的直接三角分解法来推导解三对角线性方程组的计算公式，接三角分解法来推导解三对角线性方程组的计算公式，用克洛特分解法，将用克洛特分解法，将A分解成两个三角阵的乘积。分解成两个三角阵的乘积。设设 A=LU，即：，即：按乘法展开按乘法展开:则可计算则可计算:当当 时时 ,由上式可惟一确定由上式可惟一确定 L L 和和 U U。可依次计算可依次计算:得：得：例例6.10 用追赶法求解三对角方程组用追赶法求解三对角方程组 解：解：由由Ly=f 解出解出y又由又由Ux=y解出解出x