线性方程组的直接法

《线性方程组的直接法》由会员分享，可在线阅读，更多相关《线性方程组的直接法（31页珍藏版）》请在金锄头文库上搜索。

1、1第二章 线性方程组的直接法在近代数学数值计算和工程应用中，求解线性方程组是重要的课题。例如，样条插值中形成的 关系式，曲线拟合形成的法方程等，都落实到解一个 元线性方程组，尤其是大型方程组的求解，即求线性方程组（2.1）的未知量 的数值。（2.1）其中 ai j，bi 为常数。上式可写成矩阵形式 Ax = b，即（2.2）其中， 为系数矩阵， 为解向量， 为常数向量。当 detA=D 0 时，由线性代数中的克莱姆法则，方程组 的解存在且惟一，且有为系数矩阵 的第 列元素以 代替的矩阵的行列式的值。克莱姆法则在建立线性方程组解的理论基础中功不可没，但是在实际计算中，我们难以承受它的计算量。例如

2、，解一个 100 阶的线性方程组，乘除法次数约为（101100 ！99 ），即使以每秒 的运算速度，也需要近 年的时间。在石油勘探、天气预报等问题中常常出现成百上千阶的方程组，也就产生了各种形式方程组数值解法的需求。研究大型方程组的解是目前计算数学中的一个重要方向和课题。解方程组的方法可归纳为直接解法和迭代解法。从理论上来说，直接法经过有限次四则运算，假定每一步运算过程中没有舍入误差，那么，最后得到方程组的解就是精确解。但是，这只是理想化的假定，在计算过程中，完全杜绝舍入误差是不可能的，只能控制和2约束由有限位算术运算带来的舍入误差的增长和危害，这样直接法得到的解也不一定是绝对精确的。迭代法是

3、将方程组的解看作某种极限过程的向量极限的值，像第 2 章中非线性方程求解一样，计算极限过程是用迭代过程完成的，只不过将迭代式中单变量 换成向量而已。在用迭代算法时，我们不可能将极限过程算到底，只能将迭代进行有限多次，得到满足一定精度要求的方程组的近似解。在数值计算历史上，直接解法和迭代解法交替生辉。一种解法的兴旺与计算机的硬件环境和问题规模是密切相关的。一般说来，对同等规模的线性方程组，直接法对计算机的要求高于迭代法。对于中等规模的线性方程组 ，由于直接法的准确性和可靠性高，一般都用直接法求解。对于高阶方程组和稀疏方程组（非零元素较少），一般用迭代法求解。1 消元法一、 三角形方程组的解形如下

4、面三种形式的线性方程组较容易求解。对角形方程组（2.3）设 ，对每一个方程， 。显然，求解 n 阶对角方程的运算量为 。下三角方程组（2.4）3按照方程组的顺序，从第一个方程至第 个方程，逐个解出 。由方程 ，得 。将 的值代入到第二个方程得将 的值代入到第 个方程得计算 需要 次乘法或除法运算， 。因此，求解过程中的运算量为上三角方程组（2.5）与计算下三角方程组的次序相反，从第 个方程至第一个方程，逐个解出。由第 个方程 。将 的值代入到第 个方程4得将 的值代入到第 个方程得解的通式计算 需要 次乘法或除法运算 。因此求解过程中的运算量为消元法的基本思想就是通过对方程组做初等变换，把一般

5、形式的方程组化为等价的具有上述形式的易解方程组。二、 高斯消元法与列主元消元法高斯消元法高斯消元法是我们熟悉的古老、简单而有效的解方程组的方法。下面是中学阶段解二元方程组（高斯消元法）的步骤：（2.6）（2.7）方程（2.6）乘以3 加到第（2.7）个方程中得5代入（2.6）得 。其方法相当于对方程组的增广矩阵做行的初等变换：已是上三角矩阵，而为原方程组的等价方程组，已化成易解的方程组形式。再用回代方法求解，得到：这就是高斯消元法解方程组的消元和回代过程。一般地，可对线性方程组（2.1）施行以下一系列变换；（1）对换某两个方程的次序；（2）对其中某个方程的两边同乘一个不为零的数；（3）把某一个

