中国科学技术大学：《计算方法》课程教学资源（课件讲义）第五章 解线性方程组的直接法

第五章解线性方程组的直接法

2 第五章 解线性方程组的直接法

线性方程组的求解 ■在科学研究和工程应用中，求解线性方程组是非常基 础的问题 ■ 一般的线性方程组 a11X1+.+a1nXn=b1 ←→ Ax=b an1x1+.+annXn=bn ■ (Gram公式)当且仅当det(A)≠0时，方程组有唯一解 x=D ,i=1,2.n a11 .a-1b1 1i+1 D=det(A),D.=det ani-bn amtl 3

线性方程组的求解  在科学研究和工程应用中，求解线性方程组是非常基 础的问题  一般的线性方程组  （Gram公式）当且仅当 时，方程组有唯一解 3 11 1 1 1 1 1 n n n nn n n ax ax b ax ax b  ++ =   ⇔   ++ = Ax = b    det( ) 0 A ≠ 11 1 1 1 1 1 1 111 , 1,2, , det( ), det i i iin i n ni n ni nn D xi n D a a ba a D D a a ba a − + − + = =     = =   A        

线性方程组的求解 ■求解线性方程组的方法可分为 ·直接解法：采用消元（初等变换）、矩阵分解等技巧；从理论上来说， 直接法经过有限次四则运算（假设运算无舍入误差），可以得到线性方 程组的精确解 ●迭代解法：采用迭代、分块、预条件处理等技巧；将线性方程的解视为 某种极限过程的向量序列，近似解 ■直接法与迭代法的使用建议 ·一般来说，对同等规模的线性方程组，直接法对计算机的要求高于送代 法 ·对于中等规模的线性方程组，考虑到直接法的准确性与可靠性，建议使 用直接法求解 ·对于高阶稀疏线性方程组（非零元素较少），建议使用迭代法求解 。要充分考虑线性方程的特性，譬如对称性、正定性、稀疏性等，来选用 合适的算法

线性方程组的求解  求解线性方程组的方法可分为  直接解法：采用消元（初等变换）、矩阵分解等技巧；从理论上来说， 直接法经过有限次四则运算（假设运算无舍入误差） ，可以得到线性方 程组的精确解  迭代解法：采用迭代、分块、预条件处理等技巧；将线性方程的解视为 某种极限过程的向量序列，近似解  直接法与迭代法的使用建议  一般来说，对同等规模的线性方程组，直接法对计算机的要求高于迭代 法  对于中等规模的线性方程组，考虑到直接法的准确性与可靠性，建议使 用直接法求解  对于高阶稀疏线性方程组（非零元素较少），建议使用迭代法求解  要充分考虑线性方程的特性，譬如对称性、正定性、稀疏性等，来选用 合适的算法 4

线性方程组的求解 求解线性方程组的常用软件 ●Matlab ●LAPACK/EISPACK/LINPACK(一般的线性方程组求解) ●TACUS(大型稀疏线性方程组) ●SuperLU(大型稀疏线性方程组) ●Eigen(开源，C++,线性代数模板库) ●MKL(商业软件) ● 推荐参考书 G.H.Golub,C.F.V.Loan.Matrix Computations.4th Ed.The Jonhs Hopkins University Press.(有影印本与中译本，人民邮电出版社) ●L.N.Trefethen,D.B.Ill.Numerical Linear Algebra.SIAM Press.(有中译 本，人民邮电出版社) 5

线性方程组的求解  求解线性方程组的常用软件  Matlab  LAPACK/EISPACK/LINPACK（一般的线性方程组求解）  TACUS（大型稀疏线性方程组）  SuperLU（大型稀疏线性方程组）  Eigen（开源，C++，线性代数模板库）  MKL（商业软件）  .  推荐参考书  G. H. Golub, C. F. V. Loan. Matrix Computations. 4th Ed. The Jonhs Hopkins University Press. （有影印本与中译本，人民邮电出版社）  L. N. Trefethen, D. B. III. Numerical Linear Algebra. SIAM Press. （有中译 本，人民邮电出版社） 5

消元法 ■基本思想：通过初等变换，将一般的线性方程组等价 变换为特殊形式的线性方程组，如上/下三角方程组、 对角方程组，进行求解 对角形线性方程组 aux =b a22X2 =b2 =: ,i=1,2n a amxn=b 附问复杂度：O(n) 6

消元法  基本思想：通过初等变换，将一般的线性方程组等价 变换为特殊形式的线性方程组，如上/下三角方程组、 对角方程组，进行求解  对角形线性方程组 时间复杂度： 6 11 1 1 22 2 2 , 1,2, , i i ii nn n n a x b a x b b xi n a ax b  =   =  ⇒= = =    =    O n( )

