高斯消元法

《高斯消元法》由会员分享，可在线阅读，更多相关《高斯消元法（11页珍藏版）》请在装配图网上搜索。

1、精选优质文档-倾情为你奉上求解线性方程组的直接解法5.1Gauss消去法 三角方程组先举一个简单的例子来说明消去法的基本思想.例1. 用消去法解方程组解 第一步.将方程(1)乘上-2加到方程(3)上去,消去(3)中的未知数,得到 第二步.将方程(2)加到方程(4)上去,消去方程(4)中的未知数,得到与原方程组等价的三角形方程组 显然,方程组(5)是容易求解的,解为上述过程相当于 其中用表示矩阵的第行.下面我们讨论求解一般线性方程组的高斯消去法.一般地 当a11a22ann0时,可解出xn=bn/annfork=n-1:1xk=(b1- ak,k+1xk+1- aknxn)/ akkend注:可

2、用同一组单元.并可解出一个未知数即代入其它方程消去该未知数Gauss消元法的流程图为:流程图中，分别为线性方程组的系数矩阵和常数向量；k 是循环次数。 顺序消去法一般地,k=1对n阶方程组消去第k个元(akk0):这里各行变换:i行-k行mik,其中mik=aik/akk,i=k+1,n而后, k=2对n-1阶方程组消第2个元我们有如下顺序消元算法:fork=1:n-1ifakk0fori=k+1:nmik=aik/akki行=i行-k行mikendelsestopendend（每行包括右端项!）可细化,也可存储mik于aik得:fork=1:n-1ifakk0fori=k+1:naik=ai

3、k/akkforj=k+1:naik=aik-aikakjendbi=bi-aikbkendelsestopendend顺序消元过程和回代过程连起来就可得精确解.顺序消元算法也可将系数矩阵和右端项分开:fork=1:n-1ifakk0fori=k+1:naik=aik/akkforj=k+1:naik=aik-aikakjendendelsestopendend(注意mik在aik)fork=1:n-1fori=k+1:nbi=bi-aikbkendendGauss消去法运算量消去第k个元素时，对矩阵作加法和乘法运算各(n-k)(n-k)次,除法(n-k)次.对右端作加法和乘法运算各(n-k)

4、次.分别共12+22+(n-1)2=n(n-1/2)(n-1)/3和1+2+(n-1)=n(n-1)/2次加法乘法,消元时还有1+2+(n-1)= n(n-1)/2次除法.另外回代过程中加法和乘法运算各n(n-1)/2次,除法n次.运算量主要是消元的贡献,加法和乘法运算各约n3/3.定理1.设Ax=b,其中A(1) 如果则可通过Gauss消去法将Ax=b约化等价的三角形方程组,且计算公式为:(a) 消元过程设,对计算(b) 回代过程(2) 如果A为非奇异矩阵,则可通过Gauss消去法(及交换两行的初等变换)将方程组Ax=b约化为.行列式和逆矩阵易知顺序消元过程中，行列式不变.因此det(A)=

5、det(U)=u11u22unn,这里U是顺序消元过程结束时的上三角矩阵.A的顺序主子式。也是同样情况,即有det(Ak)=det(Uk)=u11u22ukk.。顺便指出,消第k个元素时，左上角的元素(称之为主元素)非零时才能进行.所有主元素非零等价于det(Ak)0,k=1,2,n-1.求A的逆矩阵相当于解n个方程组,它们的系数矩阵是A,n个右端项是n个单位向量.用增广矩阵表示即(AI)，其中I是单位矩阵.消元过程可对所有右端项同时进行,消元过程结束再分别回代.也可巧妙安排就地求逆. 主元素法如果akk=0顺序消元无法进行,如果akk很小，可以进行。但将引出很大误差.例2. 用顺序消去法解方

6、程组解 用精确运算:解得(10000/9999,9998/9999)(1.100,0.900)若在十进三位尾数舍入的浮点计算机系统中运算,第二行将是(0-10000-10000)从而得到解,与实解相去甚远.究其原因,小主元作分母扩大误差所致.如果两个方程(两行)交换次序再消元:得到解,与实解很近.下面引进的列主元素法在消元前，先选该列中绝对值最大的做主元(交换两行,每行包括右端项!):fork=1:n-1找p:p行k行ik=pifakk0fori=k+1:nmik=aik/akki行=i行-k行mikendelsestopendendik=p记录每次选主元(两行交换)的指标.跟前面一样,算法还

7、可细化,把矩阵和右端分开算(这时就要用指标ik)。列主元素法乘数mik绝对值不大于1,不会增加误差。列主元素法用来求行列式时，要注意两行交换行列式变号。还有一种全主元素法,它是在整个右下(n-k)(n-k)矩阵找绝对值最大的做主元(交换行及列).这对误差控制有利,但搜索太费时.通常列主元素法误差控制就已可以了. 以下是列主元素法的流程图: 流程图中，分别为线性方程组的系数矩阵和常熟向量；k 是循环次数；d 是主元素； 二 实验部分本章实验内容：实验题目：Gauss消元法,追赶法,范数。实验内容：编制用Gauss消元法求解线性方程组Ax=f的程序。 编制用追赶法求解线性方程组Ax=f的程序。 编

