数值计算方法课件-CH2解线性方程组的直接法—21～23Gauss消去法.ppt

1、华长生制作1第二章 解线性方程组的直接法线性方程组线性方程组 稠密和稀疏稠密和稀疏（按系数矩阵含零元多少分）高阶和低阶高阶和低阶（按阶数的高低分）对称正定、三对角占优等对称正定、三对角占优等（按系数矩阵的形 状性质分）基基 本本 解解 法法 直接法直接法（通过有限步计算得到精确解精确解，适用于低阶线性 方程组，第二章内容）迭代法迭代法（通过逐次迭代逼近得到近似解近似解，适用于大型线 性方程组和非线性方程，第六章内容）线性方程组及方法分类nnnnnnnnbbbbxxxXaaaaaaaaaA2121212222111211nnnnnnnnnnbxaxaxabxaxaxabxaxaxa2211222

2、2212111212111（2.1）求解线性方程组：求解线性方程组：根据根据Cramer(克莱姆克莱姆)法则法则,若若 0)det(A|)det(AA 则方程组则方程组 有唯一解有唯一解。bAx 三角形线性方程组解法三角形线性方程组解法UXb11 11221122222nnnnnnnnu xu xu xbu xu xbu xb（2.3）上三角形上三角形Gaussian Elimination高斯消去法高斯消去法消元消元回代回代化上三角方程组的过程思思路路首先将首先将A化为上三角阵化为上三角阵 ，再回代求解，再回代求解=nnnnnnnnbxabxaxabxaxaa2222211212111x自下

3、而上解上三角形方程组的过程),(),()1()1(bAbAA),()2()2(bA),()()(nnbA 经过经过n-1次次以上求解线性方程组的方法称为以上求解线性方程组的方法称为高斯高斯(Gauss)消去法消去法利用利用bAx)()(nnbxA同 解假设假设 ，对增广矩阵作，对增广矩阵作行初等变换行初等变换:0)det(A上三角阵通过解通过解 得原方程组得原方程组 的解。的解。bAx)()(nnbxA1.不改变行列式的值2.不改变未知量次序设设 ，计算因子，计算因子0)1(11 a).,2(/)1(11)1(11niaamii 将增广矩阵将增广矩阵 第第i 行行 mi1 第第1 1行行，得到

4、：，得到：)1(1)1(1)1(12)1(11.baaan)2(A)2(b其中其中记记,)()1()1(nnijaAATnbbbb)1()1(1)1(行乘数Step 1：0)det().,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij 0)det(设设 ，计算因子，计算因子0)(kkka).,1(/)()(nkiaamkkkkikik ).,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij Step k：其中其中行乘数将增广矩阵将增广矩阵 第第i 行行 mik 第第k行行，得到：，得到：)1(1)1(1

5、)1(12)1(11.baaan)(kb)()()(kkkknkkkbaa.)(kA共进行共进行？步步n 1 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa 以上消元过程均假定以上消元过程均假定0)(kkka注注:如果如果 怎么办怎么办 0)(kkka)2()2()2(2)2(2)2(2)2(22)1(1)1(1)1(12)1(1100nnnnnnbaabaabaaa 由于由于 ，则，则 A 的第一列中至少有一元素不为零。的第一列中至少有一元素不为零。0)det(A如果如果 ，则将，则将 的第的第1行与第行与第 行交换后再行

6、交换后再消元，得消元，得 0)1(11ia1i),()1()1(bA假设例：例：0(1)11a当当 时，采取类似的处理措施。时，采取类似的处理措施。0)(kkka由于由于 ，所以，所以0)det(Ani,2,10)(iiia即得线性方程组即得线性方程组 Ax=b 解：解：因此，上三角形方程组因此，上三角形方程组 有唯一解。有唯一解。)()(nnbxA)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijjiijiiiNo unique solution exists.Then we must find the integer k i with ,and interc

