Chapt-4 线性代数方程组的数值解法

《Chapt-4 线性代数方程组的数值解法》由会员分享，可在线阅读，更多相关《Chapt-4 线性代数方程组的数值解法（46页珍藏版）》请在金锄头文库上搜索。

1、第四章 线性代数方程组的数 值解法 4.1 概 述线性代数方程组(System of Linear Algebra Equations)的求解是数值计 算方法中的一个重要课题。现代工程技术或科研过程中所遇到的一些实际问 题，常常直接或间接地归结为求解一个线性代数方程组。例如有分支水流的 流速分布、建筑结构中的设计计算和应力分析、仪器分析中的质谱分析、光 谱分析、色谱分析、电力系统中的电网分析等等；另外有些数值计算方法本 身也是以线性代数方程组的数值解、有限元法和边界元等等，其中间过程或 者最后都会导致求解线性代数方程组。这些线性代数方程组的解法是十分必 要的，有着十分重要的意义。 4.1 概

2、述本章介绍求解n阶线性代数方程组的一般形式是：或简写成矩阵形式： 其中A称为方程组(4.1)式的系数矩阵；B称为方程组的右端列向 量；x称谓方程组解的列向量 。它们分别为 (4.1)(4.2)4.1 概 述求解线性代数方程组的数值计算方法很多，大致可分为两大类：消去（元 ）法和迭代法。消去法是直接从方程组的系数矩阵入手，经过有限步运算求 出方程组的精确解（假如没有舍入误差的话）。迭代法则是将求方程组的问 题化为构造一组递推计算结构，从一组近似解出发，用这组递推结构逐步算 出精度更高的近似解。上述这两类算法各有其优点和缺点，消去法的计算量 小，但程序复杂；迭代法计算量大，精度不高，但程序结构简单

3、。本章将主要介绍求解线性代数方程组的简单高斯消去法和三角分解法，迭 代法将在以后相关章节中介绍。4.2 高斯消去法4.2.1高斯消去法的基本步骤 我们以三元线性代数方程组为例，叙述简单高斯消去法（以下简称为消去 法）的基本步骤，这各方法是理解其它方法的基础，消去法分为消元和 回代两个过程。 例4-1：消去过程实际上是对增广矩阵作行初等变换。上例可表示为 4.2 高斯消去法这是上三角方程组，它极容易求解：由第三个方程得 ， 代入第二个方程得 ，再代入第一方程 。此一过程 称为回代过程。从上述消元过程可以看出，三元议程组要经过两次消元（ 因为 不用消）才能把增广矩阵化为拟上三角矩阵。对于 一般的n

4、元线性代数方程组，经经过(n-1)次消元才能把相应 的增广矩阵变换为拟上三角矩阵。n元线性代数方程组的增广 矩阵的一般形式如(4.3)式。4.2 高斯消去法以下是消元步骤（共分n-1部）： 第一步(k=1)：从第一列中消去第2n行中x1的系数，即消去a11下方元素； 第二步(k=2)：从第一列中消去第3n行中x2的系数，即消去a22下方元素； (4.3)4.2 高斯消去法第j步(k=j)：从第j列中消去第j+1n行中xj的系数；即消去ajj下方元素;第n-1步(k=n-1)：从第n-1列中消去第n行中xn-1的系数；即消去an-1n-1下方元 素因此，高斯消元步骤的计算通式可写为： (4.4)

5、4.2 高斯消去法经过n-1步消元后，增广矩阵(4.3)式变为： (4.5)4.2 高斯消去法高斯回代过程的通用递推计算公式可写为： (4.6)4.2 高斯消去法4.2.2高斯消去法的计算量分析 我们从(4-4)式可以看出，高斯消去法消去过程共分n-1步，第k步变换n-k行 ：对这些行先乘系数，再从n+1-k元素减去第k行相对应列的元素；因此共 需乘、除次数为回代过程求xn需1次除法，求xn-1需1次乘法、1次除法，求x1需n-1次乘法 、1次除法，因此共需乘除次数两过程共需要乘除次数为 。当n=20时， N=3060.4.2 高斯消去法4.2.2 高斯消去法的程序框图与通用程序 STARTI

