第5章解线性方程组的直接法 实际中,存在大量的解线性方程组的问题。很多数值方 法到最后也会涉及到线性方程组的求解问题:如样条插值的 M和m关系式,曲线拟合的法方程,方程组的 Newton迭代等 问题
第5章 解线性方程组的直接法 实际中，存在大量的解线性方程组的问题。很多数值方 法到最后也会涉及到线性方程组的求解问题：如样条插值的 M和m关系式，曲线拟合的法方程，方程组的Newton迭代等 问题
对线性方程组: x+…+a1nxn=b aLn1X1+……+an,Xn= nn n b 或者:Ax=b 我们有Gram法则:当且仅当deA)≠0时,有唯一的解,而且解为: 1-1 li+1 D=det(A),D=det D ni+1
+ + = + + = 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
但Gram法则不能用于计算方程组的解,如nη=100,1033次/秒的计算机要算10120年 解线性方程组的方法可以分为2类 ①直接法:准确,可靠,理论上得到的解是精确的 ②迭代法:速度快,但有误差 本章讲解直接法
但Gram法则不能用于计算方程组的解，如n＝100，1033次/秒的计算机要算10120年 解线性方程组的方法可以分为2类： ①直接法：准确，可靠，理论上得到的解是精确的 ②迭代法：速度快，但有误差 本章讲解直接法
51消元法 我们知道,下面有3种方程的解我们可以直接求出 n次运算 A=dig(a1,2a22∵,am )→x= si=1,…,n (n+1)m/2次运算 b一∑lx 2 nn
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次运算
(n+1)m2次运算 In ∑unx A= 22 =1 →x1= l=n
, , ,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次运算
对方程组,作如下的变换,解不变 ①交换两个方程的次序 ②一个方程的两边同时乘以一个非0的数 ③一个方程的两边同时乘以一个非0数,加到另一个方程 因此,对应的对增广矩阵A,b,作如下的变换,解不变 ①交换矩阵的两行 ②某一行乘以一个非0的数 ③某一个乘以一个非0数,加到另一行 消元法就是对增广矩阵作上述行的变换,变为我们已知的3种类型之一,而后求根
对方程组，作如下的变换，解不变 ①交换两个方程的次序 ②一个方程的两边同时乘以一个非0的数 ③一个方程的两边同时乘以一个非0数，加到另一个方程 因此，对应的对增广矩阵(A，b)，作如下的变换，解不变 ①交换矩阵的两行 ②某一行乘以一个非0的数 ③某一个乘以一个非0数，加到另一行 消元法就是对增广矩阵作上述行的变换，变为我们已知的3种类型之一，而后求根
>高斯消元法: 思首先将A化为上三角阵,再回代求解。 路 1) (1) lI 2 12 0 (2) 2) 22 b 00a(3) 3n b C 000
➢ 高斯消元法： 思 路 首先将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 = (1) (1) (1) (1) (1) 11 12 13 1 1 (2) (2) (2) (2) 22 23 2 2 (3) (3) (3) 33 3 3 ( ) ( ) 0 0 0 0 0 0 n n n n n nn n a a a a b a a a b a a b a b
步骤如下: 第一步 第行x二+第i行,=2,…,n 11 12 b 12 (2) (2)(2) 421 C 0 n 0a(2) 2) 2 nn 运算量:(m-1)(1+m)
步骤如下： 第一步： 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)
第二步:第2行×x2) +第行,i=3,…,n II 12 13 In 11 12 0 2 (2) 0 (2) 2) 2 00 (3) 33 an 0 a (2) (2) n2 nn 00an3)…a0)b) 运算量:(mn-2)(1+-1)=(n-2n
(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
类似的做下去,我们有: 第k步:第k行×K a(k)+第i行,i=k+1 k 运算量:(mn-k(1+n-k+1)=(n-k(mn-k+2) n一1步以后,我们可以得到变换后的矩阵为: 12 13 0 (2) C22 (2) (2)(2) C a b 00 (3) ) a 000 (n) h(n)
第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步以后，我们可以得到变换后的矩阵为：