6、方程两边同乘一个常数后加到另一个方程的两边。记变换后的方程组为：（2.8）显然方程组（2.1）与（2.8）是等价方程组，或者说它们有相同的解。分别记方程组（2.1）与（2.8）的增广矩阵为：6可以看出， 实际上是由 按一系列初等换后得到的（1）对换 某两行元素；（2） 中的某行乘一个不为零的数；（3）把 的某一行乘一个常数后加到另一行。高斯消元法就是通过以上（3）的变换，把 化为等价的上三角形式。下面我们以 为例演示消元过程。设方程组：（2.9）其增广矩阵为：7（1）若 ，则将第一行乘以 加到第二行上；将第一乘以加到第三行上；将第一行乘以 加到第四行上得到（2.10）即 其中：（2）若 则将第

7、二行乘以 加到第三行上；将第二行乘以加到第四行上，得到（2.11）其中：（3）若 则将第三行乘以 加到第四行上，得到8（2.12）其中：已是上三角矩阵，于是得到了与原方程等价的易解形式的方程组：（2.13）再对方程组（2.13）依次回代解出 。从式（2.12）可以得到系数矩阵 的行列式的值为 的对角元素的乘积。即这也正是在计算机上计算方阵 的行列式的常规方法。要将上述解方程步骤推广到 阶方程组，只需将对控制量“4”的操作改成对控制量 的操作即可。元方程组高斯消元法的步骤如下：对于 约定 有（2.14）9经过以上消元，我们已得到与 等价的方程组 ，其中 已是一个上三角矩阵。为简单起见，仍记 的元

8、素为（2.15）即已得到原方程组的解。高斯消元法算法在算法中略去了变量，矩阵和向量的定义部分。在消元过程中，将 仍放在 元素的位置上。1输入：方程组阶数 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:=biFOR j:=i+1 TO n DO104输出方程组的解 。高斯消元法的运算量整个消元过程即式（2.14）的乘法和除法的运算量为回代过程即式（2.15）的乘除运算量为故高斯消元法的

9、运算量为（2.16）高斯消元法的可行性在上面的消元法中，未知量是按照在方程组中的自然顺序消去的，也叫顺序消元法。在消元过程中假定对然元素 ，消元步骤才能顺利进行，由于顺序消元不改变的主子式值，故高斯消元法可行的充分必要条件为 的各阶主子式不为零。但是，实际上只要 方程组 就有解。故高斯消元法本身具有局限性。另一方面，即使高斯消元法可行，如果 很小，在运算中用它作为除法的分母，会导致其它元素数量级的严重增长和舍入误差的扩散。这是高斯消元法的另一缺陷。11（2.17）例 2.1 方程组 （2.18）的精确解为： 。在高斯消元法计算中取 5 位有效数字。解：方程（2.17）（1）/0.0003+方程

10、（2.18）得：，代入方程（2.17）得 。由此得到的解完全失真，如果交换两个方程的顺序，得到等价方程组经高斯消元后有由此可看到，在有些情况下，调换方程组的次序对方程组的解是有影响的，对消元法中抑制舍入误差的增长是有效的。如果不调换方程组的次序，取 6 位有效数字计算方程组的解，得到取 9 位有效数字计算方程组的解，得到由此可见有效数字在数值计算中的作用。12列主元消元法如果在一列中选取按模最大的元素，将其调到主干方程位置再做消元，则称为列主元消元法。调换方程组的次序是为了使运算中做分母量的绝对值尽量地大，减少舍入误差的影响。用列主元方法可以克服高斯消元法的额外限制，只要方程组有解，列主元消元

