计算机编程c语言求解线性代数方程组

1、安徽三联学院本科专业学年论文题目：线性方程组求解方法比较姓 名万里龙专 业计算机科学技术系班 级 08级本科（2）班 指导教师刘晓娜完成日期：2010年11月21日题目：线性方程组求解方法比较摘要随社会的快速发展，随着科学和社会的发展，科学计算己经成为科学计算 的重要方法z,线性代数已经成为应用数学里非常重要的一门学科了，线性代 数的研究问题己经直接关系到fi常的生产问题，对于提高效率有很大作用。本文 主要介绍了线性代数中的解方程组问题与计算机相结合的方法及实现的结果，由 于计算机技术的飞速发展和普及应用，许多问题经过离散化处理后，需要借助数 值计算，木文详细介绍了三种方法用计算机解决线性方程

2、组的问题，在第二章中 本文详细的介绍了线性代数方程组的三种解法的理论知识与证明过程。为了更加 清晰的展现三种方法的不同点以及其各自的优越性，在第三章有以一个实例来证 明三种算法所得的结果。最后，本文又以计算不岀各种算法的时间复杂度来进一 步说明三种算法的优缺点。关键字:迭代高斯消去lu分解时间复杂度线性方程组雅克比高斯- 赛德尔第一章绪论1第二章求解线性方程组常见算法的比较22. 1迭代法22.2高斯消去法42.3 lu分解法.5第三章线性方程组的求根问题73. 1 迭代法73.2高斯消去法93.3 lu分解法11153.4算法的比较14参考文献第一章 绪论线性代数问题不但是其他数学课程的基础

3、，也是解决实际问题的工具。另外, 由于计算机技术的飞速发展和普及应用，许多问题经过离散化处理后，需要借助 数值计算，而数值计算离不开线性代数的基础知识。线性代数中许多数值计算与 计算机结合，才能得到更很好，更快，更精准的结果。为了将计算机与线性代数 方程组更好的结合在一起，本文做了比较全面的的解说。本文将线性方程组的求解过程用计算机实现，本文的编写由以下几个特点： 对于难点问题从具体模型引入（即解决给定的方程组），淡化抽象的概念 与定理，通俗易通； 注重开放的思维，对于具体以模型本文给岀了多种解题的思想及方法； 把问题数学方法与数学思想单独提岀来，并进行简洁易懂的理论证明，既 突岀了线性代数的

4、理论和基本思想，又可以帮助读者对该数学方法的理解。 基于了解数学的思想及方法后，本文基于c语言的基础上，给出了详细的 算法以及流程图，以配合读者理解计算机实现该算法的全过程。最后，本文简要分析了这些算法的计算效果，稳定性，收敛效果，计算 精度，时间复杂度，优劣性。第二章 求解线性方程组的三种常见算法2.1 迭代法迭代法的基木思想是将线性方程组转化为便于迭代的等价方程组，对任选一 组初始值台(i二1,2n),按某种计算规则，如：对于给定的线性方程组ax二b , 我们可以用不同的方法把它变为与之等价的，形为：x二bx+f的方程组。将上式 改写成迭代式：x(k+u=bx®+f选定初始值x&

5、#174; ,不断地对所得到的值进行修正，最终获得满足精度要 求的方程组的近似解。对线性方程组：ax二b,其中，a=(呦)g rz为奇异矩阵，将a分裂为：a=m-n, 其中，m为非奇异矩阵，且要求线性代数方程组mx二d容易求解，其中m是a的 分裂矩阵，于是就有ax二b转化为mx二nx+b,即ax二box二 nx+ b 由此可构造一个迭代法x(o)(初始向量)(1),如)二b)+f(k二0, 1, 2, 3, 4, 5)(2)其中,b=m_in=wi (m-a) =1 -m"a, f=m_ib,通过选取不同的m矩阵，就可得ax=b解的到不同迭代方法 设色vo (i=l, 2, 3-.

6、n)将a分为三部分:0 -an ._吗“_|_少.“°一。23一 a2,n- a2,n雅克比迭代法（j-迭代法）：选取a的分列矩阵m为对角阵，即m二d （对 角阵），因此a二d-n,由此得:x（0）（初始向量）严）二bp）+f（k=0, 1, 2, 3, 4, 5）0令卅）=（屮+垮）+址）戏）丁,由迭代公式得:dxa+1）= （l+d）兀+bo*m二 d" （l+u） xk） + dlb即有：_1hau x!a+1）二一工 ad x（ik） 一ati 券）+ 勺 （i二 1, 2, 3.n;j=1j=mk二0,1, 2）于是，得到解ax二b得：雅克比的计算公式为：'

