线性方程组的解法1.ppt

第二章 线性方程组的解法 设有n元线性方程组 或记为 其中 (2.1) (2.2) 设系行列式则方程组(2.1)有唯一解。 解线性方程组的两类方法 v直接法 如果不计运算过程的舍入误差，经过有限 次运算后可得到方程组的精确解的方法。 v迭代法 从解的某个近似值出发， 通过构造一个无穷序 列去逼近精确解的方法。 迭代法一般在有限步内得不到方程组的精确解 。 C r a m e r 法 则 由Cramer(克莱姆)法则，方程(2.1)的解为 其中是将中第 列换为列向量所得到的矩 阵。 如果用按照某行(或某列)展开的方法计算 行列式， 那么用Cramer法则求解一个 n 元线性 方程组所需的乘法运算次数为加 法运算次数为当 n 较大时， 这个计算量 大得惊人。 2.1 Gauss消去法 v消元过程 写出方程组(2.1)的增广矩阵， 并记 2.1.1 顺序Gauss消去法 若则施行第一次消元： 计算对 原增广矩阵被变换成 将这一过程继续下去 步的计算过程为第 若则施行第一次消元： 对计算 原增广矩阵被变换成 若所有的 则经过 次消元得到： 以以为增广矩阵的上三角线性方程组 (2.3) 与原方程组(2.1)是同解方程组。 v回代过程 回代过程就是由方程组(2.3)的最后一个方程解 然后通过逐步回代， 依次求出出 具体算法为 例 1 用顺序Gauss消去法解以下线性方程组 解用增广矩阵表示法求解： 消元过程 回代过程 同解方程组为 乘除法次数 顺序Gauss消去法的运算量 v消元过程 加减法次数 v回代过程 乘除法次数 加减法次数 v总运算量 乘除法次数 加减法次数 2.1.2 列主元Gauss消去法 引例 考虑用顺序Gauss消去法求解以下方程组， 在运算中每次运算保留到小数点后四位。 消元后的同解方程组为 回代求解得 与准确解相差很大。 改进： 对调方程 消元后的同解方程组为 回代求解得 与准确解相差不大。 误差分析： 设准确解为顺序Gauss消去法求得的解 为改进后的Gauss消去法求得的解 为 顺序Gauss消去法的误差 则 改进后的Gauss消去法的误差 则 列主元Gauss消去法 若 1 消元过程 对 选主元找使 则计算停止， 若则换行， 消元对计算 2 回代过程 则计算停止 ， 若 对 否则 例2 2.2 直接三角分解法 2.2.1 Doolittle分解法与Cout分解法 如果方程组的系数矩阵 A 能分解成 其中 L 是下三角矩阵， U 是上三角矩阵， 这时方 程组就可化为两个容易求解的三角形方程组 先由解出向量 y , 再由解出向量 y 这就是原方程组的解。 (2.4) 矩阵 A 分解成(2.4)的形式称为矩阵的三角分 解。 若 L 是单位下三角阵， 则称相应的分解为 Doolittle分解(也称为LU分解)。若 U 是单位上 三角阵， 则称相应的分解为Crout分解。 定理 1 矩阵有唯一的Doolittle分解的 充分必要条件是 A 的前个顺序主子式 定理 2 矩阵有唯一的Crout分解的充 分必要条件是 A 的前个顺序主子式 Doolittle分解法 设矩阵非奇异， 且 A 的前个顺序 主子式都不为零。 则 A 有Doolittle分解 (2.5) 由分解式(2.5)及矩阵的乘法知 当时有 Doolittle分解算法 v对 v对 Doolittle分解表上作业法 第1步 第2步 第n步 利用LU分解求解线性方程组的算法 先求解即 所以 再求解即 回代求解 例3 利用Doolittle分解求解以下方程组 解 回代求解x 2.2.3 追赶法求解三对角线性方程组 设n元线性方程组Ax=b的系数矩阵A为非奇异 的三对角矩阵 这类方程组具有许多明显的应用背景， 这种方程组称为三对角线性方程组。 分方程数值解、三次样条函数等问题中， 在求微 都会遇 到这样的线性方程组。 设 A 的前个顺序主子式都不为零， 唯一的 LU分解， 则 A 有 并且A的LU分解有如下形式 其中 v 向前“追”的过程 v 往回“赶”的过程 (2) 对 计算 (1) 求解三对角线性方程组的追赶法 (1) (2)计算对 表上作业的“追赶法” 例4利用追赶法求解以下方程组 解 2.4 解线性方程组的迭代法 v直接法: 经过有限次运算后可求得方程组精确 解的方法(不计舍入误差!)如前面我们介绍过的 Gauss消去法和直接三角分解方法。 v迭代法：从解的某个近似值出发，通过构造一个 无穷序列去逼近精确解的方法。（一般有限步内得 不到精确解） 直接法比较适用于中小型方程组。对高阶方程 组，既使系数矩阵是稀疏的，但在运算中很难保 持稀疏性，因而有存储量大，程序复杂等不足。 迭代法则能保持矩阵的稀疏性，具有计算简单 ，编制程序容易的优点，并在许多情况下收敛较 快。故能有效地解一些高阶方程组。 2.4.1 迭代法概述 迭代法的一般形式 设 n 元线性方程组(1) 的系数矩阵为 n 阶可逆方阵， 从而此方程组有唯一的非零解向量。构造形如 (2) 的方程组，其中 G 为 n 阶可逆方阵， 任取作为(1)的初始近似解， 按递推公式 (3) 产生向量序列 当 k 充分大时， 以 作为方程组的近似解， 这种求解线 性方程组的方法称为迭代法。递推公式(3)称为 迭代公式，其中 G 称为迭代矩阵。 迭代矩阵的产生方法 把系数矩阵 A 分解成两个矩阵 N 和 P 的差 其中N是 n 阶可逆方阵，代入(1)式得 即可取 关于收敛性的概念 定义 设为中的向量序列，如果 其中为某种向量范数， 则称序列收敛于x, 记为 如果对任意的初始向量迭代公式 所产生的向量序列都收敛于同一向量 则称该迭代法是收敛的。 此时，是方程组(2) 解向量， 即有成立。 收敛定理1中的向量序列收敛于中的 向量x的充分必要条件是 其中 证明：由收敛性的定义及范数等价性定理有， 收敛于 x , 对任意的有 收敛定理2 定义2若 n 阶方阵 G 的特征值为 则 称为方阵 G 的谱半径。 对任意的向量 d , 迭代公式(3)收敛 的充分必要条件是 收敛定理3 若方阵 G 的某种范数则 方程组存在唯一的解向量 对于迭代公式(3)产生的序列有 并且(4) (5) 对收敛定理3的几点说明 由(4)式知，越小，收敛的越快； 由(5)式知，不是很接近于1时，当 只要很小，就会充分接近于 方程组的解所以在实际计算中可用 作为迭代的终止条件。 接近于1时，当即使很小， 也不能断言接近于方程组的解 此时，应构造其它的迭代方法求解。 设线性方程组 的系数矩阵满足 称迭代公式 所表示的迭代法为Jacobi迭代法(或简单迭代法)。 2.4.2 Jacobi迭代法 记 其中 则Jacobi迭代法可表示为 (7) 若取 则公式(7)中的的和 d 又可表示为 (8) 收敛条件 Jacobi迭代法收敛的充分必要条件 若则Jacobi迭代收敛。 若n 阶方阵 A是主对角线按行(或按列)严格 占优阵，则用Jacobi迭代法求解线性方程组 Ax = b 必收敛。 说明 当n阶方阵A为主对角线按行严格占优阵，即 满足条件 此时有 由收敛定理3知线性方程 组Ax = b有唯一解， 并且Jacobi迭代法收敛。 当n阶方阵A为主对角线按列严格占优阵，即 满足条件 可用反证法 得到从而说明Jacobi法收敛。 例1 用Jacobi迭代法求解 解： 此方程组的系数矩阵是主对角线按行严格占 优阵， 常数项迭代矩阵 Jacobi迭代公式为 所以用Jacobi迭代法求解必收敛。 可任取。初始值 计算结果 由于 所以用作为原方程组的近似解， 绝对误 差限为 Jacobi迭代法的计算过程： 1. 输入 维数 n , 误差 初 始值最大迭代次数 N ； 2. 置 k =1； 3. 对 4. 若输出 x ，停机；否则转5。 5. 若置 转3； 否则，输出失败信息，停机。 2.4.3 Gauss-Seidel迭代法代法 在Jacobi迭代公式 需同时保留两个近似解向量和 若把迭代公式改写成 (9) 便得到所谓的Gauss-Seidel迭代公式。 它只需用 n 个单元储存近似解分量。 而且通常情况下， 得到的近似解可能比老近似解更接近精确解， 新 因此，可望这种迭代会更有效。 矩阵表示 记 其中 则Gauss-Seidel迭代法可表示为 其中， 为Gauss-Seidel迭代法的 迭代矩阵，是其右端常数项。 收敛条件 Gauss-Seidel迭代法收敛的充分必要条件 若则Gauss-Seidel迭代收敛。 若n 阶方阵 A是主对角线按行(或按列)严格 占优阵， 则用Gauss-Seidel迭代法求解线性方 程组 Ax = b 必收敛。 例2 用Gauss-Seidel迭代法求解 解： 此方程组的系数矩阵