线性代数方程组的解法

线性代数方程组的解法

金靖翰

摘 要： 本文论述了线性代数方程组的几种解法 .

关键词： 线性代数方程组；高斯消元法；列主元消元法；三角分解法；杜立特尔分解法；迭代法；雅可比迭代法；高斯-赛德尔迭代法

1引言

目前，解线性代数方程组在计算机上常用的的方法大致把它分为两类：“直接法”与“迭代法”.在线性代数中曾指出 阶线性代数方程组有唯一的解，并且可以用克拉默法则求方程组的解，初次看来问题已经解决，但从使用效果看并不是这样的.因为求 阶线性代数方程组，如果用克拉默法则，需要计算个 阶行列式，每个 阶行列式为 项之和，每项又是 个元素的乘积，所以计算中仅乘法次数就高达次，当 较大时，它的计算量是非常惊人的.因为现在所碰到的很多问题都需要很大的计算量，故需要好用的算法来求解.

先来回顾一下回代过程和迭代过程.

(1)

是一个三角形方程组，当 有唯一解时，可以用反推的方式求解，也就是先从第 个方程解得

， (2)

然后代入第 个方程，可得到

， (3)

如此继续下去，假设已得到 ， ， , ,代进第 个方程即得 的计算 ， (4)

上述求解的过程叫做回代过程.

定义1^[1] (向量的范数) 若向量 的某个实值函数 满足

1. 是非负的，即 且 的充要条件是 ;

2. 是齐次的，即 ;

3. 三角不等式，即对 ，总是有

.

那么 上向量 的范数（或模）就是 .

下面给几个最常遇到的向量范数.

向量 的“1”范数：

(5)

向量 的“2”范数：

(6)

向量 的 范数：

(7)

例1 设 求 , , .

解 由式（5）,（6）及（7）知

.

定义2 若矩阵 的某个实值函数 满足

1. 是非负的，即 且 的充要条件是 ;

2. 是齐次的，即 ;

3. 三角不等式，即对 总有

;

4. 矩阵的乘法不等式，即对 总有

，

那么称 为 上矩阵 的范数（或模）.

表 1是矩阵 几个常用算子范数的定义与算式.

表 1

的极限就是方程组 的解向量，这时候在给定允许的误差内，只要 适当的大,就可以作为方程组在满足精度要求条件下的近似解.这种求近似解的方法就是解线性方程组的一类基本的迭代解法，其中 称为迭代矩阵，公式（9）称迭代公式（或迭代过程）,由迭代公式得到的序列 叫做迭代序列.如果迭代的序列是收敛的，则称为迭代法收敛；如果迭代的序列是不收敛，则称它是迭代法发散.

定理3 设 .如果约化主元素 ，则可以利用高斯消元的方法把方程组 约化成三角形方程组

来求解，其计算公式如下：

（1）消元计算：对 依次计算

（2）回代计算：

3用高斯消元法与列主元消元法解线性代数方程组（重点）！

3.1 高斯消元法解方程组

用高斯消元的方法求线性代数方程组的解的整个计算过程可分为两个环节，也就是利用按照次序消去未知数的方法，把原来的方程组转化成跟它同解的三角形方程组（这个转化的过程叫消元过程），再通过回代过程求三角形方程组的解，最终得到原来方程组的解.其中按照方程的顺进行消元的高斯消元法，又叫顺序消元法.

3.2列主元消元法解方程组

列主元消元法实际上是一种行交换的消元法，它跟顺序消元法比较而言，主要特点是在进行第 次消元前，不管 的值是否等于零，都在子块 的第一列中选择一个元 ，使

，

并将 中的第

行元与第 行元互相变换（相当于交换同解方程组 中的第 个方程），然后再进行消元计算得到结果.

注：列主元素法的精度虽然稍低于全主元素法^[1]，但它计算简单，相对比全主元素法它的工作的量大大减少，并且从计算经验和理论分析都可以表明，它与全主元素法同样拥有很好的值稳定性，列主元素法是求解中小型浓密型方程组的最好的方法之一.

4用三角分解法解线性代数方程组

4.1 矩阵的三角分解

定义4 把一个 阶矩阵 分解成两个三角矩阵相乘的形式称为矩阵的三角分解.

常见的矩阵三角分解是

其中 是下三角形的矩阵, 是上三角形的矩阵.

定理5^[1]（矩阵三角分解基本定理）设 .若的顺序主子式 ，那么存在唯一的杜利特尔分解

其中是单位下三角形矩阵，为非奇异的上三角形矩阵.

如果 是单位下三角形的矩阵， 是上三角形的矩阵，那么把这种分解法称为杜利特尔分解法，其中杜利特尔分解法是这种三角分解的一种特例，下面主要介绍利用杜利特尔分解法来求方程组的解.

4.2 用杜利特尔分解法解线性代数方程组

用杜利特尔分解法解方程组的步骤可以把它归纳为

（1）实现 分解，也就是

1. 按算式

（11）

（12）

依次计算 的第一行元 与 的第一列元 ；

2. 对 按算式

（13） （14）

依次计算 的第 行元 与 的第 列元 .

（2）求解三角形方程组 ，即按算式 依次计算 .

（3）求解三角形方程组 ，即按算式 依次计算.

利用杜利特尔分解法解方程组与高斯消元法是相似的，它重要的优点是：在利用 分解，解有相同的系数矩阵的方程组时,用杜利特尔分解法非常方便，只用两个式子就可以得到方程组的解.

5用迭代法解线性代数方程组

用迭代法求方程组 的解，需要考虑迭代过程的收敛性，在下面的讨论中，都假设方程组 的系数矩阵的对角阵是不为零的.

5.1 用雅可比迭代法解方程组

对于一般线性方程组 ，如果从第 个方程解出 ，就可以把它转化成等价的方程组

. （15）

从而可以得到对应的迭代公式

（16）

这就是解一般方程组 的分量形式的雅可比(Jacobi)迭代公式.如果把它改成

（17）

并把系数矩阵 表示成

（18）

其中

则可以看出 式的左右两端分别是向量 和 的第 个分量，故

因为 可逆，所以

于是就可以得到 是雅可比迭代的公式.

其中 （称为雅可比迭代矩阵）， .

5.2 用高斯-赛德尔迭代法解方程组

高斯-赛德尔迭代法也是常用的迭代法，设线性代数方程组为 ，则高斯-赛德尔迭代法的迭代公式为

（19）

其中迭代法（19）就称为高斯-赛德尔迭代法.通过雅可比迭代法类似的途径，就可以得到矩阵的表达式

其中 （称为高斯-赛德尔迭代矩阵）， .

高斯-赛德尔迭代法与雅可比迭代法都有算式简单、容易在计算机上实现等优点，但是用计算机来计算时，雅可比迭代法需要两组工作单元用来寄存 与 的量，而高斯赛-德尔迭代法只需一组工作单元存放 或 的分量.对于给定的线性方程组，用这两种方法求解可能都收敛或者都不收敛，也可能一个收敛另一个不收敛，两种方法的收敛速度也不一样.

5.3 迭代法的收敛条件与误差分析

定义6^[1] 矩阵 全部的特征值 的模的最大值，叫做矩阵 的谱半径，记作 ,即

.

定理7^[1] 对任意初始向量 迭代过程 收敛的充要条件是 ；当 时， 越小，那么其收敛的速度是越快的.

由定理7可知，用雅可比迭代法求解时，其迭代的过程是收敛的，而用高斯-赛德尔迭代法来求解,其迭代的过程是发散的.在不同条件下，收敛的速度是不同的，对同一矩阵，一种方法是收敛的，一种方法发散.

第 7 页