第二章 解线性代数方程组的直接法

1、第二章 解线性方程组的直接法本章研究的对象是阶线性方程组 （2.1）其矩阵形式为 （2.1）其中，是方程组的系数矩阵，,分别为方程组的未知向量和常数向量。所谓直接法，就是在不计舍入误差时，经过有限步运算能求得方程组精确解的方法。下面介绍几种较实用的直接法。2.1 Gauss消去法2.1.1 Gauss顺序消去法高斯（Gauss）消去法实质是消元法,只是步骤规范,便于编程。它的基本做法是把方程组(2.1)转化成一个等价的三角方程组 (2.2)这个过程称为消元。然后,逐个求出,这个过程称为回代。(一) 高斯消去法的计算过程为了符号统一,把方程组(2.1)改写成下面形式 (2.3)用矩阵表示为 (2

2、.3)其中, 若,用第二个方程减去第一个方程的倍,第三个方程减去第一个方程的倍,等等。即得与(2.3)等价的方程组 (2.4)用矩阵表示为 (2.4)其中, 令,则 (2.5)类似地,若,(2.4)中第个方程减去第二个方程的倍,得(2.4)的等价方程组 (2.6)用矩阵表示为 (2.6)其中, 令,则 (2.7)若,上述步骤可继续进行下去,经过步,即得等价的三角方程组 (2.8)用矩阵表示为 (2.8)其中, 把系数矩阵化为上三角矩阵的过程称为消元过程。消元过程元素的计算公式为 (2.9)有了等价的三角方程组(2.8),就很容易求解了。从(2.8)最后一个式子,得把它代入倒数第二个式子,可求出

3、,把代入倒数第三个式子可求出,依次求得全部变量,这一过程叫回代过程,其计算公式为 (2.10)(二) 高斯消去法的运算量因为相对于乘除法而言，加减法所需的时间很少，故只计乘除法的运算量。消去第一列的个系数,需做乘法次, 消去第二列的个系数,需做乘法次,。共需次乘法,要做的除法运算次数为，消元过程所需的乘除次数为回代过程所需的乘除次数为,所以高斯消去法的运算量为 2.1.2 Gauss主元消元法高斯消去法消元过程中，第步求个倍数用到的除数,称为主元，若它为，或接近于，计算机将因“作除数”或“溢出”而中止计算，或产生较大的误差。例2.1 方程组的精确解为若在尾数为三位十进数字的计算机上用高斯消元求

4、解。消去第二个方程的,得回代得，与精确解相差甚远。这是因为用0.0001作除数,使舍入误差剧增造成的。为了避免这种情况,先将方程组的两个方程交换一下,变为消去第二个方程的,得回代得。结果和精确解非常接近,因为这样避免了小主元。一般地,为避免出现小主元，可在消去过程的第步，在第列中选主元(绝对值最大的数)，交换两行,这种选主元的高斯消去法称为列主元高斯消去法。若在消去过程的第步,在行,列中选主元,则称为全主元高斯消去法。全主元法选主元要花大量的时间,并且需要交换变量的次序。而列主元高斯消去法,计算简单,且基本能控制误差的影响。故一般采用列主元法。算法2.1 列主元高斯消去法1输入系数矩阵，常数列

5、向量，阶数2对 做 (1) 按列选主元 保存主元所在的行标 (2) 若，则系数矩阵奇异，计算停止；否则顺序进行。 (3) 若,交换两行 (4) 计算, (5) 消元: 3回代解存于常数项中例2.2 用列主元高斯消去法求解方程组解 用增广矩阵表示计算过程 这就是上三角方程组的增广矩阵。回代得所以2.2 三角分解法2.2.1 Doolittle 分解法 求解线性方程组的三角分解法,源于高斯消去法的矩阵形式。从矩阵的角度看,把(2.3)化为(2.4),相当于系数矩阵和常数列向量左乘初等矩阵 即把(2.4)化为(2.5),相当于系数矩阵和常数列向量左乘初等矩阵 即.经过步,得 (2.11)其中为单位下

6、三角矩阵(对角元为1的下三角矩阵),其逆也是单位下三角矩阵。其逆的乘积也是单位下三角阵。由(2.11)令 则 (2.12)其中是单位下三角矩阵,是上三角矩阵。将系数矩阵分解为单位下三角矩阵和上三角矩阵的乘积叫做分解。当的所有顺序主子式都不为0时,矩阵可惟一分解为。其中是单位下三角矩阵,是上三角矩阵。设, 当系数矩阵实现了分解,方程组求解就很容易了。因为这时方程组可写为令 ,则 解得 (2.13)再解得 (2.14)下面讨论系数矩阵的分解:,比较两边的元,得, 注意是单位下三角矩阵，,得从而 , 同理,比较两边()元,因是上三角矩阵，,所以从而, 于是得计算各元素的公式为 (2.15)特别地，

