第二高斯消元法及其计算机实现教学课件.ppt（35页）

1、第二高斯消元法及其计算机实现 数值求解方法有以下三条途径（三种框架）数值求解方法有以下三条途径（三种框架）直接法：利用直接法：利用Gauss消元或矩阵分解，通过有限次运算消元或矩阵分解，通过有限次运算 可求出精确解。可求出精确解。迭代法：构造迭代格式，产生迭代序列，通过无限迭代法：构造迭代格式，产生迭代序列，通过无限 次迭代过程求解。有限次截断得近似解。次迭代过程求解。有限次截断得近似解。极小化方法：构造二次模函数，用迭代过程求二次极小化方法：构造二次模函数，用迭代过程求二次 模函数的极小化问题，即变分法（经模函数的极小化问题，即变分法（经n 次运算，理论上得精确解）要求次运算，理论上得精确解

2、）要求A 对称正定对称正定(S.P.D)用增广矩阵表示为用增广矩阵表示为同解同解初等变换初等变换组组化为同解的上三角方程化为同解的上三角方程将原方程组将原方程组求解求解gUxbAxgUxbAxRAbAxnn 第二节第二节 高斯消元法及其计算机实现高斯消元法及其计算机实现 A b U g )1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaa )()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnnnnnnbabaabaaa 三角形方程组包括上三角形方程组和下三角三角形方程组包括上三角形方程组

3、和下三角形方程组，是最简单的线性方程组之一。上三角形方程组，是最简单的线性方程组之一。上三角方程组的一般形式是方程组的一般形式是：),.,2,1(0.111112222211212111niabxabxaxabxaxabxaxaxaiinnnnnnnnnnnnnnn 其其中中一、三角形方程组的解法一、三角形方程组的解法1242343444573131313131xxxxxxxxx 用用回回代代法法求求解解线线性性方方程程组组例例43424314212341(1313)/30(75)(750)244121,)(1,2,0:,1)TTxxxxxxxxxxxxx 所所以以，解解为为（解解1,1/)(

4、/1 niaxabxabxnikiikikiinnnn 为求解上三角方程组，从最后一个方程入手，先为求解上三角方程组，从最后一个方程入手，先解出解出 x xn n=b=bn n/a/annnn,然后按方程由后向前的顺序，从方然后按方程由后向前的顺序，从方程中依次解出程中依次解出x xn-1n-1,x,xn-2n-2,x,x1 1。这样就完成了上三角方这样就完成了上三角方程组的求解过程。这个过程被称为回代过程其计算步程组的求解过程。这个过程被称为回代过程其计算步骤如下：骤如下：11212322232429xxxxxx 用用回回代代法法求求解解线线性性例例、方方程程组组1231232/21(21)

5、/11(93121)/41,)(1,1,):1xxxxxx 所所以以，解解为为（解解21111)(1)22ninin nn 求求解解一一个个三三角角形形方方程程组组需需 次次除除法法与与（次次乘乘法法。12111111,/()/(2,3,)niiiikkiikxxxxbaxba xain 下下三三角角形形方方程程组组可可以以参参照照上上三三角角形形方方程程组组的的解解法法来来求求解解，下下三三角角形形方方程程组组的的求求解解顺顺序序是是从从第第一一个个方方程程开开始始，按按从从上上到到下下的的顺顺序序，依依次次解解出出：其其计计算算公公式式为为：如如上上解解三三角角形形方方程程组组的的方方法法

6、称称为为回回代代法法.1111211222211220,1,2,nnnnnniia xbaxaxbaxaxaxbain 下下三三角角方方程程组组的的一一般般形形式式为为：其其中中 高斯消元法是一个古老的直接法高斯消元法是一个古老的直接法,由它改进得到由它改进得到的选主元法的选主元法,是目前计算机上常用于求低阶稠密矩阵是目前计算机上常用于求低阶稠密矩阵方程组的有效方法方程组的有效方法,其特点就是通过消元将其特点就是通过消元将一般线性一般线性方程组方程组的求解问题转化为的求解问题转化为三角方程组三角方程组的求解问题。的求解问题。高斯消元法的求解过程高斯消元法的求解过程,可大致分为两个阶段可大致分为