7、;0）=（屮,閉,卅丁1i-l门兀e =匚（勺-亍驴-匕用）aii;=1./=/+1（k二0, 1, 2, :i=l, 2, 3, n）高斯一塞德尔迭代法（gs迭代法）：选m为a的下三角部分，即m二d-l （下三角矩阵），因此a=m-n,由此得：x（0）（初始向量）,2)二b)+f(k=0,1, 2,3,4, 5)0令严二(屮+疔+垮).宅')丁,由迭代公式得:(d-l),如)二ux+b即d严)二 lx(z+u卅)+bo 严)二(d-£)-,uxw+ (d-lb得ait x+) = s /兀,+d工 an xk (i=l, 2, 3 n;>1j=/+lk=0, 1, 2

8、)于是，得到解ax=b得：高斯-赛徳尔的计算公式：乂(0)_“(0) v(o)jo)卩a 一 i儿9 a2 州)1i-lh&叫_(勺-立屛-5>用)aiij=1j=/+l(k=0, 1, 2, :i=l, 2, 3, n)2.2高斯消去法高斯顺序消去法的基本思想对线性代数方程组所对应的增广矩阵（a|b）进 行一系列“把某一行的非零常数倍加到另一行上”的初等变换，使得（a|b）中 a的对角线以下的元素全变为0,从而使原方程组等价的转化为容易求解的上三 角形线性代数方程组，再通过回代得到上三角形线性代数方程组的解，即可求得 原方程组的解，对线性方程组:ax二b ；令增广矩阵为：a(1

9、)=(a(1):z?(i) = (a:z?)具体步骤为：a 消元过程：令zzl=-，把式的增广矩阵中的第1行的厶倍依次加到该增广矩阵的第i （i>l）行，则第i（i>l）行第j列位置的元素为：(i, j=2, 3, 4,n)切=甲）+側"一塔勺 （1=2, 3,n）因此，式可转化为:a(12a(2) =a"=0疋)e 00un20a；?a竝1冴）u n-l_ 00a(fl) nn労） 回代过程:代数方程组经过n-l次消元以后,线性代数方程组。若需",则可得,q”-i4卫1依次做下去，一直做到第n-l步，即有aa）x = ba）化为艸=対）为:得到上述对

10、应的的上三角(rn ) ful(k=nl n-2,，2, 1)丿=&+1高斯顺序消去法定理：设ax二b,其中ag r,txn,若或)ho (k二1,2, 3.n), 则可通过高斯顺序消去法将ax=b化为等价的上三角形线性代数方程组，且计算 公式为:消元计算(k二1,2, 3,n1)：“+1)冋代计算:u(k=n-l, n2, ., 2, 1)2.3 lu分解法将高斯消去法改写为紧凑形式，可以直接从矩阵a的元素得到计算l, u元 素的递推公式，而不需奥任何屮间步骤，这就是所谓的lu分解法，实现了 a的 lu分解，那么求解线性代数方程组ax=b的问题就等价于求解两个三角方程组： ly二b,

11、求 yux=y,求 x设a为非奇异矩阵，且有分解式a=lu,其中l为单位下三角矩阵，u为上三角矩 阵,即：1 "11 u2a 二 211u22 hi2 丨第一步：用l的第一行分别乘u的弟j (j二1,2.n)列，比较两边可得如-aj( j二 1，2n)分别用l的第i (i=l,2.n)行乘u的第一列，比较两边可得 之】x知(1=1,2.n)即 £=鱼(i二l,2.n)l的第一列和u的第一行的所有元素都求出来了。第二步：用l的第二行分别乘u的第j (j=l,2n)列，比较两边可得 u2j =ci2j kuj( j二2, 3.n)分别用l的第i (1=1,2,n)行乘u的第二列

12、，比较两边可得.=宀 m(i 二 3,4.n)这样就求出了 l的第二列和u的第二行的所有元素。第k步:用l的第k行分别乘u的第j (j=k, k+l,k+2.n)列，比较两边可 得ukj = akjkuj +hk-mij)(j=k, k+j n)分别用l的第i (i二1,2.n)行乘u的第k列，比较两边可得aik kuk (i二k+1,n)lu分解的计算公式为:uv =aj (j=l, 2n),li = (i=l, 2. n)w11r-l嗨=兔一kmumj(j=k+l,k+2.n),m=(k+l, k+2.n)未知数的计算公式：求解ly=b, ux二y的计算公式：j?i =bk-yk=bk_2

