第二章 数值代数ppt课件

.,第二章数值代数,2.1Gauss消去法2.2直接三角分解法2.3范数和误差分析,.,引例：Cramer法则不可行,Cramer法则n20时，计算量太大，现实上不可行Cramer法则数学上很重要，计算上无价值,.,2.1Gauss消去法,1理论基础2顺序Gauss消去法3选主元技术4追赶法,.,1.理论基础,引理2.1证明(P14),.,2顺序Gauss消去法,例2.1消元过程回代过程,.,顺序Gauss消去法,b,Ax,.,消元过程(第1步),用矩阵初等行变换化系数矩阵为三角形,.,消元过程(第2步),.,消元过程(第k步)编程用计算公式,.,消元过程(结果),.,上三角方程组,.,回代过程,.,计算量(乘除法次数),消元回代总和,计算量主要在消元,比较Cramer法则Gauss法快很多,.,可行性,如果A=(aij)nn的顺序主子式均不为零，顺序Gauss消去法求解可行。,.,3选主元技术,为什么要选主元素？主元素=0，计算就不能进行。主元素0,计算过程数值不稳定。怎样选主元素？把绝对值大的数调到对角线上例2.23位有效数字,.,例2.3(选列主元素Gauss消去法),.,可行性,如果A=(aij)nn的行列式不为零，选列主元素Gauss消去法求解可行。,比较：如果A=(aij)nn的顺序主子式均不为零，顺序Gauss消去法求解可行。,.,4追赶法,三对角方程组顺序Gauss消去法应用于三对角线性方程组得到所谓追赶法，其中消元过程为“追”，回代过程为“赶”。,.,4追赶法,追k=2,n赶k=n-1,1追赶法不对零元素计算，只有2(n-1)+(n-1)+n+(n-1)=5n-4次乘除法计算量注意:追赶法假定主元不为0,计算中不选主元.,.,2.2直接三角分解法,高斯消去法的矩阵表示LU分解法平方根法改进的平方根法,.,高斯消去法的矩阵表示,对一个矩阵施行一次行变换，相当于左乘一个相应的初等矩阵。顺序高斯消去法相当于矩阵三角分解A=LUP21例题P3P2P1A=U选列主元高斯消去法相当于三角分解PA=LU,其中P为行置换矩阵(详见课本38页),.,LU分解,A=LU(Doolittle分解)解方程组P22例2.5待定系数法,.,LU分解计算顺序,待定系数法(依次显式计算，无须解方程组),.,LU分解法vs.Gauss消去法,LU分解法和Gauss消去法具有相同的可行性条件,基本相同的计算量和计算精度。LU分解法具有比Gauss消去法更好的设计灵活性。当多次求解具有相同系数矩阵和不同右段向量的线性方程组；防止“大数吃小数”；LU分解存储可使用紧凑格式。三角分解的其他形式:Crout分解等.,.,平方根法,A=LLT(Cholesky分解)基本方法:待定系数法手算：由顺序主子式先求对角线编程:使用公式i=k+1,n,k=1,n乘除法次数n(n+4)(n-1)/6,开方n次P24例2.6,.,数值稳定性,可行性条件:对称正定.直接验证知：在平方根法中，k=1,n,j=1,k中间量lkj不会出现放大,从而平方根法是数值稳定的。不必选主元.,.,改进的平方根法,A=LDLT,待定系数法利用顺序主子式先求对角线,改进在哪里？(1)避免了开方运算;(2)计算的可行性条件减弱为A对称非奇异。,P26例2.7,.,2.3范数和误差分析,1范数和条件数2数据扰动分析,.,1范数和条件数,引例,病态方程组：数据小扰动解大误差。,注意：两组解都是相应方程组的精确解，没有计算误差,.,问题,什么原因导致方程组病态？怎样识别病态方程组？病态方程组怎样求解？,.,向量范数,Rn上实值函数|.|,满足正定性|x|0,且|x|=0x=0齐次性|x|=|x|三角不等式|x+y|x|+|y|常用向量范数,.,矩阵范数,Rnn上实值函数|.|,满足正定性|A|0,且|A|=0A=0齐次性|A|=|A|三角不等式|A+B|A|+|B|相容性|AB|A|B|与向量范数相容|Ax|A|x|,.,常用矩阵范数,相容性：|Ax|v|A|v|x|v,v=1,2,|Ax|2|A|F|x|2,.,范数的等价性(P44,ex10),|x|p0|x|q0,.,病态方程组,病态方程组：系数矩阵条件数很大P32例2.10(2)(P16例2.2),病态,顺序Gauss,选主元,不病态,不病态,.,2数据扰动分析,右端数据扰动Ax*=b,A(x*+x)=b+b证明|x|A-1|b|b|A|x*|,病态方程组：数据小扰动解大误差。,.,2数据扰动分析,系数矩阵扰动(A+A)(x*+x)=b证明x=-A-1A(x*+x)|x|A-1|A|(|x*|+|x|),病态