第二高斯消元法及其计算机实现-课件.ppt

1、第二节第二节 高斯消元法及其计算机实现高斯消元法及其计算机实现第五章第五章 解线性代数方程组的直接方法解线性代数方程组的直接方法n第一节第一节 求解线性代数方程组的基本定理求解线性代数方程组的基本定理线性代数方程组的一般形式线性代数方程组的一般形式(1)mnAxbAR 用用矩矩阵阵形形式式表表示示为为其其增增广广矩矩阵阵记记为为 11112211211222221122 nnnnmmmnnma xa xa xba xa xaxbaxaxaxb 11121121222212,nnmmmnmaaabaaabAA baaab 第一节第一节 求解线性代数方程组的基本定理求解线性代数方程组的基本定理Ax

2、bAA 线线性性方方程程组组 有有解解的的充充分分必必定定理理1 1（线线性性代代数数方方程程组组要要条条件件是是：秩秩（）=秩秩有有解解判判定定理理（别别）(1)()(),AxbAArnAxb 线线性性方方程程组组有有解解（即即相相容容）时时，秩秩定定理理2 2秩秩则则方方程程组组存存在在唯唯一一解解。(2)()(),r Ar ArnAxb 方方程程组组有有无无穷穷多多解解。通通解解原原方方程程组组一一个个特特解解对对应应齐齐次次方方程程组组的的基基础础解解系系的的线线性性组组合合。222,|min|mnAxbxxxxAxb 常常见见是是，称称为为欠欠定定方方程程组组（方方程程数数少少于于未

3、未知知数数）此此时时，从从的的无无穷穷多多个个解解中中需需求求出出范范数数最最小小的的解解。即即求求使使，满满足足。22()()()|minr Ar AAxbmnbAR AxxbAx 方方程程组组无无解解（即即不不相相容容）。常常见见是是，称称为为超超定定方方程程组组（又又称称矛矛盾盾方方程程组组）此此时时，向向量量 不不在在 的的列列空空间间之之中中，原原方方程程组组无无解解，但但可可求求出出最最小小二二乘乘意意义义下下的的解解。即即求求 使使MATLAB实现实现:x=Ab11112211211222221122 nnnnnnnnnnna xa xa xba xa xaxba xaxaxb

4、本本章章介介绍绍求求解解 阶阶线线性性方方程程组组的的数数值值方方法法 数值求解方法有以下三条途径（三种框架）数值求解方法有以下三条途径（三种框架）直接法：利用直接法：利用Gauss消元或矩阵分解，通过有限次运算消元或矩阵分解，通过有限次运算 可求出精确解。可求出精确解。迭代法：构造迭代格式，产生迭代序列，通过无限迭代法：构造迭代格式，产生迭代序列，通过无限 次迭代过程求解。有限次截断得近似解。次迭代过程求解。有限次截断得近似解。极小化方法：构造二次模函数，用迭代过程求二次极小化方法：构造二次模函数，用迭代过程求二次 模函数的极小化问题，即变分法（经模函数的极小化问题，即变分法（经n 次运算，

5、理论上得精确解）要求次运算，理论上得精确解）要求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 三角形方程组包括上三角形方

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

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

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

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

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

11、2111313111212111)1(aamaamanbAA增增广广矩矩阵阵：解：解：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的系数矩阵与右端项合并

12、为的系数矩阵与右端项合并为 11121121222212,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.nnnnnnnaaabaa

13、bL AAbaab (2)(1)(1)1 1(2)(1)(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,11

14、1,100000nnnnnn nnmALmaaaabaaabL 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 Aaabmaaaaaa

15、aaaa -(1)1(2)2(3)(3)3)(3)(3),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,.,)kkikkkkikkkkaamaiknGauss

16、L 设设取取，构构造造变变换换阵阵,111111Tkkkkn 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.

17、是是高高斯斯消消元元的的前前提提。)1,2,1(,0)(nkakkk(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,3kkikikkkkkkijijikkjkkkiiikkkniknmaa

18、aam ajknbbm b （）（），（）步步消消元元计计算算后后，第第的的二二维维数数组组存存放放一一个个用用用用动动态态存存储储方方式式。最最初初在在计计算算机机中中计计算算时时，采采存存储储方方式式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 消元过程全部完成后，原来的二维数组中存放的消元过程全部完

19、成后，原来的二维数组中存放的元素实际上是一个新的矩阵，记为元素实际上是一个新的矩阵，记为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)中找出第中找出第一个出现的绝对值

20、最大者一个出现的绝对值最大者,例如例如 ，再把第再把第i 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)中中,找出绝对值找出绝对值最大者最大者,例如

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

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

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

24、det,),(8detdet7)1,2,2,1(/)(/,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

25、（1-0.0001)x2=1x1+x2=2消元，得消元，得解得：解得：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

26、.996 5.5625 4 7.4178 3.996 5.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,然后进行消元计算可得然后进行消元计算可得