线性方程组的直接解法

资源描述

《线性方程组的直接解法》由会员分享，可在线阅读，更多相关《线性方程组的直接解法（44页珍藏版）》请在金锄头文库上搜索。

1、第五章线性方程组的直接解法 /* Direct Methord for Solving Linear Systems */上一页下一页返回第一节 Gauss消去法第二节直接三角分解方法第三节方程组的性态与误差估计1求解上一页下一页返回 21 Gauss消去法一、高斯顺序消去法思路首先将A化为上三角阵 /* upper-triangular matrix */ ，再回代求解 /* backward substitution */。=是一种古老的求解线性方程组的方法, 按自然顺序进行消元的方法. 上一页下一页返回 3例1 解方程组解：step1 消元上一页下一页返回

2、4Step2 对上三角形方程进行回代求解, 得下面我们来一般性地讨论求解n阶线性方程组的高斯顺序消去法.上一页下一页返回 5消元 Step 1：设，计算因子将增广矩阵/* augmented matrix */ 第 i 行 li1 第1行，得到与(1)式等价的方程组上一页下一页返回 6Step 2：一般第 k 次消元 (1k n-1) 上一页下一页返回 7上一页下一页返回 8Step 3：继续上述过程, 且设 aii（i-1）0(i=1,2,n-1),直到完成第 n-1 次消元, 最后得到与 A(0)x=b(0) 等价的三角形方程组 A(n-1)x=b(n-1).将

3、(1)式化为(2)式的过程称为消元过程.上一页下一页返回 9回代定理若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。注注：事实上，只要 A 非奇异，即 A1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。上一页下一页返回 10高斯顺序消去法流程图FTk=k+1FT消元过程回代过程上一页下一页返回 11顺序消去法的缺点为当主元akk(k -1)=0时, 消元过程不能继续进行. 或者当akk (k -1) 0时, 虽然消元过程

4、可以进行, 但若akk (k -1) 0时, 时, 会出现很小的数作除数的现象,使舍入误差增大,导致解的严重失真.上一页下一页返回 12例：解方程组/* 精确解为 */用Gauss消去法计算：二、主元素消去法上一页下一页返回 13由上例可以看出,为提高算法的数值稳定性, 应选取绝对值尽可能大的元素作主元. 上一页下一页返回按列部分选主元的消去法也称列主元消去法。14解：上一页下一页返回 15一些特殊情况, 主元就在对角线上,不需选主元. 元素满足如下条件的矩阵即对角线上每一元素的绝对值均大于同行其他各元素绝对值之和,这样的矩阵称为按行严格对角占优矩阵,简称严格对角

5、占优矩阵.例：性质：严格对角占优矩阵必定非奇异.上一页下一页返回 16三、高斯-约当消去法（求矩阵逆）与 Gauss消去法的主要区别：每一步不计算 lik ，而是先将当前主元 akk(k-1) 变为 1; 把 akk(k-1) 所在列的上、下元素全消为0;这种方法是不是比Gauss 消去法更好?Gauss消去法过程中，消去对角线下方和上方的元素，称这种方法为高斯-约当消去法.上一页下一页返回这种方法不用回代过程了，看上去是要好些？17 运算量 /* Amount of Computation */由于计算机中乘除 /* multiplications / divisions

6、 */ 运算的时间远远超过加减 /* additions / subtractions */ 运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。 Gauss消去法:Step k：设，计算因子且计算共进行n 1步(n k) 次(n k)2 次(n k) 次(n k) (n k + 2) 次消元时乘除次数：1 次(n i +1) 次回代时乘除次数：Gauss消去法的总乘除次数为，运算量为级。上一页下一页返回 18 Gauss-Jordan 消去法:运算量约为。故通常只用于求逆矩阵，而不用于解方程组。求逆矩阵即。上一页下

7、一页返回 192 直接三角分解法一、 LU分解法 /* LU Factorization. */就 n=3的情况分析顺序消去法的消元过程.上一页下一页返回 20可见, 消元过程相当于下述矩阵乘法运算：由分块乘法可得：直接计算可得由(*)式可得上一页下一页返回 21Step 1:记M(1) =，则Step n 1:其中M (k)=以上分析推广到n阶线性方程组可得上一页下一页返回 22记为L单位下三角阵 /* unitary lower-triangular matrix */记 U =A 的 LU 分解 /* LU factorization */ 也称 A 的Doolittle分

