矩阵的LU分解.doc

第四章 矩阵的分解将矩阵分解为具有某种特性的因子之积，从以我们所熟悉的Gauss消去法为依据而导出的LU分解，到上个世纪60、70年代以Givens和Householder变换发展起来的QR分解，在矩阵理论的研究与应用中都具有十分重要的意义。这些特殊的分解式一方面反映了原矩阵的某些数值特征，另一方面，分解的方法与过程也为某些数值计算方法和理论分析提供了有效的工具。4.1 阶矩阵的三角分解和LU分解在线性代数中我们已经学过应用Gauss消去法求解元线性方程组，其中：，。Gauss消去法的基本思路是将系数矩阵化为上三角形矩阵，或将增广矩阵化为上阶梯形矩阵，而后回代求解。现在应用所谓选主元素法来实施Gauss消去法的消去过程，至于回代过程我们不做讨论。设，记的阶顺序主子式为。如果，令 ，构造Frobenius矩阵：，则 （4.1.1）因此，在的第一列中除主元素外，其余元素均被化为零。式（4.1.1）即为，由于倍加变换不改变矩阵行列式的值，所以由得到的二阶顺序主子式为。如果，则必有。令 ，构造Frobenius矩阵：， 则 （4.1.2）因此，在的前两列中，主元素以下的元素均已化为零。式（4.1.2）即为，由于倍加变换不改变矩阵行列式的值，所以由得到的三阶顺序主子式为。依此类推，直到第步，得到：，。如果，则必有。令 ，构造Frobenius矩阵：，计算 （4.1.3）而在的前列中，主元素以下的元素均已化为零。式（4.1.1）即为，由于倍加变换不改变矩阵行列式的值，所以由得到的阶顺序主子式为。依此类推，在第步之后得到以上即为Gauss消元的过程，Gauss消元过程能够进行到底的充分且必要条件是：均不等于零，即 （4.1.4）由于Gauss顺序消元过程没有用到行、列的交换，所以条件（4.1.4）是合理的。在条件（4.1.4）下，有所以是一个主对角线上的元素都是1的下三角矩阵，我们称之为单位下三角矩阵，而是一个上三角矩阵。令，则。定义4.1.1如果阶矩阵能够分解为一个下三角矩阵和一个上三角矩阵的乘积，则称其为三角分解或分解。如果阶矩阵能够分解为，其中为单位下三角矩阵，为对角矩阵，为单位上三角矩阵，则称之为分解。在一个阶矩阵的分解中，若取一个主对角线上的元素都不为零的对角矩阵，则就可以记作，其中，仍分别为下三角矩阵与上三角矩阵，因此，阶矩阵的分解不唯一。定理4.1.1矩阵的分解式唯一的充分且必要条件为的顺序主子式 。其中是单位下三角矩阵，是单位上三角矩阵，是对角矩阵，并且 。推论4.1.1 阶非奇异矩阵有分解的充分且必要条件为的顺序主子式 。例1、 求矩阵 的分解。解：因为，所以有唯一的分解，构造Frobenius矩阵：，则=；对构造Frobenius矩阵：，则=；因此，；所以。由于矩阵的分解与分解都要求的前阶顺序主子式不为零。如果这个条件不满足，则可以对矩阵右（左）乘以置换矩阵，将矩阵的列（或行）重新排列顺序，使排列后的矩阵的前阶顺序主子式不为零。因此有以下的 定理4.1.2设是阶非奇异矩阵，则存在置换矩阵，使得的阶顺序主子式不为零。推论4.1.2设是阶非奇异矩阵，则存在置换矩阵，使 （4.1.5）其中是单位下三角矩阵，是上三角矩阵，是单位上三角矩阵，是对角矩阵。对于线性方程组而言，如果其系数矩阵为非奇异矩阵，并且 ，则存在三角分解。这时，就与方程组等价，而方程组中的两个子方程组很容易求解，这就是解线性方程组的三角分解法。将矩阵分解为一个单位下三角矩阵与一个上三角矩阵的乘积的分解法叫做Doolittle分解。如同Gauss顺序消去法不能消元到底一样，矩阵也不一定存在Doolittle分解。定理4.1.3 阶矩阵有唯一的Doolittle分解的充分且必要条件是为非奇异矩阵，其中 是的阶顺序主子矩阵。证：（充分性）应用数学归纳法设为非奇异矩阵，显然有。设可以分解为，其中是单位下三角矩阵，是非奇异上三角矩阵。的阶顺序主子矩阵 ，其中向量与元素已知。令则有；即。记，则有，并且是单位下三角矩阵，是上三角矩阵，只要，由于是非奇异矩阵，所以也是非奇异矩阵。由归纳法，当时，有其中是单位下三角矩阵，是上三角矩阵。如果是非奇异矩阵，则也是非奇异矩阵；如果是奇异矩阵，则的主对角线上的元素，。再设有两种Doolittle分解。如果是非奇异矩阵，由此式可得，由于是单位下三角矩阵，是上三角矩阵，所以它们只能是单位矩阵，即，所以，。如果是奇异矩阵，则将式写成分块形式 其中都是非奇异矩阵，类似的有 ，所以，。（必要性）设有唯一的Doolittle分解。当是非奇异矩阵时，与都是非奇异矩阵；如果是奇异矩阵，则必有， ，否则，要么的Doolittle分解不存在，要么这种分解虽然存在但不唯一。因此，不论是否是奇异矩阵，与的阶顺序主子矩阵与都是非奇异矩阵。而 ，所以为非奇异矩阵。 推论4.1.3 顺序Gauss消去法的主元素的充分且必要条件是方程组的系数矩阵的阶顺序主子矩阵是非奇异矩阵。以下来看Doolittle分解如何进行。设的顺序主子矩阵为非奇异矩阵，且，。因为，即，所以， 由此得到计算与的递推公式：，；对于，计算当为实对称正定矩阵时，。于是有唯一的分解，即，其中，且。令，则有，由，因此=，再由分解的唯一性有，所以，或者 （4.1.6）其中是下三角矩阵。定义4.1.2 实对称正定矩阵的分解式（4.1.6）叫做实对称正定矩阵的Cholesky分解（也叫做平方根分解，或对称三角分解）令，由式（4.1.6）有， 由此得到计算的公式：因为的对角元素，所以， 由此式可知Cholesky分解中的中间量得以控制。将矩阵分解为一个下三角矩阵和一个单位上三角矩阵之积的分解，叫做矩阵的Crout分解。定理4.1.4阶矩阵有唯一的Crout分解的充分且必要条件是的顺序主子式为非奇异矩阵。仍用表示的Crout分解，这里是下三角矩阵，是单位上三角矩阵，。与定理4.1.3类似可得到计算与的递推公式：，；对于，计算例2、 求矩阵的Doolittle分解与Crout分解。解：由Doo