第三章 线性方程组解法
（对线性代数方程组的近似解法）
问题的提出：
求解线性方程组，且 ,其中
，
，
对方程组的解法主要用法则求解。
（Cramer 法则：若，则线性方程组的解为其中，是以常数项向量代换中的第列向量后得到的阶行列式）
困难：
当方程组的阶数很大时，法则的计算量很大，不便使用。
解决方法：
直接解法：（消去法及其变形、矩阵分解法等）
迭代解法：构造某种极限过程去逐步逼近方程组的解（迭代法、迭代法、逐次超松弛迭代法等）。
注：如果没有特别提出，总是假定系数行列式的值。
§1 消去法、矩阵分解法
逐步消去法：
例1、求解三阶线性代数方程组的解。其中
, ,
解：对线性方程组的求解，主要是讨论其增广矩阵，即：
等价的线性方程组为：
由第三个方程当中解出，代入第二个方程可得，将上述两个值代入第一个方程中解得：。
经过上述解题过程当中的消元和回代过程的解题方法，称之为逐步消元法。其中称为主元素。只要，，逐步消元法就可以做下去。
由上述解题过程可得，对于一般的线性方程组，解题步骤主要有如下几步：
①判断？若则做 ，将化为0；
②判断？若，重复上述步骤，直至将最后一个方程化为：，则可解出；
③将回代于第二个方程解出，再回代到第一个方程中解出。
特点：在顺序的消元过程，存在一些重复的步骤（可利用计算机的长处）。
下面来看阶线性代数方程组的逐步消去法：
设。一般情况下的逐步消去法过程为，对方程组，即：
进行消元，对其增广矩阵，首先消去第一列除之外的所有元素，做
然后对第二列也作同样的处理，即：自第二个方程起，消去的所有元素，做 得：
其第步的结果为：
第步消元过程：以第个方程为基础，后面的第个方程，第个方程，直至第个方程，作如下的计算：
，
其中:
,
,上述过程经过步之后，得
上面的所有过程就是消元过程。下面的过程即为回代过程：
由第个方程，可以解得：
，
将其值代入到第 个方程，可以解得：
逐步回代，到第个方程可求出，即：
直至第一个方程，可以得到：
逐步消去法的工作量的大小：运算数量级大约为
其实质：对增广矩阵作初等行变换
其缺点：任一，就无法做下去
任一绝对值很小时，也不行（误差大）
主元素消去法（逐步消去法的改进）
1.列主元消去法:
基本思想：逐步消去法时，消去第列时，取为:
对应的那个元素。判断，若，则，即交换第个方程与第个方程。再判断？， （其中是用来控制的大小的量），若，消元可继续；否则，消元不能继续。
与逐步消去法相比，增加了一个选主元和换行的步骤，其它过程均没有变化。
2.全主元消去法:
基本思路：在列主元消去法中，找的是各列元素的绝对值的最大值。在全主元消去法中，找的是每一步中的子行列式中的各元素的绝对值的最大值。考虑到找的是整个子行列式的最大值，故有可能要交换行和列的值，对应的未知量的次序有改变，所以消元过程结束后，要对未知量的顺序进行还原。
在一些特殊情况下，选主元与不选主元效果一样，为了节省机时就可以不选主元。如：在实际工作中常见系数行列式中元素满足：
这样的矩阵我们称其为按行严格对角占优矩阵，简称严格对角占优矩阵。
即对角线上每一元素的绝对值均大于同行各元素绝对值之和。例如：
由于严格对角占优矩阵必定非奇异，且消元过程中第步主元必为，所以不必选主元，用顺序消去法求解即可。
例2．用高斯消去法及列主元素法求解方程组：
解：高斯消去法：
对增广矩阵进行初等变换
得同解方程组
可得：
列主元消去法：
得同解方程组：
解得：
课堂练习：
用高斯消去法和列主元素法解方程组
解：高斯消去法：
对增广矩阵做初等变换
列主元素法：
追赶法
设，为三对角矩阵
（*）
用前面介绍的方法求解这类矩阵很不经济，大量的零元既占内存又浪费计算机机时。我们根据顺序消元的思想导出一个简便的算法——追赶法。首先进行顺序消元，且每步都将主元系数化为1，这样
其中系数按下式计算
然后回代求解，得
定理1 若三对角方程组（*）系数矩阵满足：
所有均不为0；
，且其中至少有一个取不等号。则追赶法计算过程中每步的分母满足
因此追赶法能进行到底。
证 下面仅就的情况用数学归纳法进行证明，对条件中其他各种情况的证明方法类似。
因为，所以，于是
假设时，
。
由于
所以
故对一切，命题成立。证毕。
注意：当中有一元素为0，方程组（*）可化为两个三对角方程组，分别进行分解或讨论。
由于追赶法在计算过程中只涉及系数矩阵的非零元，大大节约了计算机内存与计算量。按所用乘除法次数进行比较，高斯顺序消去法大约需次，约当消去法大约需次，而追赶法只有次。
例：用追赶法解三对角方程组
解：用追赶法对其增广矩阵进行初等变换
得同解方程组
解得
