计算方法21ppt课件

1,计算方法,第二章线性方程组的解法,2,2.1高斯列主元消去法,2.2对称正定矩阵的平方根法,第二章线性方程组的解法,2.4线性方程组的迭代法,2.5向量范数与矩阵范数,2.6方程组的性态和迭代法的收敛分析,3,2.1Gauss列主元消去法,一、Gauss消去法,4,对线性方程组,对其增广矩阵施行行初等变换:,一般的,5,定义行乘数,6,且,7,定义行乘数,8,9,10,运算量:,计算机作乘除运算所耗时间要远远多于加减运算,且在一个算法中，加减运算和乘除运算次数大体相当,故在衡量一个算法的运算量时只需统计乘除的运算次数,乘法次数：,除法次数：,11,全部回代过程需作乘除法的总次数为,于是Gauss消去法的乘除法运算总的次数为,数级,12,Gauss消去法乘除法约为2700次,而如果用Cramer法则的乘除法运算次数约为,用行列式定义,13,例1.,用Gauss消去法解线性方程组(用3位十进制浮点数计算）,解:,本方程组的精度较高的解为,用Gauss消去法求解(用3位十进制浮点数计算),引例:,二、Gauss列主元消去法,14,9999,回代后得到,与精确解相比,该结果相当糟糕,究其原因,在求行乘数时用了很小的数0.0001作除数,15,如果在求解时将1,2行交换,即,0.9999,回代后得到,这是一个相当不错的结果,16,例2.,解线性方程组(用8位十进制尾数的浮点数计算),解:,这个方程组和例1一样,若用Gauss消去法计算会有小数作除数的现象,若采用换行的技巧,则可避免,17,18,经过回代后可得,事实上,方程组的准确解为,19,例2所用的方法是在Gauss消去法的基础上,利用换行避免小主元作除数,该方法称为Gauss列主元消去法,20,1.Gauss消去法消元过程的矩阵描述,行变换相当于左乘初等矩阵,由于,2.2对称正定矩阵的平方根法,一、矩阵的三角分解,21,令,则,显然若令,22,则有,因此,从而,故,23,即,且,顺序主元,24,定义1.不带行交换的Gauss消去法的消元过程,产生一个单位下三角矩阵L和一个上三角矩阵U,即该过程称之为,由上述分析不难得到,注：Crout分解,25,Gauss消去法可以执行,定理1.,在定理中,可能注意到,可能存在,26,如何求L,U?,27,上式可记为,28,同样,由,29,综合以上分析,有,因此可以推导出,U的第一行,L的第一列,-(1),-(2),30,U的第r行,L的第r列,-(3),-(4),称上述(1)(4)式所表示的分解过程为Doolittle分解,31,对于线性方程组,系数矩阵非奇异,经过Doolittle分解后,线性方程组可化为下面两个三角形方程组,32,33,例1.用Dolittle分解和Crout分解方法分别解方程组,34,1、定理1.(Cholesky分解),且该分解式唯一.,这种关于对称正定矩阵的分解称为Cholesky分解.,二、对称正定矩阵的平方根法,35,-(6),-(7),-(8),36,37,2、对称正定线性方程组的解法,线性方程组,-(10),-(11),则线性方程组(10)可化为两个三角形方程组,-(12),-(13),38,-(14),-(15),对称正定方程组的平方根法,39,例1.,用平方根法解对称正定方程组,解:,40,41,即,42,所以原方程组的解为,练习.求下列矩阵的Cholesky分解,43,3、平方根法的数值稳定性,用平方根法求解对称正定方程组时不需选取主元,由,可知,因此,平方根法是数值稳定的,事实上,对称正定方程组也可以用顺序Gauss消去法求解,而不必加入选主元步骤,44,三、三对角方程组求解的追赶法,45,46,47,48,其计算工作量为