【文档说明】第二高斯消元法及其计算机实现-课件.ppt，共(33)页，460.535 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77224.html

以下为本文档部分文字说明：

第二节高斯消元法及其计算机实现第五章解线性代数方程组的直接方法n第一节求解线性代数方程组的基本定理线性代数方程组的一般形式(1)mnAxbAR用矩阵形式表示为其增广矩阵记为1111221121122

2221122nnnnmmmnnmaxaxaxbaxaxaxbaxaxaxb11121121222212,nnmmmnmaaabaaabAAbaaab第一节求解

线性代数方程组的基本定理AxbAA线性方程组有解的充分必定理1（线性代数方程组要条件是：秩（）=秩有解判定理（别））(1)()(),AxbAArnAxb线性方程组有解（即相容）时，秩定理2秩则方程组存在唯一解。(2)()(),rArArnAxb方程组有无穷多解。通解原方

程组一个特解对应齐次方程组的基础解系的线性组合。222,||||min||||mnAxbxxxxAxb常见是，称为欠定方程组（方程数少于未知数）此时，从的无穷多个解中需求出范数最小的解。即求使，满足。22()()()||||minrArAAxbmnbARAxxbAx方程组无

解（即不相容）。常见是，称为超定方程组（又称矛盾方程组）此时，向量不在的列空间之中，原方程组无解，但可求出最小二乘意义下的解。即求使MATLAB实现:x=A\b11112211211222221122nnnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb

本章介绍求解阶线性方程组的数值方法数值求解方法有以下三条途径（三种框架）直接法：利用Gauss消元或矩阵分解，通过有限次运算可求出精确解。迭代法：构造迭代格式，产生迭代序列，通过无限次迭代过程求解。有限次截断得近似解。极小化方法：构造二次模函数，用迭代过程

求二次模函数的极小化问题，即变分法（经n次运算，理论上得精确解）要求A对称正定(S.P.D)用增广矩阵表示为同解初等变换组化为同解的上三角方程将原方程组求解gUxbAxgUxbAxRAbAxnn

第二节高斯消元法及其计算机实现AbUg

)1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaa)()()2(2)2(2)2(22)1

(1)1(1)1(12)1(11nnnnnnnbabaabaaa三角形方程组包括上三角形方程组和下三角形方程组，是最简单的线性方程组之一。上三角方程组的一般形式是：),......,2,1(0.............................................

.......................................................111112222211212111niabxabxaxabxaxabxaxaxaiinnnnnnnnnnnnnnn

其中一、三角形方程组的解法1242343444573131313131xxxxxxxxx用回代法求解线性方程组例43424314212341(1313)/30(75)(750)244121,,,)(1,2,0:,1)TTxxxxxxxxx

xxxx所以，解为（解1,,1/)(/1niaxabxabxnikiikikiinnnn为求解上三角方程组，从最后一个方程入手，先解出xn=bn

/ann,然后按方程由后向前的顺序，从方程中依次解出xn-1,xn-2,…,x1。这样就完成了上三角方程组的求解过程。这个过程被称为回代过程其计算步骤如下：11212322232429xxxxxx用回

代法求解线性例、方程组1231232/21(21)/11(93121)/41,,)(1,1,):1xxxxxx所以，解为（解21111)(1)22nininnn求解一个三角形方程组需次除法与

（次乘法。12111111,,,,/()/(2,3,,)niiiikkiikxxxxbaxbaxain下三角形方程组可以参照上三角形方程组的解法来求解，下三角形方程组的求解顺序是从第一个方程开始，按从上到

下的顺序，依次解出：其计算公式为：如上解三角形方程组的方法称为回代法.1111211222211220,1,2,,nnnnnniiaxbaxaxbaxaxaxbain下三角方程组的一般形式为：其中高斯消元法是一个古老的直接法,由它改进得到

的选主元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题。高斯消元法的求解过程,可大致分为两个阶段:首先,把原方程组化为上三角形方程组,称之为“消元”过程;然后,用逆次序逐一求出上三

角方程组(原方程组的等价方程组)的解,称之为“回代”过程.高斯“消元”过程可通过矩阵运算来实现。具体过程如下：二、高斯消元法12312312323623493263Gaussxxxxxxxxx用消元法求解方程例组11/1/21/

