第4章_线性方程组直接解

计算方法课件第4章线性方程组的直接解法§4.1引言在自然科学和工程技术中,很多问题归结为解线性方程组.有的问题的数学模型中虽不直接表现为含线性方程组,但它的数值解法中将问题“离散化”或“线性化”为线性方程组.因此线性方程组的求解是数值分析课程中最基本的内容之一.线性方程组:结束)1.4(22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa常记为矩阵形式Ax=b(4.2)1计算方法课件此时A是一个n×n方阵,x和b是n维列向量.根据线性代数知识若|A|≠0,(4.2)的解存在且唯一.关于线性方程组的解法一般分为两大类,一类是直接法,即经过有限次的算术运算,可以求得(4.1)的精确解(假定计算过程没有舍入误差).如线性代数课程中提到的克莱姆算法就是一种直接法.但该法对高阶方程组计算量太大,不是一种实用的算法〔１〕.实用的直接法中具有代表性的算法是高斯消元法,其它算法都是它的变形和应用.另一类是迭代法,它将(4.1)变形为某种迭代公式,给出初始解x0,用迭代公式得到近似解的序列｛xk｝,k=0,1,2,,在一定的条件下xk→x*(精确解).迭代法显然有一个收敛条件和收敛速度问题.这两种解法都有广泛的应用,我们将分别讨论,本章介绍直接法.结束2计算方法课件§4.2高斯(Gauss)消元法高斯消元法是一种古老的方法.我们在中学学过消元法,高斯消元法就是它的标准化的、适合在计算机上自动计算的一种方法.4.2.1高斯消元法的基本思想例1解方程组(4.3)(4.4)(4.5)3946572132321321321xxxxxxxxx第一步,将(4.3)乘-2加到(4.4)；(4.3)乘-1加到(4.5),得到(4.3)(4.6)(4.7)462431323232321xxxxxxx3结束计算方法课件第二步,将(4.6)乘-2/3加到(4.7),得到(4.3)(4.6)(4.8)32032043132332321xxxxxx回代:解(4.8)得x3,将x3代入(4.6)得x2,将x2,x3代入(4.3)得x1,得到解x*=(2,1,-1)T容易看出第一步和第二步相当于增广矩阵［Ａ:b］在作行变换,用ri表示增广阵［A:b］的第i行:441620130321361941572321:3132122rrrrrrbA结束4计算方法课件320413200013032132332rrr由此看出上述过程是逐次消去未知数的系数,将Ax=b化为等价的三角形方程组,然后回代解之,这就是高斯消元法.4.2.2高斯消元法公式记Ax=b为A(1)x=b(1),A(1)和b(1)的元素记为和,i,j=1,2,,n.第一次消元,目的是消掉第二个方程到第n个方程中的x1项,得到A(2)x=b(2),这个过程须假定≠0.)1(ija)1(ib)1(11a结束5计算方法课件)2()2()2()2(2)1(1)2()2(2)1(1)2(2)2(22)1(12)1(11),,3,2()1()1(2)1(1)1()1(2)1(1)1(2)1(1)1(22)1(21)1(12)1(11)1()1(:00:11bAbbbaaaaaaabbbaaaaaaaaabAnnnnnnrrlrninnnnnnniii在［A(1):b(1)］中,红方框中的元素是要化为0的部分；［A(2):b(2)］中,红方框中的元素全部已发生变化,故上标由(1)改(2),计算公式为:结束6计算方法课件)1(11)1()2()2(1)1(11)1()2()1(11)1(110blbbaalaaaaliiiijiijijii(i=2,3,,n)(i,j=2,3,,n)(i=2,3,,n)(i=2,3,,n)第k次消元(1≤k≤n-1)设第k-1次消元已完成,且≠0,此时增广矩阵如下:)(kkka)()()2(2)1(1)()()2(2)1(1)()()2(2)2(22)1(1)1(12)1(11)()(:knkkknnkknnnknkkkkkkkkbbbbaaaaaaaaaaabA结束7计算方法课件本次消元的目的是对框内部分作类似第一次消元的处理,消掉第k+1个方程到第n个方程中的xk项,即把到化为零.计算公式如下:)(,1kkka)(knka)()()1()1()()()1()()(0kkikkikikikkkjikkijkijkkkkikikblbbaalaaaal(i=k+1,,n)(i,j=k+1,,n)(i=k+1,,n)(i=k+1,,n)只要≠0,(k=1,2,,n-1)消元过程就可以进行下去.当k=n-1时,消元过程完成,得:)()2(2)1(1)()2(2)1(1)2(22)1(12)1(11)()(:nnnnnnnnnbbbaaaaaabA)(kkka结束8计算方法课件它的方阵部分A(n)是一个上三角形矩阵,它对应的方程组是一个上三角形方程组,只要≠0,就可以回代求解,公式为)(nnna)(1)()()()(iiinijjiijiiinnnnnnaxabxabx(i=n-1,n-2,,1)综合以上讨论,高斯消元法解线性方程的公式为:1消元①令(i,j=1,2,…,n)iiijijbbaa)1()1(,结束9计算方法课件)()()1()()()1()1()()(0kkikkikikkjikkijkijkikkkkkikikblbbalaaaaal(i=k+1,k+2,,n)(i,j=k+1,k+2,,n)(i=k+1,k+2,,n)(4.9)2回代,若≠0)(nnna)(1)()()()(iiinijjiijiiinnnnnnaxabxabx(i=n-1,n-2,,1)(4.10)结束②对k=1到n-1,若≠0,进行:(i=k+1,k+2,,n))(kkka10计算方法课件4.2.3高斯消元法的条件以上过程中,消元过程要求≠0(i=1,2,,n-1),回代过程则进一步要求≠0,但就方程组Ax=b讲,是否等于0是无法事先看出的.)(nnna)(iiia)(iiia注意A的顺序主子式Di(i=1,2,,n)在消元过程中不变.这是因为消元所作的变换是“将某行的若干倍加到另一行”上,据线性代数知识,此类变换不改变行列式的值.若高斯消元过程已进行了k-1步(此时当然应有≠0,i≤k-1),这时计算A(k)的顺序主子式:)(iiia(1)111(1)(2)21122(1)(2)(1)111221,1(1)(2)()1122kkkkkkkkDaDaaDaaaDaaa结束11计算方法课件)(1)1(111iiiiiaDDaD有递推公式(i=2,3,,k)显然,,可知,消元过程能进行到底的充要条件是Di≠0,(i=1,2,,n-1),若要回代过程也能完成,还应加上Dn=｜A｜≠0,综合上述有:00)(iiiiaD定理4.1高斯消元法消元过程能进行到底的充要条件是系数阵A的1到n-1阶顺序主子式不为零；Ax=b能用高斯消元法解的充要条件是A的各阶顺序主子式不为零.4.2.4高斯消元法的计算量估计消元过程的工作量,参看公式(4.9),k是消元次数,k=1,2,,n-1,第k步消元时,计算lik(i=k+1,,n)需要n-k次除法；计算(i,j=k+1,,n)需要(n-k)2次乘法及(n-k)2次加减法；计算需要n-k次乘法及n-k次减法,合计:)1(kija)1(kib结束12计算方法课件乘除法次数加减法的次数111122)1(6)12)(1()()(nknknnnnnknkn111122)1(26)12)(1()(2)(nknknnnnnknkn回代过程的工作量,参见公式(4.10),求xk需n-k次加减法,n-k次乘法和1次除法,合计为乘除法次数12)1()1(nknnkn加减法次数12)1()(nknnkn总的运算次数为乘除法(当n较大时)333323nnnn结束13计算方法课件加减法(当n较大时)36)12)(1(3nnnn一般讲乘除法的运算比加减法占用机时多得多,往往只统计乘除法次数而称高斯消元法的运算量为次.33n§4.3选主元的高斯消元法在上节的算法中,消元时可能出现=0的情况,高斯消元法将无法继续；即使≠0,但1,此时用它作除数,也会导致其它元素数量级严重增加,带来舍入误差的扩散,使解严重失真.)(kkka)(kkka)(kkka例2线性方程组3200001.100001.02121xxxx准确解是(1,1)T.结束14计算方法课件现设我们的计算机为四位浮点数,方程组输入计算机后成为103000.0101000.0101000.0102000.0101000.0101000.0214xx(4.11)用高斯消元法:l12=0.2×106,r2=r2-l12×r162164102000.0101000.0102000.00101000.0101000.0xx回代:x2=0.1000×10=1,x1=0,解严重失真.若将r1和r2交换.101000.0103000.0101000.0101000.0101000.0102000.0214xx消元,l12=0.5×10-5,r2=r2-l12×r1101000.0103000.0101000.00101000.0102000.021xx结束15计算方法课件回代,x1=0.1000×10,x2=0.1000×10,得到准确解.从上例中可以看出,对方程组作简单的行交换有时会显著改善解的精度.在实际使用高斯消元法时,常结合使用“选主元”技术以避免零主元或“小主元”出现,从而保证高斯消元法能进行或保证解的数值稳定性.4.3.1列主元消元法设已用列主元消元法完成Ax=b的第k-1次消元(1≤k≤n-1),此时方程组Ax=b→A(k)x=b(k),有如下形式:)()()2(2)1(1)()()()()2(22)1(12)1(11)()(:knkkknnkknknkkkkkkbbbbaaaaaaabA(4.12)结束16计算方法课件进行第k次消元前,先进行①、②两个步骤:①在方框内的一列内选出绝对值最大者,即,确定ik.若=0,则必有方框内的元素全为零,此时易证｜A｜=｜A(k)｜=0,即方程组Ax=b无确定解,应给出信息退出计算.)()(,maxkiknikkkiaak)(,kkika②若≠0,则交换ik行和k行元素即)(,kkika)(,)(kjikkjkaa)()(kikkkbb(kjn)然后用高斯消元法进行消元.这样从k=1做到k=n-1,就完成了消元过程,只要｜A｜≠0,列主元高斯消元法必可进行下去.结束17计算方法课件4.3.2全主元消元法在(