《解线性方程组的直接方法主元素方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的直接方法主元素方法ppt课件.ppt（58页珍藏版）》请在三一办公上搜索。
1、1,Gauss消去法简单易行，但其计算过程中，要求,(称为主元素)均不为零，因而适用范围小，只适用于从1到,先看一个例子。,阶顺序主子式均不为零的矩阵A，计算实践还表明,Gauss消去法的数值稳定性差,当出现小主元素时,会严重,影响计算结果的精度,甚至导出错误的结果.,2 主元素法,(2-10a),式（2-10a）中所有系数均有2位有效数字.,解 为减少误差，计算过程中保留3位有效数字.,按Gauss消去法步骤，第一次消元得同解方程组,例2 求解方程组,2,3,第二次消元得,回代得解,容易验证，方程组（2-10）的准确解为,显然两者相差很大.但若在解方程组前,先把方程的次序,4,交换一下,如把
2、（2-10a）改写成,再用Gauss消去法求解，消元后得同解方程,5,产生上述现象的原因在于舍入误差.因为按式(2-10)的,方程顺序进行消元时，主元,回代得解,与准确解相同.,都比较小，以它们为除数就增长了舍入误差，从而导致,计算结果不准确。为了在计算过程中，抑制舍入误差的增,长,应尽量避免小主元的出现.如例2中第二种解法,通过交,换方程次序,选取绝对值大的元素作主元.基于这种想法导,出了主元素法.,6,2.2.1 列主元素法,为简便起见，我们用方程组（2-1）的增广矩阵,表示它，并直接在增广矩阵上进行运算.,7,是在每次消元前，在要消去未知数的系数中找到,绝对值最大的系数作主元，通过方程对
3、换将其换到,对角线上，然后进行消元。具体步骤如下：,第一步：首先在矩阵（2-11）的第1列中选取绝对值,则,中第1行与第,矩阵为,，然后进行第一次消元，得矩阵,最大的元，比如为,将(2-11),行互换.为方便起见,记行互换后的增广,列主元素法基本思想:,8,第二步：在矩阵,的第2列中选主元，比如,使,将矩阵,行与第,行互换，再进行第二次消元，得矩阵,的第2,第,步：在矩阵,的第 k 列中选主元，如,使,将,的第,行与第,行互换，进行第,次消元.,9,如此经过,步，增广矩阵（2-11）被化成上三角,形，最后由回代过程求解。,在上述过程中，主元是按列选取的，列主元素法由此,得名.例2中的第二种解法
4、就是按列主元素法进行的.,2.2.2 全主元素法,如果不是按列选主元，而是在全体待选系数,中选取主元，则得到全主元,素法，其计算过程如下：,p11,10,第一步：在全体系数,值最大的元作为主元，并通过行与列的互换把它换到,中选取绝对,的位置，然后进行第一次消元,得到矩阵,第,步：在矩阵,的右下方,阶子矩阵,的所有元素,中,选取绝对值最,大的元作为主元,并通过行与列的互换将它换到,的位置，然后进行第,次消元.,经过,次消元后,得到与方程组(2-1)同解的上三角,形方程组,再由回代过程求解.,11,例3 用主元素法求解线性方程组,计算过程保留三位小数。,解按列主元素法，求解过程如下:,p13,p9
5、,12,13,由回代过程得解,按全主元素法，求解过程如下:,p11,14,15,由回代过程得解,例3的计算结果表明，全主元素法的精度优于主元素法,这是由于全主元素是在全体系数中选主元，故它对控制,同解方程组为,16,舍入误差十分有效。但全主元素法在计算过程中，需同,时作行与列的互换，因而程序比较复杂，计算时间较长.,列主元素法的精度虽稍低于全主元素法，但其计算简单,工作量大为减少,且计算经验与理论分析均表明,它与全,主元素法同样具有良好的数值稳定性，故列主元素法是,求解中小型稠密线性方程组的最好方法之一.,17,2.3 直接三角分解法,2.3.1 Gauss 消去法的矩阵形式,如果用矩阵形式表
6、示，Gauss消去法的消元过程是对,方程组（2-1）的增广矩阵A，b进行一系列行初等变换，,将系数矩阵A化成上三角形矩阵的过程.,将系数矩阵A化成上三角形矩阵的过程，也等价于用一串初等矩阵去左乘增广矩阵，因此消元过程可以,通过矩阵运算来表示。,我们知道,对矩阵进行一次初等行变换,相当于用相应的初等矩阵去左乘原来的矩阵.,18,的系数矩阵A的顺序主子式不为零,在Gauss消去法中,第一次消元时等价于用单位下三角阵,设方程组,19,其中,（2-12）,左乘矩阵,即,20,进行第二次消元时,等价于用矩阵,左乘,其中,于是有,一般地，第k次消元等价于用矩阵,其中,经过,次消元后得到,（2-13）,左乘
7、矩阵,21,21,22,因为,的逆矩阵存在。容易求出,均为非奇异阵，故它们,23,（2-14）,令,23,24,于是有,(2-15),即,（2-16）,25,其中,为单位下三角矩阵，,为上三角矩阵。,这说明，消元过程实际上是把系数矩阵A分解成单位,下三角阵与上三角矩阵的乘积的过程。,26,上述分解称为杜利特尔（Doolittle）分解，也称为,的问题就变得十分容易，它等价与求解两个三角形方程组,和,分解.,当系数矩阵进行三角分解后，求解方程组,因此，解线性方程组问题可转,27,化为矩阵的三角分解问题。,2.3.2 矩阵的三角分解,正如Gauss消去法要在一定条件下才能进行到底一样,矩阵A也必须
8、满足一定条件才能进行三角分解.,定理2.设为n阶方阵，若的顺序主子式,证明 当,均不为零，则矩阵存在唯一的Doolittle分解。,时，因为,由.段的讨论，存在矩阵,p33,28,其中,使得,29,由行列式的性质易得,的各阶顺序主子式,满足,假定结论对j=k-1成立,即,30,且,于是有,因为,故存在矩阵,31,其中,，使得,且,32,使得,其中,为单位下三角矩阵，,为上三角矩阵。存在性得证。,按归纳法原理，存在初等矩阵,由式（2-15）得,33,由于单位下（上）三角阵的逆仍是单位下（上）三角阵,所以,对A是奇异的情况，可参考1.,惟一性。设矩阵A有两种Doolittle分解,当A非奇异时，,
9、均为非奇异矩阵.于是由,式（2-17），有,上（下）三角阵的乘积仍为上（下）三角阵，故有,(2-17),p27,34,两个矩阵相等就是他们的对应元素都相等，比较A与,下面讨论如何如何对A进行LU分解.,LU的对应元素，即可得出L,U中元的计算公式. A=LU,即,由矩阵的乘法法则，得,35,设已定出U的第一行至第r-1行元素, 与L的第一列至第r-1列元素,(注意到当 ),故有,又,故有,(U的第r行),(L的第r列),36,由此可得计算,和,的公式,（2-18）,37,计算过程应按第1行,第1列,第2行，第2 列，.的顺序进行.,2.计算U的第r行，L的第r列,计算U的第1行, L的第1列,
10、具体步骤如下：,38,的三角分解。,例4 求矩阵,解 按式（2-18）,39,所以,40,两个矩阵相等就是他们的对应元素都相等，比较A与,下面讨论如何如何对A进行LU分解.,LU的对应元素，即可得出L,U中元的计算公式. A=LU,即,由矩阵的乘法法则，得,41,计算过程应按第1行,第1列,第2行，第2 列,.的顺序进行.,2.计算U的第r行，L的第列r,计算U的第1行, L的第1列,具体步骤如下：,42,紧凑格式。,根据式（2-18）的特点，矩阵的三角分解可按以下格,式及顺序进行。这种格式既便于记忆，又便于计算,称为,表2-1,43,框从外到内进行。每一框中先算行，从左向右依次计算,；再算列
11、，自上而下求,2.计算方法：按行计算时，需将所求元,的对应元,逐项减去,所在行左面各框的元,乘以,所在列上面各框相应的元,按列计算,时，在作上述运算后还需除以,所在框的对角元,例4中矩阵,说明：,计算顺序：将,按表2-1列好，计算时按,的三角分解按,44,(2) 2,(2) 2,(3) 3,表2-2,紧凑格式计算，结果见下表。,45,所以,即由,2.3.3 直接三角分解法,如果线性方程组,的系数矩阵已进行三角分解,则解方程组,两个三角形方程组,等价于求解,46,可求出,(2-20),(2-19),47,再由,解得,(2-22),(2-21),48,容易看出,式（2-20）与式（2-18）的运算
12、规律相同,2-1的最后一列，按,的计算方法即,表2-3是求解线性方程组的紧凑格式，其计算顺序与,故在利用三角分解求解方程组时，只需把右端向量,计算方法与三角分解相同。按表2-3计算后，再按式,列在表,(2-22) 即可求出方程组的解,可求出,49,表2-3,50,例： 用杜利特尔分解法求解线性方程组,解： 设,51,按式（2-18）,52,所以,由,即,解得,由,即,解得,54,解 按表2-3计算,例5 用紧凑格式解线性方程组,55,（3）3,(2) 2,(5) 5,(6) 6,56,所以,解方程组,得原方程组的解,57,用三角分解法求解线性方程组的乘除运算量也是,数量级。由于在求出,和,后,和,就无,需保留了，故上机计算时可把,和,存在,所在的单元，回代时,取代,整个计算过程中不需,要增加新的存贮单元.,从三角分解法的推导及例中可以看出，系数矩阵的,三角分解与右端项无关.因而在计算系数矩阵相同而,右端项不同的一系列方程组时用三角分解法更为简便.,58,详细内容可参看2.,也可以把矩阵,分解成一个下三角矩阵,单位上三角矩阵,与一个,的乘积，矩阵的这种分解称为克劳特,(Crout)分解.在这种分解下,解线性方程组问题也转化成,求解两个三角形方程组问题.,素法，如果系数矩阵中元素的数量级相差悬殊，求解时有,