7、hange the k-th row with the i-th row.0)(ikiaNo unique solution exists.事实上事实上,只要只要 A 非奇异非奇异,即即 A 1 存在存在,则可通过逐次消元则可通过逐次消元及行交换及行交换,将方程组化为三角形方程组将方程组化为三角形方程组,求出唯一解。求出唯一解。若若A的所有的所有顺序主子式顺序主子式 均不为均不为0，则高斯消元无需，则高斯消元无需换行即可进行到底，得到唯一解。换行即可进行到底，得到唯一解。0)(nnnaWhat if?0)(iiiaWhat if?What if we cant find such k?iiii

8、iaaaaA.)det(1111 由于计算机中乘除运算的时间远远超过加减运算的时间，故估计由于计算机中乘除运算的时间远远超过加减运算的时间，故估计某种算法的运算量时，往往只估计某种算法的运算量时，往往只估计 乘除次数乘除次数，而且通常以乘除次数，而且通常以乘除次数的的 最高次幂最高次幂 为运算量的为运算量的 数量级数量级。(n k)次次Step k：设设 ，计算因子，计算因子 且计算且计算0)(kkka).,1(/)()(nkiaamkkkkikik ).,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共进行共进行 n 1 步步 )()2(2

9、)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijjiijiii(n k)2 次次(n k)(n k+2)次次nnnknknnk6523)2)(2311 消元乘除次数：消元乘除次数：1 次次(n i+1)次次22)1(1211nninni 回代乘除次数：回代乘除次数：(n k)次次n-1 步回代过程需作乘除运算总次数为：步回代过程需作乘除运算总次数为：niin1)1(222nnGauss消去法的乘除运算总次数为消去法的乘除运算总次数为：MD3323nnn)(3

10、23nOn11)2)(nkknkn652323nnn完成完成 n-1 步消元需作乘除运算总次数为：步消元需作乘除运算总次数为：333323nnnnMD例如例如而如果用而如果用 Cramer 法则法则的乘除法运算次数约为：的乘除法运算次数约为：20)120)(120(!2020109当当 n 很大时，很大时，当当 n=20 时，时，Gauss 消去法消去法乘除法约为乘除法约为 2700 次次Gauss 消去法算法设计消去法算法设计1、输入：矩阵阶数输入：矩阵阶数 n，增广矩阵增广矩阵 A(n,n+1)2、对于对于nk,2,13、回代计算：回代计算：nkiaamkkikik,1 1,1 ;,1 n

11、kjnkiamaakjikijij(2)(2)消元：消元：(1)(1)如果如果 ，找非零元，找非零元 ，交换第，交换第 k 行和第行和第 i 行，行，若不存在非零元，算法停止若不存在非零元，算法停止0kkaika(1)(1)若若 ，算法停止，算法停止0)(nnna1,1,11,nnixaaxnijjijnii(2)(2)回代：回代：例例1.用用Gauss消去法解线性方程组消去法解线性方程组(用用3 位十进制浮位十进制浮点数计算）点数计算）210001.02121xxxx解解:本方程组的精度较高的解为本方程组的精度较高的解为Tx)00010001.1,99989999.0(*用用Gauss消去法

12、求解（用消去法求解（用3位十进制浮点数计算）位十进制浮点数计算）),(bAA21111000100.01000021m441000.111000.101000100.0-99991.000.0021,xx回代后得到回代后得到与精确解相比与精确解相比,该结果很差！该结果很差！主元-9998在求行乘数时用了很小的数在求行乘数时用了很小的数0.0001作除数。作除数。原因原因:0001.021m00.1200.1011),(bAA121000100.011如果在求解时将如果在求解时将1,2行交换行交换,即即0.99991.00,1.0021xx回代后得到回代后得到0.9998与与 很接近！很接近！T

13、x)00010001.1,99989999.0(*例例2.解线性方程组解线性方程组(用用8位十进制尾数的浮点数计算位十进制尾数的浮点数计算)321643.5072.12623.4712.3132103218xxx 解解:此方程组同例此方程组同例1,若用若用Gauss消去法计算会有小数消去法计算会有小数作除数的现象作除数的现象,若采用换行的技巧，则可避免若采用换行的技巧，则可避免。(,)A b321643.5072.12623.4712.3132108行交换行交换因此因此列元素为列元素为的的绝对值最大绝对值最大很小,很小,3 ,1,2 10138a 31rr1233210623.4712.316

14、43.5072.128),()1()1(bA83121105.05.0mm101.05.03103.0102.001018015.0103176.00643.5072.12),()2()2(bA92722629.032m54138685.05.031041555186.0001018015.0103176.00643.5072.12),()3()3(bA回代后可得回代后可得:绝对值最大不需换行)3()3(3333abx 54138685.01041555186.039257367.0)2(223)2(23)2(22axabx103176.01018015.05.03x05088607.0)1(

15、113)1(132)1(12)1(11axaxabx49105820.0事实上事实上,方程组的准确解为方程组的准确解为:Tx)367257384.0 ,050886075.0,491058227.0(*上述方法是在上述方法是在GaussGauss消去法的基础上消去法的基础上,利用换行避免利用换行避免小主元作除数小主元作除数,该方法称为该方法称为 GaussGauss列主元消去法列主元消去法4、),(/)(:)(nnAnbnb),(/):1():1,()(:)(iiAnibniiAibibT对于对于1:1:1 ni 回代回代列列主主元元消消去去法法算算法法设设计计1、输入：输入：方程组维数方程组

16、维数 n，矩阵矩阵A，右端项，右端项 b 和控制精度和控制精度 eps2、对于对于1:1nk(1),(max),(kiAkuAnik 选主元选主元(2)如果如果 ，停止运算，停止运算epskuA),(控制小主元控制小主元(3)如果如果 uk,转转(4)，否则执行，否则执行)1:,()1:,(nkuAnkkA 换行换行3、如果如果 ，则停止，则停止 无解无解0),(nnA5、输出解输出解Tnb):1(计算行乘数公式(2.1)公式(2.2)(4),(/),:1(:),:1(kkAknkAknkA):1,(),:1():1,:1(:):1,:1(nkkAknkAnknkAnknkA 消元消元)(),

17、:1():1():1(kbknkAnkbnkbTT开始EPSnbA,输入输出无解信息k1x输出解EPSnnA|),(|nk kk1P选取主元素EPSP|消元换行停机回代求解TTTFFF三、Gauss列主元消去法的算法设计(一)流程图(二)自然语言n输入方程组的维数.11,2,1,2,1,),(njniabAij的元素增广矩阵EPS控制条件转移精度1:1.2nk对于PkkA),(1.2nki:2.2对于|),(|PkiA如果).(7,|3.2输出无解信息则转到如果EPSP 0,),(IiPkiA则选主元1:nkj对于wjkA),(),(),(0jkAjIA),(0jIAw,:15.2nki对于,

18、1:1nkj对于),(),(/),(kimkkAkiA),(),(*),(),(jiAjkAkimjiA).(7,|),(|.3无解则转到如果EPSnnA换行消元则如果,4.20kI)(),(/)1,(.4nxnnAnnA1:1:1.5 nk对于)(nnnnnabx)(1)()(iiinijjiijiiiaxabx),()(),()1.(1kkAjxjkAnkAxnkjk0Snkj:1对于SjxjkAS)(*),(SSnkA)1,()(),(/kxkkAS.8),(,),2(),1(.6并转输出解nxxxxT回代输出无解信息.7停机.8上述过程中的储存空间需要:注意:1:1,:1),(njni

19、jiA增广矩阵1:1,:1),(nknkikim行乘数矩阵nkkx:1),(解向量SIPkji,0储存空间需要较大(三)自然语言的改进选主元n输入方程组的维数.1EPS控制条件转移精度1,2,1,2,1,),(njniabAij的元素增广矩阵1:n-1.2k对于PkkA),(1.2k:ni2.2对于|),(|PkiA如果,),(0则IiPkiA.7,|3.2则转到如果EPSP 1:nkj对于wjkA),(),(),(0jkAjIA),(0jIAwnki:15.2对于1:1nkj对于),(),(/),(kimkkAkiA),(),(*),(),(jiAjkAkimjiA.7,|),(|.3则转到

20、如果EPSnnA),(),(/),(,kiAkkAkiA该条语句可改为：为了节省存储空间),(),(*),(),(jiAjkAkiAjiA改为：换行消元)(),(/)1,(.4nxnnAnnA0S则如果,4.20kI 1:1:1.5 nk对于)1,(),(/)1,(,nnAnnAnnA该条语句可改为：为了节省存储空间1:1,:1),(njnijiA增广矩阵1:1,:1),(nknkikim行乘数矩阵nkkx:1),(解向量1:1,:1),(njnijiA回代停机.8输出无解信息.7.),(,),2(),1(.6并转8输出解nxxxxT)(),(/kxkkASSSnkA)1,(SjxjkAS)(*),(nkj,1对于SnjAjkAS)1,(),(:改为)1,(),(/,nkAkkAS该条语句可改为：为了节省存储空间注意：为提高算法效率，下列矩阵和向量共用了相同的存储空间：