2/01,3623194326321][11313111212111)1(aamaamanbAA增广矩阵：解：11121,:11LAxLb1L=,完成第一步消元得(2)(2)(2)223232222212110,/1/(

1)111,11amaaLLLAxLLb=,完成第二步消元得3332632332321xxxxxx3231231233/31(32)(321)162362

13111,1,1xxxxxxxxx回代求得故所求解为011032106321)2(A330032106321)3(A将方程组Ax=b的系数矩阵与右端

项合并为11121121222212,nnnnnnnaaabaaabAbAaaab(1)(1)(1)1111(1)(1)(1)(1)(1)12(1)(1)(1)1...,,.

..,,...nnnnnnaabAAbaab记(1)(1)1(1)11111,,0,...,0.TALLa对的第一列构造使1(1)11111110,,2,...,iiaamina（）（）：设取第一步2111111n

mLm(1)(1)(1)(1)111211(2)(2)(2)(1)(2)(2)(2)(2)(2)2222112(2)(2)(2)2...0...,,...,,0...nnnnnnnaaabaabLAAbaab

(2)(1)(1)11(2)(1)(1)112,,,2,,,2,,ijijijiiiaamainjnbbmbin(1)(1)1(1)(1)11AxbLLAx

Lb对方程组从左边乘以(1)(1)(1)1111(1)211(1)(1)(1)111...1...1nnnnnnaabmLAaabm(2)(2)2222(2)2203,...,iiaamina：设，，第二步

取(2)(2)32222(1)(1)(1)(1)(1)1112131,1(2)(2)(2)(2)22232,2(2)(1)(3)(3)(3)(3)221333,3(3)(3)(3)3,111,100000nnnnnn

nnmALmaaaabaaabLALLAaaAbaab-对的第二列构造-使(2)22(2)22,iiama(1)(1)2121LLAxLLb(3

)(2)(2)22(3)(2)(2)22,,3,,3,4,...,ijijijiiiaamaijnbbmbin(1)(1)(1)(1)111211(2)(2)(2)(2)2222322(2)(2)(2)22(1)(1)(1)(1)1112131,

(2)(2)(2)22232,(3)(3)333,(331...10...10...100000nnnnnnnnnnnaaabaabmLAaabmaaaaaaaaaa

--(1)1(2)2(3)(3)3)(3)(3),nnnbbAbab进行到第k步消元时()(1)()kkkAAAk下一步消元，从，将的第列的对角元以下的元素化为零。(1)(1)(1)(1)(1)11121311

(2)(2)(2)(2)222322(3)(3)(3)3333()()()()1()()()1,1,11()()()(),1..........................................nnnkkkkkkkkkkkkkkkkkkkkknknknnnaa

aabaaabaabAaabaabaaab()()()0,(1,...,)kkikkkkikkkkaamaiknGaussL设取，构

造变换阵,,111111TkkkknkIlemm(1)()kkkALA消元计算递推公式：()(1,2,,1)kkkakn称为主元素.()()(1)()()(1

)()()1,,1/21,,3kkikikkkkkkijijikkjkkkiiikkiknmaaaamajknbbmb（）（），（）(1)(1)(1)(1)11112211(2)(2)(2)22222()()nnnnnnnnnnaxaxaxbaxaxbaxb

即用回代过程求解上三角方程组，即可得解向量(x1*,x2*,…,xn*)T.是高斯消元的前提)1,,2,1(,0)(nkakkk(1)(1)121121nnLLLAxLLLb(1)(1)(1)(1)111211

(2)(2)(2)()2222()()000nnnnnnnnaaabaabAab最后得求解的全过程包括两个步骤：消元和回代1.顺序消元2.回代求解()()()()()1/()/1,2,,1nnnnnnnkkk

kkkjjkkjkxbaxbaxaknn()()(1)()()(1)()()1,,11,,1/21,,3kkikikkkkkkijijikkjkkkiiikkkniknmaaaamajknbbmb（）（），（）步消元计算后，第的二维数组存放一个用

用动态存储方式。在计算机中计算时，采存储方式kAnn),,1;,,1(),,1()1()()(nkjnkiaankimakijkijikkik

)()(1,)()(1,1)(,1)(1)()3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)(................................

..........knnkknknkkkkkkkkkkkkknnnkaaaaaaaaaaaaaaaaAikm)1(kijaUIL消元过程全部完成后，原来的二维数组中存放的元素实际上是一个新的矩阵，记为FAFAA用动态形式表示为

)(1,321)3(3)3(1,3)3(333231)2(2)2(1,2)2(23)2(2221)1(1)1(1,1)1(13)1(12)1(11nnnnnnnnnnnnnnFammmmaaammaaaamaaaa

aA选主元基本思想用高斯消元法求解线性方程组时,为避免小的主元.在进行第k步消元前,应该在第k列元素(i=k,…,n)中找出第一个出现的绝对值最大者,例如，再把第ik个方程与第k个方

程组进行交换,使成为主元.我们称这个过程为选主元.由于只在第k列元素中选主元,通常也称为按列选主元.)(kika()()maxkkkikikkinaa)(kija如果在第k步消元前,在第k个方程到第n个方程所有的xk到xn的系数(i=k,…,n;j=k,…,n)中,找出绝对值最大者,

例如()kkika三、选主元高斯消元法再交换第k,ik两个方程和第k,jk列,使成为主元.称这个过程为完全选主元.不论是哪种方式选出主元,而后再按上面介绍的计算步骤进行消元的计算,一般都称为选主元的高斯消元法.在实际计算中,常用按列选主元的高斯消元法.()kkkija()(),maxkkkkiji

jkijnaa()()()()()()()||max||,,1,,,(1)),(,,2kkkkkkkkkkkikikkinkkkkkkjijkjkjijijkikkiikikinaaAAbikTikaajkknTaaaaTbbTbbbbT

对每一步第步消元，分两步确定使对增广矩阵使列主元高斯消元法具体做法是：选列主元换行在计算机上，用一个工作单元来完成，对，包括消元计算算法列主元高斯消元法解线性方程组Ax=b停机。信息输出失败则认为如果使确定、选列主元步。循环执行到第对、

置,,0det,0,max251,,2,11det1kikiiknikkikkkkaaaainkdetdet,),,1,(,4,3kkikjikjkbbnkkjaaki否则交换行步转出执行第、如果

具体执行行交换要通过工作单元T。TbbbbTTaaaaTkkkkiikkjijikjkj;;;;。、输出解向量、否则停机。输出失败信息则认为如果、回代求解、FTnnniinijjijiinnnnnnnnkkAAbbbxanniababbabb

aaadet,,),,,(8detdet7)1,2,,2,1(/)(/,,0,6detdet5211(3)),,1((2)/(1),,2,14kikiikjikijijkkikikikbabbnkjaaaaaamankki

、消元计算假设求解是在四位浮点十进制数的计算机上进行0.0001x1+x2=1x1+x2=2将两个方程对调，得x1+x2=20.0001x1+x2=1在四位浮点十进制数的计算机上,上式为x1+x2=2即x1+x2=2(0.1000×101

-0.00001×101x2=1x2=1（1-0.0001)x2=1x1+x2=2消元，得解得：x1=1，x2=1现在我们再用列主元法解例4例5用列主元消去法解方程组解第一次消元对因列主元素为a31(1),故先作行交换E1E3,然后进行

消元计算可得-0.002x1+2x2+2x3=0.4x1+0.78125x2=1.38163.996x1+5.5625x2+4x3=7.4178-0.002220.4[A(1)|b(1)]=10.7812501.38163.9

965.562547.41783.9965.562547.4178[A(2)|b(2)]=0-0.61077-1.0010-0.4747102.00292.00200.40371由此回代,得x=(1.9272,-0.69841,0.90038)T与精确解x=(1.9273,

-0.69850,0.90042)T相比较是比较准确的.3.9965.562547.4178[A(3)|b(3)]=02.00292.00200.4037100-0.39050-0.35160第二次消元对[A(2)|b(2)],

因列主元素为a32(2),故先作行交换E2E3,然后进行消元计算可得