第一节-高斯消去法

第六章线性方程组的数值解法主要内容一、线性方程组的直接解法二、线性方程组的迭代法1、高斯消去法2、高斯消去法的变形1、雅克比迭代法2、高斯-塞德尔迭代法第一节高斯消元法思想通过初等变换逐步消去未知元，将原方程组化为同解的三角方程组。一、三角方程组及其解法1111221122222nnnnnnnnaxaxaxbaxaxbaxb称形如的方程组为上三角方程组。111121122221122...nnnnnnaxbaxaxbaxaxaxb若系数行列式不为零，即，则方程组的解0iia/,nnnnxba1121()/,(,,...,)niiijjiijixbaxainn上述求解过程成为回代过程。类似方法可用于求解如下下三角方程组设求解方程组，其中Axb(1)第一步消元。若，记1110()a11111112112222222222200()()()()()()()()()()........................nnnnnnaaabaabaab二、高斯消去法11111112()()()()[],[,,...,]ijnnnAAabbbbb11111123()(),,,...,iialina将第一行乘以，加到第行上去，得1ili22[]Ab211112111123()()()()()()(,,,,)ijijijiiiaalaijnbblb其中于是得到如下与原方程组等价的方程组22Axb(2)第二步消元。若，对增广矩阵进行类似2220()a22[]Ab行初等变换得下述方程组11111112112222222333200()()()()()()()()()()........................nnnnnnaaabaabaab33[]Ab其中232222322222222234()(()()()()))()(/,(,,,,)ijijijiiiiiaalaijnblaablb于是得到如下与原方程组等价的方程组33Axb(3)第k步消元。设第k-1次消元已经完成，若增广矩阵111111113121122222222230()()()()()()()()()()()()()()()...............nnkkkkkkknkkknknnnabaaaabaaabaaba[]kkAb若，对做类似的初等变换的等价0()kkka[]kkAb方程组,其中11kkAxb1111111131112111111111110()()()()()()()()()()(),,()()(),........................nkkkknkkkkkkkkknkkkknknnnabaaaabaaababa11[]kkAb其中111()()()(()()())()/(,,),,kkkijijikkikkjkkkiiikkkikkkaalaijknblaablb1111111121122222222()()()()()()()()().........nnnnnnnnxaaabxaabxab(4)当时，经过n-1次消元得到0121()(,,...,)kkkakn与原方程等价的上三角方程组：1221(,,,,)inn(5)回代求解1()()()()(),()nnnnnnniiiiiijjiijixbaxbaxa等价方程组()()nnAxbijijikkjaaaa;ikikkkaaa121,,,knfor11,,jknfor12,,,ikknfor高斯消去法的消元过程回代过程11,,,;nnnnnnaaa1111,,,,,()ninijjnjiiniiaaaaa11,,in例5：用基本Gauss消元法求解下列方程组123123123223347712457xxxxxxxxx解：增广矩阵223347712457()Ab223303150684223347712457()Ab223303150684223303150066121121112()()ala131131111()()ala232232222()()ala321122,,xxx基本Gauss消元法的工作量消元过程：11111()()()nnkknknknk回代过程：12()nn325326nnn332333nnnn加减法的次数32353263nnnn乘除法的次数3()On510.Th（基本Gauss消元法的实现条件）全不为零的充要条件是12()(,,,())iiiaikkn的顺序主子式都不等于零，即A111212122212012,,,,()iiiiiiiaaaaaaiknaaa证明：归纳法证明(略)小主元可能导致计算失败例6：在8位制计算机上解方程组912121012xxxx要求用高斯消去法计算。921211110/laa9992221110001101010....al8个92212110bl9991011010102110,xx解：121xx二、选主元素的高斯消元法思想每次消元之前，在剩余元素中选择绝对值最大的非零元素作为主元，然后经过换行换到主元位置列主元消去法Stepk：第k步首先选择主元121,,,kn寻求满足ki1()(),,max,,,,kkkikikkinaaikkn然后交换矩阵的第行和行，再进行消元过程()kAkki121()()()(),,;;,,,,kkkkkkkjkjijijtaaaatjn算法:Gauss列主元消去算法求方程组Ax=b的解.输入:增广矩阵An(n+1)=（A|b）.输出:近似解xk=ak,n+1(k=1,2,…,n)或失败信息.消元过程fork=1,2,…,n-1doStep1-Step4Step1寻找行号ik,使得Step2如果，则交换第k行和ik行；否则转Step71,,max,,,,kikikkinaaikkn0,kika算法:Gauss列主元消去算法（续）Step3fori=k+1,…,n计算Step4forj=k+1,…,n+1计算回代过程Step5Step6fori=n-1,…,1计算Step7Output(系数矩阵奇异);/*不成功*/STOP.ikikkkalaijijikkjaala1,,nnnnnaxa11,,,()/niinijjiijixaaxa例7：用Gauss列主元消去法求解下列方程组123123123223347712457xxxxxxxxx解：首先写出增广矩阵223347712457()Ab47712233245712iStep112rr4771123321457221211112ala31311112ala消元4771351122221517131222223iStep223rr4771151713122223511222232312215ala15消元4771151713122226611255547715171222611255122