6、NPUT N, A(), BCALL eliminationCALL backOUTPUT X(N)END4.2 高斯消去法10 OPEN(8, 或在kn行、kn列选绝对值最大的元素 apq，交换k、p行和k、p列，然后继续进行消去过程。这两种消去法为行 主元消去法和全主元消去法。本节讨论应用广泛且易于在计算机上实现 的列主元素消去法。列主元素消去法的计算步骤可归纳如下： 选主元素； 把主元素所在的行与第k行互换 ； 消元 ； 回代 4.2 高斯消去法其中、两步与简单高斯消去法中的消元与回代过程完全一 样，也就是说，列主元消去法是在简单消去法的基础上引入 选列主远过程，这个过程并不影响获得正确

7、结果。列主元高斯消去法的程序框图与通用程序为了简单和说明问题，将上面的和两步单独用一个子程 序。因此，列主元高斯消去法的程序框图只需在简单高斯消 去法的流程图中增加一个选列主元子程序gaussp，具体如下 ： 4.2 高斯消去法SUBROUTINE gausspk=1, n-1 a(p,j)=t i=k+1,nc= abs(a(i,k); p=iend it=a(k,j); a(k,j)=a(p,j)end jEND SUBROUTINE gausspc= abs(a(k,k); p=kIf abs(a(i,K)c? YNj=1, n+1 end k4.2 高斯消去法10 SUBROUTINE

8、 gaussp(a,b,n) 20 DIMENSION a(n,n+1),b(n) 30C 生成增广矩阵 40 DO i=1,n 50 a(i,n+1)=b(i) 60 END DO 70C 选主元开始 80 DO k=1,n-1 90 c=abs(a(k,k);p=k 100 DO i=k+1,n 110 IF(abs(a(i,k)c) THEN 120 c= a(i,k);p=i 130 END IF 140C p,k行交换开始150 DO j=1,n+1 160 t=a(k,j);a(k,j)=a(p,j) 170 a(p,j)=t 180 END DO 190 END DO 200 E

9、ND SUBROUTINE gaussp4.2 高斯消去法4.2.4 高斯-约当法 前面所讲的是如何将一个线性方程组的系数矩阵改变为一个上三角矩阵，然 后回代求解。本节所讲的是如何将系数矩阵改变为一个对角矩阵，即，除 对角线元素外，其他元素均为零 4.2 高斯消去法列主元高斯-约旦消元过程的递推计算通式结构为：高斯-约旦消去法消元过程的计算量比高斯消去法有所增加（约为1.3倍），但是总 的计算量增加并不大，另一方面，这一方法的程序结构简单，所以在实际中得到了 广泛的应用。 高斯-约旦消去法的程序框图与通用程序自行设计。 改进后 (4.8)(4.7)4.3 三角分解法线性方程组的另一直接解法是三

10、角形分解法，即方程组（4-2）的系数矩 阵A分解成两个形式简单的三角形矩阵L和U的乘积：A=LU。从而求解 Ax=b的问题转化为三角形方程组Lx=yUy=b 其中(4.9)(4.10)4.3 三角分解法比较等式左边和右边乘积矩阵LU的第r行主角元右边（含主角元）的对应元 素，得再比较等式两边第r列主角元以下（不含主角元）的对应元素，得当r=1时，有(4.11)(4.12)(4.13) (4.14)4.3 三角分解法假定已求出U的第1至第n-1行和 L的第1至第n-1列，由（4-11）式计算出U的 第r行元素和由（4-12）式计算出L的第r列元素（4-13）式至（4-16）式所表示的矩阵分解称D

11、oolittle分解。 类似地，若U为单位上三角矩阵，而L为下三角矩阵，则有(4.15)(4.16)(4.17)4.3 三角分解法规定 。称上述分解为Crout分解。实现了系数矩阵A的Doolittle或Crout分解后，方程组Ax=b可以分解成为Ly=b 和Ux=b这两个三角矩阵来进行求解。设U为上三角矩阵，而L为单位下三角矩阵，并且 ，根 据公式（4-4）和（4-6）得与Doolittle分解相对应的方程组解为(4.18)(4.19)4.3 三角分解法类似地，与Crout分解相应的求解公式(4.20)(4.21)4.3 三角分解法无论Doolittle分解还是Crout分解，其运算量均小于

12、高斯消去法。为保证它们 能顺利、稳定进行，也可选列主元。 用Crout分解法求解方程组Ax=b的步骤如下： 用（4-17）式求lir; 确定最大列主元；用（4-18）式求uir, 进行分解； 回代。通用公式为(4.22)(4.23)4.3 追赶法求解三对角占优方程组若作Crout分解，则有4.3 追赶法比较Crout解，易知回代得 。(4.24)(4.25)4.3 追赶法按照以上公式求解Ax=b的方法就叫做追赶法，其中ui、li 和yi 称追，回代称赶 ， 乘除法运算量仅为5n-4，远比一般方程组的高斯消去法或三角分解法的 运算量少。不用选主元，就可保证顺利、稳定进行计算。4.4 舍入误差对解

13、的影响本节研究线性代数方程组解的误差。衡量数的误差用绝对值。方程组的解 是向量，衡量其误差，自然也会想到绝对值的概念。 4.4.1 向量与矩阵范数众所周知，数x的绝对值x是x的函数: x=(x),具有以下三性质 ： （1） （2）对任意实数 （3） 推广到向量 ，具有如下类似性质的函数： 。该函数成为向量 x的范数或模或长度，它也应该具有以下性质： （1）非负性 （2）齐次性：对任意实数 （3）三角不等式：4.4 舍入误差对解的影响几何上三角不等式表示：在以向量x、y及其和x-y构成的三角形中，一边之长不超过另 两边边长之和，即从而表示以x、y和x-y为边的三角形中，一边之长不小于另两边边长之

14、差。 常用向量范数有3种，即：分别称为1范数、2范数和无穷大范数。不难验证它们具有性质（1）和（2）。对于性4.4 舍入误差对解的影响性质（3），这里已2范数为例，给出证明，以供参考。最后不等式称Cauchy不等式。注意对任意实数 4.4 舍入误差对解的影响由 二次式的判别式 ，便可推出Cauchy不等式，因而2范数的性质（3 ）得证。对于n阶方阵，具有如下4种性质的函数 称为矩阵范数。 （1） （2）对任意实数 （3） （4） 容易验证矩阵函数具有上述4种性质，因而，它是一种范数，称为矩阵的F范数。 常用矩阵范数是如下三种范数：4.4 舍入误差对解的影响其中 表示矩阵 的谱半径，即 特征值绝

15、对值的最大值。 三种范数分别称为1范数或列范数，无穷大范数或行范数，2范数或谱范数 。 可以证明，矩阵的这三种范数还具有以下3种性质：（满足性质（1）的矩阵 范数成为相容范数） （1） （2）单位矩阵I的范数 （3） 时 可逆且 (4.26)4.4 舍入误差对解的影响例4-3 设则4.4 舍入误差对解的影响它的三个根为4.4.1 误差分析设线性方程组Ax=b中，A为非奇异矩阵，x为方程组的精确解。假定b有误差 b,则解为x+x,即4.4 舍入误差对解的影响即 两边取范数又因 由（4-30）和（4-31）式，得另外，若矩阵A有误差A，则解为x+x，即(4.27) (4.28)(4.29)(4.30)(4.31)(4.32)(4.33)4.4