实际问题中解线性方程组的经典解法

1、第二章 在实际问题中解线性方程组的经典解法 直接法与三角形方程组的求解分析 线性方程组求解问题在许多科学计算问题中都会遇到，如应力分析、电学网络、自由振动问题等。在计算机数值方法的课程中，2线性方程组求解在样条插值、数据拟合的最小二乘法以及常微分方程边值问题中都要用到.产生的线性方程组的类型有很多，如按系数矩阵含零元素多少分类，有稠密和稀疏（零元素占80%以上）线性方程组之别；如按阶数的高低分类，有高阶（阶数在1000阶以上）和低阶之别；如按系数矩阵的形状和性质分类，又有对称正定、三对角线对角占优等之别，因为在电子计算机上求解，必须要考虑算法的计算复杂性以及算法的数值稳定性问题。所以针对不同类

2、型的线性方程组有不同的解法，但是，基本的方法可归结为两大类，即为直接法和迭代法。本章介绍的经典解法，都把原方程组化为一个或者两个三角形方程组来求解，主要包括Gauss4消去法和它的变形-直接三角分解法 设有线性方程组 （1，1）其中 根据线性代数知识，当时，方程组（1.1）的解存在且唯一，对增广矩阵施行行初等变换，化为上三角形矩阵，同时化为，这时与增广矩阵相应的线性方程组为上三角形方程组 （1.2）其中 设 则（1.2）的解为 （1.3）它便是原方程组（1.1）的解，实现上述求解过程的方法称为Gauss消去法 如果方程组（1.1）的系数矩阵可分解为两个形式简单的三角形矩阵和的乘积，即 (1.4

3、) 若为下三角形矩阵，则为上三角形矩阵，反之亦然 从而求解的问题转化为解三角形方程组 (1.5)和 （1.6）其中 则为下三角形方程组，它的第个方程为 （1.7） 假定按的顺序解得 （1,8）上三角形方程组的第个方程为 （1.9）假定按的顺序求解得 （1, 10） 直接法的求解过程，在计算过程中无舍入误差的前提下，都可以经有限步算数运算而得到精确解。由于计算机的字长有限，初始数据取浮点数以及运算过程都不断地产生舍入误差，这些误差的传播和积累，会影响计算精度，所以，如何避免舍入误差的增长是设计算法时必须考虑的问题。直接法通常需要存储系数矩阵的全部元素，当方程组的阶数很高时，需要相当大的内存空间，

4、因此，在算法设计上应当注意节省内存，比如，对称矩阵可以只存其下三角形部分于一维数组中。综上所述，如果矩阵非奇异，总可以通过带有行交换或不带行交换的消元过程，将化为非奇异上三角形矩阵因此，回代求解过程（1,3）也可以进行到底，但是，在实际应用中，常常难于事先判断系数矩阵的奇异性，因此，需要进一步考虑当为奇异矩阵时计算过程可能发生的情况。一是消元过程的某一步找不到非零的，于是计算中断；二是虽然消元过程能进行到底，但，使回代求解过程无法进行下去，因此，在计算设计中必须考虑到上述两种可能发生的情形，此时应在算法设计中给出计算中断的信息。1 Gauss列主元素消去法 在Gauss消元过程中位于矩阵的主对

5、角线位置上的元素称为主元素，因为在计算解的分量时，都做除数，但应当避免用小的数做除数，即避免用较在数量级上相对小的主元做除数，以防止舍入误差的扩大，降低解得精度，下面的例子说明“小主元”对解得精度的影响。例1用Gauss消去法解线性方程组 用8位十进制尾数的浮点数计算解 类似的算出我们看到，由于小主元做除数，使得行乘数的数量级变得很大，这样在计算时，即与在计算机上做代数和时，由于阶码升为使尾数右移变成了机器零，这里揭示了数量级相对于分子数做除数，会使Gauss消去法在计算机有限字长的环境下造成较大舍入误差的原因。 经第一步消元得 经第二步消元得这一结果表明原方程组有无穷多个解，在计算机上，将会

