二-数值代数PPT课件.ppt

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