(精品)三角分解解线性方程组的公式

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,yfnie,*,的求,解,过程为,:,可推导求,解,单位下三角形方程组 的递归公式为,:,求,解,上三角形方程组 的递归公式为,:,三角分解解线性方程组的公式,11/28/2024,1,yfnie,直接三角分解法,发现计算 的规律与计算 的规律相同,因此计算 的求方程组的过程可用三角分解的紧凑格式取代。事实上，这只要把 做为,A,的第,n,1,列进行直接三角分解即可。,Reamrk,：,上述直接三角分解法所对应的是,Gauss,顺序消去法，二者的乘除运算次数是相当的。实际中对阶数较高的线性方程组，应采用选主元的三角分解法求解，以保证计算结果的可靠性。,续,11/28/2024,2,yfnie,设对 的分解已完成,k-1,步，即,L,的前,k-1,列,U,之的前,k-1,行已求出：,第,k,步计算：先选主元，再计算列，最后计算行,3.3,列主元直接三角分解法,11/28/2024,3,yfnie,参选主元量,若,则需将第,k,行与第,i,k,行完全交换，这样满足前面情形，按第一种情形实施计算。,11/28/2024,4,yfnie,1.,正定矩阵的,C,holesky,分解,定义,：,设,A,为,n,阶 对称正定矩阵，,L,是非奇异下三角矩阵，称 为矩阵,A,的,Cholesky,分解。,定理,:,n,阶 对称正定矩阵,A,一,定存在分解,:,其中,L,为单位下三角阵，,D,是对角元全为正的对角阵且这种分解式唯一,;,其中,L,为下三角阵，当限定,L,的对角元为正时的分解式唯一（,C,holesky,分解,）,.,3.4,平方根法（,Cholesky,分解）,11/28/2024,5,yfnie,证明：,因为,因为,A,对称正定，故其顺序主式 ，,有唯一的,Doolittle,分解,从而,A,平方根法（,Cholesky,分解）,定理证明,11/28/2024,6,yfnie,（,D,可逆）,平方根法（,Cholesky,分解）,即,由,Doolittle,分解,的唯一性，及 的分解过程可知该分解式的唯一性。,续,1,由,Doolittle,分解的唯一性有,11/28/2024,7,yfnie,改写,则,这时 为一般的下三角矩阵，故,，若 的对角元全为正时，由,Doolittle,分解的唯一性及上述分解的推理过程，可以得到,Cholesky,分解的唯一性。,平方根法（,Cholesky,分解）,续,2,11/28/2024,8,yfnie,第一步,：,平方根法（,Cholesky,分解）：,分解公式,设,L,前,k-1,列元素已求出，则第,k,步,11/28/2024,9,yfnie,平方根法（,Cholesky,分解）,11/28/2024,10,yfnie,在分解过程中有,n,次,开方运算，故,Cholesky,分解法,也称为,平方根法,。,用,Gauss,顺序消去法求解对称正定的方程组,Ax,b,，,由,用平方根法解对称正定的方程组时，不必考虑选主元的问题，算法本身数值稳定。,这表明用,Gauss,顺序消去法求解对称正定方程组也不用选主元。,几点说明,11/28/2024,11,yfnie,从运算量的角度看，平方根法是有利的，用平方根法解,Ax,b,所需乘除法的运算次数为：,令有,n,次开方运算。,n,次开方运算一般使用迭代法，所需乘除法的运算次数大约为,n,的常数倍。故平方根法总的乘除法运算次数大约为,为避免开方运算，也可对,A,做 分解。,续,11/28/2024,12,yfnie,矩阵对角占优的概念,类似地，也可定义按列对角占优和按列严格对角占优的概念。通常的对角占优是指按行或者按列。,则称矩阵,A,按行严格,对角,占优。,则称矩阵,A,按行对角占优,。,3.5,三对角线性方程组求解,11/28/2024,13,yfnie,满足严格对角占优条件,严格对角占优的矩阵行列式不等于零,，故该系数矩阵的各级顺序主子式不等于零。,追赶法解三对角方程组,11/28/2024,14,yfnie,若,A,为上述三对角阵时，则,A,有三角分解：,追赶法解三对角方程组,分解公式,11/28/2024,15,yfnie,追赶法解三对角方程组,由 得,由 得,方程求解公式,11/28/2024,16,yfnie,追赶法解三对角方程组,Remark,：,只要三对角矩阵按行严格对角占优，则追赶法定能进行下去，且计算过程是稳定的（不必选主元素），其乘除法运算次数为,5,n,4,。,上述方法,称为解三,对角方程组的,追赶法,，又称为,Thomas,方法。,说明,11/28/2024,17,yfnie,其中,A,i,，,B,i,，,C,i,均为,q,阶矩阵，,， 是,q,维向量。对于这种方程组，可以类似地建立追赶法。,追赶法解块状三对角方程组,11/28/2024,18,yfnie,追赶法解块状三对角方程组,其中,I,为,q,阶单位矩阵，,L,i,和,U,i,是,q,阶矩阵。,根据矩阵的分块运算，容易求得块三对角方程组的追赶法如下：,续,11/28/2024,19,yfnie,追赶法解块状三对角方程组,续,2,11/28/2024,20,yfnie,4.1,向量范数,1.,定义：,设 的某个实值函数 满足,(3).,（三角不等式）,(2).,（齐次性）,c,为任意实数,(1).,（非负性,),当且仅当 时有 ,0,则称 是 上的一个向量范数。,4,矩阵的条件数和方程组的性态,11/28/2024,21,yfnie,证明,：,故必有,命题,1,向量范数具有性质：,4.1,向量范数,连续性定理,：设 为 上的某种范数，则 为分量,的连续函数,.,证明,：,11/28/2024,22,yfnie,对任意给定正数,向量范数范数连续性证明,11/28/2024,23,yfnie,等价性定理,：设 是 上的两种向量范数，则存在与 无关的常数,，,使得,证明,：,当 时上式显然成立。故假设,首先证明存在常数,由连续性定理结论成立。,等价性定理,11/28/2024,24,yfnie,向量范数的性质,联合即得,即 ，其中,使,同理 有,续,11/28/2024,25,yfnie,1,定义,：如果矩阵,A,的实值函数 ，满足：,（,1,）正定性：,（,当且仅当,A=0,）,（,2,）,齐次性：,c,为实数,（,3,）三角不等式,其中,A,B,（,4,）,则称 是 上的一个矩阵范数。,特别地，若还具备特性,（,5,）,(,为 的某种向量范数,),则方阵范数特别叫做与向量范数 相容的方阵范数。,4.2,矩阵范数,11/28/2024,26,yfnie,称为,A,的行范数；,称为,A,的列范数；,称为,A,的,2,一范数，其中 表示 的按模最大的特征值。,称为,A,的,F,一范数。,常用的矩阵范数,11/28/2024,27,yfnie,设,A ,给出一种向量范数,(p=1,，,2,或 等,),定义矩阵的非负函数,是 上矩阵的一种范数,称为,A,的,算子范数,，也称,从属范数,。,Remark,：,向量范数 所导出的矩阵范数 与该向量范数是相容的。,矩阵的算子范数,11/28/2024,28,yfnie,定理,：,设,则,证明,：,（,1,）设,。,不妨设,A,。,(A=0,时,显,然,二者一致,),常用向量范数与矩阵范数间的关系,11/28/2024,29,yfnie,即对任何非零向量,有,（,a,）,下面来说明有一向量 使,设 在第 行达到，即,算子范数,（续）,证明,11/28/2024,30,yfnie,且,A,的第 个分量为,即有,（,b,）,结合（,a,），（,b,）,得,取向量,其中,（,j=1,，,2,，,，,n,）,（,2,）,证明与（,1,）类似。,算子范数,（续）,这说明,证明,11/28/2024,31,yfnie,（,3,）因,A,为实矩阵，故 为实对称的，并且还是非负定的。,设,为任一非零向量，则有,故,的特征值排列为,其中 为标准正交的特征向量， 为组合系数。设,算子范数,（续）,证明,11/28/2024,32,yfnie,即,从而得到,取,则,算子范数,（续）,证明,11/28/2024,33,yfnie,背景,：实际求解,方程组,Ax,b,时，,A,和,b,都可能有微小变化，如计算机计算时产生的舍入误差，采集数据误差等，此时方程组的解会如何变化？,例,：求解方程组,该方程组的精确解是,x,1,=,x,2,=1,。,考虑系数矩阵及右端项有微小扰动的方程组：,该方程组的精确解是,x,1,=-2,，,x,2,=8.5,。,扰动方程组解的误差界,11/28/2024,34,yfnie,从,上例可看出，虽系数矩阵和右端向量变化很小，但解的误差却很大。这说明该方程组的解对系数矩阵和右端项的扰动很敏感。,事实上，该方程组的系数矩阵行列式仅为,-0.002,，方程组的解为两条接近平行的直线的交点，因而当其中一条直线稍微变化时，新交点与原来的交点相偏离很远。,方程组的这种扰动性质是由其系数矩阵的固有性质所确定的。,举例分析,11/28/2024,35,yfnie,定理,：设有方程组,Ax=b,，,其中,A,非奇异。设,A,和,b,有微小扰动,A,和,b,，,扰动后的方程组为,这里用到向量范数和矩阵范数相容。,则当 时，有误差估计,扰动方程组解的误差界,证明,：,将,扰动方程组与原方程组相减，得,11/28/2024,36,yfnie,扰动方程组解的误差界（续）,因,Ax,b,，,故上式为：,故,证明,11/28/2024,37,yfnie,扰动方程组解的误差界,Remark,：,若方程组仅有右端扰动,b,，即,A,0,时,解的误差界为：,若方程组仅有系数矩阵扰动,A,，,即,b,0,时，解的误差界为：,结论,：解的相对误差是在扰动相对误差 和 的基础上通过量 所刻划的，其大小反映了解的相对误差的大小。,分析,11/28/2024,38,yfnie,定义,：设,A,是,n,阶非奇异矩阵，称 为矩阵,A,的,条件数,。,由此可见，当,Cond,(,A,),较大时，,A,和,b,的小扰动可能引起解的较大误差，故条件数,Cond,(,A,),刻划了方程组,Ax,b,的性态。,条件数,11/28/2024,39,yfnie,例,：,n,阶,Hilbert,矩阵,n,Cond,2,(,A,),n,Cond,2,(,A,),3,5.2410,2,7,4.75 10,8,4,1.55 10,4,8,1.53 10,10,5,4.77 10,5,9,4.93 10,11,6,1.50 10,7,10,1.6010,13,例,11/28/2024,40,yfnie,Remark,：,对于给定的,Ax,b,，,计算 涉及到矩阵求逆。按照定义，若,Ax,b,的解,x,和有小扰动的方程组 的解 误差很大，则原方程组是病态的。但这并不是一个实用的判断方法。,一种可能的情况,是，若 接近于零或者说,A,的行向量组（或列向量组）近似线性无关，则有可能方程组,Ax,b,病态。至于 是否接近于零，可在列主元消去法的进行过程中观察是否某个主元 绝对值很小而进行判断。,说明,11/28/2024,41,yfnie,矩阵的条件数和方程组的性态,另外一种情况,是，当,A,的元素数量级差别很大并且无一定规则时，方程组,Ax,b,可能病态。,如：,相应的方程组,Ax,b,是,病态的。,但,对于,相应的方程组,Ax,b,是,良态的。,续,11/28/2024,42,yfnie,一般病态方程组的求解是比较困难的,。方程组给定，其系数矩阵的条件数就随之确定，所以方程组的性态是方程组的固有性质，与求解方法无关。一般来说，在计算机上求解的方程组都是所给方程组的扰动方程，这是因为计算机存储数据的舍入误差所致。对于良态方程组，只要求解方法稳定，即可得到比较满意的计算结果。但对于病态方程组，即使用稳定性很好的算法求解也未必得到理想的结果。,对于病态方程组,Ax,b,的求解，可在计算实践中考虑下述方法的使用：,关于病态方程组的求解,11/28/2024,43,yfnie,关于病态方程组的求解,1.,采用高精度的算术运算,，如采用双精度运算，使由于舍入误差的放大损失若干有效位数之后，还能保留一些有效位数，从而改善和减轻“病态”的影响,。,2.,对,原方程组作一些预处理,，如进行,矩阵平衡,，以降低矩阵的条件数。矩阵平衡就是给,A,的每一行（或每一列）分别乘以适当的常数，即找可逆的对角阵,D,1,和,D,2,，,使方程组,Ax,b,转化为：,D,1,AD,2,y=D,1,b,D,2,y=x,理论上应选择,D,1,和,D,2,，使,Cond,(,D,1,AD,2,),min,，,但实际上这很难实现，一般矩阵的平衡只是针对具体问题进行具体的处理。,续,11/28/2024,44,yfnie,关于病态方程组的求解,一种简单的处理办法,是令,D,2,I,，,这称为行平衡。,D,1,的选择可使 每一行的,范数大体相当，以避免消元过程中“大数吃掉小数”。具体的处理方法如下：,设有,n,阶方程组,Ax,=,b,，,A,=(,a,ij,),n,n,非奇异，计算,则得到与,Ax,=,b,等价的方程组,DAx,=,Db,，,其系数矩阵,DA,的条件数有可能大大低于,A,的条件数。,续,2,11/28/2024,45,yfnie,关于病态方程组的求解,例,：,对,方程组,系数矩阵的条件数 故此方程组病态的。,采用行平衡，取,D,=,diag,(10,10,-10,),，,则得到同解方程组,此时系数矩阵的条件数,续,3,11/28/2024,46,yfnie,