计算方法Gauss消去法ch05ar

1第五章解线性方程组的直接方法计算方法——Gauss消去法2本章内容预备知识Gauss消去法矩阵三角分解法误差分析3本讲内容向量与矩阵特征值与谱半径一些特殊矩阵预备知识一般过程对应的矩阵三角分解列主元Gauss消去法Gauss消去法4线性方程组直接解法Axb自然科学和工程计算中,很多问题最终都需要求解一个线性代数方程组(1)直接法:适合低阶方程组或某些特殊大型稀疏方程组目前使用的数值解法:(2)迭代法:解大型稀疏方程组的主流算法,nnnARbR在本章中，我们总是假定A是n阶方阵5预备知识向量与矩阵预备知识特征值与特征向量矩阵的谱：()max()AA(A)={A的所有特征值}矩阵的迹：矩阵的谱半径：1122tr()nnaaAaAxx(,,0)nCxCx6预备知识相关性质11AxxAxx12tr()nA12det()nAA与AT有相同的特征值7特殊矩阵一些特殊矩阵对角矩阵、三角矩阵、三对角矩阵对称矩阵、Hermite对称矩阵、对称正定矩阵正交矩阵、酉矩阵初等置换阵、置换阵（排列阵）上Hessenberg矩阵1112131212223232333,1nnnnnnnaaaaaaaaaaaaa0for1ijaij8性质定理1（解的存在唯一性，教材141页）定理2（对称正定矩阵的性质，教材141页）定理3（对称正定矩阵的充分条件，教材141页）定理4（Jordan标准型，教材141页）9Gauss消去法例：直接法解线性方程组1231231232222334463xxxxxxxxx解：1222(,)23344163Ab61121702128006178921122200131x23871xx1232222xxx10Gauss消去法高斯消去法的主要思路：将系数矩阵A化为上三角矩阵，然后回代求解。11112211211222221122.........nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb考虑n阶线性方程组：Axb矩阵形式=11Gauss消去法第一步：消去第一列依次将增广矩阵的第i行-mi1第1行，得)1(1)1(1)1(12)1(11...baaan)2(A(2)b(1)110a(1)(1)1111(2,...,)iimaain设，计算(2)(1)(1)11(2)(1)(1)11ijijijiiiaamabbmb其中(,2,...,)ijn第二步：消去第二列依次将上述矩阵的第i行-mi2第2行，得(3)(2)(2)22(3)(2)(2)22ijijijiiiaamabbmb其中(,3,...,)ijn(2)(2)2222(3,...,)iimaain设，计算(2)220a)1(1)1(1)1(12)1(11...baaan(3)A(3)b(2)(2)(2)2222...naab记(1)1(1)(1)(1)(1)(),ijnnnbAaAbbb，即。(1)(1),ijijiiaabb12Gauss消去法高斯消去法第k步：消去第k列依此类推，直到第n-1步，原方程化为()()(1,...,)kkikikkkmaaikn设，计算()0kkka(1)(1)(1)(1)1112111(2)(2)(2)22222()()nnnnnnnnaaabxxaabxba回代求解：()()nnnnnnxba计算(1)()()(1)()()kkkijijikkjkkkiiikkaamabbmb(i=k+1,…,n)()()()1()niiiiiijjiijixbaxa(i=n-1,…,1)13几点注记主元：(1,2,...,)in()iiiaGauss消去法能进行到底的条件：主元全不为0定理：（i=1,2,...,n）的充要条件是A的顺序主子式不为零，即()0iiia11111110,0,1,2,,iiiiiaaDaDinaa推论：(1)()1111,,2,,iiiiiaDaDDin14运算量第k步：消第k列()()(1,...,)kkikikkkmaaikn计算计算(1)()()(1)()()kkkijijikkjkkkiiikkaamabbmb(i,j=k+1,…,n)回代求解：()()nnnnnnxba()()()1()niiiiiijjiijixbaxa(i=n-1,…,2,1)n–k次(n–k)2次n–k次n(n+1)/2次Gauss消去法的乘除运算量为：3233nnn计算机中做乘除运算的时间远远超过做加减运算时间，故我们只估计乘除运算的次数15LU分解Gauss消去过程其实就是一个矩阵的三角分解过程则A(k)与A(k+1)之间的关系式可以表示为：(1)()kkkALA其中：1,,1111kknkkmmL()()kkikikkkmaa(i=k+1,…,n)将Gauss消去过程中第k-1步消元后的系数矩阵记为：(1)(1)(1)1111()()()()()knkkkkkknkknknnaaaAaaaa(k=1,…,n-1)16LU分解LU分解记：，则111()12,nnLLLLUAALU其中：L---单位下三角矩阵，U---上三角矩阵LU分解于是有：()(1)121nnALLLA1)1(1)(21()nnALLAAL容易验证：1,,11111kknkkmmL(k=1,…,n-1)(杜利脱尔Doolittle分解)17LU分解存在唯一性LU分解存在()0kkka高斯消去法不被中断定理：若A的所有顺序主子式不为零，则A存在唯一的LU分解（证：自学）所有顺序主子式不为零18列主元Gauss消去法Gauss消去法有效的条件是：主元全不为零例：解线性方程组12011101xx①先选取列主元：()||=kkika()max||0kikkina②ifikkthen交换第k行和第ik行③消元列主元Gauss消去法在第k步消元时，在第k列的剩余部分选取主元19列主元Gauss消去法算法(列主元Gauss消去法)fork=1ton-1()()||=max||0kkkikikkinaaifthenstop()=0kkikaifikkthenswapk-thandik-throw(includingb)ikikkkmaafori=k+1ton,1,2,...,ijijikkjiiikkaamajkknbbmbendend1,,1,...,2,1()nnnniiijjiijixbaxbaxain20PLU分解列主元Gauss消去法对应的矩阵分解为PLU定理：若A非奇异，则存在排列矩阵P，使得PA=LU其中L为单位下三角矩阵，U为上三角矩阵列主元Gauss消去法比普通Gauss消去法要多一些比较运算，但比普通高斯消去法稳定列主元Gauss消去法是目前直接法的首选算法21全主元Gauss消去法全主元高斯消去法：第k步消元时，在剩余的n-k阶子矩阵中选取主元①先选取全主元：()||=kkkija(),max||0kijkijna②ifikkthen交换第k行和第ik行ifjkkthen交换第k列和第jk列③消元列交换改变了xi的顺序，须记录交换次序，解完后再换回来全主元高斯消去法具有更好的稳定性，但很费时，在实际计算中很少使用22作业1.教材175页，习题12.教材176页，习题7（只需解方程组）3.教材177页，习题11