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

中图 科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第5章解线性方程组的直接法 实际中，存在大量的解线性方程组的问题。很多数值方 法到最后也会涉及到线性方程组的求解问题：如样条插值的 M和m关系式，曲线拟合的法方程，方程组的Newton:迭代等 问题

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第5章 解线性方程组的直接法 实际中，存在大量的解线性方程组的问题。很多数值方 法到最后也会涉及到线性方程组的求解问题：如样条插值的 M和m关系式，曲线拟合的法方程，方程组的Newton迭代等 问题

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 对线性方程组： a古++anxn=h dndmxn=bn 或者：Ax=b 我们有Gram法则：当且仅当det(4)≠0时，有唯一的解为： 11 .a1-1ba1+l an ani bn anit

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS      + + = + + = n n n n n n n a x a x b a x a x b    1 1 1 1 1 1 1 det(A)  0 对线性方程组： 或者： Ax = b 我们有Gram法则：当且仅当 时，有唯一的解为：           = = = − + − + n n i n n i n n i i n i i i a a b a a a a b a a D A D D D x          1 1 1 1 1 1 1 1 1 1 1 , det( ), det

中固科营技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 但Gram法则不能用于计算方程组的解， 如n=100,1033次/秒的计算机要算10120年 解线性方程组的方法可以分为2类： ①直接法：准确，可靠，理论上得到的解是精确的 ②迭代法：速度快，但有误差 本章讲解直接法

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 但Gram法则不能用于计算方程组的解， 如n＝100，1033次/秒的计算机要算10120年 解线性方程组的方法可以分为2类： ①直接法：准确，可靠，理论上得到的解是精确的 ②迭代法：速度快，但有误差 本章讲解直接法

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 5.1消元法 我们知道，下面有3种方程的解我们可以直接求出： ① n次运算 A=diag(a11,a2,.,amn）→x= b,i=1,.,n ② (n+)/2次运算 21 12 →X= j=1 A -,i=1,.,n nn

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 5.1 消元法 我们知道，下面有3种方程的解我们可以直接求出： i n a b A diag a a a x i i i n n i ( , , , ) , 1, , = 1 1 2 2   = =  ① n次运算 i n l b l x x l l l l l l A i i i j i i j j i n n n n , 1, , 1 1 1 2 2 1 2 2 1 1      = −  =               =  − = ② (n＋1)n/2次运算

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS ③ (n十)/2次运算 l12 u2n 6-∑4，x A= 1U22 →X= 一，i=n,.1 : 消元法就是对方程组做些等价的变换，变为我们已知的3种类型 之一，而后求根

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS , , ,1 2 2 2 1 1 1 1 2 1      i n u b u x x u u u u u u A i i n j i i i j j i n n n n = −  =               = = + ③ (n＋1)n/2次运算 消元法就是对方程组做些等价的变换，变为我们已知的3种类型 之一，而后求根

中图科萝技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 对方程组，作如下的变换，解不变 ①交换两个方程的次序 ②一个方程的两边同时乘以一个非0的数 ③一个方程的两边同时乘以一个非0数，加到另一个方程 因此，对应的对增广矩阵(A,),作如下的变换，解不变 ①交换矩阵的两行 ②某一行乘以一个非0的数 ③某一个乘以一个非0数，加到另一行

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 对方程组，作如下的变换，解不变 ①交换两个方程的次序 ②一个方程的两边同时乘以一个非0的数 ③一个方程的两边同时乘以一个非0数，加到另一个方程 因此，对应的对增广矩阵(A,b)，作如下的变换，解不变 ①交换矩阵的两行 ②某一行乘以一个非0的数 ③某一个乘以一个非0数，加到另一行

品 中图 科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 1、Gauss消元法 思 首先将A化为上三角阵，再回代求解。 专路 11 a3 ain b a 412 . b 0 a品 a21 a422 b, 0 0 a a an an2 ann 0 0 0 d b

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 思 路 首先将A化为上三角阵，再回代求解 。               n n n n 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) 3 3 (2) 2 (2) 2 (2) 2 3 (2) 2 2 1 1 1 2 1 3 1 1 0 0 0 0 0 0 n n n n n n n n a b a a b a a a b a a a a b           1、Gauss消元法

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 步骤如下： 第一步：第1行xa1+第行，i=2,.,n 11 11 12 b C a12 b a21 022 a2n b2 0 唱 a .: an an2 ann 0 a 运算量：(n-)*(1+m)

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 步骤如下： 第一步： i i n a ai 1 , 2, , 1 1 1 + =  − 第 行 第 行               n n n n n n n a a a b a a a b a a a b         1 2 2 1 2 2 2 2 1 1 1 2 1 1               (2) (2) (2) 2 (2) 2 (2) 2 (2) 22 11 12 1 1 0 0 n n n n n n a a b a a b a a a b         运算量： (n-1)*(1+n)

中图 科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第二步： 第2行× a 第行，i=3,.,n 0 a12 3 6 1 2 ain b 0 0 b2 媼 a唱 0 0 b . a . 0 a a 0 0 a 运算量： (-2)*(1+n-)=(n-2)n

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS                 (3) (3) (3) 3 (3) 3 (3) 3 (3) 3 3 (2) 2 (2) 2 (2) 2 3 (2) 2 2 1 1 1 2 1 3 1 1 0 0 0 0 0 n n n n n n n a a b a a b a a a b a a a a b           运算量： (n-2)*(1+n-1)=(n-2)n 第二步： i i n a ai 2 , 3, , (2) 2 2 (2) 2 + =  − 第 行 第 行               (2) (2) (2) 2 (2) 2 (2) 2 (2) 22 11 12 1 1 0 0 n n n n n n a a b a a b a a a b        

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 类似的做下去，我们有： 第步：第行×一 (k) +第行，i=k+1,.,n C 运算量： n-)*1十n-k+l)=(n-n-k十2) n一1步以后，我们可以得到变换后的矩阵为： a a12 an b 0 a a 0 0 a .: 0 0 0

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第k步： i i k n a a k kk k i k k , 1, , ( ) ( ) + = +  − 第 行 第 行 类似的做下去，我们有： 运算量： (n－k)*(1＋n－k＋1)=(n－k)(n－k＋2)                 ( ) ( ) (3) 3 (3) 3 (3) 3 3 (2) 2 (2) 2 (2) 2 3 (2) 2 2 1 1 1 2 1 3 1 1 0 0 0 0 0 0 n n n n n n n n a b a a b a a a b a a a a b           n－1步以后，我们可以得到变换后的矩阵为：