线性代数方程组的直接解法_赖志柱.doc

第二章 线性代数方程组的直接解法 教学目标：1.了解线性代数方程组的结构、基本理论以及相关解法的发展历程；2.掌握高斯消去法的原理和计算步骤，理解顺序消去法能够实现的条件，并在此基础上理解矩阵的三角分解（即LU分解），能应用高斯消去法熟练计算简单的线性代数方程组；3.在理解高斯消去法的缺点的基础上，掌握有换行步骤的高斯消去法，从而理解和掌握选主元素的高斯消去法，尤其是列主元素消去法的理论和计算步骤，并能灵活的应用于实际中。教学重点：1. 高斯消去法的原理和计算步骤；2. 顺序消去法能够实现的条件；3. 矩阵的三角分解（即LU分解）；4. 列主元素消去法的理论和计算步骤。教学难点：1. 高斯消去法的原理和计算步骤；2. 矩阵的三角分解（即LU分解）；3. 列主元素消去法的理论和计算步骤。教学方法：教具：引 言在自然科学和工程技术中，许多问题的解决常常归结为线性方程组的求解，有的问题的数学模型中虽不直接表现为线性方程组，但它的数值解法中将问题“离散化”或 “线性化”为线性方程组。例如，电学中的网络问题、船体数学放样中建立三次样条函数问题、最小二乘法用于求解实验数据的曲线拟合问题、求解非线性方程组问题、用差分法或有限元法求解常微分方程边值问题及偏微分方程的定解问题，都要导致求解一个或若干个线性方程组的问题。目前，计算机上解线性方程组的数值方法尽管很多，但归纳起来，大致可以分为两大类：一类是直接法（也称精确解法）；另一类是迭代法。例如线性代数中的Cramer法则就是一种直接法，但其对高阶方程组计算量太大，不是一种实用的算法。实用的直接法中具有代表性的算法是高斯（Gauss）消元法，其它算法都是它的变形和应用。在数值计算历史上，直接法和迭代法交替生辉。一种解法的兴旺与计算机的硬件环境和问题规模是密切相关的。一般说来，对同等规模的线性方程组，直接法对计算机的要求高于迭代法。对于中、低阶（）以及高阶带形的线性方程组，由于直接法的准确性和可靠性高，一般都用直接法求解。对于一般高阶方程组，特别是系数矩阵为大型稀疏矩阵的线性方程组用迭代法有效。2.1 基本定理和问题设具有个未知数的个方程的线性方程组为 （2.1）或 （） （2.1）其矩阵形式可以表示为 （2.2）其中其增广矩阵为（，） （2.3）则方程组（2.1）、（2.1）或（2.2）和（2.3）是一一对应的。若用表示矩阵的秩，则有关于线性方程组（2.2）的解的存在性的基本定理（在高等代数或线性代数中有证明）：定理2.1 （1）方程组（2.2）有解的充分必要条件是；（2）若，则方程组（2.2）具有一族解，其解可表示为其中为的任一特解，是齐次方程组的解，且线性无关，为任意常数。（3）若，则方程组（2.2）有唯一解。定义2.1 如果两个方程组的解相同，则称这两个方程组为同解（等价）方程组。不难证明：将方程组中任意两个方程交换次序，所得方程组和原方程组为同解方程组；将方程组中任一方程的一个倍数加到另一个方程上，所得方程组和原方程组为同解方程组。用表示（2.1）的第个方程或（2.3）的第行，记（2.3）的第行与第行互换为，而（2.3）的第行乘以加到第行记为。这是矩阵的初等变换，相当于左乘一个初等矩阵。同样的运算符号，我们也理解为方程组（2.1）作相应的变换。经过这些变换后得到的方程组与方程组（2.1）同解（或等价）。对于线性方程组（2.2）的求解，在理论上并不存在困难。若，即为非奇异（可逆）矩阵，它的行列式，则应用Cramer法则可求得（）其中是用代替中第列而得到的相应的行列式。然而在实际中，当未知数的个数比较大时，按Cramer法则进行计算，其工作量就会大得惊人，因而该方法在实际操作中并不可行。阶行列式共有项，每项都有个因子，所以计算一个阶行列式需要做次乘法，我们共需要计算个行列式，要计算出，还要做次除法，因此用Cramer法则求解线性方程组（2.2）就要做次乘除法（不计加减法）。如时，；当时，可见，在实际计算中Cramer法则几乎没有什么用处。本章的主要目的就是研究求解线性方程组（2.2）的有效算法。某一算法的效率可以用下列两个主要的准则来判断：（1）该算法的计算速度如何？即计算中要设计多少次运算？（2）计算所得到解的精度如何？这两个准则是针对在计算机上求解高阶方程组而提出的。由于线性方程组阶数很高时求解所需要的计算量极其巨大，因而很自然地提出准则（1）。准则（2）的提出，是由于在实际问题当中舍入误差的影响，可能使计算解产生偏离真实解的不可忽视的误差。特别地，在解高阶方程组时涉及大量的运算，舍入误差潜在地积累有可能造成计算解对真实解的严重偏离。后续章节还要详细地研究误差的影响。在研究（2.2）的数值方法之前，先考察一下求解中会遇到的一些困难，这有助于理解后面将要提出的一些数值计算方法。2.2 Gauss消去法从这一节开始，我们来讨论线性方程组（2.1）或（2.2）的直接解法。所谓直接法，就是它只包含有限次的四则运算，若假定每一步运算过程中都不产生舍入误差，计算的结果就是方程组的精确解。这种方法中最基本和最简单的就是Gauss消去法及其变形。2.2.1 Gauss消去法的计算过程设方程组（2.1）或（2.2）的系数矩阵非奇异，并记，这样方程组（2.2）又记为。要完成Gauss消去法的第1步须先假定，令（），则运算（）将变换为 （2.4）其中，对应（2.4）的方程组是，它与（2.2）等价，而其第2至第个方程中的项已经消去。一般地，设消去法已进行了步，得到方程组。此时对应的增广矩阵为 （2.5）假设，令（），则运算（）的结果是方程组，对应增广矩阵为，其中的元素为 （2.6）如果依次有（），则可进行第步，得到与（2.2）等价的方程组，其中是一个上三角阵，且这样就完成了消去过程。因为非奇异，故有。接下来解，因为是上三角阵，这只要用逐次向后代入的方法即可，这个过程称为回代过程，其计算公式为 （2.7）以上有消去过程和回代过程合起来求出（2.2）的解的过程就称为Gauss消去法，或称为顺序Gauss消去法。从（2.6）可以看出，消去过程的第步共含有除法运算次，乘法和减法运算各次，所以消去过程共含有乘除法次数为含加减法次数为 而回代过程含乘除法次数为，加减法次数为，所以Gauss消去法总的乘除法次数为，加减法次数为。当时，用Cramer法则需要乘除法，而用Gauss消去法仅需430次乘除法运算。例2.1 用Gauss消去法解方程组：（1）（2）解：（1）对增广矩阵进行初等变换得等价的方程组，解得，。（2）对增广矩阵进行初等变换得等价方程组 回代得，。2.2.2 消去法的进一步讨论，矩阵的LU分解从上面的消去过程可以看出，Gauss消去步骤能顺序进行的条件是全不为零。设矩阵的顺序主子式为，即， （2.8）则有下面的定理：定理2.2 （）全不为零的充分必要条件是的顺序主子式（），其中。证明：设（），则可以进行消去法的步，每步由逐次实行的运算得到，这些运算不改变相应顺序主子式之值，所以有这样便有（），必要性得证。用归纳法证明充分性。时显然成立。设命题对成立。现设。由归纳假设有，Gauss消去法就可以进行步，约化为其中是对角元为的上三角阵。因为是通过消去法由逐步得到的，的阶顺序主子式等于的阶顺序主子式，即由可推出。定理2.3 对方程组，其中非奇异，若的顺序主子式均不为零，则可以Gauss消去法求出方程组的解。定义2.2 设矩阵每一行对角元素的绝对值都大于同行其它元素绝对值之和，即，则称为严格（行）对角占优矩阵。定理2.4 设线性方程组的系数矩阵为严格对角占优矩阵，则用顺序Gauss消去法求解时（）全不为零。证明：（略）下面我们来讨论Gauss消去过程用矩阵运算表示的形式。第1步令，作一次运算，这相当于左乘矩阵，第1步的全过程相当于，其中设步后系数矩阵化为，其分块形式写成 其中为上三角的阶方阵，为阶方阵，设其左上角元素，则下一步的乘数为，。若记是第个分量为1的单位向量，记，其前个分量为零，从而有。第步中系数矩阵的约化可用矩阵运算描述为 其中是上三角的阶矩阵，是阶方阵，而 （2.9）可以验证 即有。这样，经过步得到，这里的是上三角阵，记，又记 （2.10）是一个对角线元素全为1的下三角阵，这种矩阵称为单位下三角阵。的对角线以下元素就是各步消去的乘数。最后我们可以得到，其中是一个单位下三角阵，是一个上三角阵。定义2.3 将矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积，称为对矩阵的LU分解或三角分解。当是单位下三角矩阵时称为Doolittle（杜里克尔）分解。当是单位上三角矩阵时称为Crout（克洛特）分解。由上面的分析过程知，Gauss消去法的实质是将系数矩阵分解为一个下三角矩阵和一个上三角矩阵相乘，即将系数矩阵进行LU分解。在矩阵的LU分解中，我们将写成，其中是对角矩阵，是单位上三角阵，进一步记，它是一个下三角阵，这样有其中是一个下三角阵，是单位上三角阵，此即的Crout分解。 在矩阵的Doolittle分解中，我们将上三角阵写成的形式，这里的为对角阵，为单位上三角阵，这样得到，其中为单位下三角阵，为对角阵，为单位上三角阵，称其为的LDU分解。定理2.5 设非奇异矩阵，若其顺序主子式都不等于零，则存在唯一的单位下三角阵和上三角阵，使。证明：上面的分析过程已经说明了非奇异矩阵可作LU分解，下面只需证明分解的唯一性。设有两个分解式和，其中都是单位下三角阵，都是上三角阵，则有。因为非奇异，从而，都可逆。故在两边同时左乘和右乘，这样得到。因为仍为上三角阵，故也是上三角阵，同理可得是单位下三角阵，结合知只可能，即有，。证毕可以证明，对于奇异矩阵依然满足定理2.5。而且，从上面的推导过程可以看到，对作LU分解时，其中的为还可以验证的顺序主子式为对应的和的顺序主子式的乘积，而的阶顺序主子式满足，。定理2.6 非奇异矩阵有唯一的LDU分解的充分必要条件是的顺序主子式都不等于零。2.3 主元素消去法2.3.1 有换行步骤的消去法顺序Gauss消去法可以进行的条件是，如果有某个，消去法就不能继续使用。例如，若，则第1步就不能进行，但我们可以在的第1列中找出一个非零元，进行换行后再做消去法，其他各步可以类似处理。有时候虽然，但很小，顺序Gauss消去法可以顺利进行下去，但计算过程舍入误差导致误差增长过大，以致结果不可靠，此时称为小主元。例2.2 用三位十进制浮点运算求解解：不难发现这个方程组的准确解应该接近。下面我们用顺序Gauss消去法来求解，则有，在三位十进制运算的限制下，得到代回第一个方程得。这显然不正确。从上例的计算过程不难发现，计算解产生误差的原因是小主元做除数。因此，为使这种不稳定现象发生的可能性减至最小，在每一步就要寻找一个远不是零的数作除数，既要寻找使，并将第行与第行对换。这样的当前值就远不是零，这时的元素称为列的主元素，行叫做主元素行，这样就引出了列主元消去法。2.3.2 列主元消去法与完全主元消去法列主元消去法也称为按列部分选主元的消去法。其具体过程如下：进行第1步之前，在的第1列中选出绝对值最大的元素，即，其中。因为非奇异，故有。若，则消去过程与顺序Gauss消去法一样；若，则先进行换行，然后类似顺序Gauss消去法的运算得到。一般地，设进行了步选主元和消去法的步骤，得到。第步先选主元，使，即在的第列的对角线及对角线以下的元素中选出绝对值最大值，显然，且由于非奇异，从而有。若，则进行顺序Gauss消去法的第步；若，则对先换行，然后进行类似Gauss消去法的运算。如上进行步选主元、换行与消去法运算，得到，其中是一个上三角阵，再回代进行求解。列主元消去算法：1、消去过程：对（1）选主元：找，使；（2）若，则停止计算（）；（3）若，则换行；（4）消元：对，；对，2、回代过程：（1）若，则停止计算（）；（2）；（3）对，。完全主元消去法：在列主元消去算法的过程中，不是按列来选主元，而是在右下角的阶子阵中选主元，即，然后将的第行与第行、第列与第列交换，再进行消去运算。完全主元法比列主元法运算量大得多，可以证明列主元消去法的舍入误差一般已比较小，在实际计算中多用列主元法。例2.3 用列主元消去法解方程组，计算过程取五位数字，其中解： 回代得：，。其精确解为而用顺序Gauss消去法，则可解得这个结果误差比较大，这是因为消去法的第1步中，按绝对值比其他元素小很多所引起的。2.4 直接三角分解法Gauss消去法还有许多变形，有些变形是为了利用特殊技巧减少误差，把Gauss消去法改写为更紧凑的形式，还有一些变形时根据某类矩阵的特性作一些修正和简化，这些方法可统称为直接三角分解法。2.4.1 矩阵的三角分解设的顺序主子式，则可建立线性方程组的Gauss消去法与矩阵分解的关系，即矩阵的LU分解。这个问题前面已经讲的比较详细了，此处不再赘述。2.4.2 Doolittle分解法首先假设的顺序主子式都不为零，则可作Doolittle分解，即，其中是单位下三角阵，有，时；是上三角阵，时。仔细写出为（2.11）在前面逐步推导和的元素公式都要借助于有关的来表示。现在强调指出，只要从给定的通过比较（2.11）式的两边就可能逐步地把和构造出来，而不必利用Gauss消去法的中间结果，这种方法称为Gauss消去法的紧凑格式。根据矩阵的乘法规则，比较（2.11）式的两边可得， （2.12）先算出的第1行，在（2.12）令，由，可得，接着在（2.12）中令，由，从而算出的第1列，若的第1至行和的第1