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

1第六章解线性方程组的数值方法§1引言§2高斯消元法§3选主元素的高斯消元法§4矩阵的三角分解§5向量和矩阵的范数§6解线性方程组的迭代法2§1引言在自然科学和工程中有很多问题的解决归结为求解线性方程组或者非线性方程组的数学问题。例如，电学中网络问题，用最小二乘法求实验数据的的曲线拟合问题，三次样条的插值问题，用有限元素法计算结构力学中一些问题或用差分发解椭圆型微分方程边值问题等等。在工程实际问题中产生的线性方程组，其系数矩阵大致有两种，一种是低阶稠密矩阵（这种矩阵的全部元素都存储在计算机的存贮器中）；另一类是大型稀疏矩阵（此类矩阵阶数高，但零元素较多，这类矩阵一般采用压缩存贮或仅存贮系数矩阵的非零元素）。本章讨论线性方程组的数值解法。3§2高斯消元法高斯消元法是一个古老的求解线性方程组的方法，但由它改进得到的选主元的高斯消元法则是目前计算机上常用的解低阶稠密矩阵方程组的有效方法。例1用高斯消元法解方程组解第1步：将方程（2.1）乘上（-3/2）加到方程（2.2）将方程（2.1）乘上（-1/2）加到方程（2.3）则得到与原方程等价的方程组2/5932/14231222321321321xxxxxxxxx（2.1）（2.3）（2.2）4282112223232321xxxxxxx其中方程（2.4），（2.5）已消去了未知数。第2步：方程（2.4）乘上2加到方程（2.5），消去（2.5）式中未知数，得到等价的三角形方程组由上述方程组，用回代的方法，即可求得原方程组的解。x1011222332321xxxxxx2/1,1,0123xxx（2.4）（2.5）2x5若用矩阵来描述消元法的约化过程，即为这种求解过程，称为具有回代的高斯消元法。从上例看出，用高斯法解方程组的基本思想是用矩阵的初等变换将系数矩阵约化为具有简单形式的矩阵（上三角矩阵，单位矩阵等），从而容易求解。下面讨论求解一般线形方程组的高斯消元法，设有n个未知数的线性方程组：01001110122222/59312/14231222],[bA28201110122216bxaxaxabxaxaxabxaxaxannnnnnnnnn22112222212111212111引进记号bbbxxxaaaaaaaaannnnnnnnbxA2121212222111211,,(2.7)(2.7)可用矩阵形式表示bAx(2.8)7为了讨论方便，记假设为非奇异矩阵（即设)。第1步（k=1）：设计算乘数用乘上（2.7）第一个方程，加到第i个中程上去，即施行行初等变换：.),(,)()1()1(1)1()1()1(bbbbaAAnijTnn0)1(11a),2()1(11)1(11niaamii)(1miA0)det(A),,2(,11niRmRRiii8(2.9)1xbbbxxxaaaaaaannnnnnn)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11消去第2到第n个方程的未知数，得到（2.7）的等价方程组其中（2.9）式中方框内元素为这一步需要计算的元素，计算公式为：)2()2(bxA记为9),,2(,),,2,(,)1(11)1()2()1(11)1()2(ninjibmbbamaaiiijiijijbbbbxxxaaaaaaaaaknkknknnknkkknkkknn)()()2(2)1(121)()()()2(2)2(22)1(1)1(12)1(11第k步：继续上述消元过程，设第1步至第k-1步计算已经完成，得到与原方程组等价的方程组。（2.10）10记为bAkkx)()(现进行第k步消元计算，设，计算乘数0)(akkk),,1(,)()(nkiaamkkkkikik用乘（2.10）的第k个方程加到第i个方程消去（2.10）中第i个方程的未知数得到原方程组的等价方程组：)(mik),,1(nki,xk11(2.11)bbbbbxxxaaaaaaaaaaaknkkkknknnkknknkkkkkknkkknn)1()1(1)()2(2)1(121)1()1(1,)1(,1)1(11)()()2(2)2(22)1(1)1(12)1(11简记为bAkkx)1()1(其中元素计算公式为：bAkk)1()1(,12重复上述约化过程，即且设，共完成n-1步消元计算，得到与原方程组（2.7）等价的三角形方程组个元素相同。前行元素相同，前与与（kknkinkjibbAAbmbbamaakkkkkkikkikikkjikkijkij)1)()()1()()()1()()()1(),,1(,),,1,(,)1,,2,1(0)(nkakkk(2.12),1,,2,1nkbbbxxxaaaaaannnnnnnn)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11(2.13)13用回代法，即可求得（2.13）的解，计算公式为：)1,,1(,)(1)()()()(niaxabxabxiiinijjiijiiinnnnn（2.14）元素称为约化的主元素。将（2.7）约化为（2.13）的过程称为消元过程；（2.13）求解过程（2.14）称为回代过程，由消元过程和回代过程求解线性方程组的方法称为高斯消元法。akkk)(14定理1（高斯消元法）设其中如果约化的主元素则可通过高斯消元法（不进行交换两行的初等变换）将方程组约化为三角形矩阵方程组（2.13），且消元和求解公式为：1.消元计算nnRA),,,2,1(0)(nkakkk,bAxbAx),,1(,),,1,(,),,1(1,,2,1)()()1()()()1()()(nkinkjinkinkbmbbamaaaamkkikkikikkjikkijkijkkkkikik152.回代计算)1,,1(,)(1)()()()(niaxabxabxiiinijjiijiiinnnnn当A为非奇异矩阵时，也可能有某但在第k列存在元素,0)(akkk)1(0)(nikkkkkia16于是可能通过交换（A，b）的第k行和第行将调到位置，然后再进行消元计算。于是，在A为非奇异矩阵时，只要引进行交换，则高斯消元法可将原线性方程组约化为三角形方程组（2.13），且通过回代法即可求得方程组的解。高斯消元法计算量:（1）消元计算：第k步1.计算乘数：需要作（n-k）次除法运算；2.消元：需作次乘法运算；3.计算：需作（n-k）次乘法运算；于是，完成全部消元计算共需作乘除运算的次数为s：kiakkik)(),(kkbAx。)1,,2,1(nk)(2knbk)(172)1(6)12()1(2)1()()(1111211)(nnnnnnnknknsnknknkkn（2）回代计算：共需要作n(n+1)/2次乘除运算。于是，用高斯消元法解的计算量为共需作)(nnRAbAx其中332)1(23nsnnMDnn（2.15）次乘除运算。18下面比较用高斯消元法和用克莱姆（Cramer）法则解20阶方程组的计算量。表6-1方法高斯消元法Cramer法则计算量3060次乘除法大约次乘法19105如果计算在每秒作次乘除法运算的计算机上进行，那么用高斯消元法解20阶方程组约需要0.03秒时间即可完成，而用克莱姆法则大约需小时完成（大约相当于年）。由此可知克莱姆法则完全不适用在计算机上求解高维方程组。105107103.11119§3选主元素的高斯消元法用高斯消元法解时，其中设A为非奇异矩阵，可能出现情况，这时必须进行带行交换的高斯消元法。但在实际计算中即使但其绝对值很小时，用作除数，会导致中间结果矩阵元素数量级严重增长和舍入误差的扩散,使得最后的计算结果不可靠。例2设有方程组0)(akkk0)(akkkakkk)(Ak)(bAx210001.02121xxxx20解精确解为[方法1]：用高斯消元法求解(用具有舍入的3位浮点数进行运算))00010001.1,99989999.0(Tx21111000100.0,bA1000021m10000100000110001000.0回代得到计算解。与精确解比较,这是一个很坏的结果。00.0,00.121xx21回代求解。对于用具有舍入的3位浮点数进行运算，这是一个很好的计算结果。方法1计算失败的原因，是用了一个绝对值很小的数作除数，乘数很大，引起约化中间结果数量很严重增长，再舍入就使得结果不可靠了。11000100.0211,000100.021,21mrrbA00.100.1021100.1,00.112xx[方法2]用具有行交换的高斯消元法(避免小主元)。22由这个例知，在采用高斯消元法解方程组时，小主元可能导致计算失败，故在消元法中应避免采用绝对值很小的主元素。对一般方程组，需要引进选主元的技巧，即在高斯消元法的每一步应该选取系数矩阵或消元后的低阶矩阵中选取绝对值最大的元素作为主元素，保持乘数以便减少计算过程中舍入误差对计算解的影响；同时，对同一个数值问题，用不同的计算方法，得到的结果的精度大不一样，一个计算方法，如果用此方法的计算过程中舍入误差得到控制，对计算结果影响较小，称此方法为数值稳定的；否则，如果用此计算方法的计算过程中舍入误差增长迅速，计算结果受舍入误差影响较大称此方法为数值不稳定。因此，我们解数值问题时，应选择和使用数值稳定的计算方法，否则，如果使用数值不稳定的计算方法去解数值计算问题，就可能导致计算失败。,1ikm233.1完全主元素消元法设有线性方程组其中A为非奇异矩阵。方程组的增广矩阵为,bAxbaaaabaaabaaannnnnjinnbA2122222111121111,第1步（k=1）:首先在A中选主元素,即选择，使ji11,0maxnj1ni11,1aaijji24再交换[A，b]的第1行与第行元素，交换A的第1列与第列元素(相当于交换未知数与)，将调到(1，1)位置(交换后为简单起见增广阵仍记为[A，b]，其元素仍记为)然后，进行消元计算。i1j1x1xj1aji11baiij,第k步：继续上述过程，设已完成第1步到第k-1步计算，[A,b]约化为下述形式（仍记元素为为元素为）：Ak)(bakij)(,bi25第k步选主元区域对于做到（3）(1)选主元素：选取使1,,2,1nkjikk,nnnknkknkknnkkbaabaab