数值分析 线性方程组直接解法

第三章线性方程组直接解法第三章线性方程组直接解法返回前进第三章目录§1.Gauus消元法§2.主元素法2.1引入主元素法的必要性2.2列主元素法2.3全主元素法2.4解三对角方程组的追赶法§3.矩阵分解法3.1Gauss消去法的矩阵形式3.2矩阵的三角分解3.3直接三角分解法§4.平方根法与改进的平方根法§5.矩阵求逆§6.方程组的性态和条件数第三章线性方程组直接解法返回前进设n阶线性方程组：1)-(222112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa其矩阵形式为：Ax=b(2-2)其中：nnnnnnnnbbbbxxxxaaaaaaaaaA∶，：，2121212222111211在科学研究和工程技术中所提出的计算问题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法在数值计算中占有较重要的地位。第三章线性方程组直接解法返回前进求解Ax=b，曾经学过高斯（Gauss）消元法，克莱姆（Cramer）法则，矩阵变换法等，但已远远满足不了实际运算的需要，主要体现两个方面：一是运算的快速和准确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也曾指出过，Cramer法则在理论上是绝对正确的，但当n较大时，在实际计算中却不能用。如果线性方程组Ax=b的系数行列式不为零，即det(A)0，则该方程组有唯一解。第三章线性方程组直接解法返回前进线性方程组的数值解法解线性方程组的数值方法大致分为两类：请注意：由于在计算中某些数据实际上只能用有限位小数，即不可避免地存在着舍入误差的影响，因而即使是准确解法，也只能求到近似解。直接法在求解中小型线性方程组（≤100个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。1.直接法：指假设计算过程中不产生含入误差，经过有限步四则运算可求得方程组准确解的方法。2.迭代法：从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。这一章介绍计算机上常用的直接法，它们都是以Gauss消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。第三章线性方程组直接解法返回前进§1Gauss消元法Gauss消元法是最基本的一种方法，下例说明其基本思想:例1解线性方程组：3)-(2153181533126321321321xxxxxxxxx解：消去x1，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以18乘第一个方程加到第三个方程上可得同解方程组：3)(a)-(29317215791563232321xxxxxxx第三章线性方程组直接解法返回前进例1（续）上述Gauss消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为消元过程。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为回代过程。3)(b)-(2566522579156332321xxxxxx再消一次元得：二次消元后将方程化为倒三角形式，然后进行回代容易解出：x3=3,x2=2,x1=1。我们的目的，是要总结归纳出一般情况下的n阶线性方程组的消元公式和回代求解公式，从而得到求解n阶线性方程组的能顺利在计算机上实现的行之有效的算法。第三章线性方程组直接解法返回前进为能更清楚地得到算法，下面以4阶线性方程组为例总结求解步骤，并且很容易地可推广至一般的n阶线性方程组。4)-(2)1(44)1(443)1(432)1(421)1(41)1(34)1(343)1(332)1(321)1(31)1(24)1(243)1(232)1(221)1(21)1(14)1(143)1(132)1(121)1(11bxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxa）（或记为这些乘数实际上可记为第四个方程上消乘第一个方程加到第三分别并以个方程中乘第一个方程加到第二而以为乘数可以要消第二个方程中假定找乘数第一步4,3,2,,,,,,,,,0,:)1(11)1(11)1(11)1(4141)1(11)1(3131)1(11)1(21211)1(11)1(41)1(11)1(31)1(11)1(21)1(11)1(211)1(11iaalaalaalaalxaaaaaaaaxaii:,,,,)1()1()1()1(首先消元并简记为统一加上标bbAAbxA第三章线性方程组直接解法返回前进可以检查，分别以li1乘第一个方程加到第i个方程上可以完成第一次消元，得同解方程组：4)(a)-(2)2(44)2(443)2(432)2(42)2(34)2(343)2(332)2(32)2(24)2(243)2(232)2(22)1(14)1(143)1(132)1(121)1(11bxaxaxabxaxaxabxaxaxabxaxaxaxa变化以后的方程组系数及右边的常数项可总结出如下的计算公式：(2)(1)(1)1l(2)(1)(1)11,2,3,4ijijijiiiaalaijbblb完成第一次消元之后的方程组记为：A(2)x=b(2)第三章线性方程组直接解法返回前进Gauss消元法的基本步骤3（4阶）4,3,,:)2(22)2(222iaalxii首先找到乘数消第二步以方程组中第i个方程减去第二个方程乘li2(i=3,4)，完成第二次消元。4)(b)-(2)3(44)3(443)3(43)3(34)3(343)3(33)2(24)2(243)2(232)2(22)1(14)1(143)1(132)1(121)1(11bxaxabxaxabxaxaxabxaxaxaxa上标为3的系数和右端项可由下面公式计算：4,3,)2(22)2()3()2(22)2()3(jiblbbalaaiiijiijij第三章线性方程组直接解法返回前进第三步：消元（4阶方程组需进行3次消元）将上述A(3)X=b(3)中最后一个方程中的x3消为零：得：个方程乘以第四个方程减去第三找乘数43)3(33)3(4343,laal4)(c)-(2)4(44)4(44)3(34)3(343)3(33)2(24)2(243)2(232)2(22)1(14)1(143)1(132)1(121)1(11bxabxaxabxaxaxabxaxaxaxa然后可回代求解：由于A(4)为上三角形，所以可按变量的逆序逐步回代求原方程组的解：5)-(21,2,3,/)(/41)()()()4(44)4(44kaxabxabxklkkklkklkkk上述消元、回代求解过程很容易推广到一般的n阶线性方程组。经过上述消元步骤，得到同解的上三角形方程组：A(4)x=b(4)第三章线性方程组直接解法返回前进Gauss消元法的消元过程1、2（n阶）6)-(2)1()1(2)1(21)1(1)1(2)1(22)1(221)1(21)1(1)1(12)1(121)1(11nnnnnnnnnnbxaxaxabxaxaxabxaxaxa一般地，设n阶方程组：消元过程为：组：得原方程组的同解方程完成第一次消元个方程乘以第个方程减去将方程组中第记设第一步,),,3,2(1),,3,2(,0:1)1(11)1(11)1(11niliniaalaiii6)(a)-(2)2()2(2)2(2)2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnbxaxabxaxabxaxaxa将上方程组中第i个方程减去第2个方程乘以li2(i=3,…,n)，完成第二步消元。njiblbbalaaiiijiijij,,3,2,)1(11)1()2()1(11)1()2(其中：第三章线性方程组直接解法返回前进第k步：设第k1步消元后得原方程组的同解方程组为：6)(b)-(2)()()()()()()2(2)2(2)2(22)2(22)1(1)1(1)1(12)1(121)1(11knnknnkknkkknkknkkkknnkknnkkbxaxabxaxabxaxaxabxaxaxaxa得同解方程组：步消元完成第个方程乘以第个方程减去将上方程组中第记设,),,,1(),,1(/,0)()()(knkilkinkiaalaikkkkkikikkkk6)(c)-(2)1()1(1)1(1)1(1)1(11)1(1,1)()(1)(1)()2(2)2(21)2(12)2(22)2(22)1(1)1(11)1(11)1(12)1(121)1(11knnknnkknkkknknkkkkkkknkknkkkkkkkknnkkkknnkkkkbxaxabxaxabxaxaxabxaxaxaxabxaxaxaxaxa第k步消元后同解方程组中上标为k+1的元素的计算公式见下屏第三章线性方程组直接解法返回前进),,1,()()()1()()()1(nkjiblbbalaakkikkikikkjikkijkij其中：照此消元下去，完成n1次消元后，可将原方程组化成同解的上三角形方程组如下：(1)(1)(1)(1)(1)11112213311(2)(2)(2)(2)22223322(3)(3)(3)33333nnnnnnaxaxaxaxbaxaxaxbaxaxb()()(2-6)(d)nnnnnnaxb第三章线性方程组直接解法返回前进Gauss消元法的回代过程（n阶）回代过程：逐步回代求得原方程组的解7)-(21,2,,2,1/)(/1)()()()()(nnkaxabxabxnklkkklkklkkknnnnnn.,,,,),()1,,2,1(0,)()2(22)1(11)()(bAxGaussaaaankannnkkkkkk：消去法求解线性方程组使用才能均不为零而只有所有主元素为主元素称条件是：消元过程能进行到底的由以上讨论可知第三章线性方程组直接解法返回前进Gauss消元法的计算量由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。由消元法步骤知，第k次消元需作nk次除法，作(nk)(nk+1)次乘法，故消元过程中乘除法运算量为：112)1(3)1)((:nknnknkn乘法次数11)1(2)(:nknnkn除法次数nkknnknnknx1)1(2)(1:乘法：次；除法：运算量为：次乘法，因此回代过程次除法和需求回代过程中所以Gauss消去法的乘除法总运算量为：33)1(2)1(2)1(3232nnnnnnnnnnN7)-(21,2,,2,1/)(/1)()()()()(nnkaxabxabxnklkkklkklkkknnn