消元法 ■上三角方程组 41X1+412X2+.+4nXn=b 4222+.+2nn=b2 →X= j=i+1 -,i=n,n-1,1 ui unnxn =bn 时间复杂度：O(n2) 下三角方程组 1 =b 12X1+122X2 =b2 b- =: →X= -,i=1,2,.,n mx+In2x2++lmxn=bn 时间复杂度：O(n2) 7

消元法  上三角方程组 时间复杂度：  下三角方程组 时间复杂度： 7 11 1 12 2 1 1 22 2 2 2 1 , , 1, ,1 n n n i ij j n n j i i ii nn n n ux ux ux b b ux ux ux b x i nn u ux b = +  + ++ =  −  + + =  ⇒= = − =    = ∑      2 O n( ) 1 11 1 1 21 1 22 2 2 1 11 2 2 , 1,2, , i i ij j j i ii n n nn n n l x b b lx lx lx b x in l lx lx lx b − =  =  −  + =  ⇒= = =    + ++ = ∑     2 O n( )

消元法 ■ 初等变换： ●交换矩阵的两行 ●某一行乘以一个非零数 ·某一个乘以一个非零数，加到另一行 ■ Gauss随元法：先将矩阵化为上/下三角矩阵，再回代 求解 a12 13 n b 412 b 0 b52 d21 a22 a2n [初等变接) 0 0 6g an an2 . 0 0 0 b 8

消元法  初等变换：  交换矩阵的两行  某一行乘以一个非零数  某一个乘以一个非零数，加到另一行  Gauss消元法：先将矩阵化为上/下三角矩阵，再回代 求解 8               n n nn n n n a a a b a a a b a a a b         1 2 21 22 2 2 11 12 1 1                 ( ) ( ) (3) 3 (3) 3 (3) 33 (2) 2 (2) 2 (2) 23 (2) 22 11 12 13 1 1 0 0 0 0 0 0 n n n nn n n n a b a a b a a a b a a a a b           初等变换

消元法 第一步：第1行x01+第i行，i=2,3,n a 412 . b a 412 b a21 a22 a2n b2 0 a品 . a b) 初等变换 : . an2 . b 0 a . a 运算量：(n-1)*(1+n) 9

消元法  第一步：第 行 第 行， 运算量： 9 1 11 i a a − 1 × + i i n = 2,3, ,                n n nn n n n a a a b a a a b a a a b         1 2 21 22 2 2 11 12 1 1               (2) (2) (2) 2 (2) 2 (2) 2 (2) 22 11 12 1 1 0 0 n nn n n n a a b a a b a a a b         初等变换 (n n − + 1*1 ) ( )

消元法 (2) 第二步：第2行×二+第i行，i=3,4,n a a12 a13 b b 11 品 a 0 b2) a品 a 0 初等变换〉 0 0 a bs 0 a品 . 0 0 a a b 运算量：（n-2)*(1+n-1)=(n-2)n 10

消元法  第二步：第 行 第 行， 运算量： 10 (2) 2 (2) 22 i a a − 2 × + i i n = 3,4, ,                  (3) (3) (3) 3 (3) 3 (3) 3 (3) 33 (2) 2 (2) 2 (2) 23 (2) 22 11 12 13 1 1 0 0 0 0 0 n nn n n n n a a b a a b a a a b a a a a b                         (2) (2) (2) 2 (2) 2 (2) 2 (2) 22 11 12 1 1 0 0 n nn n n n a a b a a b a a a b         初等变换 (n n nn -2 * 1 -1 -2 ) ( + =) ( )

消元法 ■类似的做下去，第k步： 第k行×需+第ī行，1=k+,.,n (K) 运算量： (nk*Hmk+1)=(n k)(n k 2) ◆ n-1步运算之后 411 a13 ain b 0 品 . a b 0 0 d . 0 0 0 总运算量： 2=③n-k+2)+(m+/2=” +n2- =0(n3) 3 3 11

消元法  类似的做下去，第 步： 第 行 第 行，  运算量：  步运算之后  总运算量： 11 k k ( ) ( )k ikk kk aa− × + i ik n = +1, ,  ( ) *(1 1) ( )( 2) nk nk nknk －＋－＋－－＋ = n − 1   ( ) ( ) ( 3 ) 3 ( 3 ) 3 ( 3 ) 33 ( 2 ) 2 ( 2 ) 2 ( 2 ) 23 ( 2 ) 22 11 12 13 1 1 0 0 0 0 0 0 n n n nnnnn a b a a b a a a b a a a a b         ( ) 1 3 2 3 1 ( )( 2) 1 / 2 ( ) 3 3 nk n n n k n k n n n On −=∑ − −+ + + = + − =