《第章线性方程组的直接解法ttt整理.ppt》由会员分享，可在线阅读，更多相关《第章线性方程组的直接解法ttt整理.ppt（34页珍藏版）》请在金锄头文库上搜索。
1、4 1Gauss消去法 4 1 4Gauss Jordan消元法 4 1 3主元素消去法 4 1 2矩阵的三角分解 4 1 1Gauss消去法的计算过程 第4章线性方程组的直接解法 教学目的1 掌握解线性方程组的高斯消去法 高斯选主元素消去法 2 掌握用直接三角分解法解线性方程组的方法 3 了解解对称正定矩阵线性方程组的平方根法与解三对角线方程组的追赶法 4 掌握向量 矩阵范数 矩阵的条件数等概念及方程组的扰动分析 教学重点及难点重点是1 解线性方程组的高斯消去法 高斯选主元素消去法 2 直接三角分解法解线性方程组的方法 3 向量 矩阵范数 矩阵的条件数等概念及方程组的扰动分析 难点是方程组的
2、扰动分析 实际中 存在大量的解线性方程组的问题 很多数值方法到最后也会涉及到线性方程组的求解问题 如样条插值的M和m关系式 曲线拟合的法方程 方程组的Newton迭代等问题 第4章线性方程组的直接解法 对线性方程组 或者 我们有Gram法则 当且仅当 时 有唯一的解 而且解为 但Gram法则不能用于计算方程组的解 如n 100 1033次 秒的计算机要算10120年 解线性方程组的方法可以分为2类 直接法 准确 可靠 理论上得到的解是精确的 迭代法 速度快 但有误差 本章讲解直接法 对于中小型方程组 常用直接解法 从本质上来说 直接方法的原理是找一个可逆矩阵M 使得MA是一个上三角阵 这一过程
3、一般称为 消元 过程 消元之后再进行 回代 即求解MAx Mb 本章讨论Gauss消去法及其变形 以及一些情况下的特殊方法 最后进行误差分析 4 1Gauss消去法 我们知道 下面有3种方程的解我们可以直接求出 n次运算 n 1 n 2次运算 n 1 n 2次运算 对方程组 作如下的变换 解不变 交换两个方程的次序 一个方程的两边同时乘以一个非0的数 一个方程的两边同时乘以一个非0数 加到另一个方程 因此 对应的对增广矩阵 A b 作如下的变换 解不变 交换矩阵的两行 某一行乘以一个非0的数 某一个乘以一个非0数 加到另一行 消元法就是对增广矩阵作上述行的变换 变为我们已知的3种类型之一 而后
4、求根 4 1 1Gauss消去法的计算过程 4 1 1 这样 方程组 4 1 1 又可写成 消元过程就是要按确定的计算过程对方程组进行初等行变换 将方程组化为上三角方程组 第一步消元 假设 作初等行变换运算 步骤如下 运算量 n 1 1 n 运算量 n 2 1 n 1 n 2 n 第二步 第k步消元 设消去法已进行k 1步 得到方程组 此时对应的增广矩阵是 第k步 类似的做下去 我们有 运算量 n k 1 n k 1 n k n k 2 n 1步以后 我们可以得到变换后的矩阵为 这就完成了消元过程 4 1 4 因此 总的运算量为 加上解上述上三角阵的运算量 n 1 n 2 总共为 求解上式的过
5、程称为回代过程 以上由消去过程和回代过程合起来求解 4 1 1 的过程就称为Gauss消去法 或称为顺序Gauss消去法 如果我们用Cramer法则计算 4 1 1 的解 要计算n 1个阶行列式 并作n次除法 如果用子式展开的方法计算行列式 则计算每个行列式有n 次乘法 所以用Cramer法则大约需要 n 1 次乘除法运算 例如 当n 10时 约需乘除法运算 而用Gauss消去法只需430次乘除法运算 例4 1用Gauss消去法解方程组 解第一步消元 令得增广矩阵 4 1 2矩阵的三角分解 从上面的消元过程可以看出 消元过程能顺利进行的重要条件是主元素 若用表示矩阵A的k阶顺序主子阵 则有下面
6、的定理 定理4 1全不为零的充要条件是A的顺序主子式其中 证先证必要性设 则可进行k 1步消元程 显然 对 由于每步进行的初等变换不改变顺序主子式的值 所以第i 1步消元后有 用归纳法证充分性 k 1时 命题显然成立 设命题对m 1成立 现设由归纳假设有Gauss消去法可进行第m 1步 矩阵A变换为 其中是对角元素为的上三角阵 因是通过消元过程由A逐步经初等变换得到的 A的m阶顺序主子式等于的m阶顺序主子式 即由可推出 定理得证 不难验证即 利用矩阵 4 1 6 第k步消元过程相当于这样经过n 1步消元过程得到 这里 是上三角阵 记 又记 这种矩阵称为单位下三角阵 L的对角线以下各元素就是各步
7、消元过程的乘数 最后我们得到A LU 4 1 7 称该式为A的LU分解 定理4 3矩阵 若其顺序主子式皆非零 则存在唯一的单位下三角阵L和上三角阵U 使A LU 4 1 3主元素消去法 解这个方程组的准确解显然应接近 但是系数是个小主元 如果用Gauss消去法求解 则有 列主元素消去法也称按列部分主元的消去法 一般地 在完成了第k 1步消元运算后 在的第k列元素之下的所有元素中选一个绝对值最大的元素作为主元素 即若 完成了n 1步主元 换行与消元运算后 得到 这是与原方程组等价的方程组 是一个上三角阵 再代回求解 这就是列主元素消去法的计算过程 除了列主元素消去法外 还有一种完全主元素消去法
8、在其过程的第k步 不是按列来选主元 而是在右下角的n k 1阶子阵中选主元 即然后将的第行与第k行交换将第列与第k列交换 同时将自变量与的位置交换并记录自变量的排列次序 直到消去法完成后 再按记录恢复自变量为自然次序 完全主元法比列主元法 运算量大得多 由于列主元法的舍如误差一般已较小 所以在实际计算中多用列主元法 例4 3用列主元素消去法解方程组Ax b 计算过程中五位有效数字进行运算 其中 消去过程至此结束 回代计算依次得到解这个例题的精确解是而用不选住主元的顺序Gauss消去法 则解得 这个结果误差较大 这是因为消去法的第1步中 按绝对值比其他元素小很多所引起的 从此例看到列主元素消去法
9、是有效的方法 下面讨论矩阵的含换行的三角分解 即列主元法中消去过程的矩阵表示 一般的 将矩阵A的第i行与第j行交换 其结果相当于矩阵A左乘一个初等排列矩阵 即 这里是单位阵I交换第i行与第j行后所得的矩阵 不难验证 若矩阵A右乘得 其结果是将A的第i列与第j列交换后所得的矩阵 我们把若干个初等排列矩阵的乘积称作排列矩阵 其结果是将单位矩阵经过若干次交换所得的矩阵 列主元素消去法的每一步 一般是先按列选主元再交换行 然后进行消元计算 所以有其中为 4 1 6 所示 是初等排列阵 是第k步列选主元所在的行号 如果第k步不需换行 则 列主元素消去法的消元过程进行n 1步之后得到上三角阵 记这就是列主
10、元法消去过程的矩阵表示 由于列主元的选取 我们可知及原始的绝对值不大于1 定理4 4设A为非奇异矩阵 则存在排列阵 单位小三角矩阵L和上三角阵U 使PA LU 证从 4 1 9 可得其中U为上三角阵 令排列阵则利用有 4 1 4Gauss Jordan消元法 考虑Gauss消去法的一种修正 消去对角线下方和上方的元素 称这种方法为Gauss Jordan消去法 设用Gauss Jordan消去法已完成k 1步 得到与方程Ax b等价的方程组 此时对应的增广矩阵是 这里 略去了矩阵元素的上标 在第k步计算时 考虑对上述矩阵地k列中的第k行上 下都进行消元计算 若用列主元素消去法 仍然是第k列元素之下的所以元素中选一个绝对值最大的元素做为主元素 即 定理4 5设A为为n阶非奇异矩阵 方程组Ax I的增广矩阵为C A I 如果对C用Gauss Jordan消去法化为 I T 则 证设 则这里 为单位矩阵I的第j列 用Gauss Jordan消去法解方程组 其解在C中I的第j列 即为T的第j列 即 因此 定理得证 例4 4用Gauss Jordan消去法求矩阵的逆矩阵 解用列主元素消去法有 在实际计算中 为了节省内存单元 单位矩阵不必存放 在上例中 可将的最后一列放在A第I列 将的第5列存放在A的第2列 将的第4列存在A的第3列 一般地 第k步消元时 可将A的第k列
