第三章解线性方程组的直接法许多科学技术问题要归结为解含有多个未知量x1,x2,…,xn的线性方程组（3.1）这里aij(i,j=1,2,…,n)为方程组的系数，bi（i=1,2,…,n）为方程组自由项。方程组（3.1）的矩阵形式为：AX=b其中线性方程组的数值解法可以分为直接法和迭代法两类。所谓直接法，就是不考虑舍入误差，通过有限步骤四则运算即能求得线性方程组（3.1）准确解的方法。如克莱姆法则，但通过第一章的分析，我们知道用克莱姆法则来求解线性代数方程组并不实用，因而寻求线性方程组的快速而有效的解法是十分重要的。本章讨论计算机上常用而有效的直接解法――高斯消去法和矩阵的三角分解等问题。为方便计，设所讨论的线性方程组的系数行列式不等于零。§1高斯消去法高斯（Gauss）消去法是解线性方程组最常用的方法之一，它的基本思想是通过逐步消元，把方程组化为系数矩阵为三角形矩阵的同解方程组，然后用回代法解此三角形方程组得原方程组的解。下面先讨论三角形方程组的解法。1．三角形方程组的解法三角形方程组是指下面两种形式的方程组（3.2）和（3.3）方程组（3.2）叫做下三角形方程组，方程组（3.3）叫做上三角形方程组，三角形方程组的求解是很简单的。如果aii¹0，i=1,2,…,n，则（3.2）的解为k=2,3,…,n（3.4）此过程称为前推过程。同样地，若aii¹0,i=1,2,…,n，则（3.3）的解为（3.5）此过程称为回代过程。从上面的公式来看，求出xk，需要作k–1次乘法和加减法及一次除法，总共完成次乘法、加法及n次除法。从（3.4）、（3.5）可以看出，求解三角形方程组是很简单的，只要把方程组化成了等价的三角形方程组，求解过程就很容易完成。2．高斯消去法为便于叙述，先以一个三阶线性方程组为例来说明高斯消去法的基本思想。把方程（I）乘（）后加到方程（II）上去，把方程（I）乘（）后加到方程（III）上去，即可消去方程（II）、（III）中的x1，得同解方程组将方程（II）乘（）后加于方程（III），得同解方程组：由回代公式（3.5）得x3=2x2=8x1=-13下面考察一般形式的线性方程组的解法，为叙述问题方便，将bi写成ai,n+1，i=1,2,…,n。（3.6）如果a11¹0，将第一个方程中x1的系数化为1，得其中j=1,…,n+1（记i=1,2,…,n;j=1,2,…,n+1）从其它n–1个方程中消x1，使它变成如下形式（3.7）其中由方程（3.6）到（3.7）的过程中，元素起着重要的作用，特别地，把称为主元素。如果（3.7）中，则以为主元素，又可以把方程组（3.7）化为：（3.8）针对（3.8）继续消元，重复同样的手段，第k步所要加工的方程组是：设，第k步先使上述方程组中第k个方程中xk的系数化为1：然后再从其它（n-k）个方程中消xk，消元公式为：(3.9)按照上述步骤进行n次后，将原方程组加工成下列形式：回代公式为：（3.10）综上所述，高斯消去法分为消元过程与回代过程，消元过程将所给方程组加工成上三角形方程组，再经回代过程求解。由于计算时不涉及xi,i=1,2,…,n，所以在存贮时可将方程组AX=b，写成增广矩阵（A,b）存贮。下面，我们统计一下高斯消去法的工作量；在（3.9）第一个式子中，每执行一次需要次除法，在（3.9）第二个式子中，每执行一次需要次除法。因此在消元过程中，共需要次乘作法。此外，回代过程共有次乘法。汇总在一起，高斯消去法的计算量为：次乘除法。3．主元素消去法前述的消去过程中，未知量是按其出现于方程组中的自然顺序消去的，所以又叫顺序消去法。实际上已经发现顺序消去法有很大的缺点。设用作除数的为主元素，首先，消元过程中可能出现为零的情况，此时消元过程亦无法进行下去；其次如果主元素很小，由于舍入误差和有效位数消失等因素，其本身常常有较大的相对误差，用其作除数，会导致其它元素数量级的严重增长和舍入误差的扩散，使得所求的解误差过大，以致失真。我们来看一个例子：例它的精确解为：用顺序消去法，第一步以0.0001为主元，从第二个方程中消x1后可得：回代可得x1=0.00显然，这不是解。造成这个现象的原因是：第一步主元素太小，使得消元后所得的三角形方程组很不准确所致。如果我们选第二个方程中x1的系数1.00为主元素来消去第一个方程中的x1，则得出如下方程式：1.00...
VIP