8、解上一页下一页返回 23 道立特分解法 /* Doolittle Factorization */： LU 分解的紧凑格式 /* compact form */根据矩阵乘法法则,先比较等式两边第1行和第1列元素有：上一页下一页返回 24设已定出U 的第1行到第k-1行的元素 L 的第1列到第k-1列的元素上一页下一页返回 25(1),(2)两式就是 LU分解的一般计算公式, 其结果与高斯消去法所得结果完全一样. 避免了中间过程的计算,故称为A的直接分解公式.上一页下一页返回 26按上图逐框求出矩阵A的LU分解,这种计算方法称为紧凑格式法。上一页下一页返回 27定理若矩

9、阵A非奇异, 则A能分解为LU 的充分必要条件是A的所有顺序主子式均不为0.定理若非奇异矩阵A有LU 分解,则此分解是唯一的.上一页下一页返回 28例：利用系数矩阵的 LU分解, 求解方程组解：LU分解的紧凑格式为上一页下一页返回 29则求解原方程组等价于求解下面两个方程组Ly=b及Ux=y上一页下一页返回 30二、三对角方程组追赶法若A满足Gauss消去法可行的条件，则可用LU分解法求解其中：上一页下一页返回 31解方程组Ax=d分为两步，即求解Ly=d和Ux=y，计算公式如下：上述方法为求解三对角方程组的追赶法，也称Thomas算法.上一页下一页返回追赶法公式简

10、单，计算量和存储量都小，整个求解过程只需要5n-4次乘除运算。32上一页下一页返回三、平方根法对称正定矩阵的分解法将对称正定阵 A 做 LU 分解记为33定理设n阶对称正定矩阵A，则存在唯一的单位下三角阵L及对角阵D 使得。称为矩阵A 的乔累斯基分解上一页下一页返回定理设矩阵A对称正定，则存在唯一的对角元为正的下三角阵 L，使得。称为对称正定矩阵A 的乔累斯基分解利用乔累斯基（Cholesky）分解式来求解Ax=b的方法也称Cholesky方法或平方根法343 方程组的性态与误差估计上一页下一页返回一、矩阵的条件数例，考查以下三个方程组及其准确解其准确解其

11、准确解其准确解可以看到，后两个方程组与第一个方程组相比，系数矩阵或右端向量仅有0.0005以下的误差，但准确解却相差很大。对这样的方程组，无论用多么稳定的算法求解，一旦计算中产生误差就使解面目全非，所以该方程组的性态很差。35上一页下一页返回定义：若方程组Ax=b的系数矩阵A与右端向量b的微小变化（小扰动）,将引起解向量x产生巨大变化，则称此方程组为病态方程组，其系数矩阵A称为病态矩阵，否则称Ax=b为良态方程组，称A为良态矩阵 .方程组的病态程度与Ax=b对A和b的扰动的敏感程度有关。36求解时，A 和的误差对解有何影响？设 A 精确，有误差，得到的解为，即

12、绝对误差放大因子又相对误差放大因子上一页下一页返回 37 设精确，A有误差，得到的解为，即(只要 A充分小，使得是关键的误差放大因子，称为 A的条件数，记为cond (A) , 越则 A 越病态，难得准确解。大上一页下一页返回 38注: cond (A) 的具体大小与 | | 的取法有关，但相对大小一致。 cond (A) 取决于A，与解题方法无关。常用条件数有：cond 1(A)cond (A)cond2 (A)特别地，若 A 对称，则条件数的性质： A可逆，则 cond p (A) 1； A可逆， R 则 cond ( A) = cond (A) ； A正交，则 co

13、nd 2 (A) =1； A可逆，R正交，则 cond 2 (RA) = cond 2 (AR) = cond (A)2 。上一页下一页返回 39精确解为例计算cond 2(A) 。A1 = 解：考察 A 的特征根39206 1 测试病态程度：给一个扰动，其相对误差为此时精确解为2.0102 200%上一页下一页返回 40例：Hilbert 阵cond (H2) = 27cond (H3) 748cond (H6) = 2.9 106cond (Hn) as n 注：一般判断矩阵是否病态，并不计算A1，而由经验得出。行列式的值很大或很小（如某些行、列近似相关）；元素间的数量级相差大，且无规则；主元消去过程中出现小主元；特征值相差大数量级。上一页下一页返回 41二、方程组解的误差估计定理上一页下一页返回 42上一页下一页返回解43 剩余向量设的近似解为，则一般有残向量（剩余向量）上一页下一页返回 44

展开阅读全文

线性方程组的直接解法

最新文档