7、(2.16)分解所需乘除次数为，解所需乘除次数为，解所需乘除次数为。用分解解方程组的计算量为 与用高斯消去法相同。虽然分解法与高斯消去法计算量相同，但分解法中主要计算量为分解的计算量。若用分解法求解一组系数矩阵相同的方程组,只需要进行一次分解即可,这样可大大节省运算量。直接进行分解时,当的绝对值很小时,计算会引起舍入误差的积累,产生较大的误差。为避免这种情况,可采用列主元分解。若步的分解已完成,在进行第步分解时,可以引进 令交换的两行,再进行第步分解。这种分解称为列主元分解。算法2.2 列主元分解1. 输入矩阵和阶2. 对做(1) 计算 (2) 选主元,并记录(3) 交换的两行,(4) 计算的

8、第行元素和的第列元素 , 分解后，和存放在中例2.3 用分解求解方程组解 先把系数矩阵进行分解, 解得,再解得2.2.2 平方根法当是正定矩阵时,存在一个非奇异下三角矩阵,使,当限定对角元为正时,这种分解是惟一的。用直接分解的办法来计算的元素,不难得出计算公式(按列计算)对,做 (2.17)计算亦可按行进行。对,做 (2.18)分解后,再由求,由求,这种方法称为平方根法,也叫Cholesky分解法。例2.4 利用平方根法求解方程组解 由（2.17）得 ,解得再由 得分解矩阵的计算量为,较高斯消去法,分解计算量减少一半,但需要次开方。为避免开方运算,把分解为,其中是单位下三角矩阵,是对角矩阵。可

9、得一种不用开方的分解法。因,令,则为Doolittle 分解,而,即是U各行分别除以对角元所的矩阵的转置。这样的计算量可节省下来。这种分解方法称为改进平方根法。算法2.3 改进平方根法1输入增广矩阵和阶2对做+13对 注：即的列存的是，的第列存的是。这种方法所需乘除次数为,比平方根法多次乘除法,少次开方;而比一般矩阵的高斯消去法、Doolittle分解法,几乎少了一半乘除法。2.2.3 追赶法将高斯消去法或三角分解法用于三对角方程组,可得对三对角方程组最适用的追赶法。三对角方程组的增广矩阵为=比较两边相应的元素,得(2.19) 回代得 (2.20)按照这些公式求解三对角方程组的方法称为追赶法,

10、其中分解的过程叫追,回代的过程叫赶.追赶法所需乘除次数为,比高斯消去法和三角分解法少的多。实际遇到的方程组，系数矩阵往往对角占优，不选主元就可顺利稳定地进行。例2.5 用追赶法求解方程组解 设 由（2.19）得，1/2，于是由（2.20）得2.3 误差分析前面介绍了求解线性方程组的各种方法，但从数值计算的角度看，只介绍算法是不够的，还要进行误差分析。而向量范数、矩阵范数及矩阵的条件数在误差分析中是十分重要的，所以先介绍向量范数、矩阵范数及矩阵的条件数。2.3.1 向量范数向量范数是维实空间中长度概念的推广。定义2.1 任一向量，对应一非负实数，具有性质：(1) 正定性：对所有有，而且当且仅当。

11、(2) 齐次性：对所有和有。(3) 三角不等式：对所有，有则称为向量的范数。在中，几种常用的范数有 （2.21）分别称为1范数，2范数和范数。其中是的个分量。例2.6 求的1范数,2范数和范数。解 向量范数有一些基本性质:(1) 连续性 向量的范数是其分量的元连续函数;(2) 等价性 设和为上任意两种范数,则存在常数,使得(3) 按范数收敛性 向量序列收敛于向量等价于2.3.2 矩阵范数类似于向量范数的定义，可定义矩阵的范数。定义2.2 任一矩阵，对应一非负实数，具有性质：(1) 正定性：对所有有，而且当且仅当。(2) 齐次性：对所有和有。(3) 三角不等式：对所有，有(4) 相容性：对所有，

