7线性方程组的直接解法 在求解线性方程组( System of Linear Equations)的算法中,有两类最基本的算法,一类是 直接法,即以消去为基础的解法。如果不考虑误差的影响,从理论上讲,它可以在固定步数 内求得方程组的准确解。另一类是迭代解法,它是一个逐步求得近似解的过程,这种方法便 于编制解题程序,但存在着迭代是否收敛及收敛速度快慢的问题。在迭代过程中,由于极限 过程一般不可能进行到底,因此只能得到满足一定精度要求的近似解。本章我们主要介绍几 种直接法,迭代法将在下一章讨论。 1.1高斯消去法解线性方程组 在直接方法中最主要的是高斯消去法 Gaussian Elimination)。它分为消元与回代两个过 程,消元过程将方程组化为一个等价的三角方程组,而回代过程则是解这个三角方程组。 1911高斯消去及其串行算法 对于方程组Ax=b,其中A为n阶非奇异阵,其各阶主子行列式不为零,x,b为n维向 量。将向量b看成是A的最后一列,此时A就成了一个n×(m+1)的方程组的增广矩阵 ( Augmented Matrⅸx),消去过程实质上是对增广矩阵A进行线性变换,使之三角化。高斯消 去法按k=1,2,…;n的顺序,逐次以第k行作为主行进行消去变换,以消去第k列的主元素以 下的元素ak+1k,ak+2k,…,amk。消去过程分为两步,首先计算: k=akak,j=k+1,…,n 这一步称为归一化( Normalization)。它的作用是将主对角线上的元素变成1,同时第k行 上的所有元素与常数向量中的bk都要除以ak。由于A的各阶主子式非零,可以保证在消去 过程中所有主元素aA皆为非零。然后计算 a= ajj-aik aki,i=k+1,…,n b=b-akbk,i=k+1,…n 这一步称为消元,它的作用是将主对角线ak以下的元素消成0,其它元素与向量B中 的元素也应作相应的变换。 在回代过程中,按下式依次解出xn,xn1,…,x ①直接解出xn,即xn=bn/anm ②进行回代求x= 在归-化的过程中,要用ak作除数,当|ak|很小时,会损失精度,并且可能会导致 商太大而使计算产生溢出。如果系数A虽为非奇异,但不能满足各阶主子式全不为零的条 件,就会出现主元素an为零的情况,导致消去过程无法继续进行。为了避免这种情形,在 每次归一化之前,可增加一个选主元(Pivo的过程,将绝对值较大的元素交换到主对角线的 置上。根据选取主元的范围不同,选主元的方法主要有列主元与全主元两种。 列主元( Column pivot)方法的基本思想是当变换到第k步时,从第k列的ak以下(包括1. 7 线性方程组的直接解法 在求解线性方程组(System of Linear Equations)的算法中，有两类最基本的算法，一类是 直接法，即以消去为基础的解法。如果不考虑误差的影响，从理论上讲，它可以在固定步数 内求得方程组的准确解。另一类是迭代解法，它是一个逐步求得近似解的过程，这种方法便 于编制解题程序，但存在着迭代是否收敛及收敛速度快慢的问题。在迭代过程中，由于极限 过程一般不可能进行到底，因此只能得到满足一定精度要求的近似解。本章我们主要介绍几 种直接法，迭代法将在下一章讨论。 1.1 高斯消去法解线性方程组 在直接方法中最主要的是高斯消去法(Gaussian Elimination)。它分为消元与回代两个过 程，消元过程将方程组化为一个等价的三角方程组，而回代过程则是解这个三角方程组。 19.1.1 高斯消去及其串行算法 对于方程组 Ax=b，其中 A 为 n 阶非奇异阵，其各阶主子行列式不为零，x，b 为 n 维向 量。将向量 b 看成是 A 的最后一列，此时 A 就成了一个 n×(n+1)的方程组的增广矩阵 (Augmented Matrix)，消去过程实质上是对增广矩阵 A 进行线性变换，使之三角化。高斯消 去法按 k=1,2,…,n 的顺序，逐次以第 k 行作为主行进行消去变换，以消去第 k 列的主元素以 下的元素 ak k ak k ank , , , +1 +2  。消去过程分为两步，首先计算： akj=akj/akk , j=k+1, …,n bk=bk/akk 这一步称为归一化(Normalization)。它的作用是将主对角线上的元素变成 1，同时第 k 行 上的所有元素与常数向量中的 bk都要除以 akk 。由于 A 的各阶主子式非零，可以保证在消去 过程中所有主元素 akk皆为非零。然后计算： aij=aij-aik akj , i,j=k+1, …,n bi= bi -aik bk , i =k+1, …,n 这一步称为消元，它的作用是将主对角线 akk以下的元素消成 0，其它元素与向量 B 中 的元素也应作相应的变换。 在回代过程中，按下式依次解出 xn,xn-1, …,x1： ① 直接解出 xn，即 xn=bn/ann； ② 进行回代求 = + = − = − n j i xi bi aij xj i n 1 , 1, , 2,1 在归−化的过程中，要用 akk 作除数，当∣akk∣很小时，会损失精度，并且可能会导致 商太大而使计算产生溢出。如果系数 A 虽为非奇异，但不能满足各阶主子式全不为零的条 件，就会出现主元素 aii 为零的情况，导致消去过程无法继续进行。为了避免这种情形，在 每次归一化之前，可增加一个选主元(Pivot)的过程，将绝对值较大的元素交换到主对角线的 位置上。根据选取主元的范围不同，选主元的方法主要有列主元与全主元两种。 列主元(Column Pivot)方法的基本思想是当变换到第 k 步时，从第 k 列的 akk以下（包括