第1章线性方程组的直接方法

§5.1引言在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的插值问题，经济运行中的投入产出问题以及大地测量、机械与建筑结构的设计计算问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因此线性方程组的求解对于实际问题是极其重要的。第五章方程组的数值解法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa...............22112222212111212111nnnnnnnnbbbBxxxXaaaaaaaaaA...,...,...............2121212222111211解线性方程组的直接法简记为Ax=b，其中(6.1)常见的线性方程组是方程个数和未知量个数相同的n阶线性方程组，一般形式为线性方程组的数值解法一般有两类：1.直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。2.迭代法:就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解)三、特殊矩阵1)对角矩阵2)三对角矩阵3)上三角矩阵4)上海森伯(Hessenberg)阵5)对称矩阵6)埃尔米特矩阵7)对称正定矩阵8)正交矩阵9)酉矩阵10)初等置换阵11)置换阵定理1设A∈Rnⅹn,A非奇异⇔…?定理2若A∈Rnⅹn对称正定矩阵，则⇒…?定理3若A∈Rnⅹn对称矩阵，则对称正定矩阵=…?定理4(若当标准型)…,211sJJJJAPP其中.1000010001000iikkiiiiJ对角化的条件：1）…；2）….§5.2高斯消去法5.2.1高斯消去法的基本思想先用一个简单实例来说明Gauss法的基本思想例5.1解线性方程组72452413221321321xxxxxxxx①②③解:该方程组的求解过程实际上是将中学学过的消元法标准化,将一个方程乘或除以某个常数,然后将两个方程相加减,逐步减少方程中的未知数,最终使每个方程只含有一个未知数,从而得出所求的解。整个过程分为消元和回代两个部分。（1）消元过程第1步:将方程①乘上(-2)加到方程②上去,将方程①乘上加到方程③上去,这样就消去了第2、3个方程的项,于是就得到等价方程组211x1232323231425313222xxxxxxx④⑤第2步：将方程④乘上加到方程⑤上去，这样就消去了第3个方程的项，于是就得到等价方程组852x4218724132332321xxxxxx⑥这样，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。（2）回代过程回代过程是将上述三角形方程组自下而上求解，从而求得原方程组的解：6,1,9321xxx前述的消元过程相当于对原方程组741021524312321xxx的增广矩阵进行下列变换(表示增广矩阵的第行）702145241312~bAA21323250214013121213)2()21(rrrr42187002140131223)85(rr同样可得到与原方程组等价的方程组⑥iri由此看出,高斯消去法解方程组基本思想是设法消去方程组的系数矩阵A的主对角线下的元素,而将Ax=b化为等价的上三角形方程组,然后再通过回代过程便可获得方程组的解。换一种说法就是用矩阵行的初等变换将原方程组系数矩阵化为上三角形矩阵,而以上三角形矩阵为系数的方程组的求解比较简单,可以从最后一个方程开始,依次向前代入求出未知变量这种求解上三角方程组的方法称为回代,通过一个方程乘或除以某个常数,以及将两个方程相加减,逐步减少方程中的变元数,最终将方程组化成上三角方程组,一般将这一过程称为消元,然后再回代求解。11,,,xxxnn通常把按照先消元,后回代两个步骤求解线性方程组的方法称为高斯（Gauss）消去法。5.2.2高斯消去法算法构造我们知道,线性方程组(6.1)用矩阵形式表示为nnnnnnnnbbbxxxaaaaaaaaa2121212222111211(6.3)解线性方程组（6.1）的高斯（Gauss）消去法的消元过程就是对(6.3)的增广矩阵进行行初等变换。将例6.1中解三阶线性方程组的消去法推广到一般的阶线性方程组并记则高斯消去法的算法构造归纳为：nn),,2,1,(,)1()1(njibbaaiiijij⑴消元过程,斯消去法的消元过程由n-1步组成：第1步设,把(6.3)中的第一列中元素消为零,令0)1(11a)1(1)1(31)1(21,,,naaa),,3,2(,)1(11)1(11niaamii用乘以第1个方程后加到第个方程上去,消去第2～n个方程的未知数,得到即1imi1x)2()2(bxA)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11nnnnnnnbbbxxxaaaaaaanjibmbbamaaiiijiijij,3,2,)1(11)1()2()1(11)1()2(其中第k步（k=2,3,…,n-1）继续上述消元过程，设第k-1次消元已经完成，得到与原方程组等价的方程组knkknkknnknkkknkkknnbbbbxxxxaaaaaaaaa)()2(2)1(121)()()()()2(2)2(22)1(1)1(12)1(11nkjibmbbamaakkikkikikkjikkijkij,1,)()()1()()()1(),,1()()(nkiaamkkkkikik记为其中)()(kkbxA只要,消元过程就可以进行下去,直到经过n-1次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组,记为0)(kkka)()(nnbxA或者写成)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa)()()2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbxabxaxabxaxaxa即(6.7)（2）回代过程就是对上三角方程组（6.7）自下而上逐步回代解方程组计算，即)1,2,,1(,)(1)()()()(niaxabxabxiiijnijiijiiinnnnnn（3）高斯消去法的计算步骤：①消元过程;设计算1,,2,1,0)(nkakkk对nkkjibmbbamaaaamkkikkikikkjikkijkijkkkkikik,,2,1,)()()1()()()1()()(②回代过程1,,2,1)(1)()()()(nniaxabxabxiiijnijiijiiinnnnnn(4)高斯消去法流程图，(5)Gauss消去法计算量≈331n①消元计算:aij(k+1)=aij(k)-mikakj(k)(i,j=k+1,k+2,…,n)第一步计算乘数mik,mik=ai1/a11(i=2,3,…,n)需要n-1次除法运算,计算aij(2）(i,j=2,3,…,n)需要(n-1)2次乘法运算及(n-1)2次加减法运算,第k步加减法次数乘法次数除法次数123…n-1(n-1)2(n-2)2(n-3)2…1(n-1)2(n-2)2(n-3)2…1(n-1)(n-2)(n-3)…1合计n(n-1)(2n-1)/6n(n-1)(2n-1)/6n(n-1)/2乘除法次数：MD=n(n-1)(2n-1)/6+n(n-1)/2=1/3n(n2-1)加减法次数：AS=n(n-1)(2n-1)/6算法.()()0,1,2,,,.kkkkaknAA若，覆盖，消去：对于nk,,2,1.1.,0)1(则停止计算若kka(2)1,,()/.()1,,.ikikkkiiikkijijikkjiknimaabbmbiijknaama对于对于,1,,.2ni回代：对于,)1(iibx,,,1)2(jijiixaxxnij对于./)3(iiiiaxx乘除法运算工作量.),,1,(,:,)(:,:)1(2)1(nkjiknbknaknmkkikijik次乘法次乘法次除法步消元：第消元过程乘除法次数：回代过程乘除法次数：nnnnkknnkkn6522131131)(2112)(111(1)(1)21nnknnk总的乘除法运算次数：nnn312331非零判断次数最多为：11()(1)21nnknnk行交换的元素个数为：11()(1)21nnknnk1(1)2nknnk21(1)(21)6nknnnk5.2.3高斯消去法的适用条件定理1方程组系数矩阵的顺序主子式全不为零则高斯消去法能实现方程组的求解。证明上三角形方程组是从原方程组出发，通过逐次进行“一行乘一数加到另一行”而得出的，该变换不改变系数矩阵顺序主子式的值。设方程组系数矩阵，其顺序主子式nijaA)(01111mmmmmaaaaA（m=1,2,…，n）经变换得到的上三角形方程组的顺序主子式0)()2(22)1(11)()2(2)2(22)1(1)1(12)1(11mmmmmmmmmaaaaaaaaaA所以能实现高斯消去法求解（m=1,2,…，n）定义5.1设矩阵每一行对角元素的绝对值都大于同行其他元素绝对值之和nijaA)(niaanijjijii,,2,1,1则称A为严格对角占优矩阵。定理1.1若方程组的系数矩阵A为严格对角占优，则用高斯消去法求解时，全不为零。bAx)(kkka证:先考察消元过程的第1步,因A为严格对角占优,故故,又根据高斯消去公式得于是njjaa2111011)1(11aanjiaaaaajiijij,,3,2,,1111)2(nijjjinijjijnijjijaaaaa2111122)2()(12111111injjiinijjijaaaaaa再利用方程组的对角占优性,由上式可进一步得111111111112)2()(aaaaaaaaaaaiiiiiiiiinijjij又由njiaaaaajiijij,,3,2,,1111)2(得11111111)2(aaaaaaaaaiiiiiiiiii故有niaaiinijjij,,3,2,)2(2)2(当A为严格对角占优时,,余下的子阵仍是对角占优的，从而又有。依次类推全不为零。定