线性方程组的直接解法.ppt

线性方程组的直接解法,概述高斯消去法矩阵分解及其在解线性方程组中的应用矩阵的条件数和方程组的性态,December16,2019,yfnie,2,1.1数值解法的必要性,求：,的解的值，根据克莱姆(Gramer)法则可表示为两个行列式之比：,1概述,December16,2019,yfnie,3,如：,若用每秒万亿次（1012）浮点乘法运算的计算机（当前国内运算速度最快）全天工作，完成这些计算约需30年。若使用一般的个人电脑，每秒完成十亿次（109）浮点乘法运算，则完成这些计算约需3万年。,计算一个阶行列式需要做个乘法，求解上述方程共做次乘除法。,研究数值方法的必要性,December16,2019,yfnie,4,1、直接法：只包含有限次四则运算。假定在计算过程中不产生舍入误差，计算结果是原方程组的精确解。,2、迭代法：基于一定的递推公式建立逼近方程组近似解的序列。收敛性是其前提，然后还有收敛速度以及误差估计等问题。,Remark：由于运算过程中舍入误差的确存在，实际上直接方法得到的解也是方程组的近似解。,1.2线性代数方程组的解法分类,December16,2019,yfnie,5,设有线性方程组,为非奇异矩阵.,或写为矩阵形式，其中,2高斯消去法,December16,2019,yfnie,6,2.1高斯顺序消去法,若令,用乘第一个方程加到第个方程，并保留第一式，得,Step1：,December16,2019,yfnie,7,Gauss顺序消去法（续）,乘除法运算次数,Step2:,December16,2019,yfnie,8,Gauss顺序消去法,记为,（续2）,乘除法运算次数,December16,2019,yfnie,9,设为,第k-1步消元完成后，有,（续3）,Stepk：,December16,2019,yfnie,10,StepK,（续4）,(i,j=k+1,n),（i=k+1,n）,乘除法运算次数,December16,2019,yfnie,11,做完n-1步，原方程可化为同解的上三角方程组。,Gauss顺序消去法,（续5）,回代过程：,（i=n-1,n-2,2，1）,回代乘除运算次数：,December16,2019,yfnie,12,在Gauss顺序消去法的消去过程中，若将右端列向量视为方程组A的第n1列，直接对该增广矩阵A进行行初等变换，将其变换为上三角矩阵，从而回代求解得原方程组的解。,计算量,Gauss顺序消去法消去过程所需的乘除运算次数为,总的乘除运算次数：,取n20，则N3060,December16,2019,yfnie,13,在消去过程中采用Gauss-Jordan消去法，即将方程组化为对角形方程组，进而化为单位阵，则右端列向量就化为方程组的解向量。该方法不需回代过程，但总的计算量为n3/2+n2-n/2，比Gauss顺序消去法有所增加。,GaussJordan消去法,December16,2019,yfnie,14,消去过程能够实施的条件是回代过程条件增加条件,命题1,定义,Gauss顺序消去法的消元条件,December16,2019,yfnie,15,高斯顺序消去法仅对原增广矩阵作行初等变换，故,命题证明,December16,2019,yfnie,16,续,定理2：若系数矩阵A的各阶顺序主子式均不为零则可以用高斯顺序消去法求解方程组AX=b。,定理1：高斯顺序消去法求解方程组AX=b的消元过程能够实施的充要条件是系数矩阵A的前n-1个顺序主子式均不为零。,December16,2019,yfnie,17,用Gauss顺序消去法求解线性方程组的条件强于解的存在唯一性条件,斯顺序消去法能进行下去，但或相对于,比较小时，计算产生的舍入误差将导致计算结果误差急剧增大，计算解与真解相差甚远，即该方法不稳定。,Gauss顺序消去法的不足,小主元是不稳定的根源，需要采用“选主元”技术，即选取绝对值较大的元素作为主元。,December16,2019,yfnie,18,2.2选主元的高斯消去法,列主元消去法,在第一列中选取绝对值最大的元素,设=调换第一行与第p行，这时的,再执行消去法的第一步,就是原来的,然后,December16,2019,yfnie,19,再考虑右下角矩阵，在第二列选取绝对值最大的元素作为主元素,将其所在行与第二行交换，消元。依此类推直至将方程组化成上三角方程组，再进行回代就可求得解。,列主元消去法（续）,优点：只要系数矩阵非奇异，消元过程就能进行，并且主元相对较大，方法稳定好。,December16,2019,yfnie,20,在系数矩阵中选取绝对值最大的元素作为主元素，如,然后交换增广矩阵的第一行与第i1行，第一列与第j1列，这时,全主元消去法,实施第一次消元。,December16,2019,yfnie,21,换把主元素移到,再消元。,消元结束后回代求解。,再考虑右下角系数矩阵，选取绝对值最大的元素作为主元素,经过行对换和列对,的位置,全主元消去法（续）,December16,2019,yfnie,22,评注1：全主元消去法每一步所选取的主元的绝对值不低于列主元消去法的同一步所选主元的绝对值，因而计算结果更加可靠。,评注2：全主元消去法每一步选主元要花费更多的机时，并且对增广矩阵做了列交换，从而未知量的次序发生了变化，对编程带来了麻烦。而列主元消去法的计算结果已比较可靠，故实用中常用列主元消去法。,特点,December16,2019,yfnie,23,3.1Gauss顺序消去法的矩阵形式,设方程组Ax=b的系数矩阵各阶顺序主子式均不为零,3矩阵三角分解法,定义符号：,December16,2019,yfnie,24,3.1Gauss顺序消去法的矩阵表示,December16,2019,yfnie,25,Gauss顺序消去法的矩阵表示,（续）,L是一系列单位下三角矩阵逆的乘积，U是上三角阵,引理：单位下三角矩阵对求逆和乘积是封闭的。,L也是单位下三角阵,December16,2019,yfnie,26,A=LU,Gauss顺序消去法的矩阵表示,（续2）,December16,2019,yfnie,27,定义1.设A为n阶矩阵（n2）,称A=LU为矩阵的三角分解，其中L是下三角矩阵，U是上三角矩阵。,定义2.如果L是单位下三角矩阵，U是上三角矩阵，则称三角分解A=LU为Doolittle分解；如果L是下三角矩阵，U是单位上三角矩阵，则称A=LU为Crout分解。高斯顺序消去法对应A的Doolittle分解。,定理3：设A为n阶(n1)矩阵，若A的前n1个顺序主子式不为零，则A有唯一的Doolittle(Crout)分解。,3.2矩阵的三角分解,December16,2019,yfnie,28,证明1,对Doolittle分解进行证明。存在性：,A的顺序主子式，根据Gauss顺序消去法的消元过程有记得A=LU。,A=LU的唯一性证明:,三角分解条件,设A有两个Doolittle分解为单位下三角矩阵,为上三角矩阵。,将矩阵进行分块如下：,December16,2019,yfnie,29,矩阵的三角分解条件,证明续,唯一性得证,December16,2019,yfnie,30,存在性：,Crout分解证明,December16,2019,yfnie,31,唯一性可类似Doolittle分解的方法可证。,Remark：实际中对A进行三角分解并不是按上述过程进行的，而是直接使用矩阵乘法得到。（下面以Doolittle型三角分解为例。）,Crout分解证明续,December16,2019,yfnie,32,设A=LU,Step1：比较第一行元素,比较第一列元素：,直接三角分解法,三角分解（2）,Step2：比较第二行元素,比较第二列的元素：,December16,2019,yfnie,34,设U的前k-1行以及L的前k-1列已求出。,比较第k行元素,直接三角分解法,Stepk：,续,续2,比较第k列元素,紧凑格式,