《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元线性代数方程组，经经过(n
4、-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),4.2 高斯消去法,经过n
5、-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 高斯消去法的程序框图与通用程序,START,INPUT N, A(
6、), B,CALL elimination,CALL back,OUTPUT X(N),END,4.2 高斯消去法,10 OPEN(8, &file=EliminationMetod.dat, &status=new)20 DIMENSION a(n,n+1), x(n), b(n)30C 输入n,a(),b40 READ(8,(1x,i2,) n50 DO i=1,n60 READ(8,(1x,e12.6) ) b(I)70 END DO80 DO i=1,n90 DO j=1,n100 READ(8, (1x,e12.6) ) a(i,j)110 END DO 120 END DO,120
7、C 消元过程130 CALL elimination(a,b,n)140C 回代过程150 CALL back(a,x,n) 160C 输出结果x170 DO i=1,n180 WRITE(9,(1x,e12.6) x(i)190 END DO 200 END210220230240250,4.2 高斯消去法,SUBROUTINE elimination,K=1,n-1,i=k+1,n,R=a(i,k)/a(k,k),j=k+1,n+1,a(i,j)= a(i,j)-R*a(k,j),end j,end j,end i,end k,END SUBROUTINE elimination,4.2
8、高斯消去法,10 SUBROUTINE &elimination(a,b,n)20 DIMENSION a(n,n+1),b(n)30C 生成增广矩阵40 DO i=1,n50 a(i,n+1)=b(i)60 END DO70C 消去过程开始80 DO k=1,n-190 DO i=k+1,n100 R=a(i,k)/a(k,k)110 DO j=k+1,n+1120 a(i,j)= a(i,j)-R*a(j,k)130 END DO,140 END DO150 END DO160 END SUBROUTINE elimination,4.2 高斯消去法,SUBROUTINE back,X(n
9、)= a(n,n+1)/a(n,n),k=n-1,1,-1,s=0,j=k+1,n,s=s+ a(k,j)*x(j),end j,X(k)=(a(k,n+1)-s)/a(k,k),end k,END SUBROUTINE back,4.2 高斯消去法,10 SUBROUTINE back(a,x,n)20 DIMENSION a(n,n+1),x(n)30 x(n)=a(n,n+1)/a(n,n)40 DO k=n-1,1,-160 s=0.0 60 DO j=k+1,n70 s=s+a(k,j)*x(j)80 END DO90 X(k)=(a(k,n+1)-s)/a(k,k) 100 END
10、 DO110 END SUBROUTINE back,4.2 高斯消去法,4.2.3 选主元法高斯消去法消去过程中，第k步求n-k个系数aik/akk用到的除数akk, 称为主元。如果akk为接近于零或零，则消元递推计算通式(4-4)将出现被零除的情况，从而使计算机溢出或无法进行下去。例4-2准确到九位小数的解是x1=0.250001875，x2=0.499998749，若在4位计算机上按高斯消去法求解，则,4.2 高斯消去法,回代得解 ， ，显然产生严重失真。造成这种结果的原因，就是小主元10-5的出现。用它作除数会产生大乘数，数乘大乘数变大数，大数吃小数产生舍入误差,如( )，从而使 也有
11、误差。 因此，为了保证获得正确的结果，在消元过程中可在第k步的第k列的元素akk,ak+1,k,， ank中选主元，即在其中找出绝对值最大的apk，然后交换第k行和第p行，继续进行消去过程。这种消去法为列主元消去法。也可在第k步的第k行的元素akk,ak,k+1,， akn中选主元，即在其中找出绝对值最大的akq，交换第k行和第q行;或在kn行、kn列选绝对值最大的元素 apq，交换k、p行和k、p列，然后继续进行消去过程。这两种消去法为行主元消去法和全主元消去法。本节讨论应用广泛且易于在计算机上实现的列主元素消去法。 列主元素消去法的计算步骤可归纳如下： 选主元素； 把主元素所在的行与第k行
12、互换 ； 消元 ； 回代,4.2 高斯消去法,其中、两步与简单高斯消去法中的消元与回代过程完全一样，也就是说，列主元消去法是在简单消去法的基础上引入选列主远过程，这个过程并不影响获得正确结果。 列主元高斯消去法的程序框图与通用程序 为了简单和说明问题，将上面的和两步单独用一个子程序。因此，列主元高斯消去法的程序框图只需在简单高斯消去法的流程图中增加一个选列主元子程序gaussp，具体如下：,4.2 高斯消去法,SUBROUTINE gaussp,k=1, n-1,a(p,j)=t,i=k+1,n,c= abs(a(i,k); p=i,end i,t=a(k,j); a(k,j)=a(p,j),
13、end j,END SUBROUTINE gaussp,c= abs(a(k,k); p=k,If abs(a(i,K)c?,Y,N,j=1, n+1,end k,4.2 高斯消去法,10 SUBROUTINE gaussp(a,b,n)20 DIMENSION a(n,n+1),b(n)30C 生成增广矩阵40 DO i=1,n50 a(i,n+1)=b(i)60 END DO70C 选主元开始80 DO k=1,n-190 c=abs(a(k,k);p=k100 DO i=k+1,n110 IF(abs(a(i,k)c) THEN120 c= a(i,k);p=i130 END IF140
14、C p,k行交换开始,150 DO j=1,n+1160 t=a(k,j);a(k,j)=a(p,j)170 a(p,j)=t180 END DO 190 END DO200 END SUBROUTINE gaussp,4.2 高斯消去法,4.2.4 高斯-约当法前面所讲的是如何将一个线性方程组的系数矩阵改变为一个上三角矩阵，然后回代求解。本节所讲的是如何将系数矩阵改变为一个对角矩阵，即，除对角线元素外，其他元素均为零,4.2 高斯消去法,列主元高斯-约旦消元过程的递推计算通式结构为： 高斯-约旦消去法消元过程的计算量比高斯消去法有所增加（约为1.3倍），但是总的计算量增加并不大，另一方面，这一方法的程序结构简单，所以在实际中得到了广泛的应用。 高斯-约旦消去法的程序框图与通用程序自行设计。,