6、给出“无唯一解”的信息，停止计算，但实际上，由于，所以原方程组有唯一解，是计算过程的舍入误差使解面目全非了，从前面的分析我们看到，导致这一错误的主要原因是用“小主元”做除数。为避免小主元做除数，在Gauss消去法中加入选主元过程，即在第步消元时，首先在的第列主对角线元以下元素中挑选出绝对值最大者，并通过交换的第与行对应元素，使位于对角线上，仍记为，并称之为第步消元的列主元素，然后再进行消元计算，第一步都按列选主元的消去法称为列主元素消去法，由于列主元素满足条件所以行乘数皆满足，因此，列主元素消去法能避免例1中所出现的问题，误差分析与数值试验表明，用列主元消去法解“良态”线性方程组，在绝大多数情

7、况下，都可以得到令人满意的结果。例2用列主元素消去法解例1的线性方程组解 ,经第一步消元，得，经第二步消元得回代求解得 方程组具有9位有效数字的解可见用Gauss列主元素消去法计算，得到了一个高精度的近似解。2-2 带有行交换的矩阵分解 设第步消元时，先交换的第行与行后再消元，用矩阵运算表示为 其中 当时称为置换矩阵。于是带行交换的消元过程用矩阵运算表示为 由此得 （2.3）比如，则有 可改写为 (2.4)令 容易证明，当时，与的形状相同，也是一个初等下三角形矩阵，只是交换了的第列对角元以下的第行与第行的元素，因此，和仍然是初等下三角形矩阵，从而 为单位下三角形矩阵，于是可以写成 将对的处理方

8、法推广到一般情形，令 （2.5） 称为排列矩阵，于是(2.3)式可以改写为 从而 其中为单位下三角形矩阵，它与(1.4)中的区别仅在于第列的主对角元一下元素的排序可能不同，取决于消元过程所做的行交换，若设行交换的次数为，则还有 （2.7） 式表明，带行交换的消元过程产生了矩阵的分解，相当于先对系数矩阵施行消元过程中所需的行交换后再分解，只要非奇异，带行交换的消元过程就可以进行到底定理2.1 设为非奇异矩阵，则必存在排列矩阵以及单位下三角形矩阵和非奇异上三角形矩阵，使 (2.8)3 直接三角分解法本节以矩阵分解定理和矩阵乘法规则为基础，研究矩阵分解的计算公式以及消去法的变形直接三角分解法 当实现

9、了系数矩阵的三角分解之后，解线性方程组原则上化为解三角形方程组(1.5)和(1.6)其解法在本章1中已经基本解决了。定理2.1表明，在满足一定条件下必有或成立，同时借助于消去法得到了和的表达式,这一节着重研究在或时，的元素与的元素之间的直接关系，并在此基础上给出求解矩阵方程组的方法。3-1 基本的三角分解法设矩阵的各阶顺序主子式均不为零，有分解式 对比等式左边和右边乘积矩阵的第行主对角元右边（含主对角元）的对应元素，得 再对比等式两边第列主对角元以下（不含主对角元）的对应元素，得当时，由式分别解出假设已求出的第至行，的第至列，由和式分别得出计算的第行、的第列元素计算公式：称由式所表示的矩阵分解

10、为分解，也称分解。如果在分解式中，设为单位上三角矩阵，为下三角矩阵，用类似于推导分解的方法，可以得到递推地计算和的公式为称上述分解为分解。注意第步分解是先算的第列，后算的第行，与分解的计算次序恰好相反。可以证明，当矩阵的顺序主子式全不为零，可以分解为一个下三角矩阵和一个单位上三角矩阵的乘积,且分解是唯一的。实现了系数矩阵的分解或分解之后，方程组的求解可以分解为和这两个三角形方程组求解。设为单位下三角形矩阵，为上三角形矩阵，并且，根据公式和得与分解相应的求解方程组的公式为及类似地。可以得出分解相应的求解出公式及综上所述，直接三角分解法的基本方法有分解和分解法，他们都包括分解系数矩阵和求解两个三角形方程组的过程。例1用法解方程组解 由公式和计算得对于，用公式和计算得解，由公式计算得解用电子计算机算时，可以用二维数组按行存放增广矩阵，数组元素记为分解计算所得及的元素冲掉数组的相应位置的元素。如用法，则，值得注意的是在计算和解的公式中，从参与计算的量在数组。中所处的相对位置看，它们遵循着相同的规则，如果用冲掉，那么，可以视为。在数组中，计算和的公式可以按如下格式计算，即-第行左方数组元素与第列上方数组元素对应元乘积之和； 利用上述格式计算，按第步先算行数组元素、后算列数组元素的次序，在完成第步计算时，在数组上三角部分得到矩阵的上三角形部分，在数组