西安交大计算方法第二章

第2章解线性代数方程组的直接法第2章解线性代数方程组的直接法11112211211222221122(21)nnnnnnnnnnxxxbxxxbxxxb线性代数方程组可以写为矩阵形式Axb其中1112111212222212,,.nnnnnnnnxbxbAxbxb求解方法方法1计算量为矩阵求逆矩阵求逆的方法:初等行变换法、伴随矩阵法、高斯约当法bAxbAAxA11bAx1第2章解线性代数方程组的直接法求解方法方法2Crammer法则iA是以右端常量向量b替代A的第i列所得矩阵的行列式11111111212122121111112121222121,2,...,iiniinnninninninnnnnnaabaaaabaaaabaaxinaaaaaaaaaA其中:是方程组的系数矩阵的行列式niAAxii,...,2,1,第2章解线性代数方程组的直接法计算量为求矩阵的行列式1212(,)12(1)nnJiiiiiniA),,,(21niiiJ1212:(,){1,2,...,}{,,...,}nnJiiiniii其中是变换到所需的置换次数,(-1)!nn因此计算一个行列式需要次浮点运算2(-1)!Nnn使用Cramer法则求解方程组需要次浮点运算求解方法方法2Crammer法则第2章解线性代数方程组的直接法1212230xxxx消去法的过程1.将n元方程组的n-1个方程通过“消元”，形成一个与原方程组等价的新方程组2.继续将n-1个方程通过“消元”形成与之等价的新方程组3.直到最后一个方程为一元一次方程为止4.从最后一个方程中解出最后一个未知量，然后回代得到其它的解122233322xxx21x从第二个方程解出11x代入第一个方程,得到第2章解线性代数方程组的直接法Gauss消去法基本思想:将求解n元方程组的问题通过降维,变为等价的n-1元方程组进行求解，逐次进行直至变为一个一元一次方程为止，然后求解，再逐步回代得到其余的解消去法的基本步骤：消去、回代第2章解线性代数方程组的直接法Gauss消去法消去过程对于以下的增广矩阵(0)(0)(0)(0)(0)11121311(0)(0)(0)(0)(0)21222322(0)(0)(0)(0)(0)(0)(0)31323333(0)(0)(0)(0)(0)123()nnnnnnnnnaaaabaaaabAbaaaabaaaab(0)11(0)11,2,3,...,,iiailina将矩阵的第行分别减去第一行的倍数得到(0)(0)(0)(0)(0)11121311(1)(1)(1)(1)222322(1)(1)(1)(1)(1)(1)323333(1)(1)(1)(1)230()00nnnnnnnnaaaabaaabAbaaabaaab(1)(0)(0)11(1)(0)(0)112,3,...,2,3,...,ijijijiiiaalabblbjnin其中第2章解线性代数方程组的直接法Gauss消去法2.1Gauss消去法2.1.1消去法依此类推，消去的第k步，得到矩阵(0)(0)(0)(0)(0)1111,111(1)(1)(1)(1),1()()(0)()()1,11,1()()(),1()kknkkkkkkkkknkkkkkkkknkkkknknnnaaaaaaaAbaaaa(1)(1)()(1)(1)()(1)(1),1,...,,1,2,...,kikikkkkkkkijijikkjkkkiiikkalaaalajknlikkn计算关系式第2章解线性代数方程组的直接法经过n-1步消去后，得到(0)(0)(0)(0)(0)11121311(1)(1)(1)(1)222322(1)(1)(2)(2)(2)3333(1)(1)()nnnnnnnnnnaaaabaaabAbaabab然后，经过回代，得到所有的解(1)(1)(1)(1)(1)11,1,2,...,1nnnnnnnkkkkkjjkjkkkbxaxbaxknna第2章解线性代数方程组的直接法Gauss消去法程序示例:系数矩阵A存放于数组A中，右端向量放在数组b中.[]11,2,...,-11.10;1.21,2,...,1.2.1/1.2.21,2,...,1.2.2.11kkikkkikijikkjijIForknIfathenstopForikknaaaforjkknaaaa消去输出错误信息.2.3iikkiaN-1次N-k次N-k次N-1次N-k次.[]2.1/2.2-1,-2,...,12.2.12.2.21,2,...,2.2.2.1-2.2.3/nnnnkkjjkkkIIaxforknnSForjkknSaxSSax回代第2章解线性代数方程组的直接法Gauss消去法时间复杂度分析1.消去算法运算量-1n分为步2.回代运算量-111,,...,,nnxxxn求需做次浮点运算求需做2次浮点运算求需次浮点运算因此所需浮点运算次数:321233nnNNNn因此,3()on即,运算量为111()(2)nkNnknk,-knk第步变换行:求倍数,1-nk再从个元素中减去k第行对应列的倍数,因此所需浮点运算次数:325326nnn2(1)12...2nnNn第2章解线性代数方程组的直接法Gauss消去法空间复杂度分析)(,)1(22nonA则空间复杂度为占用空间为系数矩阵)(,)2(nonb则空间复杂度为占用空间为常量)(,)3(nonx则空间复杂度为占用空间为变量用额外存储空间消去过程中认为没有使)4()(,2no度为消去法的总的空间复杂因此第2章解线性代数方程组的直接法Gauss消去法第1种情况下(1)若A非奇，则可以通过交换方程组中各方程的行序,可以继续执行消去过程(2)若A奇异，则不能继续执行消去过程23123123522140xxxxxxxx12323123215240xxxxxxxx交换第1行和第2行,0:)1(kkka，在消去过程中有当系数矩阵非奇时性质第2章解线性代数方程组的直接法列主元Gauss消去法第2种情况下121(10,5,10,10)22xFx-5102例:在浮点数系下,求解3真实解为按Gauss消去法为*0.2500018750.499998749x6214110.20000*101110.10000*100.20000*100.10000*100.20000*100.30000*100.20000*10l411660.10000*100.20000*100.10000*100.40000*100.20000*10000.00000*100.50000*10Tx第2章解线性代数方程组的直接法列主元Gauss消去法例使用高斯消去法解方程组演示Gauss消去法可以顺利执行的条件(1)0kkka若在Gauss消去过程中出现以下两种情况(1)(1)0kkka则Gauss消去过程中会出现问题(2)1,...,kkikaaikn(1)kkkak这里,将称为第步的主元第2章解线性代数方程组的直接法列主元Gauss消去法原因则jjbbijijikkjl()ijikkjlijikkjikllijikliiikbbl同理倍误差将会被放大在消去的过程中ikl,若有误差列主元Gauss消去法第2章解线性代数方程组的直接法在Gauss消去法中,第k步选取若A非奇则可以通过选主元的方式继续执行消去过程(1)max,1,...,kikaikn列主元Gauss消去法第2章解线性代数方程组的直接法kka作为,并且交换相应的行,然后继续进行Gauss消去法,这种方法称为列主元Gauss消去法kkkkkk1.1amax1.20;1.3j1,2,....[]11,2,...,-11.5i1,2,...,,1.3.11.4kikikkkjjIForknaIfathensForkktopForkknaan找到满足的下标输出错误信息消去1.5.1/1.5.21,2,...,1.5.2.11.5.3ikkkikijikkjijiikkiaaaforjkknaaaaa列主元消去法.[]2.1/2.2-1,-2,...,12.2.12.2.21,2,...,2.2.2.1-2.2.3/nnnnkkjjkkkIIaxforknnSForjkknSaxSSax回代列主元Gauss消去法第2章解线性代数方程组的直接法列主元消去法的特点：当系数矩阵的行列式不为0时，算法总可以执行完成算法稳定，在消去过程中计算误差能被有效控制；当矩阵A是对称正定或严格对角占优，则不选主元，Gauss消去法也是稳定的列主元Gauss消去法第2章解线性代数方程组的直接法2.2三角分解法(0)(0)(n-1)(n-1)GaussAbAb消去法的消去过程是将变换到矩阵(0)(0)(0)(0)1112131(0)(0)(0)(0)2122232(0)(0)(0)(0)(0)3132333(0)(0)(0)(0)123nnnnnnnnaaaaaaaaAaaaaaaaa(0)(0)(0)(0)1112131(1)(1)(1)22232(1)(1)(1)(1)32333(1)(1)(1)23000nnnnnnnaaaaaaaAaaaaaa-c,可以验证将第k行的倍加于第i行相当于左乘初等矩阵101E1kic第2章解线性代数方程组的直接法2.2三角分解法(1)(0)11312()nAEEEA可以验证21111001001nlEl其中仍为初等变换矩阵第一步消去等价于用一个初等下三角阵左乘方程组的两端第2章解线性代数方程组的直接法(0)1EA1,1111kkknkEll依此类推有(-1)(0)121-1,nnnnAEEEA因此,可以得到,经过步后有k由于E为初等变换矩阵111(1)121nnAEEEA因此,有(-1)nRA记1,kE因此存在111121nAEEER因此,有(1)()(),(1,2,...,;,1,...,)nijijRinjiin2.2三角分解法第2章解线性代数方程组的直接法11,1111kkknkEll可以证明,初等变换阵有性质111121L=nEEE因此,2131321231111nnnllllll2.2三角分解法第2章解线性代数方程组的直接法(2-8)ALR因此可知(2-8)LR,Doolittle式称为矩阵的分解也称为三角分解或分解即A可以表示成为一个单位下三角阵与一个上三角阵的乘积2.2三角分解法第2章解线性代数方程组的直接法21313212311=11n