13、gyjj=1(k=2,. n )xk =九一 dke八k+1(k=nl, k=n22,1)第三章线性方程组的求解问题理论知识是实际解题的基础，只有熟练掌握理论知识以及一般情况下的解题 方法才能在实际应用中更好的运用。而本章主要是通过实际实例比较以上三种算 法在求解线性方程组中的应用，并得到相应结论。7.0*x l + 2.0*x2+l 0*x3+(2.0 严 x4 = 4.0求解方程组9,0*xl + 150*x2+3.0*x3+(20fx4=7.0 (2.0 严 xl+(2.0 产 x2+11.0x3+5,0*x4 =1.0 1.0*xl+30*x2+20*x3+130*x4=00gs迭代法

14、解题:解：取兀(°)= (0,0,0,0)，得屮= j-(4.0-2.0 -1 喝 + 2.0#)卅利=占 (70一90彳利一30£ + 20址)屮 二占(1.0 + 2.0屮 + 2,0才5.0丘)屮=丄(_1.0屮_3.0屮_2.0护i 413.01-3对k二0, 1, 2.，计算c语言代码：include "math. hinclude "stdio.hint gausdl(int ndouble a, double b,double x,double eps) int i, j, u, v;double p, t, s, q;for (i=0;

15、i<=n1; i+) u二i*n+i; p二0. 0; xi二0. 0;for (j=0; j<=n-l; j+)if (i!=j) v二i*n+j; p=p+fabs(av);if (p>二fabs(au) printf (/zfailn)； return(-1) ;p二eps+1.0;while (p>=eps) p=0. 0;for (i二0; i<=nl; i+) t二xi; s=0. 0;for (j=0; j<=n-l; j+) if (j!=i) s二s+ai*n+j*xj;xi = (bis)/ai*n+i;q=fabs (xit)/(1.

16、o+fabs (xi); if (q>p) p=q；rcturn (1);void main() int i;double eps;static double a16 = 7. 0, 2. 0, 1. 0, -2. 0, 9. 0, 15. 0, 3. 0, -2. 0,-2. 0, -2. 0, 11. 0, 5. 0, 1. 0, 3. 0, 2. 0, 13. 0;static double x5, b4二4. 0, 7. 0, t. 0, 0. 0;cps=0. 000001;if (gausdl (4, a, b, x, eps) >0)for (i=0;i<=3;

17、 i+) printf (x(%d) =%13. 7en，i, xi);运行结果：x(0)=4. 9793130e-001x(l)二l4449392e-0016.2858050e-002x(3)=-8. 1317628e-0023.2高斯消去法解题构造增广矩阵得:7.02.01.()-2.04.09.015.03.0-2.07.0-2.0-2.011.05.0-1.0经一次消去得，3.02.013.00.07.02.01.()-2.()4.00.0-12.0-15.0-1 15.07.00.04.015.031.0-1.00.0-19.0-13.0-93.04.01.0再经过二次消元得，7.0

18、2.01.0-2.04.00.0-12.0-15.0-115.07.00.00.010.0-7.3-1.30.00.00.0-9744010220,经一次回代可求出x4,两次回代可求x3,三次回代可求x2,四次回代可求xl.c语言代码：#inelude "stdlib. h#include "math. h#inelude "stdio. hint rgauss( int n,double a,double b) int *js, 1, k, i, j, is, p, q;double d, t;js= (int*)malloc(n*sizcof(int);1=1

19、；for (k=0;k<=n2;k+) d=0. 0;for (i二k; i<=nt ; i+)for (j=k;j<=n-l;j+) t二fabs(ai*n+j);if (t>d) d=t; jsk=j; is二i; if (d+1.0=1.0) 1=0;else if (jsk!=k) for (i=0;i<=n-l;i+) p二i*n+k; q二i*n+jsk;t二ap ; ap=aq ; aq=t;if (is!=k) for (j=k;j<=n-l;j+) p二k*n+j; q二is*n+j;t=ap; ap=aq; aq=t;t=bk; bk=b

20、is; bis=t; 辻(1二二0) free(js) ; printf (/zfailn，z); return (0);d二ak*n+k;for (j二k+1;j二n-1;j+) p=k*n+j; ap=ap/d; bk=b k/d;for (i=k+l;i<=nl;i+) for (j二k+1;j二n-1;j+) p二i*n+j; ap=ap-a,i*n+k*ak*n+j;bi二bi-ai*n+k*bk;d=a(nt)*n+nt;if (fabs(d)+l. 0=l. 0) free(js) ; printf (/zfailn，z); retum (0); bn-l=bn-l/d;f

21、or (i=n-2;i>=0;i) t二0. 0;for (j二i+1;j二n-1;j+)t二t+ai*n+j*bj;jsn-l=n-l;for (k=nl;k>=0;k-)if (jsk!=k) t=bk; bk=bjsk; bjsk=t; free(js);return (1);void main() int i;static double a16= 7. 0, 2. 0, 1. 0, -2. 0, 9. 0, 15. 0, 3. 0, -2. 0,-2. 0, -2. 0, 11.0, 5. 0, 1.0, 3. 0, 2. 0, 13.0;static double b4

22、= 4. 0, 7. 0, -1. 0, 0. 0; if (rgauss (4, a, b) !二0) for (i=0;i<=3;i+)printf (x (%d)二 %13. 7e n，z, i, bi);运行结果：x(0)=4. 9793125e-001iox(l)=1.4449395e-001x(2)=6. 2858052e-002x(3)=-8. 1317632e-00211.3010000求得，l二0.3-0100.10.20.11y2, y4,由 ux二y 得，xl,7.002.012.41.01.7-2.00.6,u 二0011.14.500012.8,由ly=b计算得

23、，yl,x2, x3, x4o3.3 lu分解法解题 令a=lu设_ 7.02.01.0-2.0_ 1000知绚2u3w149.015.03.0-2.0<2i1000n °。w23w24-2.0-2.011.05.0厶21000w33w341.03.02.013.0j4i421000w44_c语言代码#include，zstdio. h#includemath. h" define n 4 /* n为方程组系数矩阵的阶数*/ void lu(float an n,float ln n, float un n) /* lu 分解 */ int i, j, k; for

24、(k=0;k<n;k+) for (i=k; i<n; i+)/*计算l矩阵的第k列元素*/lik=aik;for(j=0;j<=k-l;j+)lik-=(lijwjk);for (j=k+l; j<n; j+)/*计算u矩阵的第k列元素*/ukj=akj;for(i=0;i<=k-l;i+)ukj-=(lki*uij);ukj/=lk k;void solve(float bn, float lnn, float unn, float xn) int j, k;float yn;for (k=0;k<n;k+)/* 计算 ly=b 中的 y */yk=bk

25、;for(j=0;j<=k-l;j+)yk=yk - lkj*yj; yk=yk/lk kj;for (k二nt ;k>二0;k-) /* 计算 ux二y 中的 x */ xk=yk;for(j=k+l;jn;j+)xk =xk-uk j*xj;void zg_matric(float an n, float bn) /* 输出增广矩阵 */ int i, j;for(i=0;i<n;i+) for(j=0;jn;j+)printf(10f, aij);printf (10f，bi);printf("n");printf(n)；floatvoid meii

26、n()staticann = 7, 2, 1,-2, 9,15, 3,-2, -2,-2, 11,5, 1,3, 2, 13; float bn = 4, 7,-1,0;float xn二0, 0, 0, 0;float un n = l,0, 0, 0, 0,1,0, 0, 0, 0,1,0, 0,0,0, 1; float lnn;int i;zg matrie (a, b);lu (a, l, u);solve (b, l, u, x);for(i=0;i<n;i+)/*输出方程组的解*/printf (“ x%d=%ll. 7fn，i+1, xi);运行结果： 增广矩阵为:7.

27、0000009. 000000 -2. 000000 1.0000002.00000015.000000-2.0000003.0000001. 0000003.00000011.0000002.000000-2.000000-2.0000005.00000013.0000004.0000007. 000000-1.000000. 00000x(l)二 0. 4979313x(2)= 0. 1444939x(3)= 0.0628581x(4)= -0. 0813176 3.4算法比较在计算机上完成一次乘除运算比完成一次加减运算所好的时间要多的多，故 当一个算法中的加减运算次数与乘除运算次数相差不多时，仅考虑乘除运算次数 就可以体现