8、制向量和矩阵的范数程序。实验目的：了解Gauss消元法原理及实现条件,熟练掌握Gauss消元法解方程组的算法,并能计算行列式的值。 掌握追赶法，能利用追赶法求解线性方程组。理解向量和矩阵范数定义,性质并掌握其计算方法.编程要求：利用Gauss消元法,追赶法解线性方程组。分析误差。计算算法:Gauss消元法:1. 消元过程设,对计算回代过程追赶法：1.分解Ax=f: ( )2.解Lg=f,求g: ()3解Ux=g,求x: （）范数：常用向量范数有：（令x=( x1,x2,xn)）1-范数： x1=x1+x2+xn2-范数： x2=(x12+x22+xn2)1/2-范数： x=max(x1,x2,

9、xn)常用的三种向量范数导出的矩阵范数是：1-范数:A1= maxAx1/x1=1=2-范数:A2=maxAx2/x2=1=,1是ATA的最大特征值.-范数:A=maxAx/x=1=实验例题：用Gauss消元法解方程组 实验例题: 用追赶法解三对角方程组Ax=b,其中 实验例题：设 ， 计算A的行列范数.程序:Gauss消元法function x=Gauss(A,b) %A是线性方程组的系数矩阵,b为自由项.n=length(A)for k=1:n-1 m(k+1:n,k)=A(k+1:n,k)/A(k,k); A(k+1:n,k+1:n)=A(k+1:n,k+1:n)-m(k+1:n,k)*

10、A(k,k+1:n); b(k+1:n)=b(k+1:n)-m(k+1:n,k)*b(k);endx=zeros(n,1);x(n)=b(n)/A(n,n);for k=n-1:-1:1 x(k)=(b(k)-A(k,k+1:n)*x(k+1:n)/A(k,k);endx=x;disp(sprintf(k x(k);for i=0:n disp(sprintf(%d %f ,i,x(i+1);end数值结果：x=Gauss(A,b)n =3k x(k)0 1. 1 0. 2 2.程序:追赶法function x,y,beta=zhuiganfa(a,b,c,f)%a,b,c是三对角阵的对角线上

11、的元素,f是自由项.n=length(b);beta(1)=c(1)/b(1);for i=2:n beta(i)=c(i)/(b(i)-a(i)*beta(i-1);endy(1)=f(1)/b(1);for i=2:n y(i)=(f(i)-a(i)*y(i-1)/(b(i)-a(i)*beta(i-1);endx(n)=y(n);for i=n-1:-1:1 x(i)=y(i)-beta(i)*x(i+1);enddisp(sprintf(k x(k) y(k) beta(k);for i=0:n disp(sprintf(%d %f ,i,x(i+1),y(i+1),beta(i+1)

12、;end数值结果:a=0 -1 -1 -1 -1;b=2 2 2 2 2;c=-1 -1 -1 -1 0;f=1 0 0 0 0;x,y,beta=zhuiganfa(a,b,c,f)k x(k) y(k) beta(k)0 0. 5.e-001 -0. 1 0. 3.e-001 -0. 2 0. 2.e-001 -0. 3 0. 2.e-001 -0. 4 0. 1.e-001 0.程序： 1.列范数:function fan=lie(A)%A为已知矩阵n=length(A)for j=1:n x(j)=0 for i=1:n x(j)=x(j)+abs(A(i,j); endendfan=

13、max(x)disp(sprintf(n x(n);for i=0:ndisp(sprintf( %d %f,i,x(i+1);end数值结果: fan=lie(A) fan =0.8000n x(n)0 0.1 0.2.行范数:function fan=hang(A)%A为已知矩阵n=length(A)for i=1:n x(i)=0 for j=1:n x(i)=x(i)+abs(A(i,j); endendfan=max(x)disp(sprintf(n x(n);for i=0:n disp(sprintf( %d %f,i,x(i+1);end数值结果: fan=hang(A) fa

14、n =1.1000 n x(n)0 1.1 0.总结:从代数上看,直接分解法和Gauss消去法本质上一样,但如果我们采用”双精度累加”计算,那么直接三角分解法的精度要比Gauss消去法为高. 求线性方程组的直接法,其算式繁杂,给人以枯燥沉闷的感觉.为了改善教学效果,本章着重介绍了三对角方程组的追赶法.三对角方程组以及其拓广形式的带状方程组有着广泛的实际应用.追赶法是解三对角线方程组(对角元占优势)的有效方法,它具有计算量少,方法简单,算法稳定等优点,具有鲜明的对称美.复习思考题 1. 用消去法解线性方程组为什么最好选主元？怎样的方程组可以不用选主元？ 2. 用高斯约当消去法求矩阵的逆，其理论根据是什么？ 3. 求矩阵A的LU分解的紧凑格式有何规律？写出LU分解法解Ax = b的算法。 4. 乔累斯基分解法适用于哪类线性方程组？有何优点？ 5. 追赶法有何优点？哪类方程组可用追赶法求解？ 6. 向量范数与矩阵范数是如何定义的？各有何性质？常用范数有哪些？7. 什么叫病态方程组？什么叫矩阵的条件数？条件数刻画了矩阵的什么性质？能否用选主元的方法求得病态方程组的高精度的解？专心-专注-专业