第五章解线性方程组的直接方法 §5.0概述 §5.1高斯消去法 §5.2矩阵分解及其在解方程组中的应用 S5.3矩阵的条件数和方程组的性质 2004-11-10
2004-11-10 1 第五章 解线性方程组的直接方法 §5.0 概述 §5.1 高斯消去法 § 5.2 矩阵分解及其在解方程组中的应用 § 5.3 矩阵的条件数和方程组的性质
§5.0概述 研究数值解法的必要性 求: aux,+a,,+.+ainIn=b ax tax++ax=b anx+an2x2t.+am,xn=b 的解xx2x的值,根据克菜姆( Gramer)法则可 表示为两个行列式之比: K k 9-9 D 2004-11-10 2
2004-11-10 2 §5.0 概述 一 .研究数值解法的必要性 + + + = + + + = + + + = n n nn n n n n n n a x a x a x b a x a x a x b a x a x a x b ... ....... ... ... 1 1 2 2 21 2 22 2 2 2 求： 11 1 12 2 1 1 (k 1,2,..., n) DD x K k = = 的解 的值，根据克莱姆(Gramer)法则可 表示为两个行列式之比： n x , x ,...x 1 2
研究数值解法的必要性(续) 计算一个n阶行列式需要做(n-1)m)个乘法,求 解上述方程共做N=(n+1)×(n-1)n)+n次乘除法 如:n=20,N≈97×1020,若用每秒完成万亿次(1012 浮点乘法运算的计算机(当前国内运算速度最快) 按每天工作24小时,完成这些计算约需30年。若使用 般的个人电脑,每秒不外完成十亿次(109)浮点乘法 运算,则完成这些计算约需3万年。 2004-11-10
2004-11-10 3 研究数值解法的必要性（续） 计算一个 阶行列式需要做 个乘法，求 解上述方程共做 次乘除法。 n (n −1)(n!) N = (n +1) × (n −1)(n!) + n 如： ,若用每秒完成万亿次（1012） 浮点乘法运算的计算机（当前国内运算速度最快）， 按每天工作24小时,完成这些计算约需30年。若使用一 般的个人电脑，每秒不外完成十亿次（109）浮点乘法 运算，则完成这些计算约需3万年。 n = 20, 20 N ≈ 9.7×10
二、线性代数方程组的常用解法 1、直接法: 只包含有限次四则运算。若在计算过程中 都不发生舍入误差的假定下,计算结果就是原方 程组的精确解. 2、迭代法: 把方程组的解向量看作是某种极限过程的极限, 而且实现这一极限过程每一步的结果是把前一步所 得的结果施行相同的演算步骤得到的 Remark:由于运算过程中舍入误差的存在,实 际上直接方法得到的解也是方程组的近始解。 2004-11-10
2004-11-10 4 二、线性代数方程组的常用解法 1、直接法： 只包含有限次四则运算。若在计算过程中 都不发生舍入误差的假定下，计算结果就是原方 程组的精确解。 2、迭代法： 把方程组的解向量看作是某种极限过程的极限， 而且实现这一极限过程每一步的结果是把前一步所 得的结果施行相同的演算步骤得到的。 Remark：由于运算过程中舍入误差的存在，实 际上直接方法得到的解也是方程组的近始解
§5.1高斯消去法 设有线性方程组 a1x1+a12x2+…+anxn=b 十a2X十.+a2X anx,+an2x2+.+amx,=b 或写为矩阵形式A=b,其中 11 12 ln A |为非奇异矩阵.x=3b4 2 2004-11-10
2004-11-10 5 §5.1 高斯消去法 + + + = + + + = + + + = n n nn n n n n n n a x a x a x b a x a x a x b a x a x a x b ... ...... ... ... 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 设有线性方程组 或写为矩阵形式 Ax b，其中 r r = 为非奇异矩阵. = n n nnnn a a a a a a a a a A ... ... ... 1 2 21 22 2 11 12 1 M M M M = n xxx x ...21 r = n bbb b ...21 r
一Gaus顺序消去法 具体过程: 将Ax=b改为A=b0 其中 x1+ (1) x n,=bi aOx taox+aOx=bo Cx1+an2x2+..+a(1), 2004-11-10
2004-11-10 6 一.Gauss顺序消去法 具体过程： (1) (1) A x br r 将 改 Ax b 为 = r v = 其中 + + + = + + + = + + + = (1) (1) 2 (1) 1 2 (1) 1 (1) 2 (1) 2 2 (1) 1 22 (1) 21 (1) 1 (1) 2 1 (1) 1 12 (1) 11 ... ...... ... ... n n nn n n n n n n a x a x a x b a x a x a x b a x a x a x b b b r r = (1) A aij n aij n ( ) ( ) (1) (1) = =
Gauss)顺序消去法(续) Stepl:若ah≠0,令 ),用-乘 第一个方程加到第i个方程(i=2,3.m),并保留第 式,则得 a1x1+a12x2+…+a1mxn a lx +...+ax x2+…+a2lxn=b2) +..+a2)x=b 记为A2)x=b(2) 其中a2)=a)-la")(nj=23m) (i=23,,n) 2004-11-10 7
2004-11-10 7 Gauss顺序消去法（续） + + = + + = + + = + + + = (2) (2) (2) 2 (2) 3 (2) 2 3 (2) 32 (2) 2 (2) 2 2 (2) 22 (1) 1 (1) 2 1 (1) 1 12 (1) 11 ... ...... ... ... ... n n nn n n n n n n n n a x a x b a x a x b a x a x b a x a x a x b Step1： 若 令 ,用 乘 第一个方程加到第 个方程 ，并保留第一 式，则得 0, (1) a11 ≠ i (1) 11 (1) 1 1 a a l i i = ( i = 2,3,... n ) ( i = 2,3,... n ) i1 − l (1) 1 1 (2) (1) ij ij i a j 其中 a = a − l ( i, j = 2,3,... n ) A x = (2) r (2) b r 记为 (1) 1 1 (2) (1) b b l b i = i − i ( i = 2,3,... n )
Gauss顺序消去法(续 step2:若a2)≠0,令l2 2) (=34,…,n),用 C 乘第二个方程加到第i个方程(=3,4,,m),则得 +a1x2+ +a(x.=b6() a2)x,+………+a42) 2n n b a3)x,+.a3)x.=b 3n an3x3+…+a nnn 记为A(3x=b 其中 (i,=3,4,…,n) 2004-11-10 (3) (2) 2) (i=3,4,…,n)
2004-11-10 8 Gauss顺序消去法（续） 若 令 ， 乘第二个方程加到第i个方程 ，则得 0, (2) a22 ≠ i2 −l (2) 22 (2) 2 2 a a l i i = (i = 3,4,..., n) Step2: (i = 3,4,..., n) 用 + + = + + = + + = + + + = (3) (3) 3 (3) 3 (3) 3 (3) 3 3 (3) 33 (2) 2 (2) 2 2 (2) 22 (1) 1 (1) 2 1 (1) 1 12 (1) 11 ... .... n nn n n n n n n n n a x a x b a x a x b a x a x b a x a x a x b LLLL LLLL LLLL A x = (3) r (3) br 记为 (i, j = 3,4,..., n) (2) 2 2 (3) (2) ij ij i a j 其中 a = a − l (2) 2 2 (3) (2) b b l b i = i − i (i = 3,4,..., n)
Gauss顺序消去法(续 第k-1步消元完成后,有 a(}x+a23x2+………+aDxn=b 2x2 (k) (k) 从xk+…+amxn=bk x, +.+ wx=b (k) 设为A()=b( 2004-11-10
2004-11-10 9 Gauss顺序消去法（续） 第k-1步消元完成后，有 + + = + + = + + = + + + = ( ) ( ) ( ) ( ) ( ) ( ) (2) 2 (2) 2 2 (2) 22 (1) 1 (1) 2 1 (1) 1 12 (1) 11 ... ........................ ... ........................ k n n k k nn k nk k n k k k kn k kk n n n n a x a x b a x a x b a x a x b a x a x a x b LLLL LLLL (k ) (k ) A x br r 设为 =
Gauss顺序消去法(续 (k) Step:若a≠0,令l (i=k+1,k+2,,) kk 用-lk来乘以第k-1步所得方程中的第k个方程,加到 第i(i=k+1,k+2,n)个方程,并保留第k个方程,则得: ax+ax2+…,+amxn=b 2) (2) a2x2+.+a2x b2) x, +,+ax=b 4k+1.k+1xk+1+.￥0+xn=6(k+) k+1) +1x1+…十n1+), n,nn 2004-11-10
2004-11-10 10 Gauss顺序消去法（续） Step k：若 0 ,令 , ( ) ≠ k kk a ( ) ( ) k kk k ik ik a a l = （i=k+1,k+2, … ) 用 - 来乘以第k-1步所得方程中的第 k个方程，加到 第 i 个方程，并保留第 k个方程，则得： ik l （i=k+1,k+2, … n ） + … + = + … + = + … + = + … + = + + … + = + + + + + + + + + + + + + ( 1) ( 1) 1 , ( 1) , 1 ( 1) 1 ( 1) 1 1, ( 1) 1, 1 ( ) ( ) ( ) (2) 2 (2) 2 2 (2) 22 (1) 1 (1) 2 1 (1) 1 12 (1) 11 k n n k k n n k n k k n k k k k n k k k k n k k k kn k kk n n n n a x a x b a x a x b a x a x b a x a x b a x a x a x b L L L L L L L L L L L L L L L L