数值分析第2章_解线性方程组的直接法.ppt

第3章 解线性方程组的直接法 LU分解求解线性方程组 小 结 3.2.2 Crout（克劳特）分解 假设 其中L为下三角矩阵， U为单位上三角矩阵， Crout Factorization 克劳特分解求方程组步骤：略 3.2.3 Cholesky（楚列斯基）分解 ——平方根法 定义3-2 若矩阵 则称A为对称正定矩阵。 A为对称正定阵，则存在唯一的LU分解 U = uij = u11 uij / uii 1 1 1 u22 unn 记为 A 对称 即 记 D1/2 = 则 仍是下三角阵 定理 设矩阵A对称正定，则存在非奇异下三角阵 使得 。若限定L对角元为正，则分解唯一。 例：对矩阵 进行楚列斯基分解。 解： A为对称矩阵，且 A对称正定。 矩阵LLT分解的实际计算公式： for for for for 解 例 解线性方程组 ? Cholesky分解法求解方程组中需说明的几个问题 ?工作量：约为LU分解的一半； ?不必选主元：A的正定性和算法的稳定性 ?稳定性：是数值稳定的； ?缺陷：存在开平方运算。 ?改进方法： LDLT 分解 改进的平方根法 改进的平方根法 ——避免开方运算 即 l. 对于 2. 引进 按行计算 元素的公式： 1. 2. 3. 对于 Step1 Step2 Step3 Stepn 元素的储存比消去法节省一半，但比平方根法多用一个单元内存， LDLT的计算顺序 LDLT分解公式： 求解方程组 等价方程组 for for for 例 用LDLT解方程组 解 例 用LDLT解方程组 解 3.3 三对角方程组的追赶法 系数矩阵为对角占优的三对角线方程组 简记为 其中，当 LU分解会是什么样子？ 其中L为下三角矩阵，U为单位上三角矩阵. 由系数阵A的特点，可以将A分解为两个三角阵的乘积， 即 设 其中 为待定系数. 由矩阵乘法 或分解为：L为单位下三角矩阵，U为上三角矩阵. 计算公式 i = 2, 3, …, n-1 求解 等价于求解两个三角形方程组： 三对角线方程组的追赶法公式： 1. 计算 的递推公式 2. 解 3. 解 赶： 追： 解 例3-7 应用追赶法求解线性方程组 * 数值分析 * 第2章 解线性方程组的直接法 3.1 Gauss消去法 3.2 LU分解 3.3 三对角方程组的追赶法 Direct Methods for Solving Linear Systems 求解 其中 本章讨论n元线性方程组 的解法。 Ax=b 方程组的矩阵形式为 求解 克莱姆（Cramer法则）: 所需乘除法的运算量大约为(n+1)!+n n=20时，每秒1亿次运算速度的计算机要算30多万年！ 其中，D=det(A), Di 是用向量b 代替A的第i 列后所得矩阵的行列式。 所谓直接解法是指若不考虑计算过程中的舍入误差， 经过有限次算术运算就能求出线性方程组的精确解的方法。 线性方程组Ax=b的一般数值解法 1.直接法： 适用于低阶稠密方程组 Gauss消去法、三角分解法 2.迭代法：通过构造迭代方程组进行迭代。 适用于大型稀疏方程组 非零元素较多，零元素较少 上万阶，零元素很多，非零元素很少 雅克比迭代法 赛德尔迭代法 3.1 Gauss消去法 3.1.1 高斯消去法 高斯消元法是一个古老的直接法, 由它改进得到的选主元法, 是目前计算机上常用于求低阶稠密矩阵方程组的有效方法, 其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题。 /* Gaussian Elimination */ 1.消元过程：用初等行变换将原方程组的系数矩阵化为 上三角形矩阵（简称上三角阵）。 2.回代过程：对上三角形方程组的最后一个方程求解，将求得的解逐步往上一个方程代入求解。 思路 首先将A化为上三角阵/* upper-triangular matrix，再回代求解。 = 1. Gauss（顺序）消去法的基本思想 不作行交换！ 例3-1 用消去法解方程组 第2步. 回代过程 解 第1步. 消元过程，对增广矩阵进行消元 得等价的三角形方程组 解为 记 Step