《线性代数》课程教学资源（PPT课件讲稿）第2章 线性代数方程组

第2章线性代数方程组 1Gaus消去法 212算法组织 算法 Gauss(A, b,nx)系数矩阵A存放于数组A中,右端向量放在数组b中 1.[消去] I For k=1,2,..,n-1 1.1ak=0ten输出错误信息;stop 1.2FOrt=k+1,k+2,..n 1.2.1a1k/ak→a1k N-1次 1.2.2fj=k+1,k+2,…,n Nk次 Nk次 1.2.2.1a 1.2.3B Bk→B .[回代 2.1Bn 2.2 for k 2.2.1B 2.2.2FOFj=k+1,k+2,,n N-1次 2.2.2.1S Nk次 22.3S/aM→

第2章 线性代数方程组 2.1 Gauss消去法 2.1.2 算法组织 算法 Gauss(A,b,n,x) 系数矩阵A存放于数组A中，右端向量放在数组b中 .[ ] 1 1,2,..., -1 1.1 0 ; 1.2 1, 2,..., 1.2.1 / 1.2.2 1, 2,..., 1.2.2.1 1 kk ik kk ik ij ik kj ij I For k n If a then stop For i k k n a a a for j k k n a a a a = = = + +  = + + −  消去 输出错误信息 .2.3    i ik k i −  a N-1次 N-k次 N-k次 N-1次 N-k次 .[ ] 2.1 / 2.2 -1, - 2,...,1 2.2.1 2.2.2 1, 2,..., 2.2.2.1 - 2.2.3 / n nn n k kj j kk k II a x for k n n S For j k k n S a x S S a x    =  = + +   回代

第2章线性代数方程组 1Gaus消去法 时间复杂度分析 1消去算法运算量 分为n-1步,第k步变换n-k行:求倍数,再从n+1-k个元素中减去 第行对应列的倍数,因此所需浮点运算次数 N1=∑(n-kMn-k+2)=+1 5n 2回代运算量 求x需做次浮点运算求xn需做2次浮点运算,…求x需m次 浮点运算,因此所需浮点运算次数: N2=1+2+…+n= n(n+1) 2 因此,N=N,+N2+n3 即,运算量为On3)

第2章 线性代数方程组 2.1 Gauss消去法 时间复杂度分析 1.消去算法运算量 -1 分为n 步 2.回代运算量 -1 1 1 , ,..., , n n 求x x x n 需做 次浮点运算 求 需做2次浮点运算 求 需 次 浮点运算 因此所需浮点运算次数: 3 2 1 2 3 3 n n 因此,N N N n = + = + − 3 O( ) 即,运算量为 n 1 1 1 ( )( 2) n k N n k n k − = = − − +  , - 第k n k 步变换 行:求倍数, 1- 再从n k + 个元素中减去 第k行对应列的倍数 ,因此所需浮点运算次数: 3 2 5 3 2 6 n n n = + −2 ( 1) 1 2 ... 2 n n N n + = + + + =

第2章线性代数方程组 1Gaus消去法 空间复杂度分析 (1)系数矩阵4用空间为n2,则空间复杂度为(n2) (2)常量b用空间为,则空间复杂度为(n) (3变量c占用空间为n,则空间复杂度为(n) (4消去过程中认为没有倗额外存储空间 因此消去法的总的空间复为(n2)

第2章 线性代数方程组 2.1 Gauss消去法 空间复杂度分析 (1) , ( ) 2 2 系数矩阵A占用空间为n 则空间复杂度为o n (2)常量b占用空间为n,则空间复杂度为o(n) (3)变 量x占用空间为n,则空间复杂度为o(n) (4)消去过程中认为没有使用额外存储空间 , ( ) 2 因此 消去法的总的空间复杂度为o n

1+2x2+x3=0 例2-1:解线性方程组2x1+2x2+3x3=3 2 2 解第次消元:按前述GaU5消去法计算 将第2方程-1×第1方程将第3方程-1×第方程得 x1+2x2+x3=0 2x,+x2=3 x3=2 第2次消元:计算l32 2 将第3方程-32×第2方程,得 x1+2x2+x2=0 2x2+x2=3 x 2 q可得

例2-1：解线性方程组 解:第1次消元: 按前述Gauss消去法计算 , 将第2方程-- 第1方程,将第3方程-- 第1方程, 得 第2次消元: 计算 , 将第3方程-- 第2方程, 得 回代可得: 1 1 1 2, 1 2 l 21 = = l 31 = − = −      − − = + + = + + = 3 2 2 2 3 3 2 0 1 2 1 2 3 1 2 3 x x x x x x x x  21 l  31 l      − + = − + = + + = 2 2 3 2 0 2 3 2 3 1 2 3 x x x x x x x 2 1 2 1 32 = − l = − l 32         = − + = + + = 2 1 2 1 2 3 2 0 3 2 3 1 2 3 x x x x x x x3 =1, x2 = −1, x3 =1

利用线性方程组的矩阵形式可将GaUs消)去的过程更清晰: 将线性方程组写成增广矩阵形式并将写入, 1210 0 2 2233 213 213 1-302 由此x=(1-1;y 类似, 21032 21032 441-10 1-7-4 252-22-13 260 21245

利用线性方程组的矩阵形式, 可将Gauss消去的过程更清晰: 将线性方程组写成增广矩阵形式,并将 写入, 由此 ; 类似, ij l             −           − −           − − = → =− → = 2 1 2 1 2 1 3 1 2 1 0 1 1 2 2 1 3 1 2 1 0 1 3 0 2 2 2 3 3 1 2 1 0 2 1 1 2 3 1 3 2 2 1 l l l ( ) T x = 1 −1 1               − − − − −               − − − − − − → = = =− 0 2 1 3 6 2 19 11 2 1 7 4 2 1 0 3 2 2 1 2 4 5 2 5 2 22 13 4 4 1 1 0 2 1 0 3 2 2 1 1 2 1 4 1 3 1 l l l