第二章线性代数方程组的数值方法

第二章线性代数方程组的数值方法第一节线性代数方程组的直接解法第二节线性代数方程组的迭代解法本章内容各种直接解法的基本原理及构造迭代格式的基本原理。重点第一节线性代数方程组的直接解法直接解法是用有限次代数运算得到方程组解的方法。如无舍入误差，则由直接解法得到的解就是精确解。但舍入误差以及误差的积累是无法避免的，因此直接解法给出的仍是近似解。本节给出的各种直接解法都是适用于计算机的有效方法。它们对稠密系数阵的较低阶方程组（几百个方程）以及带状系数阵的高阶方程组（几千个方程）都很有效。高斯消去法主元消去法高斯-约当消去法三角分解法对称矩阵的三角分解---乔列斯基法三对角阵的三角分解----追赶法方程组的逆矩阵解法与矩阵求逆直接解法列主元法全主元法设有n阶线性代数方程组方程组的矩阵形式为可简记为BAX本节假定A非奇异或其行列式不为零，方程组有解且唯一。一、高斯消去法高斯消去法是解线性方程组的经典方法，由它改进得到的选主元的消去法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题高斯消去法举例11221733230636321321321xxxxxxxxx112217332521321321321xxxxxxxxx第一步消元过程(1)(2)(3)消x1式(1)/6(4)(5)(6)式(5)-式(4)×2式(6)-式(4)623725213232321xxxxxxx(7)(8)(9)高斯消去法623725213232321xxxxxxx62327215213232321xxxxxxx消x2式(8)/2式(12)-式(11)×(3/2)(7)(8)(9)(10)(11)(12)43412721521332321xxxxxx(13)(14)(15)高斯消去法43412721521332321xxxxxx第二步回代过程321321xxx(13)(14)(15)由式（15）得到x3，代入式（14）得到x2，再代入式（13）得到x1。结果如下高斯消去法高斯消去法的步骤)0()0(2)0(21)0(1)0(2)0(22)0(221)0(21)0(1)0(12)0(121)0(11nnnnnnnnnnbxaxaxabxaxaxabxaxaxa第一步消元)1()1(3)1(32)1(2)1(2)1(23)1(232)1(22)1(1)1(13)1(132)1(121nnnnnnnnnnbxaxaxabxaxaxabxaxaxax原方程（一）消元过程高斯消去法niababbabbnjiaaaaaaaaabbnjaaaaiiiiijiijjiijijjj2,/,2,//2,/0)0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)1(1)0(11)0(1)1(1)0(11若第k-1步消元的结果)1()1(1)1(1)1()1()1(1)1(1)1()1(1)1(1)1(11)2(2)2(23)2(232)1(1)1(13)1(132)1(121knnknnkknkkknkkknkknkkkkkkkkkknknkkkkkknnnnbxaxaxabxaxaxabxaxaxbxaxaxbxaxaxax)()(1)(1)()(1)(1)1(1)1(1)1(11)2(2)2(23)2(232)1(1)1(13)1(132)1(121knnknnkknkkknkknkkkkkkknknkkkkkknnnnbxaxabxaxaxbxaxaxbxaxaxbxaxaxax第k部消元高斯消去法)(,0)(,),(,/)1(,/0)()()1()1()()()1()1()()1()1()()1()1()()1(nikanikbabbnjikaaaaabbnjkaaaakikkkkikkikikkjkikkijkijkkkkkkkkkkkkjkkjkkk以上为高斯消去法的消元过程的算法。高斯消去法第n-1步消元结果)1()1(1)()2(2)1(1)1()1(1)()(1)2(2)2(23)1(1)1(13)1(1210111nnnnkknnnnnnkknkkknnbbbbbaaaaaaaaa及（二）回代过程以上为高斯消去法的回代过程的算法。高斯消去法102212423321321321xxxxxxxxx题1试用高斯消去法解下列方程（小数点后取4位数字计算）。解:第一步消元6667.83333.116667.06667.23333.003333.16667.303333.03333.01BA高斯消去法第二步消元6365.70909.36667.05455.2003636.0103333.03333.01BA回代结果0000.30001.20000.1X高斯消去法题2试用高斯消去法解下列方程。52213614282321321321xxxxxxxxx高斯消去法题2试用高斯消去法解下列方程。52213614282321321321xxxxxxxxx解:第一步消元967090220141BA第二步消元1837900110141BA回代215X二、主元消去法（称为主元）11221732521321321321xxxxxxxxx6237521323321xxxxxx)1(kkka主元消去法（1）Gauss消去法消x1得消x2无法进行，因为。0)1(22a12102221xyzxyzxyz121212121212121212102101010210101021010zyzyzyx（2）考虑如下线性方程组的Gauss消去法假定计算能保证10位有效数字，则在此精度内x=y=z=1是真解。消x无法求解。原因:第一个主元过小。解（一）:主元消去法12)0(1110a12102221xyzxyzxyz12102212zyxzyxzyx33222yzyzyx选较大主元消x结果x=y=z=1选择绝对值尽可能大的系数作为主元，会减少舍入误差的影响，提高解的精度，并保证算法的稳定性。解（二）:主元消去法主元消去法在每一步消元中选取绝对值尽可能大的主元的高斯消去法称为主元消去法。列主元法全主元法有两种主元消去法：主元消去法在消去的系数前，先从中选取绝对值最大者作为主元，交换第k行与此主元所在的行，再按高斯消去法消去第k行之后的方程中的系数，只要方程是可解的，这一过程定能执行到底。（一）列主元法kxkx)1()1(1)1(,,,knkkkkkkkaaa主元消去法)1()1(1)1(1)1()1()1(1)1(1)1()1(1)1(1)1(11)2(2)2(23)2(232)1(1)1(13)1(132)1(121knnknnkknkkknkkknkknkkkkkkkkkknknkkkkkknnnnbxaxaxabxaxaxabxaxaxbxaxaxbxaxaxax解：举例：列主元法第一步选列主元为，交换第1行与第3行996.331a再消元计算得.40371.00020.20028.2047471.00010.161077.008563.10010.13920.11)()1()1(bA第二步选列主元为,交换第2行与第3行，再消元计算得0028.232a.35159.039047.00020157.09996.0108563.10010.13920.11)()2()2(bA.474710010.161077.0040371.00020.20028.208563.10010.13920.11)()2()2(bA回代计算得到解为这个例题的精确解是9273.1,69850.0,90043.0123xxx,)900423.0,698496.0,92730.1(Tx,)88888.0,68695.0,9300.1(Tx高斯消去法的结果是主元消去法（二）全主元法n阶线性代数方程组矩阵形式行交换变量顺序？列交换变量顺序？（2）从方程组系数中选出绝对值最大者，作为第一个主元。交换第一行与此元素所在的行，并交换第一列与此元素所在的列，使选出的主元位于第一行第一列，一般地，在第k次消元之前，先从中选出绝对值最大者作为主元，假定其位于第p行第q列，然后交换系数阵A及右端项阵B的第k行与第p行，并交换A的第k列与第q列，且交换序列向量的第k个元素与第q个元素的内容。（1）设置一标识变量顺序的一维向量，其初始内容为基本思想Tn,,3,2,1),1(njiaij；),()1(njikakij主元消去法（3）按高斯消去法完成第k步消元，反复执行（2），直至消元过程结束；（4）回代求解，解的顺序就是序列向量所示的顺序。主元消去法解举例：全主元法解为x2和x3次序变化全主元法的精度略优于列主元法，这是由于全主元法是在全体系数中选主元，故它对控制舍入误差比较有效。但全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂，计算时间较长。列主元法的精度虽稍低于全主元法，但其计算简单，工作量大为减少，实践表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好方法之一。一般采用列主元法。说明：主元消去法题3分别用列主元消去法和全主元消去法求解线性方程组。000.3643.5072.1000.2000.2623.4712.3000.1000.1000.3000.2001.0321321321xxxxxxxxx精确解舍入到4位有效数字为Tx)3675.0,05104.0,4904.0(主元消去法关于主元法的几点讨论（1）有两类系数阵可以避免选主元，直接使用高斯消去法便可得到满意的结果。它们是：严格对角占优矩阵和对称正定矩阵。严格对角占优矩阵是指其元素满足)1(,niaanijijii或以列为准，其元素满足)1(,njaanjiijjj严格对角占优矩阵必定是非奇异阵，且每步消元后，仍保持对角占优的性质，因此，不必选主元。对称正定矩阵其行列式大于零，方程组可解，且在每步消元中，剩下的子阵仍保持对角占优和对称性，因此不必选主元。行列（2）关于病态方程002755853.0006324242.0068528.2446949.1446949.1012671.1