计算方法第三讲

《计算方法第三讲》由会员分享，可在线阅读，更多相关《计算方法第三讲（30页珍藏版）》请在文档大全上搜索。

1、第二章第二章 解线性代解线性代数方程组的直接法数方程组的直接法 Gauss 消去法 三角分解法 矩阵求逆 舍入误差对解的影响第三讲 Gauss 消去法11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb3.1 Gauss 消去法 3.3 列主元的Gauss 消去法3.2 Jordan 消去法 3.4 LU分解法不考虑舍入误差，通过有限四则运算进行求解，不考虑舍入误差，通过有限四则运算进行求解，这就是所谓这就是所谓直接法直接法。1112121222121212,nnnnnnTTnnaaaaaaAaaabb bbxx xxA

2、xb方程类型： n个方程，n个未知量 |A|0方法1. Gramer 法则，运算量为 ，完美但不现实。方法2. Gauss 消去法，它的发现可疑追溯2BC的中国，该算法以其高效性为诸多计算机系统广泛使用。,1,2,iiDxinD(1)!(1)nnn引例：123123123471225815361019xxxxxxxxx1232334712369 1xxxxxx 123111xxx注：Gauss 消元法包括两个主要步骤：1. 消去（一般方程组 上三角形式的方程组）2. 回代，即求上三角形是方程组的解。消元步骤的实质是用初等变换作用于系数矩阵A的增广矩阵 上，将 化为上三角形式矩阵，即AA1471

3、225815361019213123rrrr 147120369061117322rr 14712036900113.1 高斯（高斯（ Gauss ）消去法）消去法第一步消元：不妨设第一步消元：不妨设a11 0，记，记 li1= ai1 / a11 ，用，用 li1 乘乘第一个方程加到第第一个方程加到第i个方程上去，个方程上去，如此继续下去，第如此继续下去，第k-1步可将方程转化为步可将方程转化为(1)(1)(1)(1)(1)(1)111122121111(2)(2)(2)(2)22222221 1(2)(2)(2)(2)221 1,nnjjnnjjijnnnnnnjnjijaxaxaxbaa

4、bbaxaxbaal aaxaxbaal a(2)(2)1 11 1,ijijijiiiaal abbl b(1)(1)(1)(1)11112211(2)(2)(2)22222( )( )( )( )( )( )( )1,1,111,1( )( )( )( ),11nnnnkkkkkkknnkkkkkkkkkkkknnkkkkkn kknkknnnka xa xa xbaxaxbaxaxbaxaxaxbaxaxaxb( )( )(1)( )( )(1)( )( )/,1,kkikikkkkkkkkkijijikkjiiikklaaki jnaal abbl b (1)(1)(1)(1)1111

5、2211(2)(2)(2)22222( )( )( )(1)(1)(1)1,111,1(1)(1)(1)11nnnnkkkkkkknnkkkkkkkknnkkkknkknnnka xa xa xbaxaxbaxaxbaxaxbaxaxb( )( )(1)( )( )(1)( )( )/,1,kkikikkkkkkkkkijijikkjiiikklaaki jnaal abbl b 按上述消元手续做按上述消元手续做n-1n-1步后，原方程组即可加工步后，原方程组即可加工成上三角方程组的形式成上三角方程组的形式(1)(1)(1)(1)11112211(2)(2)(2)22222( )( )( )(

6、 )( )( )0nnnnkkkkkkknnknnnnnnnnna xa xa xbaxaxbaxaxbaxba第二步，回代第二步，回代 即是利用回代求解经过消元手续最终得到的方即是利用回代求解经过消元手续最终得到的方程组，其程组，其回代回代公式为：公式为： ( )( )1/()/,1,2,1nnnnnnnkkkkkkjjkkj kxbaxbaxaknn 消去法计算量的估计：消去法计算量的估计：消去法中消去法中第第k步步的乘除法计算量为的乘除法计算量为(n-k)(n-k+2) 加减法计算量为加减法计算量为(n-k)(n-k+1)做完做完n1步后总计算量：步后总计算量：乘除法：乘除法：加减法：加

7、减法：321115()(2)326nknnnNnk nk3111()(1)33nknnQnk nk回代过程计算量：回代过程计算量： 乘除法计算量乘除法计算量 加减法计算量加减法计算量总计算量为：总计算量为：乘除法计算量乘除法计算量加减法计算量加减法计算量221(1)22nknnNnk2121()22nknnQnk321233nnNNNn32125326nnnQQQ消去过程算法如下：for k=1,n-1for i=k+1,nC=A(i,k)/A(k,k)for j=k+1,n+1A(i,j)= A(i,j)-C*A(k,j)endendend回代过程算法如下：x(n)=A(n,n+1)/A(n

8、,n)for k=n-1,1for j=k+1,nA(k,n+1)= A(k,n+1)-A(k,j)*x(j)endx(k)=A(k,n+1)/A(k,k)end3.2 Jordan 消去法14712258153610192 2 13 3 1rrrr 14712036906111731243 2 2rrrr 101003690011132 6 3rrrr 100103030011123r 100101010011Jordan 消去法包含n+1步，其第k步为：若 ，则( )( )(1)( )( )(1)( )( )/,1,kkikikkkkkkkkkijijikkjiiikklaaaal abb

9、l bik jkn ( )0,1,kkkakn其第n+1步为：( )(1)( )( ),1,1,iiniiiiiiibbaina 其复杂度为321()(2)22nknnnk nknnn=25时，Gauss 消去法计算乘除共Jordan消去法计算乘除共注：Gauss 法要优于Jordan 法32582833nnnflop32842522nnnflop3.3 选主元的高斯消去法选主元的高斯消去法称称 为消去法第为消去法第k步计算的主元，当步计算的主元，当 绝绝对值很小时，会导致误差增加，从而引起算对值很小时，会导致误差增加，从而引起算法不稳定。法不稳定。因此，在消去法中，我们需要引入选主元法。因此

10、，在消去法中，我们需要引入选主元法。即每次消元时，从该列中选取系数绝对值最即每次消元时，从该列中选取系数绝对值最大者作为主元进行消元，大者作为主元进行消元，称为列主元消去法称为列主元消去法。( )kkka( )kkka全主元的Gauss消去法 一类特殊的矩阵（对角占有矩阵，对称正定阵）在Gauss消去的意义下，不改变其性质，不必选主元。 可以证明，全主元的Gauss消去法对于非奇异矩阵是稳定的。3.4 高斯消去法的矩阵形式高斯消去法的矩阵形式消去法消元过程可以通过对下面增广矩阵作初消去法消元过程可以通过对下面增广矩阵作初等变换来实现。等变换来实现。11121121222212 , nnnnnn

11、naaabaaabA baaab设设 ， 记记( )0kkka( )( )/,1,kkikikkklaaikn 1,100010010001kkkn kLll则消去法相当于则消去法相当于记记(1)(1)(1)(1)111211(2)(2)(2)222211( )( )0 , 00nnnnnnnnaaabaabLL A bab111121nLLLL则则2131321,11,21,31231101111nnnnnnnnlllLlllllll我们记我们记于是可得矩阵于是可得矩阵A的如下分解的如下分解这称为这称为矩阵矩阵A的的LR分解分解(1)(1)(1)11121(2)(2)222( )00nnnnnaaaaaRaALRLR分解应用于解方程组：分解应用于解方程组：1211,(,),1,2,nkkkkjjjLybAxbLRxbyy yyRxyybl ykn(1)(1)(1)1111121(2)(2)22222( )00nnnnnnnxyaaaxyaaRxxya( )( )11(),1,1nkkkkjjkj kkkxyaxkn na