《数值计算_第3章 解线性方程组的直接法.doc》由会员分享，可在线阅读，更多相关《数值计算_第3章 解线性方程组的直接法.doc（55页珍藏版）》请在金锄头文库上搜索。
1、第3章解线性方程组的直接法在近代数学数值计算和工程应用中，求解线性方程组是重要的课题。例如，样条插值中形成的关系式，曲线拟合形成的法方程等，都落实到解一个元线性方程组，尤其是大型方程组的求解，即求线性方程组（3.1）的未知量的数值。（3.1）其中ai j，bi为常数。上式可写成矩阵形式Ax = b，即 （3.2）其中，为系数矩阵，为解向量，为常数向量。当detA=D0时，由线性代数中的克莱姆法则，方程组的解存在且惟一，且有 为系数矩阵的第列元素以代替的矩阵的行列式的值。克莱姆法则在建立线性方程组解的理论基础中功不可没，但是在实际计算中，我们难以承受它的计算量。例如，解一个100阶的线性方程组，
2、乘除法次数约为（101100！99），即使以每秒的运算速度，也需要近年的时间。在石油勘探、天气预报等问题中常常出现成百上千阶的方程组，也就产生了各种形式方程组数值解法的需求。研究大型方程组的解是目前计算数学中的一个重要方向和课题。解方程组的方法可归纳为直接解法和迭代解法。从理论上来说，直接法经过有限次四则运算，假定每一步运算过程中没有舍入误差，那么，最后得到方程组的解就是精确解。但是，这只是理想化的假定，在计算过程中，完全杜绝舍入误差是不可能的，只能控制和约束由有限位算术运算带来的舍入误差的增长和危害，这样直接法得到的解也不一定是绝对精确的。迭代法是将方程组的解看作某种极限过程的向量极限的值，
3、像第2章中非线性方程求解一样，计算极限过程是用迭代过程完成的，只不过将迭代式中单变量换成向量而已。在用迭代算法时，我们不可能将极限过程算到底，只能将迭代进行有限多次，得到满足一定精度要求的方程组的近似解。在数值计算历史上，直接解法和迭代解法交替生辉。一种解法的兴旺与计算机的硬件环境和问题规模是密切相关的。一般说来，对同等规模的线性方程组，直接法对计算机的要求高于迭代法。对于中等规模的线性方程组，由于直接法的准确性和可靠性高，一般都用直接法求解。对于高阶方程组和稀疏方程组（非零元素较少），一般用迭代法求解。3.1 消元法3.1.1 三角形方程组的解形如下面三种形式的线性方程组较容易求解。对角形方
4、程组 （3.3）设，对每一个方程，。显然，求解n阶对角方程的运算量为 。下三角方程组 （3.4）按照方程组的顺序，从第一个方程至第个方程，逐个解出。由方程，得。将的值代入到第二个方程得将的值代入到第个方程得计算需要次乘法或除法运算，。因此，求解过程中的运算量为上三角方程组 （3.5）与计算下三角方程组的次序相反，从第个方程至第一个方程，逐个解出。由第个方程。将的值代入到第个方程得将的值代入到第个方程得解的通式 计算需要次乘法或除法运算。因此求解过程中的运算量为消元法的基本思想就是通过对方程组做初等变换，把一般形式的方程组化为等价的具有上述形式的易解方程组。3.1.2 高斯消元法与列主元消元法高
5、斯消元法高斯消元法是我们熟悉的古老、简单而有效的解方程组的方法。下面是中学阶段解二元方程组（高斯消元法）的步骤：（3.6）（3.7）方程（3.6）乘以3加到第（3.7）个方程中得代入（3.6）得。其方法相当于对方程组的增广矩阵做行的初等变换：已是上三角矩阵，而为原方程组的等价方程组，已化成易解的方程组形式。再用回代方法求解，得到：这就是高斯消元法解方程组的消元和回代过程。一般地，可对线性方程组（3.1）施行以下一系列变换；（1）对换某两个方程的次序；（2）对其中某个方程的两边同乘一个不为零的数；（3）把某一个方程两边同乘一个常数后加到另一个方程的两边。记变换后的方程组为： （3.8）显然方程组
6、（3.1）与（3.8）是等价方程组，或者说它们有相同的解。分别记方程组（3.1）与（3.8）的增广矩阵为：可以看出，实际上是由按一系列初等换后得到的（1）对换某两行元素；（2）中的某行乘一个不为零的数；（3）把的某一行乘一个常数后加到另一行。高斯消元法就是通过以上（3）的变换，把化为等价的上三角形式。下面我们以为例演示消元过程。设方程组： （3.9）其增广矩阵为：（1）若，则将第一行乘以加到第二行上；将第一乘以加到第三行上；将第一行乘以 加到第四行上得到 （3.10）即其中：（2）若则将第二行乘以加到第三行上；将第二行乘以加到第四行上，得到（3.11）其中：（3）若则将第三行乘以加到第四行上，
7、得到 （3.12）其中：已是上三角矩阵，于是得到了与原方程等价的易解形式的方程组：（3.13）再对方程组（3.13）依次回代解出。从式（3.12）可以得到系数矩阵的行列式的值为的对角元素的乘积。即这也正是在计算机上计算方阵的行列式的常规方法。要将上述解方程步骤推广到阶方程组，只需将对控制量“4”的操作改成对控制量的操作即可。元方程组高斯消元法的步骤如下：对于约定有（3.14）经过以上消元，我们已得到与等价的方程组，其中已是一个上三角矩阵。为简单起见，仍记的元素为 （3.15）即已得到原方程组的解。高斯消元法算法在算法中略去了变量，矩阵和向量的定义部分。在消元过程中，将仍放在元素的位置上。1输入
8、：方程组阶数n，方程组系数矩阵A和常数向量b。2FOR k:=1 TO n-1 /消元过程 FOR i:=k+1 TO n / 假定 FOR j:=k+1 TO n / ENDFORJ / ENDFORI / ENDFORK3FOR i:=n TO1/回代求解 s:=bi FOR j:=i+1 TO n DO 4输出方程组的解。高斯消元法的运算量整个消元过程即式（3.14）的乘法和除法的运算量为回代过程即式（3.15）的乘除运算量为故高斯消元法的运算量为 （3.16）高斯消元法的可行性在上面的消元法中，未知量是按照在方程组中的自然顺序消去的，也叫顺序消元法。在消元过程中假定对然元素，消元步骤才
9、能顺利进行，由于顺序消元不改变的主子式值，故高斯消元法可行的充分必要条件为的各阶主子式不为零。但是，实际上只要方程组就有解。故高斯消元法本身具有局限性。另一方面，即使高斯消元法可行，如果很小，在运算中用它作为除法的分母，会导致其它元素数量级的严重增长和舍入误差的扩散。这是高斯消元法的另一缺陷。例3.1 方程组（3.17）（3.18）的精确解为：。在高斯消元法计算中取5位有效数字。解：方程（3.17）（1）/0.0003+方程（3.18）得：，代入方程（3.17）得。由此得到的解完全失真，如果交换两个方程的顺序，得到等价方程组经高斯消元后有由此可看到，在有些情况下，调换方程组的次序对方程组的解是
10、有影响的，对消元法中抑制舍入误差的增长是有效的。如果不调换方程组的次序，取6位有效数字计算方程组的解，得到取9位有效数字计算方程组的解，得到由此可见有效数字在数值计算中的作用。列主元消元法如果在一列中选取按模最大的元素，将其调到主干方程位置再做消元，则称为列主元消元法。调换方程组的次序是为了使运算中做分母量的绝对值尽量地大，减少舍入误差的影响。用列主元方法可以克服高斯消元法的额外限制，只要方程组有解，列主元消元法就能畅通无阻地顺利求解，同时又提高了解的精确度。更具体地，第一步在第一列元素中选出绝对值最大的元素，交换第一行和第行的所有元素，再做化简为零的操作。对于每个在做消元前，选出中绝对值最大
11、的元素，对行和行交换后，再做消元操作，这就是列主元消元法的操作步骤。由于，可证中至少有一个元素不为零，从理论上保证了列主元消元法的可行性。列主元消元法与高斯消元法相比，只增加了选列主元和交换两个方程组（即两行元素）的过程。列主元消元法算法1输入：方程组阶数，方程组系数矩阵和常数向量项。2 /选主元的消元过程 /选择 / 交换第行和第行 / ENDFORI / ENDFORK3FOR i:=n TO 1 / 回代求解4输出方程组的解 。如果对于第步，从行至行和从列至列中选取按模最大的，对第行和第行交换，对第列和第v列交换，这就是全主元消元法。在k列和第v列交换时，还要记录下v的序号，以便恢复未知
12、量xk和xv的位置。3.1.3 高斯若尔当（GaussJordan）消元法高斯消元法将系数矩阵化为上三角矩阵，再进行回代求解；高斯若尔当消元法是将系数矩阵化为对角矩阵，再进行求解，即对高斯消元法或列主元消元法得到的等价增广矩阵：用第4行乘加到第3行上，用第4行乘加到第2行上，用第4行乘加到第1行上，得到用第3行乘加到第2行上，用第3行乘加到第1行上，再用第2行乘加到第1行上，得到（3.19）为方便起见，仍记式（3.19）系数矩阵元素为 ，常数项元素为。那么用初等变换化系数矩阵为对角矩阵的方法称为高斯若尔当消元法。从形式上看对角矩阵（3.15）比上三角矩阵（3.11）更为简单，易于计算 ，但是将上三角矩阵（3.11）化为对角矩阵（3.15 ）的工作量略大于上三角矩阵回代的工作量。高斯若尔当消元法求逆矩阵设为非奇异矩阵，方程组的增广矩阵为。如果对应用高斯-若尔当消
