Chapter3线性方程组的解法(上)-109P-ZTY

下午5时34分0秒1下午5时34分0秒1线性方程组第三章2在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。这些方程组的系数矩阵大致分为两种，一种是低阶稠密矩阵（例如，阶数大约为≤150），另一种是大型稀疏矩阵（即矩阵阶数高且零元素较多）。3.1引例及问题综述3.1.1引例引例1电路问题（电网络KCL、KVL、回路电流法等等)3.1.2问题综述nnnnnnnbxaxabxaxa1111111大型稠密矩阵？？3直接法就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。这类算法中最基本的高斯消去法及其某些变形。这类方法是解低阶稠密矩阵方程组的有效方法，近十几年来直接法在求解某些大型稀疏矩阵方程组方面取得了较大进展。线性方程组的数值解法一般分为直接法和迭代法两类。4迭代法基本思想与解一元非线性方程的迭代法类似。从任意给定的初始近似解向量出发，按照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法。可以用有限步运算算出具有指定精确度的近似解。迭代法主要有：雅可比（Jacobi)迭代法；高斯-赛德尔（Gauss-Seidel)迭代法。迭代法具有需要计算机的存贮单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点，但存在收敛性及收敛速度问题。迭代法是解大型稀疏矩阵方程组（尤其是由微分方程离散后得到的大型方程组）的重要方法。53.2线性方程组的直接解法我们知道，下面有3种方程的解我们可以直接求出：niabxaaadiagAiiiinn,,1,),,,(2211①nilxlbxllllllAiiijjijiinnnn,,1,1121222111②对角矩阵下三角矩阵1,,,122211211niuxubxuuuuuuAiinijjijiinnnn③消元法就是对方程组做些等价的变换，变为我们已知的3种类型之一，而后求根上三角矩阵7对方程组，作如下的变换，解不变①交换两个方程的次序②一个方程的两边同时乘以一个非0的数③一个方程的两边同时乘以一个非0数，加到另一个方程因此，对应的对增广矩阵(A,b)，作如下的变换，解不变①交换矩阵的两行②某一行乘以一个非0的数③某一个乘以一个非0数，加到另一行83.2.1高斯消去法的基本思想高斯消去法是一个古老的求解线性方程组的方法，但由它改进、变形得到的选主元素消去法、三角分解法仍然是目前计算机上常用的有效方法。思路首先将A化为上三角阵，再回代求解。=9例1用高斯消去法解方程组1231231232221(1)3241/2(2)395/2(3)xxxxxxxxx解第1步：将方程（1）乘上（-3/2）加到方程（2）上去，将方程（1）乘上（-1/2）加到方程（3）上去，则得到与原方程组等价的方程组3.2.1高斯消去法的基本思想（续）102/5932/14231222321321321xxxxxxxxx123232322211(4)282(5)xxxxxxx其中方程（4），（5）已消去了未知数x1。第2步：将方程（4）乘上2加到方程（5），消去（5）式中未知数x2，得到与原方程组等价的三角形方程组3.2.1高斯消去法的基本思想（续）113.2.1高斯消去法的基本思想（续）12323322211(6)0xxxxxx最后由上述方程组，用回代的方法，即可求得原方程组的解。x3=0，x2=1，x1=-1/2这种求解过程，称为具有回代的高斯消去法。12010011101222228201110122212/59312/14231222],[bA2/5932/14231222321321321xxxxxxxxx用高斯消去法解方程组的基本思想是用矩阵行的初等变换将系数矩阵A约化为具有简单形式的矩阵（如：上三角阵），而三角形方程组是很容易解的——（回代）3.2.1高斯消去法的基本思想（续）增广矩阵13通常把这种按照先消元，再回代两个步骤求解线性方程组的方法称为高斯（Gauss)消去法。3.2.2高斯消去法的算法构造设有n个未知数的线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(3.1)14引进记号nnnnnnaaaaaaaaa212222111211Anxxx21xnbbb21bbAx(3.1)可用矩阵形式表示(3.2)为了讨论方便，记，假设A为非奇异矩阵（即设det(A)≠0）。nnija)()1()1(AATnbb),()1()1(1)1(bb3.2.2高斯消去法的算法构造（续）15第1步（k=1）：设计算乘数：0)1(11a(1)11(1)11,(2,,)iiamina用mi1乘上第一个方程，加到第i个方程上去（i=2，…，n）（即施行行的初等变换Ri←Ri+mi1*R1，i=2，…，n），消去第2个方程～第n个方程的未知数x1，得到等价方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11nnnnnnnbbbxxxaaaaaaa3.2.2高斯消去法的算法构造（续）(1)消元过程16记为:A(2)x=b(2)；其中(2)(1)(1)11(2)(1)(1)11,(,2,3,,),(2,3,,)ijijijiiiaamaijnbbmbin3.2.2高斯消去法的算法构造（续）173.2.2高斯消去法的算法构造（续）第2步（k=2）：对线性方程组(3.3)中的第2，3，…，n个方程组成的n-1元方程组做类似于第1步的处理，消去除第一个方程之外的变元x2，得到第2步消元后的线性方程组18式中19第k步：（k=1，2，…，n-1）继续上述消去过程，设第1步～第k-1步计算已经完成，得到与原方程组等价的方程组()()()()(1)(1)(1)(1)1111211(2)(2)(2)2()(2222)kkkkkknkkkknknnnnnknxaaabxaaabaaabxbx记为A(k)x=b(k)；现进行第k步消元计算，设，计算乘数0)(kkka()(),(1,,)kikikkkkamikna用（mik）乘上式的第k个方程加到第i个方程（i=k+1，…，n），消去第i个方程（i=k+1，…，n）的未知数xk，得到与原方程组等价的方程组3.2.2高斯消去法的算法构造（续）20(1)(1)(1)111,n1(1)(1)(1),1(1)(1)(1)(1)1111121(2)(2)(2)22222()()()kkkkkkkkkknknnnnnkkkkkkkknnaabaabbxaaabxaabxaax简记为A(k＋1)x=b(k＋1)；其中A(k＋1)，b(k＋1)元素计算公式为：(1)()()(1)()()(1)()(1)(),(,1,,),(1,,)kkkijijikkjkkkiiikkkkkkaamaijknbbmbiknkkAAbb与前行元素相同，与前个元素相同。3.2.2高斯消去法的算法构造（续）21最后，重复上述约化过程，即k=1，2，…，n-1且设（k=1，2，…，n-1）共完成n-1步消元计算，得到与原方程组（3.1）等价的三角形方程组0)(kkkannnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa3.2.2高斯消去法的算法构造（续）223.2.2高斯消去法的算法构造（续）第1步在方程（3.4）的最后一个方程中解出xn，得（2）回代过程233.2.2高斯消去法的算法构造（续）第3步依次继续下去，一般可得xk的计算公式()()1(),(2,3,,1)nkkkkjjjkkkkkbaxxknna第2步将xn的值代入式（3.4）的倒数第二个方程，解出xn-1，得当k=1时，就完成了回代过程，得到所求的解。24将（3.1)约化为(3.4)的过程称为消元过程，（3.4）的求解过程称为回代过程，由消元过程和回代过程求解线性方程组的方法称为高斯消去法。11112211211222221122(3.1)nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb3.2.2高斯消去法的算法构造（续）25①消元计算()()(1)()()(1)()(),(1,,),(,1,,),(1,,)kikikkkkkkkijijikkjkkkiiikkamiknaaamaijknbbmbiknk=1，2，…，n-13.2.2高斯消去法的算法构造（续）定理3.1设线性方程组Ax=b，其中A∈Rn×n(Rn×n表示n阶方阵的集合）。（1）如果则可通过高斯消去法将Ax=b化为等价的上三角方程组，且有计算公式：()0(1,2,,)kkkakn26()()()()1(),(1,2,,1)nnnnnnkkkkjjjkkkkkbxabaxxknna②回代计算(2)如果A为非奇异矩阵时，可能有某，则在第k列存在有元素，于是可能通过交换（A，b）的第k行和第ik行元素，将调到（k，k）位置，然后再进行消元计算。于是，在A为非奇异矩阵时，只要引进行交换，则高斯消去法可将化为上三角方程组，且通过回代即可求得方程组解。0)(kkka)1(0)(nikakkkik)(kkikaAxb3.2.2高斯消去法的算法构造（续）有零怎么办？换掉继续算！27高斯消去法要求()0(1,2,,)kkkakn第k步消元的主元素3.2.2高斯消去法的算法构造（续）判断主元素的一个充要条件：()0(1,2,,)kkkakn定理3.2对矩阵A=(aij)n×n消元时，主元素的一个充要条件是矩阵的各阶顺序主子式()0(1,2,,)kkkakn283.2.2高斯消去法的算法构造（续）即293.2.3高斯消去法算法分析消元过程的计算量，高斯消去法消去过程分n-1步第k步的计算工作量为：1）计算乘数：需要作（n-k）次除法运算；2）消元：需作(n-k)2次乘法运算，和(n-k)2次加减法运算；3）计算b(k)：需作（n-k）次乘法运算和(n-k)次加减法运算；（1）高斯消去法的计算量302)1(6)12()1(2)1()()()(1111211