《线性方程组AX=B的数值解法j ppt课件.ppt》由会员分享，可在线阅读，更多相关《线性方程组AX=B的数值解法j ppt课件.ppt（54页珍藏版）》请在金锄头文库上搜索。
1、 1 单击此处编辑母版标 题样式 单击此处编辑母版副标题样式 第3章 线性方程组AX B的数值解法 引言 n在自然科学和工程技术中很多问题的解决常常归 结为解线性代数方程组 例如电学中的网络问题 船体数学放样中建立三次样条函数问题 用最 小二乘法求实验数据的曲线拟合问题 解非线性 方程组问题 用差分法或者有限元法解常微分方 程 偏微分方程边值问题等都导致求解线性方程 组 而且后面几种情况常常归结为求解大型线性 方程组 n线性代数方面的计算方法就是研究求解线性方程 组的一些数值解法与研究计算矩阵的特征值及特 征向量的数值方法 2020 3 8 n华南师范大学数学科学学院 谢骊玲 线性方程组求解问
2、题 n考虑线性方程组 Ax b n其中A是一个 n n 的非奇异矩阵 x是要求解的 n维未知向量 b是n维常向量 2020 3 8 n华南师范大学数学科学学院 谢骊玲 线性方程组的解的存在性和唯一性 n定理3 4 设A是N N方阵 下列命题等价 给定任意N 1矩阵B 线性方程组AX B有唯一 解 矩阵A是非奇异的 即A 1存在 方程组AX 0有唯一解X 0 det A 0 2020 3 8 n华南师范大学数学科学学院 谢骊玲 线性方程组的解 n最常见的求线性方程组Ax b的解的方法是在方 程组两侧同乘以矩阵A的逆 nGram法则 Ax b 2020 3 8 n华南师范大学数学科学学院 谢骊玲
3、线性方程组的解 续1 n求逆运算和行列式计算由于运算量大 实 际求解过程中基本不使用 仅作为理论上 的定性讨论 n克莱姆法则在理论上有着重大意义 但在 实际应用中存在很大的困难 在线性代数 中 为解决这一困难给出了高斯消元法 n还有三角分解法和迭代求解法 2020 3 8 n华南师范大学数学科学学院 谢骊玲 解法分类 n关于线性方程组的数值解法一般有两类 直接法 若在计算过程中没有舍入误差 经 过有限步算术运算 可求得方程组的精确解 的方法 迭代法 用某种极限过程去逐步逼近线性方 程组精确解的方法 迭代法具有占存储单元少 程序设计简单 原始系数矩阵在迭代过程中不变等优点 但 存在收敛性及收敛速
4、度等问题 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 3 上三角线性方程组 n定义3 2 N N矩阵A aij 中的元素满足对所 有i j 有aij 0 则称矩阵A为上三角矩阵 如果A中的元素满足对所有i j 有aij 0 则 称矩阵A为下三角矩阵 n定理3 5 回代 设AX B是上三角线性方程 组 如果akk 0 其中k 1 2 N 则该方程 组存在唯一解 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 3 上三角线性方程组 续1 n定理3 6 如果N N矩阵A aij 是上三角矩阵或下 三角矩阵 则 n 条件akk 0很重要 因为回代算法中包含对akk的除 法 如果
5、条件不满足 则可能无解或有无穷解 n 联系定理3 4 可知要条件akk 0成立才能保证方 程组存在唯一解 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 3 上三角线性方程组 续2 n求解上三角线性方程组的回代算法 最后 2020 3 8 n华南师范大学数学科学学院 谢骊玲 上三角线性方程组的求解 n基本算法 2020 3 8 n华南师范大学数学科学学院 谢骊玲 上三角线性方程组的求解 续1 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 n求解有N个方程和N个未知数的一般方程组 AX B的一般做法 构造一个等价的上三角 方程组UX Y 并利用回代法
6、求解 n如果两个N N线性方程组的解相同 则称二 者等价 n对一个给定方程组进行初等变换 不会改 变它的解 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续1 n考虑一个简单的例子 n求解第二个方程 得 n第二个方程减去第 一个方程除以3再乘 以4得到的新方程 得到新的方程组 n 回代到第一个方程 得 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续2 n考虑包含n个未知数的方程组 or n作如下行变换之后方程组的解向量 x 不变 对调方程组的两行 用非零常数乘以方程组的某一行 将方程组的某一行乘以一个非零常数 再加到另一
7、行上 n 通过对增广矩阵 A B 进行如上的行变换求解 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续3 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续4 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续5 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续6 利用3 3节的回代法求解上述上三角方程组 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续7 消去过程 2020 3 8 n华南师范大学数学科学学院 谢骊玲
8、 3 4 高斯消去法和选主元 续8 回代过程 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续9 n上述消去过程中 如果akk 0 则不能使用第k行 消除第k列的元素 而需要将第k行与对角线下的 某行进行交换 以得到一个非零主元 如果不能 找到非零主元 则线性方程组的系数矩阵是奇异 的 因此线性方程组不存在唯一解 n选主元以避免 如果此主元非零 则不 换行 如果此主元为零 则寻找第p行下满足 的第1行 将此行与第p行互换 使新主元非零 平凡选主元策略 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续10 n选主元以减少误差
9、 把元素中的最大绝对值移到 主对角线上 例3 17和3 18 n 偏序选主元策略 akp max app app 1 aN 1p aNp n 按比例偏序选主元 平衡 策 略 sr max arp arp 1 arN 其中r p p 1 N 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续11 n病态问题 矩阵A中元素的微小变化引起解 的很大变化 cond A 207 012 2020 3 8 n华南师范大学数学科学学院 谢骊玲 图形解释 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 4 高斯消去法和选主元 续12 n一个线性方程组称 为是病态的
10、如果 其系数矩阵接近奇 异且它的行列式接 近0n 矩阵条件数 cond A A A 1 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 5 三角分解法 nA LU 下三角矩阵L的主对角线为1 上三角矩阵 U的对角线元素非零 定义3 4 如果非奇异矩阵A可表示为下三角矩阵L和上 三角矩阵U的乘积 A LU 则A存在一个三角分解 A非奇异蕴含着对所有的k有ukk 0 k 1 2 3 4 2020 3 8 n华南师范大学数学科学学院 谢骊玲 矩阵的LU分解 n是否所有的非奇异矩阵A都能作LU分解呢 n一个例子 nN阶方阵A有唯一LU分解的充要条件是A的各阶 顺序主子式均不为零 2020 3
11、 8 n华南师范大学数学科学学院 谢骊玲 3 5 三角分解法 续1 n 利用前代 回代算法求解形如Lx b或Ux b的线性 方程组是容易的 n 如果对一个给定的矩阵A 能够找到一个下三角 矩阵L和一个上三角矩阵U 使A LU n 则求解线性方程组Ax b的问题可以分解成两个简 单的问题 p Ly b p Ux y n 易见 Ax LU x L Ux Ly b 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 5 三角分解法 续2 n 假设已有矩阵A n 对A作LU分解 n 检验分解结果 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 5 三角分解法 续3 n 构造一系列乘数矩
12、阵M1 M2 M3 M4 MN 1使得 MN 1 M4M3M2M1 A是上三角矩阵 把它重新记成U n对4 4矩阵A M1可取 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 5 三角分解法 续4 nM2可取 nM3可取 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 5 三角分解法 续5 n 则U M3M2M1 A是上三角形矩阵 n 每个M矩阵都是下三角形矩阵 n 如M2的逆为 n 注意到每个M矩阵的逆只是它自身下三角部分元素取相反数 n A M3M2M1 1 U M1 1 M2 1 M3 1 U n 定义L M1 1 M2 1 M3 1 则L就是一个对角元素全为1的下三
13、 角矩阵 因为所有的M矩阵的逆都是对角元素全为1的下三角矩阵 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 5 三角分解法 续6 n计算复杂性 高斯消去法与三角分解法的三角化 过程是一样的 都需要 次乘法和除法 次减法 求解LUX B又需要N2次乘法和除法 以 及 N2 N 次减法 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 5 三角分解法 续7 n 每一个M矩阵中都需要计算1 A i i n 当第i个对角元素为0或者很接近0时就没法计算M 这时A的直接LU分解就没法继续进行 n 可以将第i行与它下面的某一行互换 该行的第i列 元素非零 n 带选主元过程的LU分解 2
14、020 3 8 n华南师范大学数学科学学院 谢骊玲 3 5 三角分解法 续8 之前我们构造了一系列的M矩阵使得 是上三角矩阵 现在我们构造一系列的M矩阵和P矩阵使得 是上三角矩阵 MN 1 M4 M3 M2 M1 A MN 1 PN 1 M4 P4 M3 P3 M2 P2 M1 P1 A 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 6 求解线性方程组的迭代法 n考虑线性方程组 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 6 求解线性方程组的迭代法 续1 n 高斯消去法 受限于舍入误差和病态性 n 迭代法 另一种求解线性方程组的方法 n 给出初始估计值 通过迭代得到更
15、好的解的近 似值 n 迭代法对求解大型线性方程组非常有效 n Jacobi 雅可比 和Gauss Seidel 高斯 赛 德尔 方法 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 6 求解线性方程组的迭代法 续2 n将方程组改写成每个方程的左边只有一个未知 数的形式 n给出初始估计值 和迭代规则 2020 3 8 n华南师范大学数学科学学院 谢骊玲 Jacobi迭代法 n初始估计值 n迭代一步后的结果 2020 3 8 n华南师范大学数学科学学院 谢骊玲 Jacobi迭代法 续1 nk步迭代后的结果 2020 3 8 n华南师范大学数学科学学院 谢骊玲 Jacobi迭代法 续2 n
16、例 nJacobi迭代公式 2020 3 8 n华南师范大学数学科学学院 谢骊玲 Jacobi迭代法 续3 n初始迭代值 20步迭代后 2020 3 8 n华南师范大学数学科学学院 谢骊玲 Jacobi迭代法 续4 n迭代会不会收敛到方程组的解 n迭代到何时会终止 终止的判断条 件是什么 两个必须考虑的问题 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 6 求解线性方程组的迭代法 续3 n定义3 6 设有N N维矩阵A 如果 其中k 1 2 N 则称A具有严格对角优势 严格对角占优 n 定理3 15 雅可比迭代 设矩阵A具有严格对角 优势 则AX B有唯一解X P 利用雅可比迭代可产 生一个向量序列 Pk 而且对于任意初始向量P0 向量序列都将收敛到P 2020 3 8 n华南师范大学数学科学学院 谢骊玲 3 6 求解线性方程组的迭代法 续4 n向量之间的距离可以用来判断 Pk 是否收敛到P 因为两个向量P x1 x2 xN 和Q y1 y2 yN 之间 的欧几里德距离 计算复杂 而1 范数具有度量的数学结构 也适 合作为一个一般化的 距离公式 而且根据线性代 数的理论可知
