《数值分析课件 第5章 解线性方程组的直接法》由会员分享，可在线阅读，更多相关《数值分析课件 第5章 解线性方程组的直接法（76页珍藏版）》请在金锄头文库上搜索。
1、第五章 线性代数方程组的数值解法线性方程求解问题是科学研究和工程计算中最常见的问题。如电学中的网络问题、工程力学中求解连续力学体（微分方程）问题的差分方法、有限元法、边界元法及函数的样条插值、最小二乘拟合等，都包含了解线性方程组问题。因此，线性方程组的解法在数值计算中占有极其重要的地位。对于阶线性方程组，若，则方程组有惟一解。由克莱姆（Cramer）法则，其解为,其中为用向量代替中第列向量所得矩阵。每个阶行列式共有项，每项都有个因子，所以计算一个阶行列式需做次乘法，我们共需要计算个行列式，要计算出，还要做次除法，因此用Cramer法则求解要做次乘除法（不计加减法），计算量十分惊人。如时，就需作
2、约次乘法。可见Cramer法则在理论上是绝对正确的，但当较大时，在实际计算中却是不可行的。因此寻求有效的数值计算方法就成为非常必要的课题。线性方程组的类型很多，若按其系数矩阵阶数的高低和含零元素多少，大致可分为两类：一类是低阶稠密线性方程组，即系数矩阵阶数不高，含零元素很少。另一类是高阶稀疏线性方程组，即系数矩阵阶数高，零元素占绝对优势（比如占以上）。线性方程组的数值解法也可分为两大类：直接法和迭代法。直接法是在没有舍入误差的情况下，通过有限步运算可以得到方程组精确解的方法。但是，在实际计算时，由于初始数据变为机器数而产生的误差以及计算过程中所产生的舍入误差等都要对解的精确度产生影响，因此直接
3、法实际上也只能算出方程真解的近似值。常用的有效算法是Gauss消去法和矩阵的三角分解法。迭代法是用某种极限过程去逼近准确解的方法。如对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列使极限为方程组的解。因为在实际计算时，只能做到有限步，所以得到的也是近似解。常用的迭代法主要有Jacobi迭代法、Gauss- Seidel迭代法、逐次超松弛法及共轭斜量法等。直接法的优点是运算次数固定，并且可以事先估计。它的缺点是通常需要存储系数矩阵和常数项的所有元素，因而所需存贮单元较多，编写程序较复杂，一般适用于求解低阶线性方程组；迭代法的优点是原始系数矩阵始终不变，且只需存储原方程组系数矩阵中的非零
4、元素，因而算法简单，编写程序较方便，且所需存贮单元也较少，所以被广泛用于求解高阶稀疏线性方程组。缺点是存在收敛性和收敛速度问题，因而只能对具有某些性质的方程组才适用。1 消元法1.1 三角方程组的解法形如 (1.1)的方程组称为上三角形方程组。写成矩阵形式简写为。若，则(1.1)有惟一解我们称求解上三角方程组(1.1)的过程为回代过程。同时也看到求解这类方程组是件容易的事，所以对一般形式的方程组，应设法将它化为(1.1)式的形式，然后再求解。1.2 Gauss消去法考虑方程组 (1.2)其矩阵形式为其中化线性方程组(1.2)为等价的三角形方程组的方法有多种，由此导出不同的直接方法，其中Gaus
5、s消去法是最基本的一种方法。Gauss消去法分消元计算和回代求解两个过程。为后面的符号统一起见，记方程组(1.2)为其中。 消元计算第一步：就是要将的第一列主对角元以下的元素全约化为0。设，计算用乘(1.2)的第1个方程，加到第个方程上，完成第一步消元，得(1.2)的同解方程组 (1.3)简记为其中的元素的计算公式为假设前步消元完成后，得(1.2)的同解方程组为 (1.4)简记为。第步：就是要将的第列主对角元以下的元素全约化为0。设，计算用乘(1.4)的第个方程加到第个 方程上，完成第步消元。得同解方程组其中元素的计算公式为继续上述过程，完成步消元后，(1.2)化成同解的上三角方程组 (1.5
6、)简记为。回代求解因，故，于是 (1.6)Gauss消去步骤能顺利进行的条件是，现在的问题是矩阵应具有什么性质，才能保证此条件成立。若用表示的顺序主子式，即有下面定理定理1 约化的主元素的充要条件是矩阵的顺序主子式。证明 必要性。因主元素，可进行步消元，每步消元过程不改变顺序主子式的值，于是必要性得证。用归纳法证明充分性。时命题显然成立。假设命题对成立。设。由归纳法假设有，Gauss消去法可以进行步，约化为其中是对角元为的上三角阵。因是通过步消去法得到的，每步消元过程不改变顺序主子式的值，所以的阶顺序主子式等于的，即由知，充分性得证。1.3 Gauss消去法的计算量1）消元过程的工作量第步消元
7、过程：计算乘子需作次除法运算；第行乘加到第行，需要乘法和减法各次（第列元素无需计算），共行（），所以需要乘法次，故消元过程中的乘、除和减法运算量为乘除法次数：加减法次数：2）回代过程的工作量计算需要次乘除法和次加减法运算，整个回代过程的运算量为：乘除法：减法：所以Gauss 消去法的总运算量为乘除法：（当较大时）加减法：（当较大时）当时，用Gauss消去法约需430次乘除运算，而用Gramer法则约需次乘除法。1.4 Gauss消去法的矩阵形式如果用矩阵形式表示，Gauss消去法的消元过程是对方程组(1.2)的增广矩阵进行一系列初等变换，将系数矩阵化成上三角形矩阵的过程，也等价于用一串初等矩阵
8、去左乘增广矩阵，因此消元过程可以通过矩阵运算来表示。第一次消元等价于用初等矩阵左乘矩阵，即一般地，第次消元等价于用初等矩阵左乘矩阵，即经过次消元后得到有将上三角矩阵记为，得到其中为单位下三角阵。这说明，消元过程实际上是把系数矩阵分解为单位下三角阵与上三角矩阵的乘积的过程。这种分解称为杜利特尔（Doolittle）分解，也称为分解。定理2（矩阵的分解）设为阶方阵，如果的顺序主子式，则存在惟一的单位下三角阵和上三角阵，使。证明 以上的分析已证明了可作分解。下面证明分解的惟一性。如果非奇异，设有两个分解式其中都是单位下三角阵，都是上三角阵。因非奇异，所以都可逆。于是左边为单位下三角阵，右边为上三角阵
9、，所以即有，惟一性得证。若为奇异阵，因其阶顺序主子式不等于零，故可记其中为阶非奇异阵，为阶单位下三角阵，由，得由已证明的结果知的分解是惟一。所以亦是惟一确定的。进而，也是惟一确定的。定理2的逆命题是：定理3 设阶方阵非奇异，若有惟一的分解（为单位下三角阵，为上三角阵），试证的顺序主子式。（证明留给读者）2 主元素法前面已指出Gauss消去法必须在各个约化主元素下才能进行。现在还需指出的是：即使，但当很小时，也不能做主元素的，因为作第次消元时，需将第个方程乘以，因此当很小时，乘数很大，用去乘第行的元素，将导致的数量级迅速增长，这样在消元计算 时，会出现大数吃掉小数的现象，因而导致最后计算结果的精
10、度很差甚至失真。例1 解方程组(1) 求精确解；(2) 在的浮点机上用Gauss消去法求解。解 (1) 容易求得方程组的精确解为。(2) 在所给浮点机上原方程组为由于消去第二式的，得对阶，出现大数“吃掉”小数，结果有解得，回代第一式得。与精确解相比较，已无精确度可言。产生不准确的原因是主元素太小，致使很大。改变上述状况的办法是将方程组的一、二两式对换，得然后再使用Gauss消去法，此时于是得近似解。此例表明，高斯消去法解方程组时，小主元可能带来严重的后果，因此应尽量避免小主元的出现；另一方面，通过对换方程组中方程的次序或改动变量次序，选择绝对值大的元素做主元，可减少舍入误差，提高计算精度。2.
11、1 列主元与全主元消去法1列主元素消去法。在第步消元时，在的第列元素中选取绝对值最大者作为主元，并将其对换到位置上，然后再进行消元计算。用方程组(1.2)的增广矩阵 (2.1)表示它，并直接在增广矩阵上进行计算。具体步骤如下：第一步：首先在上述矩阵的第一列中选取绝对值最大的，比如，则。将(2.1)中第一行与第行互换。为方便起见，记行互换后的增广矩阵为，然后进行第一次消元，得矩阵假设已完成步的主元素消去法，约化为第步：在矩阵的第列中选主元，如，使。将的第行与第行互换，进行第次消元。经过步，增广矩阵(1.7)被化成上三角形算法1（Gauss列主元素消去法）说明：消元结果冲掉，行乘数冲掉，det存放
12、行列式值。输入，置，1. 消元过程对(1) 选主元：(a) 按列选主元，即确定，使(b) 若，停机；(c) 若（进行行交换）(2) 对（）对(3) 5. 回代过程(a) 若，输出失败信息，停机(b) (c) 对注：计算程序中对的判断可以用或（是预选的很小正数）。2完全主元素法。在第步消元时，在的右下方阶矩阵的所有元素中，选取绝对值最大者作为主元，并将其对换到位置上，再做消元计算。全主元消去法和列主元消去法相比，每步消元过程所选主元的范围更大，故它对控制舍入误差更有效，求解结果更加可靠。但全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂，计算时间较长。列主元法的精度虽稍低于全主元法，
13、但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好方法之一。2.2 列主元消去法的矩阵形式第步消元时，需先交换的第行与第行，然后再做消元计算，相当于对进行如下的矩阵计算：(1) 用初等排列矩阵左乘，即其中由交换单位矩阵的第与两行所得。显然。(2) 用初等矩阵左乘，即于是对施行带行交换的步消元过程，可用矩阵表示为从而有因为，所以上式可改写为其中可以证明，若是指标为的单位下三角阵，则仍是一个指标为的单位下三角阵。若令则是排列阵。于是即注意到仍为单位下三角阵，若令则有上式表明，带行交换的Gauss消去过程所产生的
14、矩阵分解，相当于对系数矩阵先施行每步消元时所做行交换后，再将所得矩阵进行分解。以上讨论可叙述为定理4（列主元三角分解定理）如果为非奇异矩阵，则存在排列矩阵，使其中为单位下三角矩阵，为上三角矩阵。3 矩阵三角分解法3.1 直接三角分解法1. 不选主元的直接三角分解法设为如下形式 (3.1)由矩阵的乘法规则，得由此可得计算和的公式 (3.2)具体步骤如下：1）计算的第1行，的第1列2 ）计算的第行，的第列例2 求矩阵的三角分解。解 按式(3.2)所以紧凑格式：例2中矩阵的三角分解按紧凑格式计算，结果见下表如果线性方程组的系数矩阵已进行三角分解，则解方程组等价于求解两个三角形方程组。第一步：先求解下三角方程组得解第二步：再求解上三角方程组得解2选主元的直角三角分解法不选主元的直接三角分解过程能进行到底的条件是，实际上，即使非奇异，也可能出现某个的情况，这时分解过程将无法进行下去。另外，如果但很小，会使计算过程中的舍入误差急剧增大，导致解的精度很差。但如果非奇异，我们可通过交换的行实现矩阵的分解，实际上是采用与列主元消去法等价的选主元的三角分解法，即只要在直接三角分解法的每一步引