7、两个阶段:首先首先,把原方程组化为上三角形方程组把原方程组化为上三角形方程组,称之为称之为“消消元元”过程过程;然后然后,用逆次序逐一求出上三角方程组用逆次序逐一求出上三角方程组(原原方程组的等价方程组方程组的等价方程组)的解的解,称之为称之为“回代回代”过程过程.高斯高斯“消消元元”过程过程可通过矩阵运算来实现。具可通过矩阵运算来实现。具体过程如下：体过程如下：二、高斯消元法二、高斯消元法12312312323623493263Gaussxxxxxxxxx 用用消消元元法法求求解解方方程程例例组组11/1/21/2/01,362319432632111313111212111)1(aamaa

8、manbAA增增广广矩矩阵阵：解：解：11121,:11L AxL b 1 1L L=,完完成成第第一一步步消消元元 得得(2)(2)(2)223232222212110,/1/(1)111,11amaaLL L AxL L b =,完完成成第第二二步步消消元元 得得 3332632332321xxxxxx3231231233/31(32)(321)16236213111,1,1xxxxxxxxx 回回代代求求得得故故所所求求解解为为 011032106321)2(A 330032106321)3(A将方程组将方程组Ax=b的系数矩阵与右端项合并为的系数矩阵与右端项合并为 1112112122

9、2212,nnnnnnnaaabaaabA bAaaab (1)(1)(1)1111(1)(1)(1)(1)(1)12(1)(1)(1)1.,.,.nnnnnnaabAAbaab记记 (1)(1)1(1)11111,0,.,0.TALLa 对对的的第第一一列列构构造造使使1(1)11111110,2,.,iiaamina （）（）：设设取取第第一一步步2111111nmLm (1)(1)(1)(1)111211(2)(2)(2)(1)(2)(2)(2)(2)(2)2222112(2)(2)(2)2.0.,.,0.nnnnnnnaaabaabL AAbaab (2)(1)(1)1 1(2)(1)

10、(1)1 12,2,2,ijijijiiiaam ain jnbbm bin (1)(1)1(1)(1)11AxbLL AxL b 对对方方程程组组从从左左边边乘乘以以(1)(1)(1)1111(1)211(1)(1)(1)111.1.1nnnnnnaabmL Aaabm (2)(2)2222(2)2203,.,iiaamina ：设设，第第二二步步取取(2)(2)32222(1)(1)(1)(1)(1)1112131,1(2)(2)(2)(2)22232,2(2)(1)(3)(3)(3)(3)221333,3(3)(3)(3)3,111,100000nnnnnn nnmALmaaaabaaa

11、bL AL L AaaAbaab -对的第二列构造对的第二列构造-使使(2)22(2)22,iiama(1)(1)2121L L AxL L b(3)(2)(2)22(3)(2)(2)22,3,3,4,.,ijijijiiiaam ai jnbbm bin (1)(1)(1)(1)111211(2)(2)(2)(2)2222322(2)(2)(2)22(1)(1)(1)(1)1112131,(2)(2)(2)22232,(3)(3)333,(331.10.10.100000nnnnnnnnnnnaaabaabmL Aaabmaaaaaaaaaa -(1)1(2)2(3)(3)3)(3)(3),

12、n nnbbAbab 进行到第进行到第k步消元时步消元时()(1)()kkkAAAk 下下一一步步消消元元，从从，将将的的第第 列列的的对对角角元元以以下下的的元元素素化化为为零零。(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333()()()()1()()()1,1,11()()()(),1.nnnkkkkkkkkkkkkkkkkkkkkknkn knnnaaaabaaabaabAaabaabaaab ()()()0,(1,.,)kkikkkkikkkkaamaiknGaussL 设设取取，构构造造变变换换阵阵,111111Tkkkk

13、n kIl emm (1)()kkkAL A 消消元元计计算算递递推推公公式式：()(1,2,1)kkkakn 称称为为主主元元素素.()()(1)()()(1)()()1,1/21,3kkikikkkkkkijijikkjkkkiiikkiknmaaaam ajknbbm b （）（），（）(1)(1)(1)(1)11112211(2)(2)(2)22222()()nnnnnnnnnnaxaxaxbaxaxbaxb 即即 用回代过程求解上三角方程组，即可得解向量用回代过程求解上三角方程组，即可得解向量(x1*,x2*,xn*)T T.是是高高斯斯消消元元的的前前提提。)1,2,1(,0)(n

14、kakkk(1)(1)121121nnLL L AxLL L b (1)(1)(1)(1)111211(2)(2)(2)()2222()()000nnnnnnnnaaabaabAab 最最后后得得求解的全过程包括两个步骤：消元和回代求解的全过程包括两个步骤：消元和回代1.1.顺序消元顺序消元2.回代求解回代求解()()()()()1/()/1,2,1nnnnnnnkkkkkkjjkkj kxbaxbaxaknn ()()(1)()()(1)()()1,11,1/21,3kkikikkkkkkijijikkjkkkiiikkkniknmaaaam ajknbbm b （）（），（）步步消消元元计

15、计算算后后，第第的的二二维维数数组组存存放放一一个个用用用用动动态态存存储储方方式式。最最初初在在计计算算机机中中计计算算时时，采采存存储储方方式式kAnn),1;,1(),1()1()()(nkjnkiaankimakijkijikkik )()(1,)()(1,1)(,1)(1)()3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)(.knnkknknkkkkkkkkkkkkknnnkaaaaaaaaaaaaaaaaAikm)1(kijaUIL 消元过程全部完成后，原来的二维数组中存放的消元过程全部完成后，原来的二维数组中存放的元素实际上是一个新的矩阵，记

16、为元素实际上是一个新的矩阵，记为FAFAA用动态形式表示为用动态形式表示为)(1,321)3(3)3(1,3)3(333231)2(2)2(1,2)2(23)2(2221)1(1)1(1,1)1(13)1(12)1(11nnnnnnnnnnnnnnFammmmaaammaaaamaaaaaA 选主元基本思想选主元基本思想 用高斯消元法求解线性方程组时用高斯消元法求解线性方程组时,为避免小的主元为避免小的主元.在进在进行第行第k k步消元前步消元前,应该在第应该在第k k列元素列元素 (i=k,ni=k,n)中找出第中找出第一个出现的绝对值最大者一个出现的绝对值最大者,例如例如 ，再把第再把第i

17、 ik k个方程与第个方程与第k k个方程组进行交换个方程组进行交换,使使 成为主元成为主元.我们我们称这个过程为选主元称这个过程为选主元.由于只在第由于只在第k k列元素中选主元列元素中选主元,通常通常也称为也称为按列选主元按列选主元.)(kika()()maxkkki kikkinaa )(kija 如果在第如果在第k k步消元前步消元前,在第在第k k个方程到第个方程到第n n个方程所有个方程所有的的x xk k到到x xn n的系数的系数 (i=k,n;j=k,ni=k,n;j=k,n)中中,找出绝对值找出绝对值最大者最大者,例如例如()kki ka三、选主元三、选主元高斯消元法高斯消

18、元法再交换第再交换第k k,ikik两个方程和第两个方程和第k k,jkjk列列,使使 成为主元成为主元.称这个过程为称这个过程为完全选主元完全选主元.不论是哪种方式选出主元不论是哪种方式选出主元,而后再按上面介绍的计而后再按上面介绍的计 算步算步骤进行消元的计算骤进行消元的计算,一般都称为选主元的高斯消元法一般都称为选主元的高斯消元法.在在实际计算中实际计算中,常用按列选主元的高斯消元法常用按列选主元的高斯消元法.()k kki ja()(),maxk kkki jijk i j naa()()()()()()()|max|,1,(1),(,2kkkkkkkkkkki kikk i nkkk

19、kkkji jkjkji ji jkikkiikikinaaAAbikTikaajk knTaaaaTbbTb bbbT 对对每每一一步步 第第 步步 消消元元，分分两两步步确确定定使使对对增增广广矩矩阵阵使使列列主主元元高高斯斯消消元元法法具具体体做做法法是是：选选列列主主元元换换行行在在计计算算机机上上，用用一一个个工工作作单单元元来来完完成成，对对，包包括括消消元元计计算算算法算法 列主元高斯消元法解线性方程组列主元高斯消元法解线性方程组 Ax=bAx=b停停机机。信信息息输输出出失失败败则则认认为为如如果果使使确确定定、选选列列主主元元步步。循循环环执执行行到到第第对对、置置,0det

20、 ,0,max 2 51,2,1 1det 1 kikiiknikkikkkkaaaaink detdet,),1,(,4 ,3 kkikjikjkbbnkkjaaki否否则则交交换换行行步步转转出出执执行行第第、如如果果具体执行行交换要通过工作单元具体执行行交换要通过工作单元 T。TbbbbTTaaaaTkkkkiikkjijikjkj ;。、输输出出解解向向量量、否否则则停停机机。输输出出失失败败信信息息则则认认为为如如果果、回回代代求求解解、FTnnniinijjijiinnnnnnnnkkAAbbbxanniababbabbaaadet,),(8detdet7)1,2,2,1(/)(/

21、,0,6detdet 5211 (3),1(2)/(1),2,14kikiikjikijijkkikikikbabbnkjaaaaaamankki 、消消元元计计算算假设求解是在四假设求解是在四位浮点十进制数位浮点十进制数的计算机上进行的计算机上进行0.0001x1+x2=1 x1+x2=2将两个方程对调，得将两个方程对调，得 x1+x2=2 0.0001x1+x2=1在四位浮点十进制数的计算机上在四位浮点十进制数的计算机上,上式为上式为 x1+x2=2 即即 x1+x2=2 (0.1000101-0.00001 101x2=1 x2=1（1-0.0001)x2=1x1+x2=2消元，得消元，

22、得解得：解得：x1=1，x2=1现在我们再用列主元法解例现在我们再用列主元法解例4例例5 5 用列主元消去法解方程组用列主元消去法解方程组解解 第一次消元对第一次消元对 因列主元素为因列主元素为a a3131(1)(1),故先作行交换故先作行交换E E1 1 E E3 3,然后进行然后进行消元计算可得消元计算可得-0.002x1+2x2+2x3 =0.4 x1+0.78125x2 =1.38163.996x1+5.5625x2+4x3=7.4178 -0.002 2 2 0.4 A(1)|b(1)=1 0.78125 0 1.3816 3.996 5.5625 4 7.4178 3.996 5

23、.5625 4 7.4178 A(2)|b(2)=0 -0.61077 -1.0010 -0.47471 0 2.0029 2.0020 0.40371 由此回代由此回代,得得x x=(1.9272,-0.69841,0.90038)=(1.9272,-0.69841,0.90038)T T与精确解与精确解 x x=(1.9273,-0.69850,0.90042)=(1.9273,-0.69850,0.90042)T T相相比较是比较准确的比较是比较准确的.3.996 5.5625 4 7.4178A(3)|b(3)=0 2.0029 2.0020 0.40371 0 0 -0.39050 -0.35160 第二次消元对第二次消元对 A A(2)(2)|b b(2)(2),因列主元素为因列主元素为a a3232(2)(2),故先故先作行交换作行交换E E2 2 E E3 3,然后进行消元计算可得然后进行消元计算可得