11、法就能畅通无阻地顺利求解，同时又提高了解的精确度。更具体地，第一步在第一列元素中选出绝对值最大的元素 ，交换第一行和第 行的所有元素，再做化简 为零的操作。对于每个 在做消元前，选出 中绝对值最大的元素 ，对 行和 行交换后，再做消元操作，这就是列主元消元法的操作步骤。由于 ，可证 中至少有一个元素不为零，从理论上保证了列主元消元法的可行性。列主元消元法与高斯消元法相比，只增加了选列主元和交换两个方程组（即两行元素）的过程。列主元消元法算法1输入：方程组阶数 ，方程组系数矩阵 和常数向量项 。2 /选主元的消元过程/选择/ 交换第 行和第 行 13 / ENDFORI / ENDFORK3FO

12、R i:=n TO 1 / 回代求解4输出方程组的解 。如果对于第 步，从 行至 行和从 列至 列中选取按模最大的，对第 行和第 行交换，对第 列和第 v 列交换，这就是全主元消元法。在 k 列和第 v 列交换时，还要记录下 v 的序号，以便恢复未知量 xk 和 xv 的位置。3.1.3 高斯若尔当（Gauss Jordan）消元法14高斯消元法将系数矩阵化为上三角矩阵，再进行回代求解；高斯若尔当消元法是将系数矩阵化为对角矩阵，再进行求解，即对高斯消元法或列主元消元法得到的等价增广矩阵：用第 4 行乘 加到第 3 行上，用第 4 行乘 加到第 2 行上，用第 4行乘 加到第 1 行上，得到用第

13、 3 行乘 加到第 2 行上，用第 3 行乘 加到第 1 行上，再用第2 行乘 加到第 1 行上，得到（2.19）为方便起见，仍记式（2.19）系数矩阵元素为 ，常数项元素为 。那么用初等变换化系数矩阵为对角矩阵的方法称为高斯若尔当消元法。从形式上看对角矩阵（2.15）比上三角矩阵（2.11）更为简单，易于计算 ，但是将上三角矩阵（2.11）化为对角矩阵（2.15 ）的工作量略大于上三角矩阵回代的工作量。高斯若尔当消元法求逆矩阵15设 为非奇异矩阵，方程组 的增广矩阵为 。如果对 应用高斯-若尔当消元法化为 ，则 。例 2.2 用高斯-若尔当消元法求 的逆矩阵 。解：解得：2 直接三角分解法仍

14、以 为例，在高斯消元法中，从对方程组进行初等变换的角度观察方程组系数矩阵的演变过程。第一次消元步骤将方程组（2.9）化为方程组（2.10），相当于用了三个初等矩阵左乘 和 。记 ，容易验证，16由 得到 其中将方程组（2.10）化为方程组（2.11），相当于用了两个初等矩阵左乘 和 。记 有17同理，将方程组（2.11）化为方程组（2.12），相当于用一个初等矩阵左乘 和 。记 ，有完成了消元过程，有18亦有所有消元步骤表示为： 左乘一系列下三角初等矩阵。容易验证，这些下三角矩阵的乘积 仍为下三角矩阵，并有于是有或这里 仍为下三角矩阵，其对角元素为 1，称为单位下三角矩阵，而 已是上三角矩阵。

15、记 ，则有结果表明若消元过程可行，可以将 分解为单位下三角矩阵 与上三角矩阵 的乘积。由此派生出解方程组的直接分解法。由高斯消元法得到启发，对 消元的过程相当于将 分解为一个上三角矩阵和一个下三角矩阵的过程。如果直接分解 得到 和 ， 。这时方程 化为，令 ，由 解出 ；再由 ，解出 。这就是直接分解法。将方阵 分解为 ，当 是单位下三角矩阵， 是上三角矩阵时，称为多利特尔（Doclittle）分解；当 是下三角矩阵， 是单位上三角矩阵时，称为库朗（Courant）19分解。分解的条件是若方阵 的各阶主子式不为零，则多利特尔分解或库朗分解是可行和惟一的。一、 多利特尔分解多利特尔分解步骤若 的各阶主子式不为零， 可分解为 ，其中 为单位下三角矩阵， 为上三角矩阵，即（2.20）矩阵 和 共有 个未知元素，按照 的行元素 的列元素的顺序，对每个 列出式（2.16）两边对应的元素关系式，一