线性代数方程组的解法

第4章线性代数方程组的解法直接法与迭代法各有优缺点，前者由于受到计算机存储容量的限制，一般来说，仅适于系数矩阵阶数不太高的问题，其工作量较小，但程序较复杂。后者主要用于某些系数矩阵阶数较高的问题，一般来说，程序较为简单，但工作量有时较大。实际计算时，应根据问题的特点和要求来决定方法的取舍。本章介绍的求解线性代数方程组的直接法有Gauss(高斯)消元法和LU分解；迭代法有Jacobi迭代和Gauss-Seidel迭代。4.1高斯消元法4.2矩阵的LU分解4.3雅可比迭代4.4高斯-塞德尔迭代4.5收敛性定理4.6应用实例4.1高斯消元法由“线性代数”我们已经知道，对于线性代数方程组：Gauss消元法的计算步骤分为消元和回代两个过程，本节的目的是给出Gauss消元法的符号描述、计算流程图。［例2］如果方程组AX=B的系数矩阵A是n阶三对角阵，即当|i-j＞1|时，aij=0或写成试设计一个算法来解这三对角的方程组。 解：假定所有主元均不等于0。在第1次消元过程中，由于系数矩阵A的第一行只有两个元素不为零，所以只需变动d2，b2

并将a1置0。再考虑存储结构，新的d2，b2仍存放在d2，b2所在的单元，即

d2-a1c1／d1d2 b2-a1b1／d1b2以后各步的消元也仅变动di、bi

并将相应的ai-1置0。设元素的下标变量为i。

根据上述对i=2的分析，可知第i步的计算公式为：

di-ai-1ci-1／di-1

di bi-ai-1bi-1／di-1

bi

消元结束后，系数矩阵的非零元素仅在主对角线和次对角线上出现，求得

bn／dn

xn (bi-cixi+1)／di

xi(i=n-1,…,1)

设置4个数组分别来存储ai，bi，ci，di，算法描述如下：input(ai),(bi),(ci),(di)fori=2,3,…,ndo

ai-1／di-1

l

di-lci-1

di

bi-lbi-1

biendbn／dn

xnfori=n-1,n-2,…,1do (bi-cixi+1)／di

xiendoutput(xi)。4.2矩阵的LU分解若矩阵A能分解为几个结构简单的矩阵乘积时，则求解AX＝b的过程可以简化。常用的一种分解方法是LU分解。给定n阶非奇异矩阵A，我们寻求两个n阶矩阵使A=LU。［例3］求下面矩阵的LU分解解：先求二阶主子矩阵的LU分解u11=a11=2，u12=a12=-1，l21=a21／u11=0，u22=a22-l21u12=-4-0=-4本题i=3，由公式（4.3）得定理2（矩阵的LU分解）若n阶方阵A的n个顺序主子矩阵都非奇异，则A可惟一地分解为单位下三角矩阵L和非奇异的上三角矩阵U的乘积。4.3雅可比迭代雅可比（Jacobi）迭代(以下统称为Jacobi迭代)是一种求解线性代数方程组的迭代方法。4.4高斯-塞德尔迭代高斯-塞德尔（Gauss-Seidel）迭代(以下统称为Gauss-Seidel迭代)是对Jacobi迭代的一种改进。我们仍用例4为例，但迭代格式改为：设初值不变，迭代两步的结果如下(见表4-3)。 表4-3迭代两步的结果4.5收敛性定理为了介绍Jacobi、Gauss-Seidel迭代的收敛性定理，我们