第五章直接法-数值积分.pptVIP

第五章. 解线性代数方程组的直接方法 §1.引言 §2. Gauss (高斯)消去法 Gauss 消去法计算过程 §3. 高斯主元素消去法 选主元素的矩阵表示 例如： L相当是由各L-1k (k=1,2,…,n-1)的所有左下元素拼凑 后加上对角元1而得. 当A进行LU分解后,Ax=b就容易解了. 即Ax=b等价于: 这样,Ax=b分解为解两个三角形方程组,三角形方程组是极易求解的.(*)即是高斯消元法的矩阵表述. 定理7 矩阵 An×n,只要A的各阶顺序主子式非零,则A可以分解为一个单位下三角阵L和一个上三角阵U的乘积,即A=LU,且这种分解是唯一的. (P173) L是下三角矩阵,且所有的对角元为1,故称为单位下三角阵.这样,A=LU称为A的LU分解,其中L是单位下三角阵,U是上三角阵. 例1 直接LU分解法 A的LU分解可以用高斯消元法完成,但也可以用矩阵乘法原理推出另一种方法,结果是完全一致的． 由矩阵乘法公式可推出直接LU分解算法,也称杜利特(Doolittle) 紧凑算法,现总结如下: 1.矩阵分解:A=LU，记 2.解 L y = b 3.解 U x = y 杜利特算法可用文字描述如下: 将A的元素划分为形如“┏”的n框, 如A的第一行和第一列元素为第一框,紧靠第一框内部的第二行和第二列元素为第二框,依此类推,ann一个元素为第n框.为便于描述我们称原A矩阵中元素为a元素,计算后每框中的每行元素为u元素(包含对角元素),每列元素为l元素(不包含对角元素). 杜利特算法实际上就是高斯消元法的另一种形式.它的计算量与高斯消元法一样.但它不是逐次对A进行变换,而是一次性地算出L和U的元素.L和U的元素算出后,不必另辟存贮单元存放,可直接存放在A的对应元素的位置,节省存贮单元,因此也称为紧凑格式法. 也可以用增广矩阵[A:b]进行以上操作,这时每框要多算一个 u元素,结果矩阵中的最后一列就是 Ly=b 的解,回代时只要解 Ux=y 就行了. 当用手工计算小型线性方程组的解时,用此方法比较方便. 这样我们可以在A上直接修改计算,作如下的操作: 得到的矩阵由L和U的元素拼合而成,它的上三角部分(包含 对角元素)即是LU分解后的U矩阵;它的下三角部分(不包含 对角元素)加上一个单位阵(即在对角元处全部写为1),就是L阵. (1)第1框: u元素等于对应的a元素;l元素等于对应的a元素 除以本框对角元素; (2)第2到n框: u元素等于对应的a元素减去已经算过的各框 中同行同列元素的乘积;l元素除进行以上操作外,还要除 以本框对角元素 方阵行列式求法 在实际问题中,有时会遇到求方阵的行列式.在线性代数中讲到的行列式定义算法和展开算法均不适用于阶数较高的行列式.而LU分解是计算行列式的十分方便和适用的算法. A=LU 即只要将U阵的对角元相乘就可得A的行列式. 为避免计算中断,还应加上选主元素过程,此时每做一次行交换(或列交换),行列式要改变一次符号,有: 其中 p 是进行的行交换次数(对列主元消元法而言),或是行交换和列交换次数的总和(对全主元消元法而言).若选不出非零的主元素,则必有det A=0. 克劳特(Crout)分解 将LU分解换一个提法:要求L为一般下三角阵,U为单位上 三角阵,就是克劳特分解. LT显然是单位上三角阵,记 这就是克劳特分解。 有 实际上将A转置为AT,进行LU分解 AT=LU 则 A=UTLT 显然当A的各阶顺序主子式非零时,它是存在且唯一的. 克劳特分解对应的解法称克劳特算法,也可用于解线性 方程组。它的特点是在回代时不做除法.它在下文的追 赶法中有应用. UT显然是一般下三角阵,记 平方根法 实际问题中Ax=b,A若是对称正定矩阵,则高斯消元法简化为 平方根法或改进的平方根法. 取 记 记 记 于是 矩阵的LDU分解 证: 由条件有A=LU,由分解过程知 定理　 若A的各阶顺序主子式非零,则A可以分解为A=LDU, 其中L是单位下三角阵,U是单位上三角阵,D是对角阵,且这种 分解是唯一的. 定理１１ 设 A 对称正定,则存在三角分解 A=LLT,L是非 奇异下三角矩阵,且当限定 L 的对角元为正时, 这种分解是唯一的. 证 因为 A 对称正定,所以A各阶顺序主子式为正. 所以有A=LDU,AT=UTDLT=A=LDU. 由LDU分解的唯一性知:UT=L, U=LT 所以 A=LDLT. 下面证D的对角元为正数, 因为 |L|=1≠0,所以 LTyi=ei 必有非零解 yi ≠ 0, yiTAyi=yiTLDLTyi=(LTyi)TD(