12、则称则称为矩阵的范数。常用的矩阵范数是按下式确定的。 （2.22）容易证明这是一种范数，称为算子范数。算子范数不仅满足矩阵范数的四个条件，还满足：(5) 相容性：证明 若不可逆,则方程组有非零解，,矛盾。所以可逆。 由三种常用的向量范数诱导出的矩阵范数为1范数 (列范数) 2范数 （2.23）范数 (行范数) 其中表示矩阵的绝对值最大的特征值，称为矩阵的谱半径。这三种范数中，1范数和范数计算简单，2范数比较复杂，但2范数有一些很好的性质，在理论证明时常用到它。此外，一个常用且易于计算的矩阵范数为范数。例2.7 设,求解 ,特征方程为特征值为，于是2.3.3 线性方程组固有性态与条件数一个线性方

13、程组是由它的系数矩阵和常数向量确定的。在实际问题中，和中的数据是带有误差的，即受到了微小的扰动。现在研究和受到微小后对解有何影响。例2.8 线性方程组的精确解为。若方程组右端常数项有一微小变化，变为，方程组变为其解为常数项的第二个分量的微小变化，引起了方程组解的巨大变化，这样的方程组称为病态方程组，矩阵称为病态矩阵。应该注意，矩阵的“病态”性质是矩阵本身固有的性态，下面我们希望找出刻画矩阵“病态”性质的量。设有非奇异方程组，其精确解为，受到扰动，从而相应的解有扰动，即由得，两边取范数此外由得以上两式相乘得若，则，从而 （2.24）此式表明，右端项有扰动时，解的相对误差不超过右端项相对误差的倍。

14、现假定是精确的，有微小扰动，从而相应的解有扰动，即可逆，当时，也可逆。此时，两边取范数，并利用，得 （2.25）此式表明，系数矩阵有扰动时，解的相对误差(近似)不超过系数矩阵相对误差的倍。若不大，则对解的影响不会很大，而很大，则扰动对解的影响可能会很大。我们把称为方程组的条件数。定义2.3 数称为矩阵(或方程组)的条件数.由以上讨论可知，条件数很大()的方程组为病态方程组，条件数很小的方程组为良态方程组。例如,例2.8中, =所以该方程组为病态方程组。例2.9 求方程组的条件数，考察方程组的性态解 , 所以，该方程组是病态方程组。 实际应用中，若方程组的条件数不易计算,下列条件可能表示方程组病

15、态。（1）系数矩阵的元素数量级相差悬殊。（2）将系数稍加变化，得出的解变化很大。（3）算出的解与期望的解相差较远（4）系数矩阵的行或列近似线性相关（5）采用选主元技术时，主元数量级相差悬殊对于病态方程组，即使算法是稳定的，所得的解也可能很差。对于病态不太严重的方程组，可采用双精度字长进行计算，或采用其他处理方法（如平衡措施,迭代改善等）。所谓平衡措施，就是将系数矩阵的各行除以该行绝对值最大的元素,例如, 采用平衡措施后,方程组变成良态的了。所谓迭代改善，即先求近似解,为求更好的近似解,求修改量，使满足所得解仍是近似解，再求修改量，再修改。这样反复解,得新解，使逐渐接近真正解的方法称为迭代改善。

16、 前面介绍的误差估计，实际上是一种“事前误差估计”，它通过计算条件数来估计误差。当条件数难以计算时,也可先上机求解,然后再作误差分析。这就是所谓的“事后误差估计”。例2.10 方程组的精确解为,现在有扰动,再解方程组,得有扰动的解,实际相对误差为，估计相对误差也是13.6。本例中估计误差和实际误差一致,一般地,实际误差应小于估计误差。本章介绍了求解线性方程组的两种直接解法：高斯消去法和三角分解法，其运算量远比克雷姆法则小。为保证计算过程顺利、稳定，一般需选主元，常用列主元。但系数矩阵对称正定或队交占优时不用选主元。高斯消去法分消元过程和回代过程。三角分解法先分解，再求解。适用于求解系数矩阵相同的若干方程组。（1）当是单位下三角阵时，即为杜里特尔分解法;（2）当时，即为平方根法，适用于对称正定阵方程组;（3），时为改进平方根法，也适用于对称正定阵方程组;（4）当是单位上三角阵时，应用于三对角方程组得追赶法。适用于三对角方程组。求解过程总有舍入误差，误差对解的影响大小取决于系数矩阵的条件数，条件数很大的方程组称为病态方程组，对病态方程组，应采取适当措施，才能得到比较精确的解。习题二2-1用高斯消去法解线性方程组（1）,