高斯消元法与选主元.ppt
《高斯消元法与选主元.ppt》由会员分享,可在线阅读,更多相关《高斯消元法与选主元.ppt(36页珍藏版)》请在三一办公上搜索。
1、,关键词:高斯消去法,主元消去法,高斯消元法与选主元 高斯消元法是一种古老的直接法,由它改进得到的选主元消元法,是目前计算机上常用于求解低阶稠密矩阵方程组的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题,一 问题的描述,(一)引言 为便于以下讨论,把涉及到的有关名词及问题的引出暂介绍如下:如果未知量的个数为 n,而且关于这些未知量x1,x2,xn 的幂次都是一次的(线性的),那末,n 个方程 a11x1+a12x2+a1nxn=b1(1)an1x1+an2x2+annxn=bn 构成一个含 n 个未知量的线性方程组,称为 n 阶线性方程组 其中,系数a11,a
2、1n,a21,a2n,an1,ann 是给定的常数;b1,bn 也是给定的常数,通常称为常数项,或称为方程组的右端.方程组(1)也常用矩阵的形式表示,写为 Ax=b,其中,A是由系数按次序排列构成的一个n阶矩阵,称为方程组的系数矩阵,x和b都是n维向量,称为方程组的解向量和右端向量,即 使方程组(1)中每一个方程都成立的一组数x1*,x2*,xn*称 为式(1)的解,把它记为向量的形式,称为解向量.,我们总是希望方程组有解,且有唯一解.由线性代数的克莱姆(cramer)规则可知,如果方程组(1)的系数矩阵A的行列式(一般记为D=|A|)不等于零,那末,这个方程组有唯一解,而且它们可以表示为 x
3、i=Di/D(i=1,2,n)这里,Di是指D中第i列元素用右端b1,b2,bn代替构成的行列式.如果方程组(1)有唯一解,我们按上面的等式求解,就必须计算n+1个n阶行列式.由行列式的定义,n阶行列式包含有n!项,每一项含有n个因子,计算一个n阶行列式就需要做(n-1)n!次乘法.而我们一共要计算n+1个n阶行列式,共需做(n2-1)n!次乘法.此外,还要做n次除法才能算出xi(i=1,2,n).也就是说,用这个办法求解就要做 N=(n2-1)n!+n次乘除法运算,这个计算量是大得惊人的.例如,当n=10(即求解一个含10个未知量的方程组),乘除法的运算次数共为32659210次;,当n=4
4、0,乘除法运算次数可达3.181049次.对于上百个未知量的方程组,次数运算量就更大了.因此克莱姆规则在理论上尽管是完善的,但在实际计算中却没有什么实用价值.本文我们将重点讨论求解线性方程组的一种有效的数值方法.(二)求解线性方程组的消元法 消(元)去法是求解线性方程组 Ax=b(3)和满秩矩阵的逆阵A-1的一种直接方法.尽管它比较古老,但它具有演算步骤,推算公式都系统化的特点(对其中选主元消去法,还可以证明是稳定的).因此,它至今仍然是求解方程组的一种有效的方法.消去法可以引出几种计算方法,下面按三角形方程组和一般线性方程组的顺序来讨论.,1.三角形方程组的解法 三角形方程组包括上三角形方程
5、组和下三角形方程组,它是最简单的线性方程组之一,实际上消元法就是通过简化一般线性方程组为三角形方程组后再求解的。上三角方程组的一般形式是:,2.Gauss消元法,(一)高斯消去法的求解过程,可大致分为两个阶段:首先,把原方程组化为上三角形方程组,称之为“消去(消元)”过程;然后,用逆次序逐一求出三角方程组(原方程组的等价方程组)的解,并称之为“回代”过程.,下面分别写出“消去(消元)”和“回代”两个过程的计算步骤.消去(消元)过程:第一步:设a110,取 做(消去第i个方程组的x1)mi1第一个方程+第i个方程 i=2,3,n则第i个方程变为,因为可得第一步消元后的方程组为,i,j=2,3,n
6、,i,j=2,3,n,第二步:设,取 做(消去第i个方程组的x2,i=3,4,n)mi2第二个方程+第i个方程 i=3,4,n类似可得第二步消元后的方程组为,第k步:设,取 做(消去第i个方程组的xk,i=k+1,k+2,n)mik第k个方程+第i个方程 i=k+1,k+2,n类似可得第k步消元后的方程组为,继续下去到第n-1步消元,可将线性方程组化为如下上三角方程组:,3.选主元,例3:考虑如下线性方程组的Gauss消元法 求解性,2x2=1 2x1+3x2=2解:因为a11=0,故此题不能用Gauss消元法求解,但交换方程组的顺序后,即 2x1+3x2=2 2x2=1就可用Gauss消元法
7、求解了.,例题4:讨论下面方程组的解法,0.0001x1+x2=1 x1+x2=2,假设求解是在四位浮点十进制数的计算机上进行,0.100010-3 x1+0.1000 101 x2=0.1000 1010.1000 101 x1+0.1000 101 x2=0.2000 101,解:本题的计算机机内形式为,因为a11=0.00010,故可用Gauss消元法求解,进行第一次消元时有a22(1)=0.1000 101-104 0.1000 101(m21=a21/a11=1/0.0001=104)=0.00001 105-0.1000 105(对阶计算)=0.0000-0.1000 105=-0
8、.1000 105,得三角方程组 0.100010-3 x1+0.1000 101 x2=0.1000 101-0.1000 105 x2=-0.1000 105,回代解得x2=1,x1=0 严重失真!(因为本题的准确解为x1=10000/9999,x2=9998/9999,列主元基本思想及程序框图 用高斯消去法求解线性方程组时,应避免小的主元.在实际计算中,进行第k步消去前,应该在第k列元素aik(i=k,n)中找出绝大值最大者,例如 a=max a 再把第p个方程与第k个方程组进行交换,使apk(k-1)成为主元.我们称这个过程为选主元.由于只在第k列元素中选主元,通常也称为按列选主元(或



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高斯消元法 选主元

链接地址:https://www.31ppt.com/p-6403868.html