第三章 线性方程组数值解法

3.1问题的提出在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的插值问题，经济运行中的投入产出问题以及大地测量、机械与建筑结构的设计计算问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因此线性方程组的求解对于实际问题是极其重要的。第3章线性方程组解法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa...............221122222121112121111112111212222212......,,...............nnnnnnnnaaaxbaaaxbAXbxbaaa常见的线性方程组是方程个数和未知量个数相同的n阶线性方程组，一般形式为简记为Ax=b，其中(3.1)一般b≠0,当系数矩阵A非奇异(即detA≠0)时，方程组（3.1）有惟一解。11121121222212...............nnnnnnnaaabaaabAaaab写为增广矩阵形式为：[Ab]Crameri=1,2,...,nnnnnn=20,iiDxD1910利用高等代数中的法则：需计算n+1个阶行列式，而一个阶行列式需！次乘法运算。总共需要（＋1）！次乘法。当时，21！＝5.10910利用每秒10（100亿）次的计算机需要162年的时间。线性方程组的数值解法一般有两类：1.直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。2.迭代法:就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解)3.2消去法3.2.1三角方程组的解法先用一个简单实例来说明Gauss法的基本思想例3.1解线性方程组123233321123315371522216163321xxxxxxxxx回代过程所需要计算量：乘除法1＋2＋...+n3.2.2高斯消去法我们知道,线性方程组(3.1)用矩阵形式表示为1111121212222212nnnnnnnnxbaaaaaaxbaaaxb(3.3)解线性方程组（3.1）的高斯（Gauss）消去法的消元过程就是对(3.3)的增广矩阵进行行初等变换。记(1)(1),1,(,1,2,,)ijijiniaaabijn⑴消元过程,高斯消去法的消元过程由n-1步组成：第1步设,把(3.3)中的第一列中元素消为零,令0)1(11a)1(1)1(31)1(21,,,naaa(1)11(1)11,(2,3,,)iialina用乘以第1个方程后加到第个方程上去,消去第2～n个方程的未知数,得到即1ili1x)2()2(bxA(1)(2)(1)(1)(1)(1)(1)(1)(1)(111211,1111211,1(1)(1)(1)(1)212222,1(1)(1)(1)(1)12,1nnnnnnnnnnnnAAaaaaaaaaaaaaaaaa1)(2)(2)(2)2222,1(2)(2)(2)2,122113311nn11(2)(1)(1)1100r+(-l)rr+(-l)r...r+(-l)r2i2nnnnnnnijijijaaaaaaaalan其中1jn第k步（k=2,3,…,n-1）继续上述消元过程，设第k-1次消元已经完成，得到与原方程组等价的方程组(1)(1)(1)(1)111211,1(2)(2)(2)2222,1()()(),1()()(),1nnnnkkkkkknknkkknknnnnaaaaaaaaaaaaa(1)()()111kkkijijikkjaalakinkjn()()(1,,)kikikkkkalikna记只要,消元过程就可以进行下去,直到经过n-1次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组0)(kkka(1)(1)(1)(1)111211,1(2)(2)(2)2222,1()(),1nnnnnnnnnnaaaaaaaaa(1)(1)(1)(1)11112211,1(2)(2)(2)22222,1()(),1nnnnnnnnnnnnnaxaxaxaaxaxaaxa即(3.7)（2）回代过程就是对上三角方程组（3.7）自下而上逐步回代解方程组计算，即(),1()()(),11(),(1,,2,1)nnnnnnnniiinijjjiiiiiaxaaaxxina（3）高斯消去法的计算步骤：①消元过程;设计算1,,2,1,0)(nkakkk对()()(1)()()111kikikkkkkkkijijikkjalaaalakinkjn②回代过程(),1()()(),11(),(1,,2,1)nnnnnnnniiinijjjiiiiiaxaaaxxina(4)Gauss消去法计算量≈331n消元计算:第k步除法次数：n-k求消元因子乘法次数：(n-k)(n-k+1)消元第k步共：(n-k)(n-k+2)消元过程需要回代计算:对方程组的高斯消元法一共11()(2)nknknk3233nnn(1)2nn方程组Ax=b的系数矩阵A经过顺序消元逐步化为上三角型A(n),相当于用一系列初等变换左乘A的结果。事实上，第1列消元将A(1)=A化为A(2)，若令：21131110001000100001nlLll(1)11(1)11,(2,3,,)iialina则根据距阵左乘有L1A(1)=A(2)(5)高斯消去法的适用条件(6)高斯消去法的另外一种理解第2列消元将A(2)化为A(3)，若令：2322100001000100001nLll(2)22(2)22,(3,4,,)iialina(1)(1)(1)(1)111211,1(2)(2)(2)2222,1(k)()()(),1()()(),1Annnnkkkkkknknkkknknnnnaaaaaaaaaaaaak对矩阵做一些行变换，相当于左乘变换矩阵L1,2,,11-1-1-1kkkkknkLlll(1)(2)(2)(3)(1)()121(1)()121111121(1)=(U,y)=(U,y)L=P(b)(U,y)nnnnnnLAALAALAALLLAALLLAA即而显然为一下三角矩阵，见55LA=LUb=Ly0011,2,,11111kkkkknkLlll00(1)(1)(1)(1)1112131(2)(2)(2)2122232(3)(3)3132333()12111,1nnnnnnnnuuuuluuuLllUuulluLUaaaaaaaaaaaaaaaaAnnnnnnnn3213333231223222111312111231231231233151831526xxxxxxxxx用高斯消去法求方程组12331512331512331537153715183115002222221216752916000164443－－－－－－－－－于是我们得到与原方程组同解的三123233321123+3=15371522216=163321xxxxxxxxx角方程组－－=－通过回代易得解为＝＝＝一般线性方程组使用高斯消去法求解时，在消元过程中可能会出现的情况，这时消去法将无法进行；即使，但它的绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺陷。0)(kkka0)(kkka3.2.3追赶法(特殊矩阵的高斯消去法)在数值计算中,有一种系数矩阵是三对角方程组nnnnnnnnnfffffxxxxxbacbacbacbacb1321132111133322211简记为Ax=f,A满足条件（1）（2）（3）011cb)1,3,2,0(nicacabiiiii0nnab3.2.4列主元高斯消去法第k步的消元因子交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为akk(k)，称这样的akk(k)为主元素，并称使用主元素的消元法为主元素法根据主元素选取范围分为：列主元素法、行主元素法、全主元素法记笔记()()(1,,)kikikkkkalikna主元素法的意义例3.2用高斯消去法求下列方程组的解211021215xxxx解：确定乘数，再计算系数52110m5)2(25122122)2(22102101bamaa假设计算在4位浮点十进值的计算机上求解,则有5555555510101000002.010210101000001.0101，这时方程组的实际形式是5252151010110xxx由此回代解出,但这个解不满足原方程组,解是错误的。这是因为所用的除数太小使得上式在消元过程中“吃掉”了下式，解决这个问题的方法之一就是采用列选主元高斯消元法。即按列选绝对值大的系数作为主元素，则将方程组中的两个方程相交换，原方程组变为1,021xx110221521xxxx得到消元后的方程组125522(110)1210xxx这时5511012102，因而方程组的实际形式是12221xxx由此回代解出,这个结果是正确的1,121xx可见用高斯消去法解方程组时,小主元可能导致计算失败,因为用绝对值很小的数作除数,乘数很大,引起约化中间结果数量级严重增长,再舍入就使得计算结果不可靠了,故避免采用绝对值很小的主元素。以便减少计算过程中舍入误差对计算解的影响。列主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对角线位置后进行消元的方法。例3.4用列主元高斯消去法解下列线性方程组10x1-19x2-2x3=3-20x1+40x2+x3=4x1+4x2+5x3=5解：选择-20作为该列的主元素，计算l21=10/-20=-0.5l31=1/-20=-0.0510-19-23-204014-20401410-19-2314551455x3=-1.76511x2=2.35230x1=4.41634记笔记列选主元素的计算方法与高斯消去法完全一样,不同的是在每步消元之前要按列选出主元-204014-204014-20401401