清华第五版数值分析第5章课件费下载

,第五章 线性代数方程组的数值解法,引言,关于线性方程组的数值解法一般有两类。直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差）. 代表性的算法是高斯(Gauss)消去法。计算代价高.迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法. 简单实用。,5.1 高斯消去法,上三角方程组的回代求解：,则,设 Ax=b. 记A(1)=A b(1)=b,第二步：,则,重复上述过程, 最后得,原方程组的同解方程组,消元过程,Gauss 消去法,上三角方程组的回代求解：,定理：若A的各阶顺序主子式不等于0，则高斯消去法能顺序进行消元，得到唯一解。,高斯消去法条件(高斯消去法适用范围),证明：高斯消去法能进行下去的充要条件是而消元过程不会改变顺序主子式的值。所以解的唯一性又要求,高斯消去法存在的问题：,如果某个 ,但很小，会引入较大的误差。,1.在高斯消去法消去过程中可能出现 的情况，这时高斯消去法将无法进行,三 高斯列主元消去法,具体步骤为：,基本思想：在每轮消元之前，选列主元素（绝对值最大的元素）,以第二步为例:,挑选从第二行开始的第二列中的最大元素,交换行将其变为主元,如此至多经过n-1步,就得到与之同解的上三角形方 程组的增广矩阵,再用回代过程即可得方程组的解.,高斯列主元消去法的适用范围,定理：系数矩阵非奇异，这高斯列主元消去法可行。,高斯消元法每一消元步骤相当于对系数矩阵左乘一个行初等矩阵，具体为,记 L1 = EnE3E2,高斯消元法第一步：,等价于,L1A(1)=A(2), L1b(1)=b(2),A(1),b(1),A(2),b(2),高斯消元法的矩阵形式,A(2),b(2),A(3),b(3),第二步消元,等价于,L2A(2)=A(3), L2b(2)=b(3),其中,Lk A(k)=A(k+1), Lkb(k)=b(k+1),一般第k步消元的矩阵表示为,其中,A(n),注： （1） L 为单位下三角阵而 U 为一般上三角阵的分解称为Doolittle 分解 （2）L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。基于这些想法我们得到下面的三角分解解线性方程组的方法,L,5.2 矩阵的三角分解法,一 矩阵的三角分解,若矩阵A有分解：A=LU，其中L为下三角阵，U为上三角阵，则称该分解为A的LU分解。若矩阵A有分解A=LU，则解线性方程组 就等价于求解,当系数矩阵A相同，有很多不同的右端向量时，用此方法很有效。如求即求方程的解，用此法很合适。下面看什么情况下，可对系数矩阵做三角分解。,三角分解的存在唯一性定理,定理,引理：若 则,存在唯一性证明,证明：存在性：高斯消去法能进行下去，则三角分解存在。 唯一性：设则下三角阵=上三角阵，所以所以,二 矩阵的直接三角分解,直接计算 A 的 LU 分解(例) （续）,1),2),3),一般计算公式,计算量与 Gauss 消去法同.,LU 分解求解线性方程组,a11 a12 a13 a1n u11 u12 u13 u1n a21 a22 a23 a2n l21 u22 u23 u2n a31 a32 a33 a3n l31 l32 u33 u3n an1 an2 an3 ann ln1 ln2 ln3 unn,.,.,.,(1),(3),(5),(2n-1),(2) (4) (6) (2n),紧凑格式,旧元素减去左边行与顶上列向量的点积计算行不用除法计算列要除主对角元,注：,例 求矩阵的Doolittle分解,例:用矩阵的直接三角分解法解方程组,或 用 Doolittle 分解法,三 解三对角线性方程组的 追赶法,设三对角方程组 为Ax=d,即:,其中|i-j|1时,aij=0,且满足如下的条件:(1)|b1|c1|0,|bn|an|0(2)|bi|ai|+|ci|, aici0, i=2,3,n-1.,可以证明A的Crout分解形式为：,L,U,由矩阵乘法,用矩阵乘法比较和Crout 分解可推导总结算法步骤如下:,1.分解计算,2.解Ly=d,3.解Ux=y,追的过程,赶的过程,定理 设A为对称正定矩阵，则存在唯一分解A=LDLT，其中L为单位下三角阵，D=diag(d1,d2,dn)且di0(i=1,n),四 系数矩阵为对称正定矩阵方程组的平方根法,A对称：AT=A A正定：A的各阶顺序主子式均大于零。即,证明：,DU0 即为L、U分解中的U,D,U0,推论：设A为对称正定矩阵，则存在唯一分解 其中L为具有主对角元素为正数的下三角矩阵。,Cholesky分解,U,从而： 其中 为下三角阵。,Cholesky分解的求法,计算公式:,求解对称正定方程组Ax=b的平方根法(计算公式) ：,1分解计算 （对L按列计算）,平方根法缺点及优点 优点：可以减少存储单元。 缺点：存在开方运算，可能会出现根号下负数。,改进平方根法,分解A=LDLT,改进平方根法,令DLTx = y，1) 解下三角形方程组Ly = b得,2) 解上三角形方程组DLTx =y得,=LU,求解 时，A 和 的误差对解 有何影响？, 设 A 精确， 有误差 ，得到的解为 ，即,绝对误差放大因子,又,相对误差放大因子,5 线性方程组的性态和解的误差分析,6 Error Analysis for ., 设 精确，A有误差 ，得到的解为 ，即,Wait a minute Who said that ( I + A1 A ) is invertible?,(只要 A充分小，使得,大,cond (H2) =,27,cond (H3) ,748,cond (H6) =,2.9 106,cond (Hn) as n ,注：现在用Matlab数学软件可以很方便求矩阵的状态数!,定义2: 设线性方程组的系数矩阵是非奇异的,如果cond(A) 越大,就称这个方程组越病态.反之,cond(A)越小,就称这个方程组越良态.,一般判断矩阵是否病态，并不计算A1，而由经验得出。 行列式很大或很小（如某些行、列近似相关）； 元素间相差大数量级，且无规则； 主元消去过程中出现小主元； 特征值相差大数量级。, 近似解的误差估计及改善：,设 的近似解为 ，则一般有,cond (A), 改善方法(1) ：,Step 1:近似解,Step 2:,Step 3:,Step 4:,若 可被精确解出，则有 就是精确解了。,经验表明：若 A 不是非常病态（例如： ），则